|
|
Close Help | ||||||||||||||
             
|
ProgramProgram is available in pdf and doc.There will be a rump session on Tuesday from 7pm till 8:30pm in the lecture room S5. The sign-up sheet is available at the registration desk. Invited lectures
Accepted papers for CCC '06A 3-Query Non-Adaptive PCP with Perfect Completeness Subhash Khot, Rishi Saket A Generic Time Hierarchy for Semantic Models with One Bit of Advice Dieter van Melkebeek, Konstantin Pervyshev A Duality Between Clause Width and Clause Density for SAT Chris Calabro, Russell Impagliazzo, Ramamohan Paturi An Isomorphism between Subexponential and Parameterized Complexity Theory Yijia Chen, Martin Grohe Circuit lower bounds via Ehrenfeucht-Fraisse games Michal Koucky, Clemens Lautemann, Sebastian Poloczek, Denis Therien Constructing Ramsey Graphs from Boolean Function Representations Parikshit Gopalan Construction of Low-Degree and Error-Correcting \epsilon-Biased Sets Amir Shpilka Derandomization of Probabilistic Auxiliary Pushdown Automata Classes - (withdrawn) H. Venkateswaran Every Linear Threshold Function has a Low-Weight Approximator Rocco A. Servedio Exposure-Resilient Extractors Marius Zimand FO[<]-Uniformity C. Behle, K.-J. Lange Grid Graph Reachability Problems Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy Hardness of the Covering Radius Problem on Lattices Ishay Haviv, Oded Regev How to get more mileage from randomness extractors Ronen Shaltiel Learning Monotone Decision Trees in Polynomial Time Ryan O'Donnell, Rocco Servedio Making Hard Problems Harder Joshua Buresh-Oppenheim, Rahul Santhanam Minimizing DNF formulas and AC^0_d circuits given a truth table Eric Allender, Lisa Hellerstein, Paul McCabe, Toni Pitassi New lower bounds for Vertex Cover in the Lovasz-Schrijver hierarchy Iannis Tourlakis Non-uniform Hardness for NP against Black-Box Samplers Albert Atserias On Arthur-Merlin Games and the Possibility of Basing Cryptography on NP-Hardness Rafael Pass On Modular Counting with Polynomials Kristoffer Arnsfelt Hansen On the Complexity of Numerical Analysis Eric Allender, Peter B|rgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen Optimal Hardness Results for Maximizing Agreements with Monomials Vitaly Feldman Oracles Are Subtle But Not Malicious Scott Aaronson Polynomial Identity Testing for Depth 3 Circuits Neeraj Kayal, Nitin Saxena QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols Scott Aaronson Random Measurement Bases, Quantum State Distinction and Applications to the Hidden Subgroup Problem Pranab Sen Strengths and Weaknesses of Quantum Fingerprinting Dmitry Gavinsky, Julia Kempe, Ronald de Wolf |
