The algebrization barrier, proposed by Aaronson and Wigderson (STOC '08, ToCT '09), captures the limitations of many complexity-theoretic techniques based on arithmetization. Notably, several circuit lower bounds that overcome the relativization barrier (Buhrman-Fortnow-Thierauf, CCC '98; Vinodchandran, TCS '05; Santhanam, STOC '07, SICOMP '09) remain subject to the algebrization barrier. In this work, we establish several new algebrization barriers to circuit lower bounds by studying the communication complexity of the following problem, called XOR-Missing-String: For m < 2^{n/2}, Alice gets a list of m strings x₁, … , x_m ∈ {0, 1}ⁿ, Bob gets a list of m strings y₁, … , y_m ∈ {0, 1}ⁿ, and the goal is to output a string s ∈ {0, 1}ⁿ that is not equal to x_i⊕ y_j for any i, j ∈ [m]. 1) We construct an oracle A₁ and its multilinear extension A₁̃ such that PostBPE^{A₁̃} has linear-size A₁-oracle circuits on infinitely many input lengths. That is, proving PostBPE ̸ ⊆ i.o.- SIZE[O(n)] requires non-algebrizing techniques. This barrier follows from a PostBPP communication lower bound for XOR-Missing-String. This is in contrast to the well-known algebrizing lower bound MA_E (⊆ PostBPE) ̸ ⊆ P/_poly. 2) We construct an oracle A₂ and its multilinear extension A₂̃ such that BPE^{A₂̃} has linear-size A₂-oracle circuits on all input lengths. Previously, a similar barrier was demonstrated by Aaronson and Wigderson, but in their result, A₂̃ is only a multiquadratic extension of A₂. Our results show that communication complexity is more useful than previously thought for proving algebrization barriers, as Aaronson and Wigderson wrote that communication-based barriers were "more contrived". This serves as an example of how XOR-Missing-String forms new connections between communication lower bounds and algebrization barriers. 3) Finally, we study algebrization barriers to circuit lower bounds for MA_E. Buhrman, Fortnow, and Thierauf proved a sub-half-exponential circuit lower bound for MA_E via algebrizing techniques. Toward understanding whether the half-exponential bound can be improved, we define a natural subclass of MA_E that includes their hard MA_E language, and prove the following result: For every super-half-exponential function h(n), we construct an oracle A₃ and its multilinear extension A₃̃ such that this natural subclass of MA_E^{A₃̃} has h(n)-size A₃-oracle circuits on all input lengths. This suggests that half-exponential might be the correct barrier for MA_E circuit lower bounds w.r.t. algebrizing techniques.

We initiate a systematic study of TFZPP, the class of total NP search problems solvable by polynomial time randomized algorithms. TFZPP contains a variety of important search problems such as Bertrand-Chebyshev (finding a prime between N and 2N), refuter problems for many circuit lower bounds, and Lossy-Code. The Lossy-Code problem has found prominence due to its fundamental connections to derandomization, catalytic computing, and the metamathematics of complexity theory, among other areas. While TFZPP collapses to FP under standard derandomization assumptions in the white-box setting, we are able to separate TFZPP from the major TFNP subclasses in the black-box setting. In fact, we are able to separate it from every uniform TFNP class assuming that NP is not in quasi-polynomial time. To do so, we extend the connection between proof complexity and black-box TFNP to randomized proof systems and randomized reductions. Next, we turn to developing a taxonomy of TFZPP problems. We highlight a problem called Nephew, originating from an infinity axiom in set theory. We show that Nephew is in PWPP∩ TFZPP and conjecture that it is not reducible to Lossy-Code. Intriguingly, except for some artificial examples, most other black-box TFZPP problems that we are aware of reduce to Lossy-Code: - We define a problem called Empty-Child capturing finding a leaf in a rooted (binary) tree, and show that this problem is equivalent to Lossy-Code. We also show that a variant of Empty-Child with "heights" is complete for the intersection of SOPL and Lossy-Code. - We strengthen Lossy-Code with several combinatorial inequalities such as the AM-GM inequality. Somewhat surprisingly, we show the resulting new problems are still reducible to Lossy-Code. A technical highlight of this result is that they are proved by formalizations in bounded arithmetic, specifically in Jeřábek’s theory APC₁ (JSL 2007). - Finally, we show that the Dense-Linear-Ordering problem reduces to Lossy-Code.

Given a circuit G: {0, 1}ⁿ → {0, 1}^m with m > n, the range avoidance problem (Avoid) asks to output a string y ∈ {0, 1}^m that is not in the range of G. Besides its profound connection to circuit complexity and explicit construction problems, this problem is also related to the existence of proof complexity generators - circuits G: {0, 1}ⁿ → {0, 1}^m where m > n but for every y ∈ {0, 1}^m, it is infeasible to prove the statement "y ̸ ∈ Range(G)" in a given propositional proof system. This paper connects these two problems with the existence of demi-bits generators, a fundamental cryptographic primitive against nondeterministic adversaries introduced by Rudich (RANDOM '97). - We show that the existence of demi-bits generators implies Avoid is hard for nondeterministic algorithms. This resolves an open problem raised by Chen and Li (STOC '24). Furthermore, assuming the demi-hardness of certain LPN-style generators or Goldreich’s PRG, we prove the hardness of Avoid even when the instances are constant-degree polynomials over 𝔽₂. - We show that the dual weak pigeonhole principle is unprovable in Cook’s theory PV₁ under the existence of demi-bits generators secure against AM/_{O(1)}, thereby separating Jeřábek’s theory APC₁ from PV₁. Previously, Ilango, Li, and Williams (STOC '23) obtained the same separation under different (and arguably stronger) cryptographic assumptions. - We transform demi-bits generators to proof complexity generators that are pseudo-surjective in certain parameter regime. Pseudo-surjectivity is the strongest form of hardness considered in the literature for proof complexity generators. Our constructions are inspired by the recent breakthroughs on the hardness of Avoid by Ilango, Li, and Williams (STOC '23) and Chen and Li (STOC '24). We use randomness extractors to significantly simplify the construction and the proof.

Given two symbolic matrices X and Y of dimensions m × n and n × m, respectively, the rank principle states that when m = n+1 and A is a scalar matrix of rank n+1, the equation XY = A is unsatisfiable. When m is arbitrarily larger than n and A has rank exceeding n, we obtain the weak rank principle. We study this principle as an algebraic generalisation of the weak pigeonhole principle (WPHP), asserting that m pigeons cannot be injected into n holes, extending its counting argument to an algebraic setting. As a strengthening of WPHP, it admits proof complexity lower bounds in settings where none are known for WPHP, yet we show that these still yield applications analogous to those of WPHP. In particular, using new generalised types of random restrictions, which may be interesting by themselves, this allows us to resolve a number of open problems in proof complexity, including the construction of proof complexity generators for Polynomial Calculus Resolution over the two-element field (PCRF2), new generators for Sherali–Adams (SA), and hardness results for circuit lower bound statements against PCRF2, as detailed below.

We study the *refuter* problems for proof complexity lower bounds. Suppose ϕ is a hard tautology that does not admit any length-s proof in some proof system P. In the corresponding refuter problem, we are given (query access to) a purported length-s proof π in P that claims to have proved ϕ, and our goal is to find an invalid derivation step within π. As suggested by witnessing theorems in bounded arithmetic, the *computational complexity* of these refuter problems is closely tied to the *metamathematics* of the underlying lower bounds.

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.

A randomized algorithm for a search problem is pseudodeterministic if it produces a fixed canonical solution to the search problem with high probability. In their seminal work on the topic, Gat and Goldwasser [ 16 ] posed as their main open problem whether prime numbers can be pseudodeterministically constructed in polynomial time. We provide a positive solution to this question in the infinitely-often regime. In more detail, we give an unconditional polynomial-time randomized algorithm B such that, for infinitely many values of n , \(B(1^n)\) outputs a canonical n -bit prime \(p_n\) with high probability. More generally, we prove that for every dense property Q of strings that can be decided in polynomial time, there is an infinitely-often pseudodeterministic polynomial-time construction of strings satisfying Q . This improves upon a subexponential-time construction of Oliveira and Santhanam [ 49 ]. Our construction uses several new ideas, including a novel bootstrapping technique for pseudodeterministic constructions, and a quantitative optimization of the uniform hardness-randomness framework of Chen and Tell [ 11 ], using a variant of the Shaltiel–Umans generator [ 51 ].

Abstract. It is a longstanding open problem whether the Minimum Circuit Size Problem ([Formula: see text]) and related meta-complexity problems are [Formula: see text]-complete and hard to approximate. In this work, we prove NP-hardness of approximating meta-complexity with nearly optimal approximation gaps. Our key idea is to use cryptographic constructions in our reductions, where the security of the cryptographic construction implies the correctness of the reduction. We present three results that give both conditional and unconditional hardness of approximation. First, assuming subexponentially-secure witness encryption exists, we prove essentially optimal NP-hardness of approximating conditional time-bounded Kolmogorov complexity ([Formula: see text]) in the regime where [Formula: see text]. Second, we unconditionally show near-optimal NP-hardness of approximation for the minimum oracle circuit size problem where Yes instances have circuit complexity at most [Formula: see text], and No instances are essentially as hard as random truth tables. Finally, we define a “multivalued” version of [Formula: see text], called [Formula: see text], and show that with probability 1 over a random oracle [Formula: see text], [Formula: see text] is NP-hard to approximate under quasi-polynomial-time reductions with [Formula: see text] oracle access.

We introduce and study the following natural total search problem, which we call the heavy element avoidance (Heavy Avoid) problem: for a distribution on$N$bits specified by a Boolean circuit sampling it, and for some parameter$\delta(N)\geq 1/$poly$(N)$fixed in advance, output an$N$-bit string that has probability less than$\delta(N)$. We show that the complexity of Heavy Avoid is closely tied to frontier open questions in complexity theory about uniform randomized lower bounds and derandomization. Among other results, we show: 1)For a wide range of circuit classes$\mathcal{C}$, including$\text{ACC}^{0}, \text{TC}^{0},\text{NC}^{1}$and general Boolean circuits, EX P does not have uniform randomized C-circuits if and only if Heavy Avoid for uniform implicit C -samplers has efficient deterministic algorithms infinitely often. This gives the first algorithmic characterization of lower bounds for EXP against uniform randomized low-depth circuits. We show similar algorithmic characterizations for lower bounds in PSPACE, NP and$\text{EXP}^{\text{NP}}$. 2)Unconditionally, there are polynomial-time pseudodeterministic algorithms that work infinitely often for several variants of Heavy Avoid, such as for uniform samplers of small randomness complexity. In contrast, the existence of a similar algorithm that solves Heavy Avoid for arbitrary polynomial-time samplers would solve a long-standing problem about hierarchies for probabilistic time. 3)If there is a time and depth efficient deterministic algorithm for Heavy Avoid, then$BPP=P$. Without the depth-efficiency requirement in the assumption, we still obtain a non-trivial form of infinitely-often deterministic simulation of randomized algorithms. These results are shown using non-black-box reductions, and we argue that the use of non-black-box reductions is essential here. The full version is available on ECCC [1].

We show that there is a language in S2E/1 (symmetric exponential time with one bit of advice) with circuit complexity at least 2n/n. In particular, the above also implies the same near-maximum circuit lower bounds for the classes Σ2E, (Σ2E∩Π2E)/1, and ZPENP/1. Previously, only ”half-exponential” circuit lower bounds for these complexity classes were known, and the smallest complexity class known to require exponential circuit complexity was Δ3E = EΣ2P (Miltersen, Vinodchandran, and Watanabe COCOON’99).

A randomized algorithm for a search problem is pseudodeterministic if it produces a fixed canonical solution to the search problem with high probability. In their seminal work on the topic, Gat and Goldwasser [1] posed as their main open problem whether prime numbers can be pseudodeterministically constructed in polynomial time. We provide a positive solution to this question in the infinitely-often regime. In more detail, we give an unconditional polynomial-time randomized algorithm B such that, for infinitely many values of $n, B\left(1^{n}\right)$ outputs a canonical n-bit prime $p_{n}$ with high probability. More generally, we prove that for every dense property Q of strings that can be decided in polynomial time, there is an infinitely-often pseudodeterministic polynomial-time construction of strings satisfying Q. This improves upon a subexponential-time construction of Oliveira and Santhanam [2]. Our construction uses several new ideas, including a novel bootstrapping technique for pseudodeterministic constructions, and a quantitative optimization of the uniform hardness-randomness framework of Chen and Tell [3], using a variant of the Shaltiel-Umans generator [4].

The range avoidance problem, denoted as C-Avoid, asks to find a non-output of a given C-circuit C:0,1^n -> 0,1^l with stretch l>n. This problem has recently received much attention in complexity theory for its connections with circuit lower bounds and other explicit construction problems. Inspired by the Algorithmic Method for circuit lower bounds, Ren, Santhanam, and Wang (FOCS’22) established a framework to design FP^NP algorithms for C-Avoid via slightly non-trivial data structures related to C. However, a major drawback of their approach is the lack of unconditional results even for C=AC^0.

It is a long-standing open problem whether the Minimum Circuit Size Problem (MCSP) and related meta-complexity problems are NP-complete. Even for the rare cases where the NP-hardness of meta-complexity problems are known, we only know very weak hardness of approximation.

We consider the range avoidance problem (called Avoid): given the description of a circuit with more output gates than input gates, find a string that is not in the range of the circuit. This problem is complete for the class APEPP that corresponds to explicit constructions of objects whose existence follows from the probabilistic method (Korten, FOCS 2021). Motivated by applications in explicit constructions and complexity theory, we initiate the study of the range avoidance problem for weak circuit classes, and obtain the following results: 1)Generalising Williams’s connections between circuitanalysis algorithms and circuit lower bounds (J. ACM 2014), we present a framework for solving $\mathscr{C}$-Avoid in FPNPusing circuit-analysis data structures for $\mathscr{C}$, for “typical” multi-output circuit classes $\mathscr{C}$. As an application, we present a non-trivial FPNPrange avoidance algorithm for De Morgan formulas./inlp>An important technical ingredient is a construction of rectangular PCPs of proximity, building on the rectangular PCPs by Bhangale, Harsha, Paradise, and Tal (FOCS 2020).2)Using the above framework, we show that circuit lower bounds for ENPare equivalent to circuit-analysis algorithms with ENPpreprocessing. This is the first equivalence result regarding circuit lower bounds for ENP. Our equivalences have the additional advantages that they work in both infinitely-often and almost-everywhere settings, and that they also hold for larger (e.g., subexponential) size bounds.3)Complementing the above results, we show that in some settings, solving $\mathscr{C}$-Avoid would imply breakthrough lower bounds, even for very weak circuit classes $\mathscr{C}$. In particular, an algorithm for AC0-Avoid with polynomial stretch implies lower bounds against NC1, and an algorithm for $NC_{4}^{0}$-Avoid with very small stretch implies lower bounds against NC1and branching programs.4)We show that Avoid is in FNP if and only if there is a propositional proof system that breaks every non-uniform proof complexity generator. This result connects the study of range avoidance with fundamental questions in proof complexity.

Meta-complexity studies the complexity of computational problems about complexity theory, such as the Minimum Circuit Size Problem (MCSP) and its variants. We show that a relativization barrier applies to many important open questions in meta-complexity. We give relativized worlds where: 1) MCSP can be solved in deterministic polynomial time, but the search version of MCSP cannot be solved in deterministic polynomial time, even approximately. In contrast, Carmosino, Impagliazzo, Kabanets, Kolokolova [CCC'16] gave a randomized approximate search-to-decision reduction for MCSP with a relativizing proof. 2) The complexities of MCSP[2^{n/2}] and MCSP[2^{n/4}] are different, in both worst-case and average-case settings. Thus the complexity of MCSP is not "robust" to the choice of the size function. 3) Levin’s time-bounded Kolmogorov complexity Kt(x) can be approximated to a factor (2+ε) in polynomial time, for any ε > 0. 4) Natural proofs do not exist, and neither do auxiliary-input one-way functions. In contrast, Santhanam [ITCS'20] gave a relativizing proof that the non-existence of natural proofs implies the existence of one-way functions under a conjecture about optimal hitting sets. 5) DistNP does not reduce to GapMINKT by a family of "robust" reductions. This presents a technical barrier for solving a question of Hirahara [FOCS'20].

We present the first compact distance oracle that tolerates multiple failures and maintains *exact* distances. Given an undirected weighted graph G = (V, E) and an arbitrarily large constant d, we construct an oracle that given vertices u, v ∈ V and a set of d edge failures D, outputs the *exact* distance between u and v in G − D (that is, G with edges in D removed). Our oracle has space complexity O(d n4) and query time dO(d). Previously, there were compact *approximate* distance oracles under multiple failures [Chechik, Cohen, Fiat, and Kaplan, SODA’17; Duan, Gu, and Ren, SODA’21], but the best exact distance oracles under d failures require essentially Ω(nd) space [Duan and Pettie, SODA’09]. Our distance oracle seems to require nΩ(d) time to preprocess; we leave it as an open question to improve this preprocessing time.

We show broad equivalences in the average-case complexity of many different meta-complexity problems, including Kolmogorov complexity, time-bounded Kolmogorov complexity, and the Minimum Circuit Size Problem. These results hold for a wide range of parameters (various thresholds, approximation gaps, weak or strong average-case hardness, etc.) and complexity notions, showing the theory of meta-complexity is very *robust* in the average-case setting.

In a recent breakthrough, [C. Murray and R. R. Williams, STOC 2018, ACM, New York, 2018, pp. 890--901] proved that ${NQP} = {NTIME}[n^{{polylog}(n)}]$ cannot be computed by polynomial-size ${ACC}^0$ circuits (constant-depth circuits consisting of ${AND}$/${OR}$/${MOD}_m$ gates for a fixed constant $m$, a frontier class in circuit complexity). This was recently strengthened by [L. Chen, FOCS 2019, IEEE, Piscataway, NJ, 2019, pp. 1281--1304] to that ${NQP}$ cannot be $(1/2+1/{polylog}(n))$-approximated by polynomial-size ${ACC}^0$ circuits. In this work we will prove that ${NQP}$ cannot be $(1/2+1/n^{\omega(1)})$-approximated by polynomial-size ${ACC}^0$ circuits. As a straightforward application, we obtain an infinitely often nondeterministic pseudorandom generator for polysize ${ACC}^0$ circuits with sub-polynomial seed length. More generally, we establish a connection showing that, for a typical circuit class $\mathscr{C}$, nontrivial deterministic algorithms estimating the acceptance probability of $\mathscr{C}$ circuits imply strong ($1/2 + 1/n^{\omega(1)}$) average-case lower bounds against $\mathscr{C}$ circuits. We also apply this connection to prove new lower bounds against several subclasses of ${\sf TC}^0$ circuits (constant-depth circuits consisting entirely of majority gates), and show that nontrivial derandomization of ${MAJ} \circ {MAJ}$ would imply worst-case lower bounds for ${TC}^0_3$ (${MAJ} \circ{MAJ} \circ {MAJ}$), suggesting that ${TC}^0_3$ lower bounds are probably within reach. Our two new important technical ingredients are (1) techniques from cryptography in ${NC}^0$ [B. Applebaum, Y. Ishai, and E. Kushilevitz, SIAM J. Comput., 36 (2006), pp. 845--888], and (2) probabilistic checkable proofs of proximity with ${NC}^1$-computable proofs.

A recent breakthrough of Liu and Pass (FOCS'20) shows that one-way functions exist if and only if the (polynomial-)time-bounded Kolmogorov complexity, K^t, is bounded-error hard on average to compute. In this paper, we strengthen this result and extend it to other complexity measures: - We show, perhaps surprisingly, that the KT complexity is bounded-error average-case hard if and only if there exist one-way functions in constant parallel time (i.e. NC⁰). This result crucially relies on the idea of randomized encodings. Previously, a seminal work of Applebaum, Ishai, and Kushilevitz (FOCS'04; SICOMP'06) used the same idea to show that NC⁰-computable one-way functions exist if and only if logspace-computable one-way functions exist. - Inspired by the above result, we present randomized average-case reductions among the NC¹-versions and logspace-versions of K^t complexity, and the KT complexity. Our reductions preserve both bounded-error average-case hardness and zero-error average-case hardness. To the best of our knowledge, this is the first reduction between the KT complexity and a variant of K^t complexity. - We prove tight connections between the hardness of K^t complexity and the hardness of (the hardest) one-way functions. In analogy with the Exponential-Time Hypothesis and its variants, we define and motivate the Perebor Hypotheses for complexity measures such as K^t and KT. We show that a Strong Perebor Hypothesis for K^t implies the existence of (weak) one-way functions of near-optimal hardness 2^{n-o(n)}. To the best of our knowledge, this is the first construction of one-way functions of near-optimal hardness based on a natural complexity assumption about a search problem. - We show that a Weak Perebor Hypothesis for MCSP implies the existence of one-way functions, and establish a partial converse. This is the first unconditional construction of one-way functions from the hardness of MCSP over a natural distribution. - Finally, we study the average-case hardness of MKtP. We show that it characterizes cryptographic pseudorandomness in one natural regime of parameters, and complexity-theoretic pseudorandomness in another natural regime.

We continue the study of distance sensitivity oracles (DSOs). Given a directed graph $G$ with $n$ vertices and edge weights in $\{1, 2, \dots, M\}$, we want to build a data structure such that given any source vertex $u$, any target vertex $v$, and any failure $f$ (which is either a vertex or an edge), it outputs the length of the shortest path from $u$ to $v$ not going through $f$. Our main result is a DSO with preprocessing time $O(n^{2.5794}M)$ and constant query time. Previously, the best preprocessing time of DSOs for directed graphs is $O(n^{2.7233}M)$, and even in the easier case of undirected graphs, the best preprocessing time is $O(n^{2.6865}M)$ [Ren, ESA 2020]. One drawback of our DSOs, though, is that it only supports distance queries but not path queries. Our main technical ingredient is an algorithm that computes the inverse of a degree-$d$ polynomial matrix (i.e. a matrix whose entries are degree-$d$ univariate polynomials) modulo $x^r$. The algorithm is adapted from [Zhou, Labahn, and Storjohann, Journal of Complexity, 2015], and we replace some of its intermediate steps with faster rectangular matrix multiplication algorithms. We also show how to compute unique shortest paths in a directed graph with edge weights in $\{1, 2, \dots, M\}$, in $O(n^{2.5286}M)$ time. This algorithm is crucial in the preprocessing algorithm of our DSO. Our solution improves the $O(n^{2.6865}M)$ time bound in [Ren, ESA 2020], and matches the current best time bound for computing all-pairs shortest paths.

Given an undirected graph G = (V, E) of n vertices and m edges with weights in [1, W], we construct vertex sensitive distance oracles (VSDO), which are data structures that preprocess the graph, and answer the following kind of queries: Given a source vertex u, a target vertex v, and a batch of d failed vertices D, output (an approximation of) the distance between u and v in G – D (that is, the graph G with vertices in D removed). An oracle has stretch α if it always holds that , where δG–D(u, v) is the actual distance between u and v in G – D, and is the distance reported by the oracle. In this paper we construct efficient VSDOs for any number d of failures. For any constant c ≥ 1, we propose two oracles: The first oracle has size n2+1/c(log n/∊)O(d) · log W, answers a query in poly(log n, dc, log log W, ∊–1) time, and has stretch 1 + ∊, for any constant ∊ > 0. The second oracle has size n2+1/cpoly (log(nW), d), answers a query in poly (log n, dc, log log W) time, and has stretch poly (log n, d). Both of these oracles can be preprocessed in time polynomial in their space complexity. These results are the first approximate distance oracles of poly-logarithmic query time for any constant number of vertex failures in general undirected graphs. Previously there are (1 + ∊)-approximate d-edge sensitive distance oracles [Chechik et al. 2017] answering distance queries when d edges fail, which have size O(n2(log n/∊)d · d log W) and query time poly (log n, d, log log W).

We consider the problem of building Distance Sensitivity Oracles (DSOs). Given a directed graph $G=(V, E)$ with edge weights in $\{1, 2, \dots, M\}$, we need to preprocess it into a data structure, and answer the following queries: given vertices $u,v\in V$ and a failed vertex or edge $f\in (V\cup E)$, output the length of the shortest path from $u$ to $v$ that does not go through $f$. Our main result is a simple DSO with $\tilde{O}(n^{2.7233}M)$ preprocessing time and $O(1)$ query time. Moreover, if the input graph is undirected, the preprocessing time can be improved to $\tilde{O}(n^{2.6865}M)$. The preprocessing algorithm is randomized with correct probability $\ge 1-1/n^C$, for a constant $C$ that can be made arbitrarily large. Previously, there is a DSO with $\tilde{O}(n^{2.8729}M)$ preprocessing time and $\operatorname{polylog}(n)$ query time [Chechik and Cohen, STOC'20]. At the core of our DSO is the following observation from [Bernstein and Karger, STOC'09]: if there is a DSO with preprocessing time $P$ and query time $Q$, then we can construct a DSO with preprocessing time $P+\tilde{O}(n^2)\cdot Q$ and query time $O(1)$. (Here $\tilde{O}(\cdot)$ hides $\operatorname{polylog}(n)$ factors.)

We prove that for all constants a, NQP = NTIME[n polylog(n)] cannot be (1/2 + 2−log a n )-approximated by 2log a n -size ACC 0 ∘ THR circuits ( ACC 0 circuits with a bottom layer of THR gates). Previously, it was even open whether E NP can be (1/2+1/√n)-approximated by AC 0[⊕] circuits. As a straightforward application, we obtain an infinitely often ( NE ∩ coNE)/1-computable pseudorandom generator for poly-size ACC 0 circuits with seed length 2logє n , for all є > 0.

In the bounded-leg shortest path (BLSP) problem, we are given a weighted graph G with nonnegative edge lengths, and we want to answer queries of the form "what's the shortest path from u to v, where only edges of length <=L are considered?". A more general problem is the APSP-AF (all-pair shortest path for all flows) problem, in which each edge has two weights - a length d and a capacity f, and a query asks about the shortest path from u to v where only edges of capacity >= f are considered. In this article we give an O~(n^{(omega+3)/2}epsilon^{-3/2}log W) time algorithm to compute a data structure that answers APSP-AF queries in O(log(epsilon^{-1}log (nW))) time and achieves (1+epsilon)-approximation, where omega < 2.373 is the exponent of time complexity of matrix multiplication, W is the upper bound of integer edge lengths, and n is the number of vertices. This is the first truly-subcubic time algorithm for these problems on dense graphs. Our algorithm utilizes the O(n^{(omega+3)/2}) time max-min product algorithm [Duan and Pettie 2009]. Since the all-pair bottleneck path (APBP) problem, which is equivalent to max-min product, can be seen as all-pair reachability for all flow, our approach indeed shows that these problems are almost equivalent in the approximation sense.