default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID48th STOC 2016: Cambridge, MA, USA
- Daniel Wichs, Yishay Mansour:
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016. ACM 2016, ISBN 978-1-4503-4132-5
Session 1A
- Boris Aronov
, Micha Sharir:
Almost tight bounds for eliminating depth cycles in three dimensions. 1-8 - Michael B. Cohen, Yin Tat Lee, Gary L. Miller, Jakub Pachocki, Aaron Sidford:
Geometric median in nearly linear time. 9-21 - Alan M. Frieze, Wesley Pegden:
Separating subadditive euclidean functionals. 22-35 - Shai Evra, Tali Kaufman:
Bounded degree cosystolic expanders of every dimension. 36-48
Session 1B
- Omer Reingold, Guy N. Rothblum, Ron D. Rothblum:
Constant-round interactive proofs for delegating computation. 49-62 - Subhash Khot, Dana Moshkovitz:
Candidate hard unique game. 63-76 - Roee David, Uriel Feige:
On the effect of randomness on planted 3-coloring models. 77-90 - Oded Goldreich, Avishay Tal:
Matrix rigidity of random toeplitz matrices. 91-104
Session 2A
- Amit Daniely:
Complexity theoretic limitations on learning halfspaces. 105-117 - Sanjoy Dasgupta:
A cost function for similarity-based hierarchical clustering. 118-127 - Elad Hazan, Tomer Koren:
The computational power of optimization in online learning. 128-141 - Gregory Valiant, Paul Valiant:
Instance optimal learning of discrete distributions. 142-155
Session 2B
- Nikhil Bansal, Aravind Srinivasan, Ola Svensson:
Lift-and-round to improve weighted completion time on unrelated machines. 156-167 - Elaine Levey, Thomas Rothvoss:
A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies. 168-177 - Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, David Steurer:
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors. 178-191 - Aleksandar Nikolov, Mohit Singh:
Maximizing determinants under partition constraints. 192-201
Session 3A
- Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf:
High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity. 202-215 - Venkatesan Guruswami, Mary Wootters:
Repairing Reed-solomon codes. 216-226 - Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk:
Efficiently decoding Reed-Muller codes from random errors. 227-235
Session 3B
- Christos Boutsidis, David P. Woodruff, Peilin Zhong:
Optimal principal component analysis in distributed and streaming models. 236-249 - Ilya P. Razenshteyn, Zhao Song, David P. Woodruff:
Weighted low rank approximations with provable guarantees. 250-263 - Michael Kapralov:
Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time. 264-277
Session 4A
- Gil Cohen:
Two-source dispersers for polylogarithmic entropy and improved ramsey graphs. 278-284 - Eshan Chattopadhyay, Vipul Goyal, Xin Li:
Non-malleable extractors and codes, with their many tampered extensions. 285-298 - Eshan Chattopadhyay, Xin Li:
Extractors for sumset sources. 299-311
Session 4B
- Pierre Fraigniaud, Amos Korman, Yoav Rodeh:
Parallel exhaustive search without coordination. 312-323 - Aviad Rubinstein:
Beyond matroids: secretary problem and prophet inequality with general constraints. 324-332 - Yuval Emek, Shay Kutten, Roger Wattenhofer:
Online matching: haste makes waste! 333-344
Session 5
- Leqi Zhu:
A tight space bound for consensus. 345-350 - Amir Abboud, Greg Bodwin:
The 4/3 additive spanner exponent is tight. 351-361
Session 6A
- Huacheng Yu:
Cell-probe lower bounds for dynamic problems via a new communication model. 362-374 - Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Ryan Williams:
Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made. 375-388 - Aaron Bernstein, Shiri Chechik:
Deterministic decremental single source shortest paths: beyond the o(mn) bound. 389-397 - Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai:
New deterministic approximation algorithms for fully dynamic matching. 398-411
Session 6B
- Shaddin Dughmi, Haifeng Xu:
Algorithmic Bayesian persuasion. 412-425 - Nikhil R. Devanur, Zhiyi Huang, Christos-Alexandros Psomas:
The sample complexity of auctions with side information. 426-439 - Justin Hsu, Jamie Morgenstern, Ryan M. Rogers, Aaron Roth, Rakesh Vohra:
Do prices coordinate markets? 440-453 - Haris Aziz, Simon Mackenzie:
A discrete and bounded envy-free cake cutting protocol for four agents. 454-464
Session 7A
- David G. Harris, Johannes Schneider, Hsin-Hao Su:
Distributed (∆+1)-coloring in sublogarithmic rounds. 465-478 - Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, Jara Uitto:
A lower bound for the distributed Lovász local lemma. 479-488 - Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai:
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. 489-498 - Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, Maxwell Young:
Contention resolution with log-logstar channel accesses. 499-508
Session 7B
- Surender Baswana, Keerti Choudhary, Liam Roditty:
Fault tolerant subgraph for single source reachability: generic and optimal. 509-518 - Ehsan Emamjomeh-Zadeh, David Kempe, Vikrant Singhal:
Deterministic and probabilistic binary search in graphs. 519-532 - Chris Hall, Doron Puder, William F. Sawin:
Ramanujan coverings of graphs. 533-541 - David R. Karger:
Enumerating parametric global minimum cuts by random interleaving. 542-555
Session 8A
- Julia Chuzhoy, David H. K. Kim, Shi Li:
Improved approximation for node-disjoint paths in planar graphs. 556-569 - MohammadHossein Bateni, Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx:
A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting. 570-583 - Vincent Cohen-Addad, Éric Colin de Verdière, Philip N. Klein, Claire Mathieu, David Meierfrankenfeld:
Approximating connectivity domination in weighted bounded-genus graphs. 584-597 - Alina Ene, Gary L. Miller, Jakub Pachocki, Aaron Sidford:
Routing under balance. 598-611
Session 8B
- Xi Chen, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan:
Near-optimal small-depth lower bounds for small distance connectivity. 612-625 - Neeraj Kayal, Chandan Saha, Sébastien Tavenas:
On the size of homogeneous and of depth four formulas with low individual degree. 626-632 - Daniel M. Kane, Ryan Williams:
Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. 633-643 - Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan:
Poly-logarithmic Frege depth lower bounds via an expander switching lemma. 644-657
Session 9
- Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren Sasoglu, Rüdiger L. Urbanke:
Reed-Muller codes achieve capacity on erasure channels. 658-669 - Eshan Chattopadhyay, David Zuckerman:
Explicit two-source extractors and resilient functions. 670-683 - László Babai:
Graph isomorphism in quasipolynomial time [extended abstract]. 684-697
Session 10A
- Sepehr Assadi, Sanjeev Khanna, Yang Li:
Tight bounds for single-pass streaming complexity of the set cover problem. 698-711 - Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký:
Streaming algorithms for embedding and computing edit distance in the low distance regime. 712-725 - Yi Li, David P. Woodruff:
On approximating functions of the singular values in a stream. 726-739 - Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, David P. Woodruff:
Beating CountSketch for heavy hitters in insertion streams. 740-753
Session 10B
- Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf:
Bipartite perfect matching is in quasi-NC. 754-763 - Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, Saket Saurabh:
Exact algorithms via monotone local search. 764-775 - Sitan Chen:
Basis collapse for holographic algorithms over all domain sizes. 776-789 - Mingji Xia:
Base collapse of holographic algorithms. 790-799 - Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs:
Separations in query complexity based on pointer functions. 800-813
Session 11A
- Andrea Montanari, Subhabrata Sen:
Semidefinite programs on sparse random graphs and their application to community detection. 814-827 - Ankur Moitra, William Perry, Alexander S. Wein:
How robust are reconstruction thresholds for community detection? 828-841 - Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, Daniel A. Spielman:
Sparsified Cholesky and multigrid solvers for connection laplacians. 842-850 - Mark Braverman, Jieming Mao, S. Matthew Weinberg:
Parallel algorithms for select and partition with noisy comparisons. 851-862
Session 11B
- Scott Aaronson, Shalev Ben-David, Robin Kothari:
Separations in query complexity using cheat sheets. 863-876 - Dmitry Gavinsky:
Entangled simultaneity versus classical interactivity in communication complexity. 877-884 - Zhengfeng Ji:
Classical verification of quantum proofs. 885-898 - Ryan O'Donnell, John Wright:
Efficient quantum tomography. 899-912 - Jeongwan Haah, Aram W. Harrow, Zheng-Feng Ji, Xiaodi Wu, Nengkun Yu:
Sample-optimal tomography of quantum states. 913-925
Session 12A
- Yang Cai, Nikhil R. Devanur, S. Matthew Weinberg:
A duality based unified approach to Bayesian mechanism design. 926-939 - Shahar Dobzinski:
Breaking the logarithmic barrier for truthful combinatorial auctions with submodular bidders. 940-948 - Aaron Roth, Jonathan R. Ullman, Zhiwei Steven Wu:
Watch and learn: optimizing from revealed preferences feedback. 949-962 - Michal Feldman, Nicole Immorlica, Brendan Lucier, Tim Roughgarden, Vasilis Syrgkanis:
The price of anarchy in large games. 963-976
Session 12B
- Anat Ganor, Gillat Kol, Ran Raz:
Exponential separation of communication and external information. 977-986 - Gillat Kol:
Interactive compression for product distributions. 987-998 - Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler:
Constant-rate coding for multiparty interactive communication is impossible. 999-1010 - Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, David P. Woodruff:
Communication lower bounds for statistical estimation problems via a distributed data processing inequality. 1011-1020
Session 13A
- Aleksandrs Belovs, Eric Blais:
A polynomial lower bound for testing monotonicity. 1021-1032 - Artur Czumaj, Pan Peng, Christian Sohler:
Relating two property testing models for bounded degree directed graphs. 1033-1045 - Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, Jonathan R. Ullman:
Algorithmic stability for adaptive data analysis. 1046-1059 - Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
The fourier transform of poisson multinomial distributions and its algorithmic applications. 1060-1073 - Constantinos Daskalakis, Anindya De, Gautam Kamath, Christos Tzamos:
A size-free CLT for poisson multinomials and its applications. 1074-1086
Session 13B
- Benny Applebaum, Shachar Lovett:
Algebraic attacks against random local functions and their countermeasures. 1087-1100 - Gilad Asharov, Moni Naor, Gil Segev, Ido Shahaf:
Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations. 1101-1114 - Aloni Cohen, Justin Holmgren, Ryo Nishimaki, Vinod Vaikuntanathan, Daniel Wichs:
Watermarking cryptographic capabilities. 1115-1127 - Vipul Goyal, Omkant Pandey, Silas Richelson:
Textbook non-malleable commitments. 1128-1141
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-12-04 01:26 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
