Humboldt-Universität zu Berlin | Mathematisch-Naturwissenschaftliche Fakultät | Institut für Informatik | Komplexität und Kryptografie | Publikationen | Abstracts Abstracts Completeness Results for Graph Isomorphism 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 1 2 3 Die nächsten 20 Inhalte
