Volume 51; Issue 2

Theory of Computing Systems

Volume 51; Issue 2

1

The Complexity of the List Homomorphism Problem for Graphs

László Egri, Andrei Krokhin, Benoit Larose, Pascal Tesson

Journal:

Theory of Computing Systems

Year:

2012

Language:

english

File:

PDF, 1.06 MB

english, 2012

2

Inseparability and Strong Hypotheses for Disjoint NP Pairs

Lance Fortnow, Jack H. Lutz, Elvira Mayordomo

Journal:

Theory of Computing Systems

Year:

2012

Language:

english

File:

PDF, 599 KB

english, 2012

3

Dispersion in Disks

Adrian Dumitrescu, Minghui Jiang

Journal:

Theory of Computing Systems

Year:

2012

Language:

english

File:

PDF, 586 KB

english, 2012

4

Representing Hyper-arithmetical Sets by Equations over Sets of Integers

Artur Jeż, Alexander Okhotin

Journal:

Theory of Computing Systems

Year:

2012

Language:

english

File:

PDF, 1003 KB

english, 2012

5

On Optimal Heuristic Randomized Semidecision Procedures, with Applications to Proof Complexity and Cryptography

Edward A. Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal

Journal:

Theory of Computing Systems

Year:

2012

Language:

english

File:

PDF, 546 KB

english, 2012

6

Collapsing and Separating Completeness Notions Under Average-Case and Worst-Case Hypotheses

Xiaoyang Gu, John M. Hitchcock, A. Pavan

Journal:

Theory of Computing Systems

Year:

2012

Language:

english

File:

PDF, 595 KB

english, 2012

7

Theoretical Aspects of Computer Science

Jean-Yves Marion, Thomas Schwentick

Journal:

Theory of Computing Systems

Year:

2012

Language:

english

File:

PDF, 132 KB

english, 2012