26. CCC 2011: San Jose, California, USA
Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, June 8-10, 2011. IEEE Computer Society 2011- 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
- 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
- Hartmut Klauck: On Arthur Merlin Games in Communication Complexity. 189-199
- 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
- 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
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-18T211851 by the dblp team