Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT), Volume 4 Issue 3, September 2012

Parameterized Bounded-Depth Frege Is not Optimal
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov
Article No.: 7
DOI: 10.1145/2355580.2355582

A general framework for parameterized proof complexity was introduced by Dantchev et al. [2007]. There, the authors show important results on tree-like Parameterized Resolution---a parameterized version of classical Resolution---and their gap...

Relativized Worlds without Worst-Case to Average-Case Reductions for NP
Thomas Watson
Article No.: 8
DOI: 10.1145/2355580.2355583

We prove that, relative to an oracle, there is no worst-case to average-case reduction for NP. We also handle classes that are somewhat larger than NP, as well as worst-case to errorless-average-case reductions. In fact, we prove that...