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 and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.