Computational Complexity, Volume 2

Volume 2, 1992

• Richard Beigel, Joan Feigenbaum: On Being Incoherent Without Being Very Hard. 1-17 BibTeX
• Judy Goldsmith, Lane A. Hemachandra, Kenneth Kunen: Polynomial-Time Compression. 18-39 BibTeX
• James F. Lynch: The Quantifier Structure of Sentences That Characterize Nondeterministic Time Complexity. 40-66 BibTeX
• Mohammad Amin Shokrollahi: Efficient Randomized Generation of Optimal Algorithms for Multiplication in Certain Finite Fields. 67-96 BibTeX
• Stephen Bellantoni, Stephen A. Cook: A New Recursion-Theoretic Characterization of the Polytime Functions. 97-110 BibTeX
• Matthijs J. Coster, Antoine Joux, Brian A. LaMacchia, Andrew M. Odlyzko, Claus-Peter Schnorr, Jacques Stern: Improved Low-Density Subset Sum Algorithms. 111-128 BibTeX
• Igor Shparlinski: A Deterministic Test for Permutation Polynomials. 129-132 BibTeX
• D. Yu. Grigoryev, Nicolai Vorobjov: Counting Connected Components of a Semialgebraic Set in Subexponential Time. 133-186 BibTeX
• Joachim von zur Gathen, Victor Shoup: Computing Frobenius Maps and Factoring Polynomials. 187-224 BibTeX
• Lajos Rónyai: Algorithmic Properties of Maximal Orders in Simple Algebras over Q. 225-243 BibTeX
• Nader H. Bshouty, Yishay Mansour, Baruch Schieber, Prasoon Tiwari: Fast Exponentiation Using the Truncation Operation. 244-255 BibTeX
• Katia S. Guimarães, William I. Gasarch, James M. Purtilo: Selection Problems via M-Ary Queries. 256-276 BibTeX
• Mikael Goldmann, Johan Håstad, Alexander A. Razborov: Majority Gates VS. General Weighted Threshold Gates. 277-300 BibTeX
• Johannes Köbler, Uwe Schöning, Jacobo Torán: Graph Isomorphism is Low for PP. 301-330 BibTeX
• Franz Aurenhammer, Johann Hagauer, Wilfried Imrich: Cartesian Graph Factorization at Logarithmic Cost per Edge. 331-349 BibTeX
• Omer Berkman, Yossi Matias, Uzi Vishkin: Randomized Range-Maxima in Nearly-Constant Parallel Time. 350-373 BibTeX
• László Babai, Lance Fortnow, Carsten Lund: Addendum to Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. 374 BibTeX , ->Computational Complexity 1: 3-40(1991) BibTeX