default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID28th CCC 2013: Palo Alto, California, USA
- Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013. IEEE Computer Society 2013, ISBN 978-0-7695-4997-2
- Ankit Gupta, Neeraj Kayal, Youming Qiao
:
Random Arithmetic Formulas Can Be Reconstructed Efficiently. 1-9 - Pavel Hrubes, Amir Yehudayoff:
Formulas are Exponentially Stronger than Monotone Circuits in Non-commutative Setting. 10-14 - Rahul Santhanam, Ryan Williams:
On Medium-Uniformity and Circuit Lower Bounds. 15-23 - Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, Nikolay K. Vereshchagin:
Towards a Reverse Newman's Theorem in Interactive Information Complexity. 24-33 - Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang:
Shared Randomness and Quantum Communication in the Multi-party Model. 34-43 - Aleksandrs Belovs, Ansis Rosmanis:
On the Power of Non-adaptive Learning Graphs. 44-55 - Daniel M. Kane:
The Correct Exponent for the Gotsman-Linial Conjecture. 56-64 - Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi:
Approaching the Chasm at Depth Four. 65-73 - Eric Blais, Li-Yang Tan:
Approximating Boolean Functions with Depth-2 Circuits. 74-85 - Adam R. Klivans, Pravesh Kothari, Igor C. Oliveira:
Constructing Hard Functions Using Learning Algorithms. 86-97 - Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand:
Short Lists with Short Programs in Short Time. 98-108 - Albert Atserias, Moritz Müller, Sergi Oliva:
Lower Bounds for DNF-refutations of a Relativized Weak Pigeonhole Principle. 109-120 - Madhur Tulsiani, Pratik Worah:
LS+ Lower Bounds from Pairwise Independence. 121-132 - Siu Man Chan:
Just a Pebble Game. 133-143 - Oded Regev, Thomas Vidick:
Quantum XOR Games. 144-155 - Patrick M. Hayden, Kevin Milner, Mark M. Wilde:
Two-Message Quantum Interactive Proofs and the Quantum Separability Problem. 156-167 - Yasuhiro Takahashi, Seiichiro Tani:
Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits. 168-178 - Andris Ambainis, Ronald de Wolf:
How Low Can Approximate Degree and Quantum Query Complexity Be for Total Boolean Functions? 179-184 - Justin Gilmer, Michael E. Saks, Srikanth Srinivasan:
Composition Limits and Separating Examples for Some Boolean Function Complexity Measures. 185-196 - Noga Alon, Gil Cohen:
On Rigid Matrices and U-polynomials. 197-206 - Irit Dinur, Gillat Kol:
Covering CSPs. 207-218 - Sushant Sachdeva, Rishi Saket:
Optimal Inapproximability for Scheduling Problems via Structural Hardness for Hypergraph Vertex Cover. 219-229 - Kai-Min Chung, Daniel Dadush, Feng-Hao Liu, Chris Peikert:
On the Lattice Smoothing Parameter Problem. 230-241 - Luca Trevisan, Tongke Xue:
A Derandomized Switching Lemma and an Improved Derandomization of AC0. 242-247 - John P. Steinberger:
The Distinguishability of Product Distributions by Read-Once Branching Programs. 248-254 - Michael Viderman:
Strong LTCs with Inverse Polylogarithmic Rate and Soundness. 255-265 - Sepp Hartung, André Nichterlein:
On the Parameterized and Approximation Hardness of Metric Dimension. 266-276 - Tatsuya Imai, Kotaro Nakagawa, Aduri Pavan, N. V. Vinodchandran, Osamu Watanabe:
An O(n½+∑)-Space and Polynomial-Time Algorithm for Directed Planar Reachability. 277-286 - Venkatesan Guruswami, Krzysztof Onak:
Superlinear Lower Bounds for Multipass Graph Processing. 287-298
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-07-09 21:34 CEST 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:
