
PreviousNext
It is well-known that if $\mathrm{P} = \mathrm{NP}$, then the seemingly larger class $\mathrm{PH}$ also collapses to $\mathrm{P}$; hence, we may base the hardness of $\mathrm{NP}$ on that of $\mathrm{PH}$, despite the widespread belief that $\mathrm{PH} \not\subseteq \mathrm{NP}$. Although well established in the decision problem setting, few such “conditional collapse ... more >>>
Rossman, Servedio, and Tan proved that the polynomial hierarchy is infinite relative to a random oracle. This paper strengthens this celebrated result by considering strong separations, witnessed by immune languages.
The main result of the paper shows that with respect to a random oracle the levels of the polynomial ... more >>>
Given a finite field $\mathbb F_q$, we say that a set $A\subseteq \mathbb F^n_q$ is an $(r,c)$ subspace evasive set if and only if for any affine subspace $U\subseteq \mathbb F^n_q$ with bounded dimension $\dim(U)\leq r$, the intersection size $|A\cap U|$ is at most $c$. The probabilistic method shows the ... more >>>
PreviousNext