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