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
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 Shparlinski: Counting Curves and Their Projections. 64-99

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

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, Jiri Sgall: Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting. 256-298

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