Schedule for Complexity '99
Monday, May 3
7:00PM Reception
Tuesday, May 4
Joint STOC/Complexity Session 1
8:35-8:55
Short Proofs are Narrow - Resolution made Simple, Eli Ben-Sasson and
Avi Wigderson
9:00-9:20
On the Complexity of Diophantine Geometry in Low Dimensions,
J. Maurice Rojas
9:25-9:45
Pseudorandom generators without the XOR Lemma, Madhu Sudan and Luca
Trevisan and Salil Vadhan
9:50-10:10
Linear Gaps Between Degrees for the Polynomial Calculus Modulo
Distinct Primes, Sam Buss and Russell Impagliazzo and Toniann Pitassi
10:10-10:35 Break
Joint STOC/Complexity Session 2
10:35-10:55
Graph Ramsey Theory and the Polynomial Hierarchy, Marcus Schaefer 
11:00-11:20
The communication complexity of pointer chasing, Applications of
entropy and sampling, Stephen J. Ponzio and Jaikumar Radhakrishnan and
S. Venkatesh
11:30-12:30 FCRC Plenary Session
12:30-2:00 Lunch
Session 1
Chair: Pierre McKenzie
2:00-2:30
A Lower Bound for Primality, Eric Allender and Michael Saks and Igor
Shparlinski
2:30-3:00
Non-automatizability of bounded-depth Frege proofs, Maria Luisa Bonet and
Carlos Domingo and Ricard Gavalda and Alexis Maciel and Toniann Pitassi
3:00-3:30
On Monotone Planar Circuits, David A. Mix Barrington and Chi-Jen Lu
and Peter Bro Miltersen and Sven Skyum
3:30-4:00 Break
Session 2
Chair: Ronitt Rubinfeld
4:00-4:30
Computing from partial solutions, Anna Gal and Shai Halevi and Richard
Lipton and Erez Petrank
4:30-5:00
Proofs, Codes, and Polynomial-Time Reducibilities, S. Ravi Kumar and D.
Sivakumar
5:00-5:30
Comparing Entropies in Statistical Zero-Knowledge with Applications to the
Structure of SZK, Oded Goldreich and Salil Vadhan
6:00 FCRC Mixer
Wednesday, May 5
Invited Speaker 1
8:35-9:50
Derandomizing BPP - The State of the Art, Avi Wigderson
9:50-10:20 Break
Session 3
Chair: Paul Beame
10:20-10:50
The Complexity of Solving Systems of Equations over Finite Groups, Mikael
Goldmann and Alexander Russell
10:50-11:20
Depth-3 Arithmetic Formulae over Fields of Characteristic Zero, Amir Shpilka
and Avi Wigderson
11:30-12:30 FCRC Plenary Session
12:30-2:00 Lunch
Session 4:
Chair: Thomas Thierauf
2:00-2:30
Stronger separations for random-self-reducibility, rounds, and advice,
Laszlo Babai and Sophie Laplante
2:30-3:00
The expected size of Heilbronn's triangles, Tao Jiang and Ming Li and Paul
Vitanyi
3:00-3:30
Upper semilattice of binary strings with the relation "x is simple
conditional to y", Andrei Muchnik and Andrei Romashchenko and Alexander Shen
and Nikolai Vereshagin
3:30-4:00 Break
Session 5:
Chair: Richard Chang
4:00-4:30
Gaps in Bounded Query Hierarchies, Richard Beigel
4:30-5:00
Query Order and NP-Completeness, Jack J. Dai and Jack H. Lutz
5:00-5:30
Quantum Bounded Query Complexity, Harry Buhrman and Wim van Dam
6:00 FCRC Mixer
7:00 Business Meeting
Thursday, May 6
Invited Speaker 2
8:35-9:50
Some Recent Progress on the Complexity of Lattice Problems, Jin-Yi Cai
9:50-10:20 Break
Session 6
Chair: Amnon Ta-Shma
10:20-10:50
Quantum simulations of classical random walks and undirected graph
connectivity, John Watrous
10:50-11:20
Deterministic Amplification of Space Bounded Probabilistic Algorithms, Ziv
Bar-Yossef and Oded Goldreich and Avi Wigderson
11:30-12:30 FCRC Plenary Session
12:30-2:00 Lunch
Session 7
Chair: Manindra Agrawal
2:00-2:30
A Note on the Shortest Lattice Vector Problem, S. Ravi Kumar and D.
Sivakumar
2:30-3:00
Applications of a New Transference Theorem to Ajtai's Connection Factor,
Jin-Yi Cai
3:00-3:30
Learning DNF by Approximating Inclusion-Exclusion Formulae, Jun Tarui and
Tatsuie Tsukiji
3:30-4:00 Break
Session 8
Chair: Frederic Green
4:00-4:30
Circuit Lower Bounds Collapse Relativized Complexity Classes, Richard Beigel
and Alexis Maciel
4:30-5:00
Complicated Complementations, Harry Buhrman and Leen Torenvliet
5:00-5:30
Complexity of k-SAT, Russell Impagliazzo and Ramamohan Paturi
6:00 FCRC Mixer