


default search action
Computational Complexity, Volume 9
Volume 9, Number 1, 2000
- Ramamohan Paturi, Michael E. Saks, Francis Zane:
Exponential lower bounds for depth three Boolean circuits. 1-15 - Frederic Green:
A complex-number Fourier technique for lower bounds on the Mod-m degree. 16-38 - Anna Bernasconi, Carsten Damm
, Igor E. Shparlinski
:
The average sensitivity of square-freeness. 39-51 - Catherine S. Greenhill:
The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. 52-72
Volume 9, Number 2, 2000
- Markus Bläser:
Lower bounds for the bilinear complexity of associative algebras. 73-112 - Ran Raz
:
The BNS-Chung criterion for multi-party communication complexity. 113-122 - Carme Àlvarez, Raymond Greenlaw:
A compendium of problems complete for symmetric logarithmic space. 123-145 - Frank Blume:
On the relation between entropy and the average complexity of trajectories in dynamical systems. 146-155
Volume 9, Number 3-4, 2000
- Prahladh Harsha
, Madhu Sudan:
Small PCPs with low query complexity. 157-201 - Marcos A. Kiwi, Carsten Lund, Daniel A. Spielman
, Alexander Russell
, Ravi Sundaram:
Alternation in interaction. 202-246 - Detlef Sieling:
A separation of syntactic and nonsyntactic (1, +k)-branching programs. 247-263

manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.