18. CCC 2003: Aarhus, Denmark

@proceedings{DBLP:conf/coco/2003,
  title     = {18th Annual IEEE Conference on Computational Complexity (Complexity
               2003), 7-10 July 2003, Aarhus, Denmark},
  booktitle = {IEEE Conference on Computational Complexity},
  publisher = {IEEE Computer Society},
  year      = {2003},
  isbn      = {0-7695-1879-6},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Session 1

• Ryan O'Donnell, Rocco A. Servedio:
  Extremal properties of polynomial threshold functions. 3-12
  
• Yijia Chen, Jörg Flum, Martin Grohe:
  Bounded Nondeterminism and Alternation in Parameterized Complexity Theory. 13-29
  

Session 2

• Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma:
  Uniform hardness vs. randomness tradeoffs for Arthur-Merlin games. 33-47
  
• Russell Impagliazzo, Philippe Moser:
  A zero one law for RP. 48-52
  
• Emanuele Viola:
  Hardness vs. Randomness within Alternating Time. 53-
  

Session 3

• Pranab Sen:
  Lower bounds for predecessor searching in the cell probe model. 73-83
  
• Detlef Sieling:
  Minimization of Decision Trees Is Hard to Approximate. 84-92
  
• Navin Goyal, Michael E. Saks, Srinivasan Venkatesh:
  Optimal Separation of EROW and CROWPRAMs. 93-
  

Session 4

• Amit Chakrabarti, Subhash Khot, Xiaodong Sun:
  Near-Optimal Lower Bounds on the Multi-Party Communication Complexity of Set Disjointness. 107-117
  
• Hartmut Klauck:
  Rectangle Size Bounds and Threshold Covers in Communication Complexity. 118-134
  
• Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi:
  The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs. 135-
  

Session 6

• Scott Aaronson:
  Quantum Certificate Complexity. 171-178
  
• Howard Barnum, Michael E. Saks, Mario Szegedy:
  Quantum query complexity and semi-definite programming. 179-193
  
• Ke Yang, Avrim Blum:
  On Statistical Query Sampling and NMR Quantum Computing. 194-
  

Session 7

• Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy:
  Derandomization and Distinguishing Complexity. 209-220
  
• Andrei E. Romashchenko:
  Extracting the Mutual Information for a Triple of Binary Strings. 221-229
  
• Wolfgang Merkle:
  The complexity of stochastic sequences. 230-
  

Session 8

• Albert Atserias, Víctor Dalmau:
  A Combinatorial Characterization of ResolutionWidth. 239-247
  
• Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind:
  Memoization and DPLL: Formula Caching Proof Systems. 248-
  

Invited Talk

• Johan Håstad:
  Inapproximability Some history and some open problems. 265-
  

Session 10

• Rahul Santhanam, Dieter van Melkebeek:
  Holographic Proofs and Derandomization. 269-283
  
• Lars Engebretsen, Jonas Holmerin:
  Three-Query PCPs with Perfect Completeness over non-Boolean Domains. 284-299
  
• Venkatesan Guruswami:
  List Decoding with Side Information. 300-
  

Session 11

• Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang:
  Disjoint NP-Pairs. 313-332
  
• Richard Beigel, Lance Fortnow:
  Are Cook and Karp Ever the Same? 333-336
  
• Alan Nash, Russell Impagliazzo, Jeffrey B. Remmel:
  Universal Languages and the Power of Diagonalization. 337-346
  
• Lance Fortnow, Aduri Pavan, Samik Sengupta:
  Proving SAT does not have Small Circuits with an Application to the Two. 347-
  

Invited Talk

• Manindra Agrawal:
  On Derandomizing Tests for Certain Polynomial Identities. 355-
  

Session 13

• Oded Regev:
  Improved Inapproximability of Lattice and Coding Problems with Preprocessing. 363-370
  
• Jonas Holmerin, Subhash Khot:
  A Strong Inapproximability Gap for a Generalization of Minimum Bisection. 371-378
  
• Subhash Khot, Oded Regev:
  Vertex Cover Might be Hard to Approximate to within 2-\varepsilon. 379-