Richard Beigel

<html>

Prior results show that most bounded query hierarchies cannot

contain finite gaps. For example, it is known that

<center>

P<sub>(<i>m</i>+1)-tt</sub><sup>SAT</sup> = P<sub><i>m</i>-tt</sub><sup>SAT</sup> implies P<sub>btt</sub><sup>SAT</sup> = P<sub><i>m</i>-tt</sub><sup>SAT</sup>

</center>

and for all sets <i>A</i>

<ul>

<li> FP<sub>(<i>m</i>+1)-tt</sub><sup><i>A</i></sup> = FP<sub><i>m</i>-tt</sub><sup><i>A</i></sup> implies FP<sub>btt</sub><sup><i>A</i></sup> = FP<sub><i>m</i>-tt</sub><sup><i>A</i></sup>

</li>

<li> P<sub>(<i>m</i>+1)-T</sub><sup><i>A</i></sup> = P<sub><i>m</i>-T</sub><sup><i>A</i></sup> implies P<sub>bT</sub><sup><i>A</i></sup> = ...
more >>>

Till Tantau

A language is called k-membership comparable if there exists a

polynomial-time algorithm that excludes for any k words one of

the 2^k possibilities for their characteristic string.

It is known that all membership comparable languages can be

reduced to some P-selective language with polynomially many

adaptive queries. We show however ...
more >>>

Cristopher Moore, Alexander Russell

The proof of Toda's celebrated theorem that the polynomial hierarchy is contained in $\P^\numP$ relies on the fact that, under mild technical conditions on the complexity class $\mathcal{C}$, we have $\exists \,\mathcal{C} \subset \BP \cdot \oplus \,\mathcal{C}$. More concretely, there is a randomized reduction which transforms nonempty sets and the ... more >>>

Akinori Kawachi, Osamu Watanabe

Impagliazzo and Levin demonstrated [IL90] that the average-case hardness of any NP-search problem under any P-samplable distribution implies that of another NP-search problem under the uniform distribution. For this they developed a way to define a reduction from an NP-search problem F with ``mild hardness'' under any P-samplable distribution H; ... more >>>

Emanuele Viola

The 3SUM problem asks if there are three integers $a,b,c$ summing to $0$ in a given set of $n$ integers of magnitude poly($n$). Patrascu (STOC '10) reduces solving 3SUM in time $n^{2-\Omega(1)}$ to listing $m$ triangles in a graph with $m$ edges in time $m^{4/3-\Omega(1)}$.

In this note we present ...
more >>>

Hamidreza Jahanjou, Eric Miles, Emanuele Viola

We reduce non-deterministic time $T \ge 2^n$ to a 3SAT

instance $\phi$ of size $|\phi| = T \cdot \log^{O(1)} T$

such that there is an explicit circuit $C$ that on input

an index $i$ of $\log |\phi|$ bits outputs the $i$th

clause, and each output bit of $C$ depends on ...
more >>>

Vahid Reza Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar

We present a new framework for designing worst-case to average-case reductions. For a large class of problems, it provides an explicit transformation of algorithms running in time $T$ that are only correct on a small (subconstant) fraction of their inputs into algorithms running in time $\widetilde{O}(T)$ that are correct on ... more >>>