Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

Completeness Results for Graph Isomorphism

erstellt von algorithmenIIAdmin — zuletzt geändert 17.02.2012 19:38

Optimal proof systems imply complete sets for promise classes

erstellt von algorithmenIIAdmin — zuletzt geändert 17.02.2012 19:38

A General Dimension for Approximate Learning

erstellt von algorithmenIIAdmin — zuletzt geändert 17.02.2012 19:38

The Complexity of Learning Concept Classes with Polynomial General Dimension

erstellt von algorithmenIIAdmin — zuletzt geändert 17.02.2012 19:37

The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3

erstellt von algorithmenIIAdmin — zuletzt geändert 17.02.2012 19:38

New Lowness Results for ZPP(NP) and other Complexity Classes

erstellt von algorithmenIIAdmin — zuletzt geändert 17.02.2012 19:38

On Pseudorandomness and Resource-Bounded Measure

erstellt von algorithmenIIAdmin — zuletzt geändert 17.02.2012 19:37

Oracles in NP(NP) are sufficient for exact learning

erstellt von algorithmenIIAdmin — zuletzt geändert 17.02.2012 19:38

On distribution-specific learning with membership queries versus pseudorandom generation

erstellt von algorithmenIIAdmin — zuletzt geändert 17.02.2012 19:38

Is the Standard Proof System for SAT P-optimal?

erstellt von algorithmenIIAdmin — zuletzt geändert 17.02.2012 19:38

Nondeterministic instance complexity and hard-to-prove tautologies

erstellt von algorithmenIIAdmin — zuletzt geändert 17.02.2012 19:38

The Complexity of Generating Test Instances

erstellt von algorithmenIIAdmin — zuletzt geändert 17.02.2012 19:38

New Collapse Consequences of NP Having Small Circuits

erstellt von algorithmenIIAdmin — zuletzt geändert 17.02.2012 19:38

Average-Case Intractability vs. Worst-Case Intractability

erstellt von algorithmenIIAdmin — zuletzt geändert 17.02.2012 19:37

On the Resource Bounded Measure of P/poly

erstellt von algorithmenIIAdmin — zuletzt geändert 17.02.2012 19:37

Complete Problems for Promise Classes by Optimal Proof Systems for Test Sets

erstellt von algorithmenIIAdmin — zuletzt geändert 17.02.2012 19:38

High Sets for NP

erstellt von algorithmenIIAdmin — zuletzt geändert 17.02.2012 19:38

Upper Bounds for the Complexity of Sparse and Tally Descriptions

erstellt von algorithmenIIAdmin — zuletzt geändert 17.02.2012 19:38

Monotonous and Randomized Reductions to Sparse Sets

erstellt von algorithmenIIAdmin — zuletzt geändert 17.02.2012 19:37

On the Power of Generalized MOD-Classes

erstellt von algorithmenIIAdmin — zuletzt geändert 17.02.2012 19:38