Volume 4,
1994
- Noam Nisan:
RL <= SC.
1-11 BibTeX
- José Luis Montaña, Luis Miguel Pardo, Tomás Recio:
A Note on Rabin's Width of a Complete Proof.
12-36 BibTeX
- Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein, Marek Karpinski:
An Algorithm to Learn Read-Once Threshold Formulas, and Transformations Between Learning Models.
37-61 BibTeX
- Etienne Grandjean:
Invariance Properties of Rams and Linear Time.
62-106 BibTeX
- Marie-Françoise Roy, Nicolai Vorobjov:
Finding Irreducible Components of Some Real Transcendental Varieties.
107-132 BibTeX
- Erez Petrank:
The Hardness of Approximation: Gap Location.
133-157 BibTeX
- Joan Feigenbaum, Lance Fortnow, Carsten Lund, Daniel A. Spielman:
The Power of Adaptiveness and Additional Queries in Random-Self-Reductions.
158-174 BibTeX
- Stephen A. Bloch:
Function-Algebraic Characterizations of Log and Polylog Parallel Time.
175-205 BibTeX
- Alan M. Frieze, Shang-Hua Teng:
On the Complexity of Computing the Diameter of a Polytope.
207-219 BibTeX
- Anne Condon:
A Theory of Strict P-Completeness.
220-241 BibTeX
- Thomas Thierauf, Seinosuke Toda, Osamu Watanabe:
On Closure Properties of GapP.
242-261 BibTeX
- Lane A. Hemaspaandra, Mitsunori Ogihara, Seinosuke Toda:
Space-Efficient Recognition of Sparse Self-Reducible Languages.
262-296 BibTeX
- Pierre McKenzie, Denis Thérien:
Special Issue on Circuit Complexity: Foreword.
297-300 BibTeX
- Noam Nisan, Mario Szegedy:
On the Degree of Boolean Functions as Real Polynomials.
301-313 BibTeX
- Richard Beigel:
When do Extra Majority Gates Help? Polylog(N) Majority Gates Are Equivalent to One.
314-324 BibTeX
- David A. Mix Barrington, Howard Straubing:
Complex Polynomials and Circuit Lower Bounds for Modular Counting.
325-338 BibTeX
- Richard Beigel:
Perceptrons, PP, and the Polynomial Hierarchy.
339-349 BibTeX
- Richard Beigel, Jun Tarui:
On ACC.
350-366 BibTeX
- David A. Mix Barrington, Richard Beigel, Steven Rudich:
Representing Boolean Functions as Polynomials Modulo Composite Numbers.
367-382 BibTeX
- Denis Thérien:
Circuits Constructed with Mod_q Gates Cannot Compute "And" in Sublinear Size.
383-388 BibTeX
Copyright © Tue Nov 18 20:33:30 2008
by Michael Ley (ley@uni-trier.de)
