default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDComputational Complexity, Volume 6
Volume 6, Number 1, 1996/1997
- Greg Barnes, Walter L. Ruzzo
:
Undirected s-t Connectivity in Polynomial Time and Sublinear Space. 1-28 - Amos Beimel, Anna Gál, Mike Paterson:
Lower Bounds for Monotone Span Programs. 29-45 - Arvind Gupta, Sanjeev Mahajan:
Using Amplification to Compute Majority with Small Majority Gates. 46-63 - Joachim von zur Gathen, Marek Karpinski, Igor E. Shparlinski:
Counting Curves and Their Projections. 64-99
Volume 6, Number 2, 1996/1997
- Uriel Feige, Carsten Lund:
On the Hardness of Computing the Permanent of Random Matrices. 101-132 - Rüdiger Reischuk, Christian Schindelhauer:
An Average Complexity Measure that Yields Tight Hierarchies. 133-173 - Nader H. Bshouty:
Simple Learning Algorithms Using Divide and Conquer. 174-194
Volume 6, Number 3, 1997
- Allan Borodin:
Tribute to Roman Smolensky. 195-198 - Roman Smolensky:
Representations of Sets of Boolean Functions by Commutative Rings. 199-208 - Jehoshua Bruck:
Reflections on "Representations of Sets of Boolean Functions by Commutative Rings" by Roman Smolensky. 209-212 - Roman Smolensky:
Easy Lower Bound for a Strange Computational Model. 213-216 - Noam Nisan, Avi Wigderson:
Lower Bounds on Arithmetic Circuits Via Partial Derivatives. 217-234 - Richard Beigel, Alexis Maciel:
Upper and Lower Bounds for Some Depth-3 Circuit Classes. 235-255 - Samuel R. Buss, Russell Impagliazzo, Jan Krajícek, Pavel Pudlák, Alexander A. Razborov, Jirí Sgall:
Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting. 256-298
Volume 6, Number 4, 1997
- Roman Smolensky:
Well-Known Bound for the VC-Dimension Made Easy. 299-300 - Victor Shoup, Roman Smolensky:
Lower Bounds for Polynomial Evaluation and Interpolation Problems. 301-311 - Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, Prasoon Tiwari:
The Electrical Resistance of a Graph Captures its Commute and Cover Times. 312-340 - Uriel Feige:
Collecting Coupons on Trees, and the Cover Time of Random Walks. 341-356 - Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky:
A Lower Bound for Randomized Algebraic Decision Trees. 357-375 - Dima Grigoriev, Marek Karpinski, Roman Smolensky:
Randomization and the Computational Power of Analytic and Algebraic Decision Trees. 376-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 2025-12-04 22:08 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:
