Abstracts

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