default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDTheory of Computing, Volume 9
Volume 9, 2013
- Nathaniel Bryans, Ehsan Chiniforooshan, David Doty
, Lila Kari, Shinnosuke Seki:
The Power of Nondeterminism in Self-Assembly. 1-29 - Daniel Gottesman, Sandy Irani:
The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems. 31-116 - Per Austrin, Mark Braverman, Eden Chlamtac:
Inapproximability of NP-Complete Variants of Nash Equilibrium. 117-142 - Scott Aaronson, Alex Arkhipov:
The Computational Complexity of Linear Optics. 143-252 - Avraham Ben-Aroya, Amnon Ta-Shma:
Constructing Small-Bias Sets from Algebraic-Geometric Codes. 253-272 - Stephan Mertens, Cristopher Moore:
The Complexity of the Fermionant and Immanants of Constant Width [Note]. 273-282 - Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff:
Pseudorandomness for Width-2 Branching Programs. 283-293 - Reut Levi, Dana Ron, Ronitt Rubinfeld:
Testing Properties of Collections of Distributions. 295-347 - Scott Aaronson, Paul F. Christiano:
Quantum Money from Hidden Subspaces. 349-401 - Pavel Hrubes:
On the Real τ-Conjecture and the Distribution of Complex Roots. 403-411 - Venkatesan Guruswami, Ali Kemal Sinop:
Improved Inapproximability Results for Maximum k-Colorable Subgraph. 413-435 - Alexandr Andoni, Atri Rudra:
Special Issue: APPROX-RANDOM 2012: Guest Editors' Foreword. 437-439 - Aditya Bhaskara, Devendra Desai, Srikanth Srinivasan:
Optimal Hitting Sets for Combinatorial Shapes. 441-470 - Jakob Nordström, Johan Håstad:
Towards an Optimal Separation of Space and Length in Resolution. 471-557 - Noga Alon, Shachar Lovett:
Almost k-Wise vs. k-Wise Independent Permutations, and Uniformity for General Group Actions. 559-577 - Elchanan Mossel, Ryan O'Donnell:
Special Issue on Analysis of Boolean Functions: Guest Editors' Foreword. 579-585 - Daniel M. Kane:
A Monotone Function Given By a Low-Depth Decision Tree That Is Not an Approximate Junta. 587-592 - Alexander A. Sherstov:
Making Polynomials Robust to Noise. 593-615 - Uriel Feige, Elchanan Mossel, Dan Vilenchik:
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems. 617-651 - Alexander A. Sherstov:
Approximating the AND-OR Tree. 653-663 - Eli Ben-Sasson, Ariel Gabizon:
Extractors for Polynomial Sources over Fields of Constant Order and Small Characteristic. 665-683 - Daniel Sheldon, Neal E. Young:
Hamming Approximation of NP Witnesses. 685-702 - Cenny Wenner:
Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four. 703-757 - Ola Svensson:
Hardness of Vertex Deletion and Project Scheduling. 759-781 - Noga Ron-Zewi, Madhu Sudan:
A New Upper Bound on the Query Complexity of Testing Generalized Reed-Muller Codes. 783-807 - Bill Fefferman, Ronen Shaltiel, Christopher Umans, Emanuele Viola:
On Beating the Hybrid Argument. 809-843 - Johan Håstad:
Satisfying Degree-d Equations over GF[2]n. 845-862 - Subhash Khot, Muli Safra:
A Two-Prover One-Round Game with Strong Soundness. 863-887 - Eric Blais, Li-Yang Tan:
Hypercontractivity Via the Entropy Method. 889-896 - Kai-Min Chung, Michael Mitzenmacher, Salil P. Vadhan:
Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream. 897-945
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-05 22:24 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:
