In this work we observe a tight connection between three topics: $\mathrm{NC}^{0}$ cryptography, $\mathrm{NC}^{0}$ range avoidance, and static data structure lower bounds. Using this connection, we leverage techniques from the cryptanalysis of $\mathrm{NC}^{0}$ PRGs to prove state-of-the-art results in the latter two subjects. Our main result is an improvement to the best known static data structure lower bounds, breaking a barrier which has stood for several decades. Prior to our work, the best known lower bound for any explicit problem with M inputs and N queries was $S \geq N^{\frac{1}{t}}(\log M)^{1-\frac{1}{t}}$ for any setting of the word length w (where $S=$ space and $t=$ time) [1]. We prove, for the same class of explicit problems considered in [1], a quadratically stronger space lower bound of the form $S \geq \tilde{\Omega}\left(N^{\frac{2}{t}} \cdot(\log M)^{1-\frac{2}{t}} \cdot 2^{-O(w)}\right)$ for all even $t\gt0$. Second, for the restricted class of nonadaptive bit probe data structures, we improve on this lower bound polynomially: for all odd constants $t\gt1$ we give an explicit problem with N queries and $M \leq N^{O(1)}$ inputs and prove a lower bound $S \geq \Omega\left(N^{\frac{2}{t}+\epsilon_{t}}\right)$ for some constant $\epsilon_{t}\gt0$ depending only on t. Our results build off of an exciting body of work on refuting semi-random CSPs (e.g., [2]–[4]). We then utilize our explicit cell probe lower bounds to obtain the best known unconditional algorithms for $\mathrm{NC}^{0}$ range avoidance: we can solve any instance with stretch $n \mapsto m$ in polynomial time once $m \gg n^{\frac{t}{2}}$ when t is even; with the aid of an NP oracle we can solve any instance with $m\gt n^{\frac{t}{2}-\epsilon}$ when t is odd for some constant $\epsilon\gt 0$. Finally, using our main correspondence we establish some barrier results for obtaining significant improvements to our cell probe lower bounds: (i) near-optimal space lower bounds for an explicit problem with $t=4, w=1$ implies $\mathrm{EXP}^{\mathrm{NP}} \nsubseteq \mathrm{NC}^{1}$; (ii) under the widelybelieved assumption that polynomial-stretch $\mathrm{NC}^{0}$ PRGs exist, there is no natural proof of a lower bound of the form $S \geq N^{\Omega(1)}$ when $t=\omega(1), w=1$.

In a pair of recent breakthroughs [1], [2] it was shown that the classes$\mathrm{S}_{2}^{\mathrm{E}}, \mathsf{ZPE}^{\mathsf{NP}}$and$\Sigma_{2}^{\mathrm{E}}$require exponential circuit complexity, giving the first unconditional improvements to a classical result of Kannan [3]. These results were obtained by designing a surprising new algorithm for the total search problem Range Avoidance: given a circuit$C:\{0,1\}^{n}\rightarrow\{0,1\}^{n+1}$, find an$n+1$-bit strina outside its range. Range Avoidance is a member of the class Tf$\Sigma_{2}^{\dot{\mathrm{F}}}$of total search problems in the second level of the polynomial hierarchy, analogous to its better-known counterpart TFNP in the first level. TF$\Sigma_{2}^{\overline{\mathrm{F}}}$was only recently introduced in [4] and its structure is not well understood. We investigate here the extent to which algorithms of the kind in [1], [2] can be applied to other search problems in this class, and prove a variety of results both positive and negative. On the positive side we show that Li's Range Avoidance algorithm [2] can be improved to give a reduction from Range Avoidance to a natural total search problem we call the Linear Ordering Principle or “LOP”: given a circuit$\prec:\{0,1\}^{n}\times\{0,1\}^{n}\rightarrow\{0,1\}$purportedly defining a total order on$\{0,1\}^{n}$, find either a witness that$\prec$is not a total order or else a minimal element in the ordering. The problem LOP is quite interesting in its own right, as it defines a natural syntactic subclass ”$\mathrm{L}_{2}^{\mathrm{P}}$“ of$\mathrm{s}_{2}^{\mathrm{p}}$which nonetheless maintains most of the interesting properties of$\mathsf{S}_{2}^{\mathrm{P}}$; in particular we show that$\mathrm{L}_{2}^{\mathrm{P}}$contains MA and that its exponential analogue$\mathrm{L}_{2}^{\mathrm{E}}$requires$2^{n}/n$size circuits. Both of these are consequences of our reduction from Range Avoidance to LOP. On the negative side we prove that the algorithms developed in [1], [2] cannot be extended to Strong Range Avoidance, a problem considered in the same paper which first introduced Range Avoidance [4]. In this problem we are given a circuit$C$:$\{0,1\}^{n}\backslash \{0^{n}\}\rightarrow\{0,1\}^{n}$, and once again seek a point outside its range. We give a separation in the decision tree (oracle) model showing that this problem cannot be solved in FP$\Sigma_{2}^{\mathrm{P}}\Vert$, which in particular rules out all of the new kinds of algorithms considered in [1], [2]. This black box separation is derived from a novel depth 3 AC°circuit lower bound for a total search problem, which we believe is of independent interest from the perspective of circuit complexity: we show that unlike previous depth 3 lower bounds, ours cannot be proven by reduction from a decision problem, and thus requires new techniques specifically tailored to total search problems. Proving lower bounds of this kind was recently proposed by Vyas and Williams in the context of the original (Weak) Avoid problem [5].

Motivated by applications in gerrymandering detection, we study a reconfiguration problem on connected partitions of a connected graph G. A partition of V(G) is connected if every part induces a connected subgraph. In many applications, it is desirable to obtain parts of roughly the same size, possibly with some slack s. A Balanced Connected k-Partition with slack s, denoted (k,s)-BCP, is a partition of V(G) into k nonempty subsets, of sizes n1,…,nk with |ni−n/k|≤s, each of which induces a connected subgraph (when s=0, the k parts are perfectly balanced, and we call it k-BCP for short). A recombination is an operation that takes a (k,s)-BCP of a graph G and produces another by merging two adjacent subgraphs and repartitioning them. Given two k-BCPs, A and B, of G and a slack s≥0, we wish to determine whether there exists a sequence of recombinations that transform A into B via (k,s)-BCPs. We obtain four results related to this problem: (1) When s is unbounded, the transformation is always possible using at most 6(k−1) recombinations. (2) If G is Hamiltonian, the transformation is possible using O(kn) recombinations for any s≥n/k, (3) there exist negative instances for s≤n/(3k), and (4) we show that determining whether a sequence of recombination that connects two (k,s)-BCP of a graph G exists is PSPACE-complete when k∈O(nε) and s∈O(n1−ε), for any constant 0<ε≤1. This statement holds even for restricted settings such as when G is an edge-maximal planar graph or when k≥3 and G is planar.

We give both efficient algorithms and hardness results for reconfiguring between two connected configurations of modules in the hexagonal grid. The reconfiguration moves that we consider are "pivots", where a hexagonal module rotates around a vertex shared with another module. Following prior work on modular robots, we define two natural sets of hexagon pivoting moves of increasing power: restricted and monkey moves. When we allow both moves, we present the first universal reconfiguration algorithm, which transforms between any two connected configurations using O(n³) monkey moves. This result strongly contrasts the analogous problem for squares, where there are rigid examples that do not have a single pivoting move preserving connectivity. On the other hand, if we only allow restricted moves, we prove that the reconfiguration problem becomes PSPACE-complete. Moreover, we show that, in contrast to hexagons, the reconfiguration problem for pivoting squares is PSPACE-complete regardless of the set of pivoting moves allowed. In the process, we strengthen the reduction framework of Demaine et al. [FUN'18] that we consider of independent interest.

We investigate the complexity of explicit construction problems, where the goal is to produce a particular object possessing some pseudorandom property in time polynomial in the size of that object. We give overwhelming evidence that APEPP, defined originally by Kleinberg et al. [12], is the natural complexity class associated with explicit constructions of objects whose existence follows from the probabilistic method, by placing a variety of such construction problems in this class. We then demonstrate that a result of Jeřábek [10] on provability in Bounded Arithmetic, when reinterpreted as a reduction between search problems, shows that constructing a truth table of high circuit complexity is complete for APEPP under NP-oracle reductions. This illustrates that Shannon's classical proof of the existence of hard boolean functions is in fact a universal probabilistic existence argument: deran-domizing his proof implies a generic derandomization of the probabilistic method. As a corollary, we prove that EXPNPcontains a language of mildly-exponential circuit complexity if and only if it contains a language of nearly maximum circuit complexity. Finally, for several of the problems shown to lie in APEPP, we demonstrate direct polynomial time reductions to the explicit construction of hard truth tables.

We identify several genres of search problems beyond NP for which existence of solutions is guaranteed. One class that seems especially rich in such problems is PEPP (for "polynomial empty pigeonhole principle"), which includes problems related to existence theorems proved through the union bound, such as finding a bit string that is far from all codewords, finding an explicit rigid matrix, as well as a problem we call Complexity, capturing Complexity Theory’s quest. When the union bound is generous, in that solutions constitute at least a polynomial fraction of the domain, we have a family of seemingly weaker classes α-PEPP, which are inside FP^NP|poly. Higher in the hierarchy, we identify the constructive version of the Sauer-Shelah lemma and the appropriate generalization of PPP that contains it, as well as the problem of finding a king in a tournament (a vertex k such that all other vertices are defeated by k, or by somebody k defeated).