default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDComputational Complexity, Volume 4
Volume 4, 1994
- Noam Nisan:
RL <= SC. 1-11 - José Luis Montaña
, Luis Miguel Pardo, Tomás Recio:
A Note on Rabin's Width of a Complete Proof. 12-36 - 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 - Etienne Grandjean:
Invariance Properties of Rams and Linear Time. 62-106 - Marie-Françoise Roy, Nicolai N. Vorobjov Jr.:
Finding Irreducible Components of Some Real Transcendental Varieties. 107-132 - Erez Petrank:
The Hardness of Approximation: Gap Location. 133-157 - Joan Feigenbaum, Lance Fortnow, Carsten Lund, Daniel A. Spielman:
The Power of Adaptiveness and Additional Queries in Random-Self-Reductions. 158-174 - Stephen A. Bloch:
Function-Algebraic Characterizations of Log and Polylog Parallel Time. 175-205 - Alan M. Frieze, Shang-Hua Teng:
On the Complexity of Computing the Diameter of a Polytope. 207-219 - Anne Condon:
A Theory of Strict P-Completeness. 220-241 - Thomas Thierauf, Seinosuke Toda, Osamu Watanabe:
On Closure Properties of GapP. 242-261 - Lane A. Hemaspaandra, Mitsunori Ogihara, Seinosuke Toda:
Space-Efficient Recognition of Sparse Self-Reducible Languages. 262-296 - Pierre McKenzie, Denis Thérien:
Special Issue on Circuit Complexity: Foreword. 297-300 - Noam Nisan, Mario Szegedy:
On the Degree of Boolean Functions as Real Polynomials. 301-313 - Richard Beigel:
When do Extra Majority Gates Help? Polylog(N) Majority Gates Are Equivalent to One. 314-324 - David A. Mix Barrington, Howard Straubing:
Complex Polynomials and Circuit Lower Bounds for Modular Counting. 325-338 - Richard Beigel:
Perceptrons, PP, and the Polynomial Hierarchy. 339-349 - Richard Beigel, Jun Tarui:
On ACC. 350-366 - David A. Mix Barrington, Richard Beigel, Steven Rudich:
Representing Boolean Functions as Polynomials Modulo Composite Numbers. 367-382 - Denis Thérien:
Circuits Constructed with Mod_q Gates Cannot Compute "And" in Sublinear Size. 383-388
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 2026-01-28 00:31 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:
