Electronic Colloquium on Computational Complexity, Volume 1, 1994

Volume 1, 1994

• Noam Nisan, Avi Wigderson:
  On Rank vs. Communication Complexity.
  
• Oded Goldreich, Avi Wigderson:
  Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing.
  
• Noam Nisan, Amnon Ta-Shma:
  Symmetric Logspace is Closed Under Complement.
  
• Eric Allender, Martin Strauss:
  Measure on Small Complexity Classes, with Applications for BPP.
  
• Noga Alon, Alan M. Frieze, Dominic Welsh:
  Polynomial Time Randomised Approximation Schemes for Tutte-Gröthendieck Invariants: The Dense Case.
  
• Alexander A. Razborov:
  On provably disjoint NP-pairs.
  
• Oded Goldreich, Rafail Ostrovsky, Erez Petrank:
  Computational Complexity and Knowledge Complexity.
  
• Oded Goldreich:
  Probabilistic Proof Systems (A Survey).
  
• Noga Alon, Raphael Yuster, Uri Zwick:
  Color-Coding.
  
• Alexander A. Razborov, Steven Rudich:
  Natural Proofs.
  
• Richard Beigel, William Hurwood, Nabil Kahale:
  Fault Diagnosis in a Flash.
  
• Wolfgang Maass:
  Bounds for the Computational Power and Learning Complexity of Analog Neural Nets.
  
• Pavel Pudlák:
  Complexity Theory and Genetics (extended abstract).
  
• Miklós Ajtai:
  The Independence of the modulo p Counting Principles.
  
• Miklós Ajtai:
  Symmetric Systems of Linear Equations modulo p.
  
• Jin-yi Cai, Wolfgang H. J. Fuchs, Dexter Kozen, Zicheng Liu:
  Efficient Average-Case Algorithms for the Modular Group.
  
• Wolfgang Maass:
  Neural Nets with Superlinear VC-Dimension.
  
• Jan Krajícek, Pavel Pudlák, Alan R. Woods:
  An Exponential Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle.
  
• Wolfgang Maass:
  Lower Bounds for the Computational Power of Networks of Spiking Neurons.
  
• Wolfgang Maass:
  Agnostic PAC-Learning of Functions on Analog Neural Nets.
  
• Lance Fortnow:
  My Favorite Ten Complexity Theorems of the Past Decade.
  
• Christoph Meinel, Stephan Waack:
  The Möbius Function, Variations Ranks, and Theta(n)-Bounds on the Modular Communication Complexity of the Undirected Graph Connectivity Problem.
  
• Matthias Krause, Pavel Pudlák:
  On the Computational Power of Depth 2 Circuits with Threshold and Modulo Gates.
  
• Marek Karpinski, Angus Macintyre:
  Polynomial Bounds for VC Dimension of Sigmoidal Neural Networks.
  
• David P. Dobkin, Dimitrios Gunopulos, Wolfgang Maass:
  Computing the Maximum Bichromatic Discrepancy, with applications to Computer Graphics and Machine Learning.
  
• Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener:
  On the Power of Different Types of Restricted Branching Programs.
  
• Stasys Jukna:
  A Note on Read-k Times Branching Programs.
  

Last update Tue May 21 13:13:24 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page