default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDComputational Complexity, Volume 3
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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-02-21 19:35 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
