11. CoCo 1996: Philadelphia, Pennsylvania, USA

Session 1

• Manindra Agrawal, Eric Allender:
  An Isomorphism Theorem for Circuit Complexity. 2-11
  
• Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer:
  Nondeterministic NC¹ Computation. 12-21
  

Session 2

• Kazuo Iwama, Chuzo Iwamoto:
  Parallel Complexity Hierarchies Based on PRAMs and DLOGTIME-Uniform Circuits. 24-32
  
• Georg Gottlob:
  Collapsing Oracle-Tape Hierarchies. 33-42
  

Session 3

• Noam Nisan:
  Extracting Randomness: How and Why A survey. 44-58
  
• Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish V. Naik:
  On Coherence, Random-self-reducibility, and Self-correction. 59-67
  

Session 4

• Uriel Feige, Oleg Verbitsky:
  Error Reduction by Parallel Repetition - a Negative Result. 70-76
  
• Marcus Schäfer:
  Deciding the Vapnik-Cervonenkis dimension is Sigma^P₃-complete. 77-80
  
• Pascal Koiran:
  VC Dimension in Circuit Complexity. 81-85
  

Session 5

• Dieter van Melkebeek:
  Reducing P to a Sparse Set using a Constant Number of Queries Collapses P to L. 88-96
  
• Lance Fortnow, Judy Goldsmith, Stephen R. Mahaney:
  L-Printable Sets. 97-106
  

Session 6

• V. Vinay:
  Hierarchies of Circuit Classes that are Closed under Complement. 108-117
  
• Helmut Veith:
  Succinct Representation, Leaf Languages, and Projection Reductions. 118-126
  

Session 7

• Michael E. Saks:
  Randomization and Derandomization in Space_Bounded Computation. 128-149
  
• Ker-I Ko, Klaus Weihrauch:
  On the Measure of Two-Dimensional Regions with Polynomial-Time computables Boundaries. 150-159
  

Session 9

• Clemens Lautemann, Thomas Schwentick, Iain A. Stewart:
  On Positive P. 162-170
  
• Klaus Ambos-Spies, Elvira Mayordomo, Xizhong Zheng:
  A Comparison of Weak Completeness Notions. 171-178
  

Session 10

• Yongge Wang:
  The Law of the Iterated Logarithm for p-Random Sequences. 180-189
  
• Rainer Schuler:
  Truth-table Closure and Turing Closure of Average Polynomial Time have Different Measures in EXP. 190-195
  

Session 11

• Alan L. Selman:
  Much Ado about Functions. 198-212
  
• Stephen A. Fenner, Lance Fortnow, Ashish V. Naik, John D. Rogers:
  Inverting Onto Functions. 213-222
  

Session 12

• Ashish V. Naik, Alan L. Selman:
  A Note on P-selective sets and on Adaptive versus Nonadaptive Queries to NP. 224-232
  
• Samuel R. Buss, Toniann Pitassi:
  Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle. 233-242
  

Session 13

• Christos H. Papadimitriou:
  The Complexity of Knowledge Representation. 244-248
  
• Ian Barland, Phokion G. Kolaitis, Madhukar N. Thakur:
  Integer Programming as a Framework for Optimization and Approximability. 249-259
  
• Stephen A. Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer:
  Complements of Multivalued Functions. 260-269
  

Session 14

• Manindra Agrawal, Vikraman Arvind:
  A Note on Decision versus Search for Graph Automorphism. 272-277
  
• Uriel Feige, Joe Kilian:
  Zero Knowledge and the Chromatic Number. 278-287
  

Session 15

• Eric Bach, Anne Condon, Elton Glaser, Celena Tanguay:
  DNA Models and Algorithms for NP-complete Problems. 290-300
  
• Ming Li, Paul M. B. Vitányi:
  Reversible Simulation of Irreversible Computation. 301-306