Volume 3,
1993
- Allan Borodin, Alexander A. Razborov, Roman Smolensky:
On Lower Bounds for Read-K-Times Branching Programs.
1-18
- Stephen A. Cook, Patrick W. Dymond:
Parallel Pointer Machines.
19-30
- Leandro Caniglia, Guillermo Cortiñas, Silvia Danón, Joos Heintz, Teresa Krick, Pablo Solernó:
(Working Group Noaï Fitchas) Algorithmic Aspects of Suslin's Proof of Serre's Conjecture.
31-55
- Marc Giusti, Joos Heintz, Juan Sabia:
On the Efficiency of Effective Nullstellensätze.
56-95
- Toniann Pitassi, Paul Beame, Russell Impagliazzo:
Exponential Lower Bounds for the Pigeonhole Principle.
97-140
- Ran Canetti, Oded Goldreich:
Bounds on Tradeoffs Between Randomness and Communication Complexity.
141-167
- Desh Ranjan, Suresh Chari, Pankaj Rohatgi:
Improving Known Solutions is Hard.
168-185
- Judy Goldsmith, Deborah Joseph:
Relativized Isomorphisms of NP-Complete Sets.
186-205
- Burchard von Braunmühl, Romain Gengler, Robert Rettinger:
The Alternation Hierarchy for Sublogarithmic Space is Infinite.
207-230
- Harry Buhrman, Edith Spaan, Leen Torenvliet:
The Relative Power of Logspace and Polynomial Time Reductions.
231-244
- Gábor Ivanyos, Lajos Rónyai:
Finding Maximal Orders in Semisimple Algebras Over Q.
245-261
- Mike Paterson, Uri Zwick:
Shallow Circuits and Concise Formulae for Multiple Addition and Multiplication.
262-291
- Anne Condon:
The Complexity of the Max Word Problem and the Power of One-Way Interactive Proof Systems.
292-305
- László Babai, Lance Fortnow, Noam Nisan, Avi Wigderson:
BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs.
307-318
- Mihir Bellare, Oded Goldreich, Shafi Goldwasser:
Randomness in Interactive Proofs.
319-354
- René Peralta, Victor Shoup:
Primality Testing with Fewer Random Bits.
355-367
- Eric Allender, Danilo Bruschi, Giovanni Pighizzini:
The Complexity of Computing Maximal Word Functions.
368-391
- Wolfgang Maass, Georg Schnitger, Endre Szemerédi, György Turán:
Two Tapes Versus One for Off-Line Turing Machines.
392-401
Copyright © Sun Nov 15 05:28:06 2009
by Michael Ley (ley@uni-trier.de)
