25. CCC 2011: San Jose, California, USA

• Andrew Drucker:
  Improved Direct Product Theorems for Randomized Query Complexity. 1-11
  
• Paul Beame, Widad Machmouchi:
  Making Branching Programs Oblivious Requires Superlogarithmic Overhead. 12-22
  
• Ryan O'Donnell, Yi Wu, Yuan Zhou:
  Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups. 23-33
  
• Yuichi Yoshida:
  Lower Bounds on Query Complexity for Testing Bounded-Degree CSPs. 34-44
  
• Jin-yi Cai, Xi Chen, Pinyan Lu:
  Non-negatively Weighted #CSP: An Effective Complexity Dichotomy. 45-54
  
• Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan:
  Symmetric LDPC Codes are not Necessarily Locally Testable. 55-65
  
• Eli Ben-Sasson, Michael Viderman:
  Towards Lower Bounds on Locally Testable Codes via Density Arguments. 66-76
  
• Venkatesan Guruswami:
  Linear-Algebraic List Decoding of Folded Reed-Solomon Codes. 77-85
  
• Shubhangi Saraf, Sergey Yekhanin:
  Noisy Interpolation of Sparse Polynomials, and Applications. 86-92
  
• Lorenzo Carlucci, Nicola Galesi, Massimo Lauria:
  Paris-Harrington Tautologies. 93-103
  
• Russell Impagliazzo:
  Relativized Separations of Worst-Case and Average-Case Complexities for NP. 104-114
  
• Ryan Williams:
  Non-uniform ACC Circuit Lower Bounds. 115-125
  
• Xin Li:
  Improved Constructions of Three Source Extractors. 126-136
  
• Xin Li:
  A New Approach to Affine Extractors and Dispersers. 137-147
  
• Marius Zimand:
  Symmetry of Information and Bounds on Nonuniform Randomness Extraction via Kolmogorov Extractors. 148-156
  
• Harry Buhrman, Oded Regev, Giannicola Scarpa, Ronald de Wolf:
  Near-Optimal and Explicit Bell Inequality Violations. 157-166
  
• Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland:
  Symmetry-Assisted Adversaries for Quantum State Generation. 167-177
  
• Sevag Gharibian, Julia Kempe:
  Approximation Algorithms for QMA-Complete Problems. 178-188
  
• Hartmut Klauck:
  On Arthur Merlin Games in Communication Complexity. 189-199
  
• Amir Shpilka, Avishay Tal:
  On the Minimal Fourier Degree of Symmetric Boolean Functions. 200-209
  
• Eric Blais, Joshua Brody, Kevin Matulef:
  Property Testing Lower Bounds via Communication Complexity. 210-220
  
• Anindya De:
  Pseudorandomness for Permutation and Regular Branching Programs. 221-231
  
• Thomas Watson:
  Pseudorandom Generators for Combinatorial Checkerboards. 232-242
  
• Shachar Lovett, Emanuele Viola:
  Bounded-Depth Circuits Cannot Sample Good Codes. 243-251
  
• Daniel M. Kane:
  k-Independent Gaussians Fool Polynomial Threshold Functions. 252-261
  
• Zohar Shay Karnin, Yuval Rabani, Amir Shpilka:
  Explicit Dimension Reduction and Its Applications. 262-272
  
• Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich:
  Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae. 273-282
  
• Boris Alexeev, Michael A. Forbes, Jacob Tsimerman:
  Tensor Rank: Some Lower and Upper Bounds. 283-291
  
• Neeraj Kayal, Chandan Saha:
  On the Sum of Square Roots of Polynomials and Related Problems. 292-299
  
• Arkadev Chattopadhyay, Shachar Lovett:
  Linear Systems over Finite Abelian Groups. 300-308
  

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