A fundamental question in computational complexity asks whether probabilistic polynomial-time algorithms can be simulated deterministically with a small overhead in time (the BPP vs. P problem). A corresponding question in the realm of interactive proofs asks whether Arthur-Merlin protocols can be simulated nondeterministically with a small overhead in time (the ... more >>>

We propose a new family of circuit-based sampling tasks, such that non-trivial algorithmic solutions to certain tasks from this family imply frontier uniform lower bounds such as ``NP is not in uniform ACC^0" and ``NP does not have uniform polynomial-size depth-two threshold circuits". Indeed, the most general versions of our ... more >>>

We prove that a $O(k \log k)$-probe local algorithm for $k$-Missing String presented by Vyas and Williams is asymptotically optimal among a certain class of algorithms for this problem. The best lower bound we are aware of for the general case is still $\Omega(k)$.

more >>>