24. CCC 2009: Paris, France

Wednesday 15 July

• Mark Braverman:
  Poly-logarithmic Independence Fools AC⁰ Circuits. 3-8
  
• Kazuyuki Amano:
  k-Subgraph Isomorphism on AC₀ Circuits. 9-18
  
• Lance Fortnow, Rahul Santhanam, Ryan Williams:
  Fixed-Polynomial Size Circuit Bounds. 19-26
  
• Kristoffer Arnsfelt Hansen, Michal Koucký:
  A New Characterization of ACC⁰ and Probabilistic CC⁰. 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, Venkatesan Guruswami, Rajsekar Manokaran:
  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, Madhur Tulsiani, Salil P. Vadhan:
  Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. 126-136
  
• Nitin Saxena, C. Seshadhri:
  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, Amir Shpilka:
  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, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner:
  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, John Watrous:
  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 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, Hartmut Klauck:
  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
  

Last update Thu May 24 04:15:02 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page