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
  

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, Jiri 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
  

Last update Sat May 18 20:07:42 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page