A problem \(\mathcal{P}\) is considered downward self-reducible, if there exists an efficient algorithm for \(\mathcal{P}\) that is allowed to make queries to only strictly smaller instances of \(\mathcal{P}\). Downward self-reducibility has been well studied in the case of decision problems, and it is well known that any downward self-reducible problem must lie in \(\mathsf{PSPACE}\). Harsha, Mitropolsky and Rosen~[ITCS 2023] initiated the study of downward self reductions in the case of search problems. They showed the following interesting collapse: if a problem is in \(\mathsf{TFNP}\) and is downward self-reducible, then it must be in \(\mathsf{PLS}\). Moreover, if the problem admits a unique solution then it must be in \(\mathsf{UEOPL}\).

Range avoidance (Avoid) is the computational problem in which the input is an expanding circuit C : {0,1}n → {0,1}n+1 and the goal is to find a string y ∈ {0,1}n+1 that is not in the image of C. Avoid was introduced recently by Kleinberg, Korten, Mitropolsky, and Papadimitriou [ITCS 2021] as an example of a total search problem that appears not to live in TFNP but does live in the second level of the total function polynomial hierarchy. Since then, Avoid has found surprising applications throughout complexity theory, and in theoretical computer science more broadly.

We show that there is a language in \(\textsf{S}_2\textsf {E}\) (symmetric exponential time) that requires circuit complexity at least \(2^n/n\) on every input length. In particular, the above also implies the same near-maximum circuit lower bounds for \(\Sigma _2\textsf {E}\cap \Pi _2\textsf {E}\) and \(\mathsf {ZPE}^{\textsf {NP}}\) . Our proofs relativise. Previously, only “half-exponential” circuit lower bounds for the aforementioned complexity classes were known, and the smallest complexity class known to require exponential circuit complexity was \(\Delta _3\textsf {E}= \textsf {E}^{\Sigma _2\textsf{P}}\) (Miltersen, Vinodchandran, and Watanabe COCOON’99). Our circuit lower bounds are corollaries of an unconditional zero-error pseudodeterministic algorithm with an \(\textsf {NP}\) oracle that solves the Range Avoidance problem. This algorithm also implies unconditional pseudodeterministic \(\textsf {FZPP}^{\textsf {NP}}\) constructions for Ramsey graphs, rigid matrices, two-source extractors, linear codes, and \(\mathrm{K}^{\mathrm{poly}}\) -random strings with nearly optimal parameters.

In a recent breakthrough, Chen, Hirahara and Ren prove that S2E/1 ⊄SIZE[2n/n] by giving a single-valued FS2P algorithm for the Range Avoidance Problem (Avoid) that works for infinitely many input size n. Building on their work, we present a simple single-valued FS2P algorithm for Avoid that works for all input size n. As a result, we obtain the circuit lower bound S2E ⊄i.o.-SIZE[2n/n] and many other corollaries: 1. Almost-everywhere near-maximum circuit lower bound for Σ2E ∩ Π2E and ZPENP. 2. Pseudodeterministic FZPPNP constructions for combinatorial objects such as: Ramsey graphs, rigid matrices, pseudorandom generators, two-source extractors, linear codes, hard truth tables, and Kpoly-random strings.

In this paper, we present a low-diameter decomposition algorithm in the LOCAL model of distributed computing that succeeds with probability 1 − 1/poly(n). Specifically, we show how to compute an (ϵ, O((log n) / ϵ)) low-diameter decomposition in O((log3(1/ϵ) log n) / ϵ) rounds.

We study the complexity of lattice problems in a world where algorithms, reductions, and protocols can run in superpolynomial time. Specifically, we revisit four foundational results in this context—two protocols and two worst-case to average-case reductions. We show how to improve the approximation factor in each result by a factor of roughly √n/logn when running the protocol or reduction in 2є n time instead of polynomial time, and we show a novel protocol with no polynomial-time analog. Our results are as follows.

We show a number of reductions between the Shortest Vector Problem and the Closest Vector Problem over lattices in different ℓp norms (SVPp and CVPp respectively). Specifically, we present the following 2∊m-time reductions for 1 ≤ p ≤ q ≤ ∞, which all increase the rank n and dimension m of the input lattice by at most one: a reduction from Õ(1/∊1/p)γ-approximate SVPq to γ-approximate SVPp; a reduction from Õ(1/∊1/p)γ-approximate CVPp to γ-approximate CVPq; and a reduction from Õ(1/∊1+1/p)-CVPq to (1 + ∊)-unique SVPp (which in turn trivially reduces to (1 + ∊)-approximate SVPp). The last reduction is interesting even in the case p = q. In particular, this special case subsumes much prior work adapting 2O(m)-time SVPp algorithms to solve O(1)-approximate CVPp. In fact, we show a stronger result in the special case when 1 ≤ p = q ≤ 2 and the SVPp oracle is exact: a reduction from O(1/∊1/p)-CVPp to (exact) SVPp in 2∊m time. For example, taking ∊ = log m/m and p = 2 gives a slight improvement over Kannan's celebrated polynomial-time reduction from to SVP2. We also note that the last two reductions can be combined to give a reduction from approximate-CVPp to SVPq for any p and q, regardless of whether p ≤ q or p > q. Our techniques combine those from the recent breakthrough work of Eisenbrand and Venzin [21] (which showed how to adapt the current fastest known algorithm for these problems in the ℓ2 norm to all ℓp norms) together with sparsification-based techniques.