6. CoCo 1991:
Chicago, Illinois, USA
Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30 - July 3, 1991.
IEEE Computer Society 1991, ISBN 0-8186-2055-5
Session 1
export record as
dblp key:
export record as
dblp key:
export record as
dblp key:
export record as
dblp key:
export record as
dblp key:
Session 2
export record as
dblp key:
export record as
dblp key:
export record as
dblp key:
export record as
dblp key:
Session 3
export record as
dblp key:
export record as
dblp key:
Uriel Feige :
On the Success Probability of the Two Provers in One-Round Proof Systems.
116-123
export record as
dblp key:
export record as
dblp key:
Rafail Ostrovsky :
One-Way Functions, Hard on Average Problems, and Statistical Zero-Knowledge Proofs.
133-138
export record as
dblp key:
Session 4
export record as
dblp key:
export record as
dblp key:
export record as
dblp key:
Rafi Heiman ,
Avi Wigderson :
Randomized vs.Deterministic Decision Tree Complexity for Read-Once Boolean Functions.
172-179
export record as
dblp key:
Miklos Santha :
On the Monte Carlo Boolean Decision Tree Complexity of Read-Once Formulae.
180-187
Session 5
export record as
dblp key:
Jack H. Lutz :
A Pseudorandom Oracle Characterization of BPP.
190-195
export record as
dblp key:
export record as
dblp key:
László Babai ,
Noam Nisan :
BPP has Subexponential Time Simulation unless EXPTIME has Pubishable Proofs.
213-219
export record as
dblp key:
export record as
dblp key:
Session 6
export record as
dblp key:
export record as
dblp key:
export record as
dblp key:
V. Vinay :
Counting Auxiliary Pushdown Automata.
270-284
export record as
dblp key:
Jun Tarui :
Degree Compexity of Boolean Functions and Its Applications to Realivized Separations.
382-390
export record as
dblp key:
Session 7
export record as
dblp key:
export record as
dblp key:
export record as
dblp key:
export record as
dblp key:
Matthias Krause :
Geometric Arguments Yield Better Bounds for Threshold Circuits and Distributed Computing.
314-321
export record as
dblp key:
Jeff Edmonds :
Lower Bounds with Smaller Domain Size On Concurrent Write Parallel Machines.
322-331
Session 8
export record as
dblp key:
export record as
dblp key:
Erich Grädel :
Capturing Complexity Classes by Fragments of Second Order Logic.
341-352
export record as
dblp key:
export record as
dblp key:
Errata
export record as
dblp key: