Abstracts
- Optimal proof systems imply complete sets for promise classes
- A General Dimension for Approximate Learning
- The Complexity of Learning Concept Classes with Polynomial General Dimension
- The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3
- New Lowness Results for ZPP(NP) and other Complexity Classes
- On Pseudorandomness and Resource-Bounded Measure
- Oracles in NP(NP) are sufficient for exact learning
- On distribution-specific learning with membership queries versus pseudorandom generation
- Is the Standard Proof System for SAT P-optimal?
- Nondeterministic instance complexity and hard-to-prove tautologies
- The Complexity of Generating Test Instances
- New Collapse Consequences of NP Having Small Circuits
- Average-Case Intractability vs. Worst-Case Intractability
- On the Resource Bounded Measure of P/poly
- Complete Problems for Promise Classes by Optimal Proof Systems for Test Sets
- High Sets for NP
- Upper Bounds for the Complexity of Sparse and Tally Descriptions
- Monotonous and Randomized Reductions to Sparse Sets
- On the Power of Generalized MOD-Classes
- On the Structure of Low Sets (Survey)
- On Reductions to Sets that Avoid EXPSPACE
- If NP has Polynomial-Size Circuits, then MA = AM
- The Power of the Middle Bit of a #P Function
- Locating P/poly Optimally in the Extended Low Hierarchy
- On Helping and Interactive Proof Systems
- Extension of Toda's Theorem to Middle Bit Classes (Survey)
- Complexity-Restricted Advice Functions
- Hausdorff Reductions to Sparse Sets and to Sets of High Information Content
- Reductions to Sets of Low Information Content
- On Bounded Truth-Table, Conjunctive, and Randomized Reductions to Sparse Sets
- Turing Machines with Few Accepting Computations and Low Sets for PP
- Graph Isomorphism is Low for PP
- Lowness and the Complexity of Sparse and Tally Descriptions
- On Counting and Approximation
- The Difference and Truth-Table Hierarchies for NP
- On Hypergraph and Graph Isomorphism with Bounded Color Classes
- Representable Disjoint NP-Pairs
- Disjoint NP-pairs from propositional proof systems
- Tuples of disjoint NP-sets
- Von der Turingmaschine zum Quantencomputer - ein Gang durch die Geschichte der Komplexitätstheorie
- The Deduction Theorem for Strong Propositional Proof Systems
- Classes of Representable Disjoint NP-Pairs
- Tuples of Disjoint NP-Sets
- A General Dimension for Query Learning
- Parameterized Learnability of k-Juntas and Related Problems
- The Space Complexity of k-Tree Isomorphism
