default search action
24th CCC 2009: Paris, France
- Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009. IEEE Computer Society 2009, ISBN 978-0-7695-3717-7
Wednesday 15 July
- Mark Braverman:
Poly-logarithmic Independence Fools AC0 Circuits. 3-8 - Kazuyuki Amano:
k-Subgraph Isomorphism on AC0 Circuits. 9-18 - Lance Fortnow, Rahul Santhanam, Ryan Williams
:
Fixed-Polynomial Size Circuit Bounds. 19-26 - Kristoffer Arnsfelt Hansen
A New Characterization of ACC0 and Probabilistic CC0. 27-34 - Pascal Koiran, Sylvain Perifel:
A Superpolynomial Lower Bound on the Size of Uniform Non-constant-depth Threshold Circuits for the Permanent. 35-40 - Pavel Hrubes, Iddo Tzameret:
The Proof Complexity of Polynomial Identities. 41-51 - Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman:
Locally Testable Codes Require Redundant Testers. 52-61 - Moses Charikar
Every Permutation CSP of arity 3 is Approximation Resistant. 62-73 - Per Austrin, Subhash Khot, Muli Safra
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs. 74-80 - Guy N. Rothblum, Salil P. Vadhan:
Are PCPs Inherent in Efficient Arguments? 81-92
Thursday 16 July
- Anup Rao:
Extractors for Low-Weight Affine Sources. 95-101 - Zeev Dvir:
Extractors for Varieties. 102-113 - Ronen Shaltiel:
Weak Derandomization of Weak Algorithms: Explicit Versions of Yao's Lemma. 114-125 - Luca Trevisan
Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. 126-136 - Nitin Saxena
An Almost Optimal Rank Bound for Depth-3 Identities. 137-148 - Akitoshi Kawamura:
Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete. 149-160 - Ilias Diakonikolas, Rocco A. Servedio
Improved Approximation of Linear Threshold Functions. 161-172 - Parikshit Gopalan, Shachar Lovett
On the Complexity of Boolean Functions in Different Characteristics. 173-183 - Neeraj Kayal:
The Complexity of the Annihilating Polynomial. 184-193 - Manindra Agrawal, Osamu Watanabe:
One-Way Functions and the Berman-Hartmanis Conjecture. 194-202 - Samir Datta
Planar Graph Isomorphism is in Log-Space. 203-214
Friday 17 July
- Tsuyoshi Ito, Hirotada Kobayashi, Keiji Matsumoto:
Oracularization and Two-Prover One-Round Interactive Proofs against Nonlocal Strategies. 217-228 - Scott Aaronson:
Quantum Copy-Protection and Quantum Money. 229-242 - Rahul Jain
Parallel Approximation of Non-interactive Zero-sum Quantum Games. 243-253 - Troy Lee, Gideon Schechtman, Adi Shraibman:
Lower Bounds on Quantum Multiparty Communication Complexity. 254-262 - Adam R. Day:
Increasing the Gap between Descriptional Complexity and Algorithmic Probability. 263-273 - Zohar Shay Karnin, Amir Shpilka
Reconstruction of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-in. 274-285 - Andrew Drucker:
Multitask Efficiencies in the Decision Tree Model. 286-297 - Luis Filipe Coelho Antunes, Lance Fortnow:
Worst-Case Running Times for Average-Case Algorithms. 298-303 - David Xiao:
On Basing ZK ≠ BPP on the Hardness of PAC Learning. 304-315 - Richard Královic:
Infinite vs. Finite Space-Bounded Randomized Computations. 316-325
Saturday 18 July
- T. S. Jayram, Swastik Kopparty, Prasad Raghavendra:
On the Communication Complexity of Read-Once AC^0 Formulae. 329-340 - Nikos Leonardos, Michael E. Saks:
Lower Bounds on the Randomized Communication Complexity of Read-Once Functions. 341-350 - Troy Lee, Adi Shraibman:
An Approximation Algorithm for Approximation Rank. 351-357 - Joshua Brody, Amit Chakrabarti
A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences. 358-368 - Rahul Jain
New Results in the Simultaneous Message Passing Model via Information Theoretic Techniques. 369-378 - Joshua Brody:
The Maximum Communication Complexity of Multi-Party Pointer Jumping. 379-386
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 2024-11-11 21:16 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: