![](https://dblp.dagstuhl.de/img/logo.ua.320x120.png)
![](https://dblp.dagstuhl.de/img/dropdown.dark.16x16.png)
![](https://dblp.dagstuhl.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
![search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
default search action
Computational 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
![](https://dblp.dagstuhl.de/img/cog.dark.24x24.png)
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.