14. CoCo 1999: Atlanta, Georgia, USA

Joint STOC/Complexity Session

• Eli Ben-Sasson, Avi Wigderson:
  Short Proofs Are Narrow - Resolution Made Simple (Abstract). 2
  
• J. Maurice Rojas:
  On the Complexity of Diophantine Geometry in Low Dimensions (Abstract). 3
  
• Madhu Sudan, Luca Trevisan, Salil P. Vadhan:
  Pseudorandom Generators without the XOR Lemma (Abstract). 4
  
• Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi:
  Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract). 5
  
• Marcus Schaefer:
  Graph Ramsey Theory and the Polynomial Hierarchy (Abstract). 6
  
• Stephen Ponzio, Jaikumar Radhakrishnan, Srinivasan Venkatesh:
  The Communication Complexity of Pointer Chasing Applications of Entropy and Sampling (Abstract). 7
  

Session 1

• Eric Allender, Michael E. Saks, Igor Shparlinski:
  A Lower Bound for Primality. 10-14
  
• Maria Luisa Bonet, Carlos Domingo, Ricard Gavaldà, Alexis Maciel, Toniann Pitassi:
  Non-Automatizability of Bounded-Depth Frege Proofs. 15-23
  
• David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum:
  On Monotone Planar Circuits. 24-
  

Session 2

• Anna Gál, Shai Halevi, Richard J. Lipton, Erez Petrank:
  Computing from Partial Solutions. 34-45
  
• Ravi Kumar, D. Sivakumar:
  Proofs, Codes, and Polynomial-Time Reducibilities. 46-53
  
• Oded Goldreich, Salil P. Vadhan:
  Comparing Entropies in Statistical Zero Knowledge with Applications to the Structure of SZK. 54-
  

Invited Speaker 1

• Avi Wigderson:
  De-Randomizing BPP: The State of the Art. 76-
  

Session 3

• Mikael Goldmann, Alexander Russell:
  The Complexity of Solving Equations over Finite Groups. 80-86
  
• Amir Shpilka, Avi Wigderson:
  Depth-3 Arithmetic Formulae over Fields of Characteristic Zero. 87-
  

Session 4

• László Babai, Sophie Laplante:
  Stronger Separations for Random-Self-Reducibility, Rounds, and Advice. 98-104
  
• Tao Jiang, Ming Li, Paul M. B. Vitányi:
  The Expected Size of Heilbronn's Triangles. 105-113
  
• Andrei A. Muchnik, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin:
  Upper Semilattice of Binary Strings with the Relation "x is Simple Conditional to y". 114-
  

Session 5

• Richard Beigel:
  Gaps in Bounded Query Hierarchies. 124-141
  
• Jack Jie Dai, Jack H. Lutz:
  Query Order and NP-Completeness. 142-148
  
• Harry Buhrman, Wim van Dam:
  Quantum Bounded Query Complexity. 149-
  

Invited Speaker 2

• Jin-yi Cai:
  Some Recent Progress on the Complexity of Lattice Problems. 158-
  

Session 6

• John Watrous:
  Quantum Simulations of Classical Random Walks and Undirected Graph Connectivity. 180-187
  
• Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson:
  Deterministic Amplification of Space-Bounded Probabilistic Algorithms. 188-
  

Session 7

• Ravi Kumar, D. Sivakumar:
  A Note on the Shortest Lattice Vector Problem. 200-204
  
• Jin-yi Cai:
  Applications of a New Transference Theorem to Ajtai's Connection Factor. 205-214
  
• Jun Tarui, Tatsuie Tsukiji:
  Learning DNF by Approximating Inclusion-Exclusion Formulae. 215-
  

Session 8

• Richard Beigel, Alexis Maciel:
  Circuit Lower Bounds Collapse Relativized Complexity Classes. 222-226
  
• Harry Buhrman, Leen Torenvliet:
  Complicated Complementations. 227-236
  
• Russell Impagliazzo, Ramamohan Paturi:
  Complexity of k-SAT. 237-240