22. CCC 2007:
San Diego,
California,
USA
22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 13-16 June 2007, San Diego, California, USA.
IEEE Computer Society 2007 
Wednesday,
June 13
- Marius Zimand:
On Derandomizing Probabilistic Sublinear-Time Algorithms.
1-9
- Prahladh Harsha, Rahul Jain, David A. McAllester, Jaikumar Radhakrishnan:
The Communication Complexity of Correlation.
10-23
- Harry Buhrman, Nikolai K. Vereshchagin, Ronald de Wolf:
On Computation and Communication with Small Bias.
24-32
- Amit Chakrabarti:
Lower Bounds for Multi-Player Pointer Jumping.
33-45
- Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto:
Low-Depth Witnesses are Easy to Find.
46-51
- Richard Chang, Suresh Purini:
Bounded Queries and the NP Machine Hypothesis.
52-59
- Wolfgang Merkle, Frank Stephan:
On C-Degrees, H-Degrees and T-Degrees.
60-69
Thursday,
June 14th
- Ryan Williams:
Time-Space Tradeoffs for Counting NP Solutions Modulo Integers.
70-82
- Alexander A. Sherstov:
Halfspace Matrices.
83-95
- Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan:
Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes.
96-108
- Richard Cleve, William Slofstra, Falk Unger, Sarvagya Upadhyay:
Perfect Parallel Repetition Theorem for Quantum XOR Proof Systems.
109-114
- Scott Aaronson, Greg Kuperberg:
Quantum versus Classical Proofs and Advice.
115-128
- Andris Ambainis, Joseph Emerson:
Quantum t-designs: t-wise Independence in the Quantum World.
129-140
- Emanuele Viola, Avi Wigderson:
Norms, XOR Lemmas, and Lower Bounds for GF(2) Polynomials and Multiparty Protocols.
141-154
- Emanuele Viola:
On Approximate Majority and Probabilistic Time.
155-168
- Kei Uchizawa, Eiji Takimoto:
An Exponential Lower Bound on the Size of Constant-Depth Threshold Circuits with Small Energy Complexity.
169-178
Friday,
June 15th
- Uriel Feige, Guy Kindler, Ryan O'Donnell:
Understanding Parallel Repetition Requires Understanding Foams.
179-192
- Guillaume Malod:
The Complexity of Polynomials and Their Coefficient Functions.
193-204
- Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani:
A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover.
205-216
- Chris Bourke, Raghunath Tewari, N. V. Vinodchandran:
Directed Planar Reachability is in Unambiguous Log-Space.
217-221
- Mark Braverman, Raghav Kulkarni, Sambuddha Roy:
Parity Problems in Planar Graphs.
222-235
- Kai-Min Chung, Omer Reingold, Salil P. Vadhan:
S-T Connectivity on Digraphs with a Known Stationary Distribution.
236-249
- Yijia Chen, Jörg Flum:
On Parameterized Path and Chordless Path Problems.
250-263
- Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur:
Testing Properties of Constraint-Graphs.
264-277
- Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky:
Efficient Arguments without Short PCPs.
278-291
Saturday,
June 16th
Copyright © Mon Nov 2 20:25:46 2009
by Michael Ley (ley@uni-trier.de)
