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