Electronic Colloquium on Computational Complexity, Volume 1, 1994

Volume 1, 1994

1. Noam Nisan, Avi Wigderson:
   On Rank vs. Communication Complexity.
   
2. Oded Goldreich, Avi Wigderson:
   Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing.
   
3. Noam Nisan, Amnon Ta-Shma:
   Symmetric Logspace is Closed Under Complement.
   
4. Eric Allender, Martin Strauss:
   Measure on Small Complexity Classes, with Applications for BPP.
   
5. Noga Alon, Alan M. Frieze, Dominic Welsh:
   Polynomial Time Randomised Approximation Schemes for Tutte-Gröthendieck Invariants: The Dense Case.
   
6. Alexander A. Razborov:
   On provably disjoint NP-pairs.
   
7. Oded Goldreich, Rafail Ostrovsky, Erez Petrank:
   Computational Complexity and Knowledge Complexity.
   
8. Oded Goldreich:
   Probabilistic Proof Systems (A Survey).
   
9. Noga Alon, Raphael Yuster, Uri Zwick:
   Color-Coding.
   
10. Alexander A. Razborov, Steven Rudich:
    Natural Proofs.
    
11. Richard Beigel, William Hurwood, Nabil Kahale:
    Fault Diagnosis in a Flash.
    
12. Wolfgang Maass:
    Bounds for the Computational Power and Learning Complexity of Analog Neural Nets.
    
13. Pavel Pudlák:
    Complexity Theory and Genetics (extended abstract).
    
14. Miklós Ajtai:
    The Independence of the modulo p Counting Principles.
    
15. Miklós Ajtai:
    Symmetric Systems of Linear Equations modulo p.
    
16. Jin-yi Cai, Wolfgang H. J. Fuchs, Dexter Kozen, Zicheng Liu:
    Efficient Average-Case Algorithms for the Modular Group.
    
17. Wolfgang Maass:
    Neural Nets with Superlinear VC-Dimension.
    
18. 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.
    
19. Wolfgang Maass:
    Lower Bounds for the Computational Power of Networks of Spiking Neurons.
    
20. Wolfgang Maass:
    Agnostic PAC-Learning of Functions on Analog Neural Nets.
    
21. Lance Fortnow:
    My Favorite Ten Complexity Theorems of the Past Decade.
    
22. 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.
    
23. Matthias Krause, Pavel Pudlák:
    On the Computational Power of Depth 2 Circuits with Threshold and Modulo Gates.
    
24. Marek Karpinski, Angus Macintyre:
    Polynomial Bounds for VC Dimension of Sigmoidal Neural Networks.
    
25. David P. Dobkin, Dimitrios Gunopulos, Wolfgang Maass:
    Computing the Maximum Bichromatic Discrepancy, with applications to Computer Graphics and Machine Learning.
    
26. Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener:
    On the Power of Different Types of Restricted Branching Programs.
    
27. Stasys Jukna:
    A Note on Read-k Times Branching Programs.