2011 IEEE 26th Annual Conference on Computational Complexity

Format:

Book

Author/Creator:

IEEE Computer Society Technical Committee on Mathematical Foundations of Computing, author, issuing body.

Contributor:

IEEE Staff, Contributor.

Language:

English

Subjects (All):

Computational complexity--Congresses.

Computational complexity.

Physical Description:

1 online resource (309 pages) : illustrations

Place of Publication:

[Place of publication not identified] IEEE 2011

Language Note:

English

Contents:

Preface

Program Committee

Steering Committee

Reviewers

Best Paper Awards

Wednesday, 8 June 2011

Improved Direct Product Theorems for Randomized Query Complexity

Making Branching Programs Oblivious Requires Superlogarithmic Overhead

Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups

Lower Bounds on Query Complexity for Testing Bounded-Degree CSPs

Non-negatively Weighted #CSP: An Effective Complexity Dichotomy

Symmetric LDPC Codes are not Necessarily Locally Testable

Towards Lower Bounds on Locally Testable Codes via Density Arguments

Linear-Algebraic List Decoding of Folded Reed-Solomon Codes

Noisy Interpolation of Sparse Polynomials, and Applications

Paris-Harrington Tautologies

Relativized Separations of Worst-Case and Average-Case Complexities for NP

Thursday, 9 June 2011 Non-uniform ACC Circuit Lower Bounds

Improved Constructions of Three Source Extractors

A New Approach to Affine Extractors and Dispersers

Symmetry of Information and Bounds on Nonuniform Randomness Extraction via Kolmogorov Extractors

Near-Optimal and Explicit Bell Inequality Violations

Symmetry-Assisted Adversaries for Quantum State Generation

Approximation Algorithms for QMA-Complete Problems

Sevag Gharibian and Julia Kempe

On Arthur Merlin Games in Communication Complexity

On the Minimal Fourier Degree of Symmetric Boolean Functions

Property Testing Lower Bounds via Communication Complexity

Friday, 10 June 2011 Pseudorandomness for Permutation and Regular Branching Programs

Pseudorandom Generators for Combinatorial Checkerboards

Bounded-Depth Circuits Cannot Sample Good Codes

k-Independent Gaussians Fool Polynomial Threshold Functions

Explicit Dimension Reduction and Its Applications

Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae

Tensor Rank: Some Lower and Upper Bounds

On the Sum of Square Roots of Polynomials and Related Problems

Linear Systems over Finite Abelian Groups

Author Index.

Notes:

Bibliographic Level Mode of Issuance: Monograph

ISBN:

9780769544113

0769544118