Various gapped maximization problems are known not to be $\mathbf{NP}$-hard under $\mathbf{AC}^0$ reductions, e.g., $\mathsf{Gap}_{1,\epsilon}\text{-}\mathsf{Max3SAT}$ (see, e.g., Proposition 4 of Allender-Ilango-Vafa'21; the analogous result for $\mathsf{MaxClique}$ is attributed to earlier unpublished work by Arora).

The usual argument for showing that, say, $\mathsf{Max\text{-}3SAT}$ requires large $\mathbf{AC}^0$ circuits is to $\mathbf{AC}^0$-reduce from $\mathsf{Parity}$, but for these gapped problems, the $\mathbf{AC}^0$ reduction from $\mathsf{Parity}$ is precisely what fails. My question is, can $\mathbf{AC}^0$ lower bounds for these problems (e.g. for $\mathsf{Gap}_{1,\epsilon}\text{-}\mathsf{Max3SAT}$, to make it concrete) be recovered in some other way?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.