Session 1

• 
  Seinosuke Toda, Mitsunori Ogiwara: Counting Classes Are at Least as Hard as the Polynomial-Time Hierarchy. 2-12
• 
  Lance Fortnow, Nick Reingold: PP is Closed Under Truth-Table Reductions. 13-15
• 
  Mitsunori Ogiwara, Lane A. Hemachandra: A Complexity Theory for Feasible Closure Properties. 16-29
• 
  Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz: Gap-Definable Counting Classes. 30-42
• 
  Sanjay Gupta: The Power of Witness Reduction. 43-59

Session 2

• 
  William I. Gasarch: Bounded Queries in Recursion Theory: A Survey. 62-78
• 
  Steven Homer, Luc Longpré: On Reductions of NP Sets to Sparse Sets. 79-88
• 
  Ricard Gavaldà, Osamu Watanabe: On the Computational Complexity of Small Descriptions. 89-101
• 
  Daniel P. Bovet, Pierluigi Crescenzi, Riccardo Silvestri: Complexity Classes and Sparse Oracles. 102-108

Session 3

• 
  Jin-yi Cai, Anne Condon, Richard J. Lipton: PSPACE Is Provable By Two Provers In One Round. 110-115
• 
  Uriel Feige: On the Success Probability of the Two Provers in One-Round Proof Systems. 116-123
• 
  Joan Feigenbaum, Lance Fortnow: On the Random-Self-Reducibility of Complete Sets. 124-132
• 
  Rafail Ostrovsky: One-Way Functions, Hard on Average Problems, and Statistical Zero-Knowledge Proofs. 133-138
• 
  Mitsunori Ogiwara, Antoni Lozano: On One Query Self-Reducible Sets. 139-151

Session 4

• 
  Ming Li, Paul M. B. Vitányi: Combinatorics and Kolmogorov Complexity. 154-163
• 
  Peter Bro Miltersen: The Complexity of Malign Ensembles. 164-171
• 
  Rafi Heiman, Avi Wigderson: Randomized vs.Deterministic Decision Tree Complexity for Read-Once Boolean Functions. 172-179
• 
  Miklos Santha: On the Monte Carlo Boolean Decision Tree Complexity of Read-Once Formulae. 180-187

Session 5

• 
  Jack H. Lutz: A Pseudorandom Oracle Characterization of BPP. 190-195
• 
  Stephen A. Fenner: Notions of Resource-Bounded Category and Genericity. 196-212
• 
  László Babai, Noam Nisan: BPP has Subexponential Time Simulation unless EXPTIME has Pubishable Proofs. 213-219
• 
  Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe: Relating Equivalence and Reducibility to Sparse Sets. 220-229
• 
  Shouwen Tang, Bin Fu, Tian Liu: Exponential Time and Subexponential Time Sets. 230-237

Session 6

• 
  José L. Balcázar: Adaptive Logspace and Depth-Bounded Reducibilities. 240-254
• 
  Richard Chang, Jim Kadin, Pankaj Rohatgi: Connections between the Complexity of Unique Satisfiability and the Threshold Behavior of Randomized Reductions. 255-269
• 
  V. Vinay: Counting Auxiliary Pushdown Automata. 270-284
• 
  Jun Tarui: Degree Compexity of Boolean Functions and Its Applications to Realivized Separations. 382-390
• 
  Richard Beigel, Nick Reingold, Daniel A. Spielman: The Perceptron Strikes Back. 286-291

Session 7

• 
  Michelangelo Grigni, Michael Sipser: Monotone Separation of Logspace from NC. 294-298
• 
  Mauricio Karchmer, Ran Raz, Avi Wigderson: Super-logarithmic Depth Lower Bounds via Direct Sum in Communication Coplexity. 299-304
• 
  David A. Mix Barrington, Howard Straubing: Superlinear Lower Bounds for Bounded-Width Branching Programs. 305-313
• 
  Matthias Krause: Geometric Arguments Yield Better Bounds for Threshold Circuits and Distributed Computing. 314-321
• 
  Jeff Edmonds: Lower Bounds with Smaller Domain Size On Concurrent Write Parallel Machines. 322-331

Session 8

• 
  Neil Immerman: DSPACE[n^k] = VAR[k+1]. 334-340
• 
  Erich Grädel: Capturing Complexity Classes by Fragments of Second Order Logic. 341-352
• 
  Phokion G. Kolaitis, Madhukar N. Thakur: Approximation Properties of NP Minimization Classes. 353-366
• 
  Stephen Bellantoni, Toniann Pitassi, Alasdair Urquhart: Approximation and Small Depth Frege Proofs. 367-390

Errata

• 
  Jack H. Lutz, William J. Schmidt: Errata for Circuit Size to Pseudorandom Oracles. 392

last updated on Sun May 26 03:41:39 2013 by the dblp team
data released under the ODC-BY 1.0 license
see also our legal information page