enter search term and/or author name
A general framework for parameterized proof complexity was introduced by Dantchev et al. . 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
Article No.: 8
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...