Issue 2/2012
Theoretical Aspects of Computer Science
Content (7 Articles)
The Complexity of the List Homomorphism Problem for Graphs
László Egri, Andrei Krokhin, Benoit Larose, Pascal Tesson
On Optimal Heuristic Randomized Semidecision Procedures, with Applications to Proof Complexity and Cryptography
Edward A. Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal
Open Access
Representing Hyper-arithmetical Sets by Equations over Sets of Integers
Artur Jeż, Alexander Okhotin
Inseparability and Strong Hypotheses for Disjoint NP Pairs
Lance Fortnow, Jack H. Lutz, Elvira Mayordomo
Collapsing and Separating Completeness Notions Under Average-Case and Worst-Case Hypotheses
Xiaoyang Gu, John M. Hitchcock, A. Pavan