Computational 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 BibTeX
• Amos Beimel, Anna Gál, Mike Paterson: Lower Bounds for Monotone Span Programs. 29-45 BibTeX
• Arvind Gupta, Sanjeev Mahajan: Using Amplification to Compute Majority with Small Majority Gates. 46-63 BibTeX
• Joachim von zur Gathen, Marek Karpinski, Igor Shparlinski: Counting Curves and Their Projections. 64-99 BibTeX

Volume 6, Number 2, 1996/1997

• Uriel Feige, Carsten Lund: On the Hardness of Computing the Permanent of Random Matrices. 101-132 BibTeX
• Rüdiger Reischuk, Christian Schindelhauer: An Average Complexity Measure that Yields Tight Hierarchies. 133-173 BibTeX
• Nader H. Bshouty: Simple Learning Algorithms Using Divide and Conquer. 174-194 BibTeX

Volume 6, Number 3, 1997

• Allan Borodin: Tribute to Roman Smolensky. 195-198 BibTeX
• Roman Smolensky: Representations of Sets of Boolean Functions by Commutative Rings. 199-208 BibTeX
• Jehoshua Bruck: Reflections on ``Representations of Sets of Boolean Functions by Commutative Rings'' by Roman Smolensky. 209-212 BibTeX
• Roman Smolensky: Easy Lower Bound for a Strange Computational Model. 213-216 BibTeX
• Noam Nisan, Avi Wigderson: Lower Bounds on Arithmetic Circuits Via Partial Derivatives. 217-234 BibTeX
• Richard Beigel, Alexis Maciel: Upper and Lower Bounds for Some Depth-3 Circuit Classes. 235-255 BibTeX
• Samuel R. Buss, Russell Impagliazzo, Jan Krajícek, Pavel Pudlák, Alexander A. Razborov, Jiri Sgall: Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting. 256-298 BibTeX

Volume 6, Number 4, 1997

• Roman Smolensky: Well-Known Bound for the VC-Dimension Made Easy. 299-300 BibTeX
• Victor Shoup, Roman Smolensky: Lower Bounds for Polynomial Evaluation and Interpolation Problems. 301-311 BibTeX
• 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 BibTeX
• Uriel Feige: Collecting Coupons on Trees, and the Cover Time of Random Walks. 341-356 BibTeX
• Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky: A Lower Bound for Randomized Algebraic Decision Trees. 357-375 BibTeX
• Dima Grigoriev, Marek Karpinski, Roman Smolensky: Randomization and the Computational Power of Analytic and Algebraic Decision Trees. 376-388 BibTeX