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