Arrow Research search

Author name cluster

R. Ryan Williams

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

53 papers
1 author row

Possible papers

53

STOC Conference 2025 Conference Paper

Simulating Time with Square-Root Space

  • R. Ryan Williams

We show that for all functions t ( n ) ≥ n , every multitape Turing machine running in time t can be simulated in space only O (√ t log t ). This is a substantial improvement over Hopcroft, Paul, and Valiant’s simulation of time t in O ( t /log t ) space from 50 years ago [FOCS 1975, JACM 1977]. Among other results, our simulation implies that bounded fan-in circuits of size s can be evaluated on any input in only √ s · poly (log s ) space, and that there are explicit problems solvable in O ( n ) space which require at least n 2−ε time on every multitape Turing machine for all ε > 0, thereby making a little progress on the P versus PSPACE problem. Our simulation reduces the problem of simulating time-bounded multitape Turing machines to a series of implicitly-defined Tree Evaluation instances with nice parameters, leveraging the remarkable space-efficient algorithm for Tree Evaluation recently found by Cook and Mertz [STOC 2024].

Details

STOC Conference 2025 Conference Paper

When Connectivity Is Hard, Random Walks Are Easy with Non-determinism

  • Dean Doron
  • Edward Pyne
  • Roei Tell
  • R. Ryan Williams

Two fundamental problems on directed graphs are to decide s - t connectivity, and to estimate the behavior of random walks. Currently, there is no known algorithm for s - t connectivity running in polynomial time and n o (1) space, and no known algorithm for estimating the n -step random walk matrix running in non-deterministic logspace. We show that for every directed graph, at least one of these problems is solvable in time and space that significantly improve on the respective state-of-the-art. In particular, there is a pair of algorithms A 1 and A 2 such that for every graph G , either: A 1 ( G ) outputs the transitive closure of G in polynomial time and polylogarithmic space. A 2 ( G ) outputs an approximation of the n -step random walk matrix of G in non-deterministic logspace. As one application, we show surprisingly tight win-win results for space-bounded complexity. For example, for certain parameter regimes, either Savitch’s theorem can be non-trivially sped up, or randomized space can be almost completely derandomized. We also apply our techniques to significantly weaken the assumptions required to derandomize space-bounded computation, and to make non-deterministic space-bounded computation unambiguous. Specifically, we deduce such conclusions from lower bounds against uniform circuits of polynomial size, which is an exponential improvement on the required hardness in previous works (Doron–Pyne–Tell STOC 2024, Li–Pyne–Tell FOCS 2024). We further show similar results for minimal-memory derandomization (Doron–Tell CCC 2024). To prove these results, we substantially improve the array of technical tools introduced in recent years for studying hardness-vs.-randomness for bounded-space computation. In particular, we develop derandomized distinguish-to-predict transformations for new types of distinguishers (corresponding to compositions of PRGs with weak distinguishers), we construct a derandomized logspace reconstruction procedure for the Shaltiel–Umans generator (JACM 2005) that can compress hard truth-tables to polylogarithmic size, and we design a version of the Chen–Tell generator (FOCS 2021) that is particularly suitable for the space-bounded setting.

Details

FOCS Conference 2024 Conference Paper

The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds

  • R. Ryan Williams

A line of work has shown how nontrivial uniform algorithms for analyzing circuits can be used to derive non-uniform circuit lower bounds. We show how the non-existence of nontrivial circuit-analysis algorithms can also imply non-uniform circuit lower bounds. Our connections yield new win-win circuit lower bounds, and suggest a potential approach to refuting the Orthogonal Vectors Conjecture in the $O(\log n)$ -dimensional case, which would be sufficient for refuting the Strong Exponential Time Hypothesis (SETH). For example, we show that at least one of the following holds: • There is an $\varepsilon>0$ such that for infinitely many $n$, read-once 2-DNFs on $n$ variables cannot be simulated by non-uniform $2^{\varepsilon n}$ -size depth-two exact threshold circuits. It is already a notorious open problem to prove that the class $E^{N P}$ does not have polynomial-size depth-two exact threshold circuits, so such a lower bound would be a significant advance in low-depth circuit complexity. In fact, a stronger lower bound holds in this case: the $2^n \times 2^n$ Disjointness Matrix (well-studied in communication complexity) cannot be expressed by a linear combination of $2^{o(n)}$ structured matrices that we call “equality matrices”. • For every $c \geq 1$ and every $\varepsilon>0$, Orthogonal Vectors on $n$ vectors in $c \log n$ dimensions can be solved in $n^{1+\varepsilon}$ uniform deterministic time. This case would provide a strong refutation of the Orthogonal Vectors conjecture, and of SETH: for example, CNF-SAT on $n$ variables and $O(n)$ clauses could be solved in $2^{n / 2+o(n)}$ time. Moreover, this case would imply non-uniform circuit lower bounds for the class $E^{NP}$, against Valiant series-parallel circuits. Inspired by this connection, we give evidence from SAT/SMT solvers that the first item (in particular, the Disjointness lower bound) may be false in its full generality. In particular, we present a systematic approach to solving Orthogonal Vectors via constant-sized decompositions of the Disjointness Matrix, which already yields interesting new algorithms. For example, using a linear combination of 6 equality matrices that express $2^6 \times 2^6$ Disjointness, we derive an $\tilde{O}\left(n \cdot 6^{d / 6}\right) \leq \tilde{O}\left(n \cdot 1. \dot{35^d}\right)$ time and $n \cdot \operatorname{poly}(\log n, d)$ space algorithm for Orthogonal Vectors on $n$ vectors in $d$ dimensions. We show similar results for counting pairs of orthogonal vectors.

Details

FOCS Conference 2023 Conference Paper

Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization

  • Lijie Chen 0001
  • Roei Tell
  • R. Ryan Williams

We establish an equivalence between two algorithmic tasks: derandomization, the deterministic simulation of probabilistic algorithms; and refutation, the deterministic construction of inputs on which a given probabilistic algorithm fails to compute a certain hard function. We prove that refuting low-space probabilistic streaming algorithms which attempt to compute functions $f \in \mathcal{F P}$ is equivalent to proving that $\operatorname{pr} \mathcal{B P} \mathcal{P}=\operatorname{pr} \mathcal{P}$, even in cases where a lower bound for f against such streaming algorithms (without a refuter) is already unconditionally known. We also demonstrate the generality of our connection between refutation and derandomization, by establishing connections between refuting classes of constant-depth circuits of sublinear size and derandomizing constant-depth circuits of polynomial size with threshold gates (i. e. , $\mathcal{T C}^{0}$). Our connection generalizes and strengthens recent work on the characterization of derandomization. In particular, the refuter framework allows to directly compare several recent works to each other and to our work, as well as to chart a path for further progress. Along the way, we also improve the targeted hitting-set generator of Chen and Tell (FOCS 2021), showing that its translation of hardness to pseudorandomness scales down to $\mathcal{T C}^{0}$.

Details

STOC Conference 2023 Conference Paper

Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic

  • Rahul Ilango
  • Jiatu Li
  • R. Ryan Williams

The range avoidance problem (denoted by Avoid ) asks to find a string outside of the range of a given circuit C :{0,1} n →{0,1} m , where m > n . Although at least half of the strings of length m are correct answers, it is not clear how to deterministically find one. Recent results of Korten (FOCS’21) and Ren, Wang, and Santhanam (FOCS’ 22) show that efficient deterministic algorithms for Avoid would have far-reaching consequences, including strong circuit lower bounds and explicit constructions of combinatorial objects (e.g., Ramsey graphs, extractors, rigid matrices). This strongly motivates the question: does an efficient deterministic algorithm for Avoid actually exist? In this work, we prove under the existence of subexponentially secure indistinguishability obfuscation ( i O ) that polynomial-time deterministic algorithms for Avoid imply NP = coNP . Combining this with Jain, Lin, and Sahai’s recent breakthrough construction of i O from well-founded assumptions (STOC’21, EUROCRYPT’22), we provide the first plausible evidence that Avoid has no efficient deterministic algorithm. Moreover, we also prove the hardness of Avoid based on polynomially-secure i O and a weaker variant of the Nondeterministic Exponential Time Hypothesis (NETH). Extending our techniques, we prove a surprising separation in bounded arithmetic , conditioned on similar assumptions. Assuming subexponentially secure i O and coNP is not infinitely often in, we show that Avoid has no deterministic polynomial-time algorithm even when we are allowed O (1) queries to an oracle that can invert the given input circuit on an arbitrarily chosen m -bit string. It follows that the dual Weak Pigeonhole Principle , the combinatorial principle underlying Avoid , is not provable in Cook’s theory PV 1 . This gives (under plausible assumptions) the first separation of Cook’s theory PV 1 for polynomial-time reasoning and Jeřábek’s theory APV 1 for probabilistic polynomial-time reasoning.

Details

MFCS Conference 2022 Conference Paper

On the Number of Quantifiers as a Complexity Measure

  • Ronald Fagin
  • Jonathan Lenchner
  • Nikhil Vyas 0001
  • R. Ryan Williams

In 1981, Neil Immerman described a two-player game, which he called the "separability game" [Neil Immerman, 1981], that captures the number of quantifiers needed to describe a property in first-order logic. Immerman’s paper laid the groundwork for studying the number of quantifiers needed to express properties in first-order logic, but the game seemed to be too complicated to study, and the arguments of the paper almost exclusively used quantifier rank as a lower bound on the total number of quantifiers. However, last year Fagin, Lenchner, Regan and Vyas [Fagin et al. , 2021] rediscovered the game, provided some tools for analyzing them, and showed how to utilize them to characterize the number of quantifiers needed to express linear orders of different sizes. In this paper, we push forward in the study of number of quantifiers as a bona fide complexity measure by establishing several new results. First we carefully distinguish minimum number of quantifiers from the more usual descriptive complexity measures, minimum quantifier rank and minimum number of variables. Then, for each positive integer k, we give an explicit example of a property of finite structures (in particular, of finite graphs) that can be expressed with a sentence of quantifier rank k, but where the same property needs 2^Ω(k²) quantifiers to be expressed. We next give the precise number of quantifiers needed to distinguish two rooted trees of different depths. Finally, we give a new upper bound on the number of quantifiers needed to express s-t connectivity, improving the previous known bound by a constant factor.

Details

SODA Conference 2022 Conference Paper

Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions

  • Lijie Chen 0001
  • Ce Jin 0001
  • R. Ryan Williams
  • Hongxun Wu

We consider low-space algorithms for the classic Element Distinctness problem: given an array of n input integers with O (log n ) bit-length, decide whether or not all elements are pairwise distinct. Beame, Clifford, and Machmouchi [FOCS 2013] gave an Õ ( n 1. 5 )-time randomized algorithm for Element Distinctness using only O (log n ) bits of working space. However, their algorithm assumes a random oracle (in particular, read-only random access to polynomially many random bits), and it was asked as an open question whether this assumption can be removed. In this paper, we positively answer this question by giving an Õ ( n 1. 5 )-time randomized algorithm using O (log 3 n log log n ) bits of space, with one-way access to random bits. As a corollary, we also obtain a poly( n )-space O ∗ (2 0. 86 n )-time randomized algorithm for the Subset Sum problem, removing the random oracles required in the algorithm of Bansal, Garg, Nederlof, and Vyas [STOC 2017]. The main technique underlying our results is a pseudorandom hash family based on iterative restrictions, which can fool the cycle-finding procedure in the algorithms of Beame et al. and Bansal et al.

Details

MFCS Conference 2021 Conference Paper

Black-Box Hypotheses and Lower Bounds

  • Brynmor Chapman
  • R. Ryan Williams

What sort of code is so difficult to analyze that every potential analyst can discern essentially no information from the code, other than its input-output behavior? In their seminal work on program obfuscation, Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, and Yang (CRYPTO 2001) proposed the Black-Box Hypothesis, which roughly states that every property of Boolean functions which has an efficient "analyst" and is "code independent" can also be computed by an analyst that only has black-box access to the code. In their formulation of the Black-Box Hypothesis, the "analysts" are arbitrary randomized polynomial-time algorithms, and the "codes" are general (polynomial-size) circuits. If true, the Black-Box Hypothesis would immediately imply NP ̸ ⊂ BPP. We consider generalized forms of the Black-Box Hypothesis, where the set of "codes" 𝒞 and the set of "analysts" 𝒜 may correspond to other efficient models of computation, from more restricted models such as AC⁰ to more general models such as nondeterministic circuits. We show how lower bounds of the form 𝒞 ̸ ⊂ 𝒜 often imply a corresponding Black-Box Hypothesis for those respective codes and analysts. We investigate the possibility of "complete" problems for the Black-Box Hypothesis: problems in 𝒞 such that they are not in 𝒜 if and only if their corresponding Black-Box Hypothesis is true. Along the way, we prove an equivalence: for nondeterministic circuit classes 𝒞, the "𝒞-circuit satisfiability problem" is not in 𝒜 if and only if the Black-Box Hypothesis is true for analysts in 𝒜.

Details

FOCS Conference 2021 Conference Paper

Constructive Separations and Their Consequences

  • Lijie Chen 0001
  • Ce Jin 0001
  • Rahul Santhanam
  • R. Ryan Williams

For a complexity class C and language L, a constructive separation of “L is not in C” gives an efficient algorithm (also called a refuter) to find counterexamples (bad inputs) for every C-algorithm attempting to decide L. We study the questions: Which lower bounds can be made constructive? What are the consequences of constructive separations? We build a case that “constructiveness” serves as a dividing line between many weak lower bounds we know how to prove, and strong lower bounds against P, ZPP, and BPP. Put another way, constructiveness is the opposite of a complexity barrier: it is a property we want lower bounds to have. Our results fall into three broad categories. 1. For many separations, making them constructive would imply breakthrough lower bounds. Our first set of results shows that, for many well-known lower bounds against streaming algorithms, one-tape Turing machines, and query complexity, as well as lower bounds for the Minimum Circuit Size Problem, making these lower bounds constructive would imply break-through separations ranging from “EXP not equal to BPP” to even “P not equal to NP”. 2. Most conjectured uniform separations can be made constructive. Our second set of results shows that for most major open problems in lower bounds against P, ZPP, and BPP, including “P not equal to NP”, “P not equal to PSPACE”, “P not equal to PP”, “ZPP not equal to EXP”, and “BPP not equal to NEXP”, any proof of the separation would further imply a constructive separation. Our results generalize earlier results for “P not equal to NP” [Gutfreund, Shaltiel, and Ta-Shma, CCC 2005] and “BPP not equal to NEXP” [Dolev, Fandina and Gutfreund, CIAC 2013]. Thus any proof of these strong lower bounds must also yield a constructive version, compared to many weak lower bounds we currently know. 3. Some separations cannot be made constructive. Our third set of results shows that certain complexity separations cannot be made constructive. We observe that for all super-polynomially growing functions $\mathbf{t}$, there are no constructive separations for detecting high t-time Kolmogorov complexity (a task which is known to be not in P) from any complexity class, unconditionally. We also show that under plausible conjectures, there are languages in NP - $\mathbf{P}$ for which there are no constructive separations from any complexity class.

Details

SODA Conference 2021 Conference Paper

Fast Low-Space Algorithms for Subset Sum

  • Ce Jin 0001
  • Nikhil Vyas 0001
  • R. Ryan Williams

We consider the canonical Subset Sum problem: given a list of positive integers a 1, …, a n and a target integer t with t > a i for all i, determine if there is an S ⊆ [ n ] such that Σ i ∊ S a i = t. The well-known pseudopolynomialtime dynamic programming algorithm [Bellman, 1957] solves Subset Sum in O ( nt ) time, while requiring Ω( t ) space. In this paper we present algorithms for Subset Sum with Õ ( nt ) running time and much lower space requirements than Bellman's algorithm, as well as that of prior work. We show that Subset Sum can be solved in Õ ( nt ) time and O (log( nt )) space with access to O (log n log log n + log t ) random bits. This significantly improves upon the Õ ( nt 1+ ∊ )-time, Õ(n log t )-space algorithm of Bringmann (SODA 2017). We also give a Õ ( n 1+ ∊ t )-time, O (log( nt ))-space randomized algorithm, improving upon previous ( nt ) O (1) -time O (log( nt ))-space algorithms by Elberfeld, Jakoby, and Tantau (FOCS 2010), and Kane (2010). In addition, we also give a poly log( nt )-space, Õ ( n 2 t )-time deterministic algorithm. We also study time-space trade-offs for Subset Sum. For parameter 1 ≤ k ≤ min{ n, t }, we present a randomized algorithm running in Õ (( n + t ) · k ) time and O (( t/k ) poly log( nt )) space. As an application of our results, we give an Õ (min{ n 2 / ∊, n/∊ 2 })-time and poly log( nt )-space algorithm for “weak” ∊ -approximations of Subset Sum.

Details

FOCS Conference 2021 Conference Paper

MAJORITY-3SAT (and Related Problems) in Polynomial Time

  • Shyan Akmal
  • R. Ryan Williams

Majority-SAT (a. k. a. MAJ-SAT) is the problem of determining whether an input n-variable formula in conjunctive normal form (CNF) has at least 2^(n-1) satisfying assignments. Majority-SAT and related problems have been studied extensively in various AI communities interested in the complexity of probabilistic planning and inference. Although Majority-SAT has been known to be PP-complete for over 40 years, the complexity of a natural variant has remained open: Majority-kSAT, where the input CNF formula is restricted to have clause width at most k. We prove that for every k, Majority-kSAT is in P; in fact, the problem can be solved in linear time (whereas the previous best-known algorithm ran in exponential time). More generally, for any positive integer k and constant p in (0, 1) with bounded denominator, we give an algorithm that can determine whether a given k-CNF has at least p(2^n) satisfying assignments, in deterministic linear time. We find these results surprising, as many analogous problems which are hard for CNF formulas remain hard when restricted to 3-CNFs. Our algorithms have interesting positive implications for counting complexity and the complexity of inference, significantly reducing the known complexities of related problems such as E-MAJ-kSAT and MAJ-MAJ-kSAT. Our results immediately extend to arbitrary Boolean CSPs with constraints of arity k. At the heart of our approach is an efficient method for solving threshold counting problems by extracting and analyzing various sunflowers found in the corresponding set system of a k-CNF. Exploring the implications of our results, we find that the tractability of Majority-kSAT is somewhat fragile, in intriguing ways. For the closely related GtMajority-SAT problem (where we ask whether a given formula has greater than 2^(n-1) satisfying assignments) which is also known to be PP-complete, we show that GtMajority-kSAT is in P for k at most 3, but becomes NP-complete for k at least 4. We also show that for Majority-SAT on k-CNFs with one additional clause of arbitrary width, the problem is PP-complete for k at least 4, is NP-hard for k=3, and remains in P for k=2. These results are counterintuitive, because the “natural” classifications of these problems would have been PP-completeness, and because there is a stark difference in the complexity of GtMajority-kSAT and Majority-kSAT for all k at least 4.

Details

FOCS Conference 2020 Conference Paper

Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization

  • Lijie Chen 0001
  • Xin Lyu 0002
  • R. Ryan Williams

In certain complexity-theoretic settings, it is notoriously difficult to prove complexity separations which hold almost everywhere, i. e. , for all but finitely many input lengths. For example, a classical open question is whether NEXP is contained in i. o. -NP; that is, it is open whether nondeterministic exponential time computation can be simulated on infinitely many input lengths by an NP algorithm. This difficulty also applies to Williams' algorithmic method for circuit lower bounds [Williams, J. ACM 2014]. [Murray and Williams, STOC 2018] proved that nondeterminstic quasi-polynomial time is not contained in ACC^0, while it remained an open problem to show that E^NP (2^O(n) time with an NP oracle) is not contained in i. o. -ACC^0. In this paper, we show how many infinitely-often circuit lower bounds proved by the algorithmic method can be adapted to establish almost-everywhere lower bounds. First, we show there is a function f in E^NP such that, for all sufficiently large input lengths n, f cannot be (1/2+exp(-n ∧ e))-approximated by exp(n^e)-size ACC^0 circuits on inputs of length n (for all small e), improving lower bounds in [Chen and Ren, STOC 2020] and [Viola, ECCC 2020]. Second, we construct rigid matrices in P^NP for all but finitely many inputs, rather than infinitely often as in [Alman and Chen, FOCS 2019] and [Bhangale et al. 2020]. Third, we show there is a positive c such that E^NP has constant-error probabilistic degree at least cn/(log^2 n) for all large enough n, improving an infinitely-often separation by [Viola, ECCC 2020]. Our key to proving almost-everywhere worst-case lower bounds is a new “constructive” proof of an NTIME hierarchy theorem proved by [Fortnow and Santhanam, CCC 2016], where we show for every “weak” nondeterminstic algorithm, a “refuter algorithm” exists that can construct “bad” inputs for the hard language. We use this refuter algorithm to construct an almost-everywhere hard function. To extend our lower bounds to the average case, we prove a new XOR Lemma based on approximate linear sums, and combine it with PCP of proximity ideas developed in [Chen and Williams, CCC 2019] and [Chen and Ren, STOC 2020]. As a byproduct of our new XOR Lemma, we obtain a nondeterministic pseudorandom generator for poly-size ACC^0 circuits with seed length polylog(n), which resolves an open question in [Chen and Ren, STOC 2020].

Details

SODA Conference 2020 Conference Paper

Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions

  • Josh Alman
  • Timothy M. Chan
  • R. Ryan Williams

We present a deterministic, truly subquadratic algorithm for offline (1 + ε )-approximate nearest or farthest neighbor search (in particular, the closest pair or diameter problem) in Hamming space in any dimension d ≤ n δ, for a sufficiently small constant δ > 0. The running time of the algorithm is roughly for nearest neighbors, or for farthest. The algorithm follows from a simple combination of expander walks, Chebyshev polynomials, and rectangular matrix multiplication. We also show how to eliminate errors in the previous Monte Carlo randomized algorithm of Alman, Chan, and Williams [FOCS’16] for offline approximate nearest or farthest neighbors, and obtain a Las Vegas randomized algorithm with expected running time. Finally, we note a simplification of Alman, Chan, and Williams' method and obtain a slightly improved Monte Carlo randomized algorithm with running time. As one application, we obtain improved deterministic and randomized (1 + ε)-approximation algorithms for MAX-SAT.

Details

SODA Conference 2019 Conference Paper

An Equivalence Class for Orthogonal Vectors

  • Lijie Chen 0001
  • R. Ryan Williams

The Orthogonal Vectors problem (OV) asks: given n vectors in {0, 1} O (log n ), are two of them orthogonal? OV is easily solved in O ( n 2 log n ) time, and it is a central problem in fine-grained complexity: dozens of conditional lower bounds are based on the popular hypothesis that OV cannot be solved in (say) n 1. 99 time. However, unlike the APSP problem, few other problems are known to be non-trivially equivalent to OV. We show OV is truly-subquadratic equivalent to several fundamental problems, all of which (a priori) look harder than OV. A partial list is given below: 1. (Min-IP/Max-IP) Find a red-blue pair of vectors with minimum (respectively, maximum) inner product, among n vectors in {0, 1} O (log n ). 2. (Exact-IP) Find a red-blue pair of vectors with inner product equal to a given target integer, among n vectors in {0, 1} O (log n ). 3. (Apx-Min-IP/Apx-Max-IP) Find a red-blue pair of vectors that is a 100-approximation to the minimum (resp. maximum) inner product, among n vectors in {0, l} O (log n ). 4. (Approximate Bichrom. - ℓ p -Closest-Pair) Compute a (1+ Ω(1))-approximation to the ℓ p -closest red-blue pair (for a constant p ∊ [1, 2]), among n points in ℝ, d ≤ n o (1). 5. (Approximate ℓ p -Furthest-Pair) Compute a (1 + Ω(1))-approximation to the ℓ p -furthest pair (for a constant p ∊ [1, 2]), among n points in ℝ, d ≤ n o (1). Therefore, quick constant-factor approximations to maximum inner product imply quick exact solutions to maximum inner product, in the O (log n )-dimensional setting. Another consequence is that the ability to find vectors with zero inner product suffices for finding vectors with maximum inner product. Our equivalence results are robust enough that they continue to hold in the data structure setting. In particular, we show that there is a poly( n ) space, n 1– ε query time data structure for Partial Match with vectors from {0, 1} O (log n ) if and only if such a data structure exists for 1 + Ω(1) Approximate Nearest Neighbor Search in Euclidean space. To establish the equivalences, we introduce two general frameworks for reductions to OV: one based on ∑ 2 communication protocols, and another based on locality-sensitive hashing families. In addition, we obtain an n 2–1/ O (log c ) time algorithm for Apx-Min-IP with n vectors from {0, 1} c log n, matching state-of-the-art algorithms for OV and Apx-Max-IP. As an application, we obtain a faster algorithm for approximating “almost solvable” MAX-SAT instances.

Details

FOCS Conference 2019 Conference Paper

Hardness Magnification for all Sparse NP Languages

  • Lijie Chen 0001
  • Ce Jin 0001
  • R. Ryan Williams

In the Minimum Circuit Size Problem (MCSP[s(m)]), we ask if there is a circuit of size s(m) computing a given truth-table of length n = 2m. Recently, a surprising phenomenon termed as hardness magnification by [Oliveira and Santhanam, FOCS 2018] was discovered for MCSP[s(m)] and the related problem MKtP of computing time-bounded Kolmogorov complexity. In [Oliveira and Santhanam, FOCS 2018], [Oliveira, Pich, and Santhanam, CCC 2019], and [McKay, Murray, and Williams, STOC 2019], it was shown that minor (n 1+ε -style) lower bounds for MCSP[2 o(m) ] or MKtP[ 2o(m) ] would imply breakthrough circuit lower bounds such as NP⊄P/ poly, NP⊄NC 1, or EXP⊄P/poly. We consider the question: What is so special about MCSP and MKtP? Why do they admit this striking phenomenon? One simple property is that all variants of MCSP (and MKtP) considered in prior work are sparse languages. For example, MCSP[s(m)] has 2 Õ(s(m)) yes-instances of length n = 2m, so MCSP[2 o(m) ] is 2 no(1) -sparse. We show that there is a hardness magnification phenomenon for all equally-sparse NP languages. Formally, suppose there is an ε > 0 and a language L ∈ NP which is 2n o(1) -sparse, and L ∈/ Circuit[n1+ε]. Then NP does not have nk-size circuits for all k. We prove analogous theorems for De Morgan formulas, B2-formulas, branching programs, AC 0 [6] and TC 0 circuits, and more: improving the state of the art in NP lower bounds against any of these models by an ε factor in the exponent would already imply NP lower bounds for all fixed polynomials. In fact, in our proofs it is not necessary to prove a (say) n 1+ε circuit size lower bound for L: one only has to prove a lower bound against n 1+ε -time n ε -space deterministic algorithms with n ε advice bits. Such lower bounds are well-known for non-sparse problems. Building on our techniques, we also show interesting new hardness magnifications for search-MCSP and search-MKtP (where one must output small circuits or short representations of strings), showing consequences such as ⊕P (or PP, PSPACE, and EXP) is not contained in P/poly (or NC 1, AC 0 [6], or branching programs of polynomial size). For instance, if there is an ε > 0 such that search-MCSP[2 βm ] does not have De Morgan formulas of size n 3+ε for all constants ß > 0, then ⊕P⊄NC 1.

Details

SAT Conference 2019 Conference Paper

On Super Strong ETH

  • Nikhil Vyas 0001
  • R. Ryan Williams

Abstract Multiple known algorithmic paradigms (backtracking, local search and the polynomial method) only yield a \(2^{n(1-1/O(k))}\) time algorithm for k -SAT in the worst case. For this reason, it has been hypothesized that the worst-case k -SAT problem cannot be solved in \(2^{n(1-f(k)/k)}\) time for any unbounded function f. This hypothesis has been called the “Super-Strong ETH”, modeled after the ETH and the Strong ETH. We give two results on the Super-Strong ETH: 1. It has also been hypothesized that k -SAT is hard to solve for randomly chosen instances near the “critical threshold”, where the clause-to-variable ratio is \(2^k \ln 2-\varTheta (1)\). We give a randomized algorithm which refutes the Super-Strong ETH for the case of random k -SAT and planted k -SAT for any clause-to-variable ratio. For example, given any random k -SAT instance F with n variables and m clauses, our algorithm decides satisfiability for F in \(2^{n(1-\varOmega (\log k)/k)}\) time, with high probability (over the choice of the formula and the randomness of the algorithm). It turns out that a well-known algorithm from the literature on SAT algorithms does the job: the PPZ algorithm of Paturi, Pudlák and Zane [ 17 ]. 2. The Unique k -SAT problem is the special case where there is at most one satisfying assignment. Improving prior reductions, we show that the Super-Strong ETHs for Unique k -SAT and k -SAT are equivalent. More precisely, we show the time complexities of Unique k -SAT and k -SAT are very tightly correlated: if Unique k -SAT is in \(2^{n(1-f(k)/k)}\) time for an unbounded f, then k -SAT is in \(2^{n(1-f(k)(1-{\varepsilon })/k)}\) time for every \({\varepsilon }> 0\).

Details

STOC Conference 2019 Conference Paper

Weak lower bounds on resource-bounded compression imply strong separations of complexity classes

  • Dylan M. McKay
  • Cody D. Murray
  • R. Ryan Williams

The Minimum Circuit Size Problem (MCSP) asks to determine the minimum size of a circuit computing a given truth table. MCSP is a natural and powerful string compression problem using bounded-size circuits. Recently, Oliveira and Santhanam [FOCS 2018] and Oliveira, Pich, and Santhanam [ECCC 2018] demonstrated a “hardness magnification” phenomenon for MCSP in restricted settings. Letting MCSP[ s ( n )] be the problem of deciding if a truth table of length 2 n has circuit complexity at most s ( n ), they proved that small (fixed-polynomial) average case circuit/formula lower bounds for MCSP[2 √ n ], or lower bounds for approximating MCSP[2 o ( n ) ], would imply major separations such as NP ⊄ BPP and NP ⊄ P / poly . We strengthen their results in several directions, obtaining magnification results from worst-case lower bounds on exactly computing the search version of generalizations of MCSP[ s ( n )], which also extend to time-bounded Kolmogorov complexity. In particular, we show that search-MCSP[ s ( n )] (where we must output a s ( n )-size circuit when it exists) admits extremely efficient AC 0 circuits and streaming algorithms using Σ 3 SAT oracle gates of small fan-in (related to the size s ( n ) we want to test). For A : {0,1} ⋆ → {0,1}, let search-oracleMCSP A [ s ( n )] be the problem: Given a truth table T of size N =2 n , output a Boolean circuit for T of size at most s ( n ) with AND, OR, NOT, and A -oracle gates (or report that no such circuit exists). Some consequences of our results are: (1) For reasonable s ( n ) ≥ n and A ∈ PH , if search-MCSP A [ s ( n )] does not have a 1-pass deterministic poly( s ( n ))-space streaming algorithm with poly( s ( n )) update time, then P ≠ NP . For example, proving that it is impossible to synthesize SAT-oracle circuits of size 2 n /log ⋆ n with a streaming algorithm on truth tables of length N =2 n using N ε update time and N ε space on length- N inputs (for some ε > 0) would already separate P and NP . Note that some extremely simple functions, such as EQUALITY of two strings, already satisfy such lower bounds. (2) If search-MCSP[ n c ] lacks Õ( N )-size, Õ(1)-depth circuits for a c ≥ 1, then NP ⊄ P / poly . (3) If search-MCSP[ s ( n )] does not have N · poly( s ( n ))-size, O (log N )-depth circuits, then NP ⊄ NC 1 . Note it is known that MCSP[2 √ n ] does not have formulas of N 1.99 size [Hirahara and Santhanam, CCC 2017]. (4) If there is an ε > 0 such that for all c ≥ 1, search-MCSP[2 n / c ] does not have N 1+ε -size O (1/ε)-depth ACC 0 circuits, then NP ⊄ ACC 0 . Thus the amplification results of Allender and Koucký [JACM 2010] can extend to problems in NP and beyond. Furthermore, if we substitute ⊕ P , PP , PSPACE , or EXP -complete problems for the oracle A , we obtain separations for those corresponding complexity classes instead of NP . Analogues of the above results hold for time-bounded Kolmogorov complexity as well.

Details

SODA Conference 2018 Conference Paper

On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity

  • R. Ryan Williams

Point location problems for n points in d -dimensional Euclidean space (and ℓ p spaces more generally) have typically had two kinds of running-time solutions: (Nearly-Linear) less than d po1y( d ) · n log O ( d ) n time, or (Barely-Subquadratic) f ( d ) · n 2–1/Θ( d ) time, for various f. For small d and large n, “nearly-linear” running times are generally feasible, while the “barely-subquadratic” times are generally infeasible, requiring essentially quadratic time. For example, in the Euclidean metric, finding a Closest Pair among n points in ℝ d is nearly-linear, solvable in 2 O ( d ). n log O (1) n time, while the known algorithms for finding a Furthest Pair (the diameter of the point set) are only barely-subquadratic, requiring Ω( n 2–1/Θ( d ) ) time. Why do these proximity problems have such different time complexities? Is there a barrier to obtaining nearly-linear algorithms for problems which are currently only barely-subquadratic? We give a novel exact and deterministic self-reduction for the Orthogonal Vectors problem on n vectors in {0, 1} d to n vectors in ℤ ω (log d ) that runs in 2 o ( d ) time. As a consequence, barely-subquadratic problems such as Euclidean diameter, Euclidean bichromatic closest pair, and incidence detection do not have O ( n 2– ∊ ) time algorithms (in Turing models of computation) for dimensionality d = ω (log log n ) 2, unless the popular Orthogonal Vectors Conjecture and the Strong Exponential Time Hypothesis are false. That is, while the poly-log-log-dimensional case of Closest Pair is solvable in n 1+ o (1) time, the poly-log-log-dimensional case of Furthest Pair can encode difficult large-dimensional problems conjectured to require n 2– o (1) time. We also show that the All-Nearest Neighbors problem in ω (log n ) dimensions requires n 2– o (1) time to solve, assuming either of the above conjectures.

Details

SODA Conference 2017 Conference Paper

Beating Brute Force for Systems of Polynomial Equations over Finite Fields

  • Daniel Lokshtanov
  • Ramamohan Paturi
  • Suguru Tamaki
  • R. Ryan Williams
  • Huacheng Yu

We consider the problem of solving systems of multivariate polynomial equations of degree k over a finite field. For every integer k ≤ 2 and finite field q where q = p d for a prime p, we give, to the best of our knowledge, the first algorithms that achieve an exponential speedup over the brute force O ( q n ) time algorithm in the worst case. We present two algorithms, a randomized algorithm with running time q n + o ( n ) · q − n / O ( k ) time if q < 2 4 ekd, and otherwise, where e = 2. 718… is Napier's constant, and a deterministic algorithm for counting solutions with running time q n + o ( n ) · q − n / O ( kq 6/7 d ). For the important special case of quadratic equations in F 2, our randomized algorithm has running time O (2 0. 8765n ). For systems over 2 we also consider the case where the input polynomials do not have bounded degree, but instead can be efficiently represented as a ΣΠΣ circuit, i. e. , a sum of products of sums of variables. For this case we present a deterministic algorithm running in time 2 n-dn for δ = 1/ O (log(s/ n )) for instances with s product gates in total and n variables. Our algorithms adapt several techniques recently developed via the polynomial method from circuit complexity. The algorithm for systems of ΣΠΣ polynomials also introduces a new degree reduction method that takes an instance of the problem and outputs a subexponential-sized set of instances, in such a way that feasibility is preserved and every polynomial among the output instances has degree O (log(s/ n )).

Details

SODA Conference 2017 Conference Paper

Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications

  • Jiawei Gao 0001
  • Russell Impagliazzo
  • Antonina Kolokolova
  • R. Ryan Williams

Properties definable in first-order logic are algorithmically interesting for both theoretical and pragmatic reasons. Many of the most studied algorithmic problems, such as Hitting Set and Orthogonal Vectors, are first-order, and the first-order properties naturally arise as relational database queries. A relatively straightforward algorithm for evaluating a property with k + 1 quantifiers takes time O (m k ) and, assuming the Strong Exponential Time Hypothesis (SETH), some such properties require O (m k-∊ ) time for any ∊ > 0. (Here, m represents the size of the input structure, i. e. the number of tuples in all relations.) We give algorithms for every first-order property that improves this upper bound to i. e. , an improvement by a factor more than any poly-log, but less than the polynomial required to refute SETH. Moreover, we show that further improvement is equivalent to improving algorithms for sparse instances of the well-studied Orthogonal Vectors problem. Surprisingly, both results are obtained by showing completeness of the Sparse Orthogonal Vectors problem for the class of first-order properties under fine-grained reductions. To obtain improved algorithms, we apply the fast Orthogonal Vectors algorithm of [3, 16]. While fine-grained reductions (reductions that closely preserve the conjectured complexities of problems) have been used to relate the hardness of disparate specific problems both within P and beyond, this is the first such completeness result for a standard complexity class.

Details

FOCS Conference 2017 Conference Paper

Distributed PCP Theorems for Hardness of Approximation in P

  • Amir Abboud
  • Aviad Rubinstein
  • R. Ryan Williams

We present a new distributed model of probabilistically checkable proofs (PCP). A satisfying assignment x ∈ {0, 1} n to a CNF formula φ is shared between two parties, where Alice knows x 1, .. ., x n/2, Bob knows x n/2+1, .. ., xn, and both parties know φ. The goal is to have Alice and Bob jointly write a PCP that x satisfies φ, while exchanging little or no information. Unfortunately, this model as-is does not allow for nontrivial query complexity. Instead, we focus on a non-deterministic variant, where the players are helped by Merlin, a third party who knows all of x. Using our framework, we obtain, for the first time, PCP-like reductions from the Strong Exponential Time Hypothesis (SETH) to approximation problems in P. In particular, under SETH we show that there are no trulysubquadratic approximation algorithms for Maximum Inner Product over {0, 1}-vectors, LCS Closest Pair over permutations, Approximate Partial Match, Approximate Regular Expression Matching, and Diameter in Product Metric. All our inapproximability factors are nearly-tight. In particular, for the first three problems we obtain nearly-polynomial factors of 2 (log n) 1-o(1); only (1+o(1))-factor lower bounds (under SETH) were known before. As an additional feature of our reduction, we obtain new SETH lower bounds for the exact “monochromatic” Closest Pair problem in the Euclidean, Manhattan, and Hamming metrics.

Details

SODA Conference 2017 Conference Paper

Faster Online Matrix-Vector Multiplication

  • Kasper Green Larsen
  • R. Ryan Williams

We consider the Online Boolean Matrix-Vector Multiplication (OMV) problem studied by Henzinger et al. [STOC'15]: given an n × n Boolean matrix M, we receive n Boolean vectors v 1, …, v n one at a time, and are required to output Mv i (over the Boolean semiring) before seeing the vector v i+1, for all i. Previous known algorithms for this problem are combinatorial, running in O ( n 3 /log 2 n ) time. Henzinger et al. conjecture there is no O ( n 3-∊ ) time algorithm for OMV, for all ∊ > 0; their OMV conjecture is shown to imply strong hardness results for many basic dynamic problems. We give a substantially faster method for computing OMV, running in randomized time. In fact, after seeing vectors, we already achieve amortized time for matrix-vector multiplication. Our approach gives a way to reduce matrix-vector multiplication to solving a version of the Orthogonal Vectors problem, which in turn reduces to “small” algebraic matrix-matrix multiplication. Applications include faster independent set detection, partial match retrieval, and 2-CNF evaluation. We also show how a modification of our method gives a cell probe data structure for OMV with worst case time per query vector, where w is the word size. This result rules out an unconditional proof of the OMV conjecture using purely information-theoretic arguments.

Details

STOC Conference 2017 Conference Paper

Probabilistic rank and matrix rigidity

  • Josh Alman
  • R. Ryan Williams

We consider a notion of probabilistic rank and probabilistic sign-rank of a matrix, which measure the extent to which a matrix can be probabilistically represented by low-rank matrices. We demonstrate several connections with matrix rigidity, communication complexity, and circuit lower bounds. The most interesting outcomes are: The Walsh-Hadamard Transform is Not Very Rigid. We give surprising upper bounds on the rigidity of a family of matrices whose rigidity has been extensively studied, and was conjectured to be highly rigid. For the 2 n X 2 n Walsh-Hadamard transform H n (a.k.a. Sylvester matrices, a.k.a. the communication matrix of Inner Product modulo 2), we show how to modify only 2 ε n entries in each row and make the rank of H n drop below 2 n (1-Ω(ε 2 /log(1/εε))) , for all small ε > 0, over any field. That is, it is not possible to prove arithmetic circuit lower bounds on Hadamard matrices such as H n , via L. Valiant's matrix rigidity approach. We also show non-trivial rigidity upper bounds for H n with smaller target rank. Matrix Rigidity and Threshold Circuit Lower Bounds. We give new consequences of rigid matrices for Boolean circuit complexity. First, we show that explicit n X n Boolean matrices which maintain rank at least 2 (log n ) 1-δ after n 2 /2 (log n ) δ/2 modified entries (over any field, for any δ > 0) would yield an explicit function that does not have sub-quadratic-size AC 0 circuits with two layers of arbitrary linear threshold gates. Second, we prove that explicit 0/1 matrices over ℝ which are modestly more rigid than the best known rigidity lower bounds for sign-rank would imply exponential-gate lower bounds for the infamously difficult class of depth-two linear threshold circuits with arbitrary weights on both layers. In particular, we show that matrices defined by these seemingly-difficult circuit classes actually have low probabilistic rank and sign-rank, respectively. An Equivalence Between Communication, Probabilistic Rank, and Rigidity. It has been known since Razborov [1989] that explicit rigidity lower bounds would resolve longstanding lower-bound problems in communication complexity, but it seemed possible that communication lower bounds could be proved without making progress on matrix rigidity. We show that for every function f which is randomly self-reducible in a natural way (the inner product mod 2 is an example), bounding the communication complexity of f (in a precise technical sense) is equivalent to bounding the rigidity of the matrix of f , via an equivalence with probabilistic rank.

Details

SODA Conference 2016 Conference Paper

Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky

  • Timothy M. Chan
  • R. Ryan Williams

We show how to solve all-pairs shortest paths on n nodes in deterministic time, and how to count the pairs of orthogonal vectors among n 0–1 vectors in d = c log n dimensions in deterministic n 2–1/ O (log c ) time. These running times essentially match the best known randomized algorithms of (Williams, STOC'14) and (Abboud, Williams, and Yu, SODA 2015) respectively, and the ability to count was open even for randomized algorithms. By reductions, these two results yield faster deterministic algorithms for many other problems. Our techniques can also be used to deterministically count k -SAT assignments on n variable formulas in 2 n – n / O ( k ) time, roughly matching the best known running times for detecting satisfiability and resolving an open problem of Santhanam (2013). A key to our constructions is an efficient way to deterministically simulate certain probabilistic polynomials critical to the algorithms of prior work, carefully applying small-biased sets and modulus-amplifying polynomials.

Details

FOCS Conference 2016 Conference Paper

Polynomial Representations of Threshold Functions and Algorithmic Applications

  • Josh Alman
  • Timothy M. Chan
  • R. Ryan Williams

We design new polynomials for representing threshold functions in three different regimes: probabilistic polynomials of low degree, which need far less randomness than previous constructions, polynomial threshold functions (PTFs) with "nice" threshold behavior and degree almost as low as the probabilistic polynomials, and a new notion of probabilistic PTFs where we combine the above techniques to achieve even lower degree with similar "nice" threshold behavior. Utilizing these polynomial constructions, we design faster algorithms for a variety of problems: · Offline Hamming Nearest (and Furthest) Neighbors: Given n red and n blue points in d-dimensional Hamming space for d = c log n, we can find an (exact) nearest (or furthest) blue neighbor for every red point in randomized time n 2-1 /O(√clog 2/3 c) or deterministic time n 2-1/O(c log2 c). These improve on a randomized n 2-1/O(c log2 c) bound by Alman and Williams (FOCS'15), and also lead to faster MAX-SAT algorithms for sparse CNFs. · Offline Approximate Nearest (and Furthest) Neighbors: Given n red and n blue points in d-dimensional ℓ 1 or Euclidean space, we can find a (1+ε)-approximate nearest (or furthest) blue neighbor for each red point in randomized time near dn+n 2-Ω(ε1/3/log(1/ε)). This improves on an algorithm by Valiant (FOCS'12) with randomized time near dn+n 2-Ω(√ε), which in turn improves previous methods based on locality-sensitive hashing. · SAT Algorithms and Lower Bounds for Circuits With Linear Threshold Functions: We give a satisfiability algorithm for AC 0 [m] o LTF LTF circuits with a subquadratic number of LTF gates on the bottom layer, and a subexponential number of gates on the other layers, that runs in deterministic 2 n-n ε time. This strictly generalizes a SAT algorithm for ACC 0 oLTF circuits of subexponential size by Williams (STOC'14) and also implies new circuit lower bounds for threshold circuits, improving a recent gate lower bound of Kane and Williams (STOC'16). We also give a randomized 2 n-n ε -time SAT algorithm for subexponential-size MAJ o AC 0 oLTF o AC 0 oLTF circuits, where the top MAJ gate and middle LTF gates have O(n 6/5-δ ) fan-in.

Details

STOC Conference 2016 Conference Paper

Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits

  • Daniel M. Kane
  • R. Ryan Williams

In order to formally understand the power of neural computing, we first need to crack the frontier of threshold circuits with two and three layers, a regime that has been surprisingly intractable to analyze. We prove the first super-linear gate lower bounds and the first super-quadratic wire lower bounds for depth-two linear threshold circuits with arbitrary weights, and depth-three majority circuits computing an explicit function. (1) We prove that for all ε ≪ √log( n )/ n , the linear-time computable Andreev’s function cannot be computed on a (1/2+ε)-fraction of n -bit inputs by depth-two circuits of o (ε 3 n 3/2 /log 3 n ) gates, nor can it be computed with o (ε 3 n 5/2 /log 7/2 n ) wires. This establishes an average-case “size hierarchy” for threshold circuits, as Andreev’s function is computable by uniform depth-two circuits of o ( n 3 ) linear threshold gates, and by uniform depth-three circuits of O ( n ) majority gates. (2) We present a new function in P based on small-biased sets, which we prove cannot be computed by a majority vote of depth-two threshold circuits of o ( n 3/2 /log 3 n ) gates, nor with o ( n 5/2 /log 7/2 n ) wires. (3) We give tight average-case (gate and wire) complexity results for computing PARITY with depth-two threshold circuits; the answer turns out to be the same as for depth-two majority circuits. The key is a new method for analyzing random restrictions to linear threshold functions. Our main analytical tool is the Littlewood-Offord Lemma from additive combinatorics.

Details

SODA Conference 2015 Conference Paper

Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity

  • Rahul Santhanam
  • R. Ryan Williams

We study algorithms for the satisfiability problem for quantified Boolean formulas (QBFs), and consequences of faster algorithms for circuit complexity. We show that satisfiability of quantified 3-CNFs with m clauses, n variables, and two quantifier blocks (one existential block and one universal) can be solved deterministically in time. poly( m ). For the case of multiple quantifier blocks (alternations), we show that satisfiability of quantified CNFs of size poly( n ) on n variables with q quantifier blocks can be solved in 2 n−n 1/( q + 1) · poly( n ) time by a zero-error randomized algorithm. These are the first provable improvements over brute force search in the general case, even for quantified polynomial-sized CNFs with two quantifier blocks. A second zero-error randomized algorithm solves QBF on circuits of size s in 2 n– Ω( q ) · poly( s ) time when the number of quantifier blocks is q. We complement these algorithms by showing that improvements on them would imply new circuit complexity lower bounds. For example, if satisfiability of quantified CNF formulas with n variables, poly( n ) size and at most q quantifier blocks can be solved in time 2 n–n w q (1/ q ) then the complexity class NEXP does not have O (log n ) depth circuits of polynomial size. Furthermore, solving satisfiability of quantified CNF formulas with n variables, poly( n ) size and O (log n ) quantifier blocks in time 2 n–w (log ( n )) time would imply the same circuit complexity lower bound. The proofs of these results proceed by establishing strong relationships between the time complexity of QBF satisfiability over CNF formulas and the time complexity of QBF satisfiability over arbitrary Boolean formulas.

Details

SODA Conference 2015 Conference Paper

More Applications of the Polynomial Method to Algorithm Design

  • Amir Abboud
  • R. Ryan Williams
  • Huacheng Yu

In low-depth circuit complexity, the polynomial method is a way to prove lower bounds by translating weak circuits into low-degree polynomials, then analyzing properties of these polynomials. Recently, this method found an application to algorithm design: Williams (STOC 2014) used it to compute all-pairs shortest paths in time on dense n -node graphs. In this paper, we extend this methodology to solve a number of problems in combinatorial pattern matching and Boolean algebra, considerably faster than previously known methods. First, we give an algorithm for B oolean O rthogonal D etection, which is to detect among two sets A, B ⊆ {0, 1} d of size n if there is an x ∊ A and y ∊ B such that 〈 x, y 〉 = 0. For vectors of dimension d = c ( n ) log n, we solve B oolean O rthogonal D etection in n 2–1/ O (log c ( n )) time by a Monte Carlo randomized algorithm. We apply this as a subroutine in several other new algorithms: In B atch P artial M atch, we are given n query strings from from {0, 1, ⋆} c ( n ) log n (⋆ is a “don't care”), n strings from {0, 1} c ( n )log n, and wish to determine for each query whether or not there is a string matching the query. We solve this problem in n 2–1 / O (log c ( n )) time by a Monte Carlo randomized algorithm. Let t ≤ ν be integers. Given a DNF F on c log t variables with t terms, and v arbitrary assignments on the variables, F can be evaluated on all ν assignments in ν · t 1–1 / O (log c ) time, with high probability. There is a randomized algorithm that solves the Longest Common Substring with don't cares problem on two strings of length n in time. Given two strings S, T of length n, there is a randomized algorithm that computes the length of the longest substring of S that has Edit-Distance less than k to a substring of T in time. Symmetric Boolean Constraint Satisfaction Problems (CSPs) with n variables and m constraints are solvable in poly( m ). 2 n (1–1/ O (log mn )) time.

Details

FOCS Conference 2015 Conference Paper

Probabilistic Polynomials and Hamming Nearest Neighbors

  • Josh Alman
  • R. Ryan Williams

We show how to compute any symmetric Boolean function on n variables over any field (as well as '/ the integers) with a probabilistic polynomial of degree O( √nlog(1/ε)) and error at most ε. The degree dependence on n and ε is optimal, matching a lower bound of Razborov (1987) and Smolensky (1987) for the MAJORITY function. The proof is constructive: a low-degree polynomial can be efficiently sampled from the distribution. This polynomial construction is combined with other algebraic ideas to give the first subquadratic time algorithm for computing a (worst-case) batch of Hamming distances in superlogarithmic dimensions, exactly. To illustrate, let c(n): ℕ → ℕ. Suppose we are given a database D of n vectors in {0, 1} c(n)logn and a collection of n query vectors Q in the same dimension. For all u ∈ Q, we wish to compute a v ∈ D with minimum Hamming distance from u. We solve this problem in n 2-1/O(c(n)log 2 c(n)) randomized time. Hence, the problem is in “truly subquadratic” time for O(logn) dimensions, and in subquadratic time for d = o((log2 n)/(loglogn) 2 ). We apply the algorithm to computing pairs with maximum inner product, closest pair in ℓ1 for vectors with bounded integer entries, and pairs with maximum Jaccard coefficients.

Details

CSL Conference 2015 Conference Paper

Thinking Algorithmically About Impossibility (Invited Talk)

  • R. Ryan Williams

Complexity lower bounds like P! = NP assert impossibility results for all possible programs of some restricted form. As there are presently enormous gaps in our lower bound knowledge, a central question on the minds of today's complexity theorists is how will we find better ways to reason about all efficient programs? I argue that some progress can be made by (very deliberately) thinking algorithmically about lower bounds. Slightly more precisely, to prove a lower bound against some class C of programs, we can start by treating C as a set of inputs to another (larger) process, which is intended to perform some basic analysis of programs in C. By carefully studying the algorithmic "meta-analysis" of programs in C, we can learn more about the limitations of the programs being analyzed. This essay is mostly self-contained; scant knowledge is assumed of the reader.

Details

SAT Conference 2011 Invited Paper

Connecting SAT Algorithms and Complexity Lower Bounds

  • R. Ryan Williams

Abstract I will describe prior and current work on connecting the art of finding good satisfiability algorithms with the art of proving complexity lower bounds: proofs of limitations on what problems can be solved by good algorithms. Surprisingly, even minor algorithmic progress on solving the circuit satisfiability problem faster than exhaustive search can be applied to prove strong circuit complexity lower bounds. These connections have made it possible to prove new complexity lower bounds that had long been conjectured, and they suggest concrete directions for further progress.

Details

STOC Conference 2010 Conference Paper

Improving exhaustive search implies superpolynomial lower bounds

  • R. Ryan Williams

The P vs NP problem arose from the question of whether exhaustive search is necessary for problems with short verifiable solutions. We still do not know if even a slight algorithmic improvement over exhaustive search is universally possible for all NP problems, and to date no major consequences have been derived from the assumption that an improvement exists. We show that there are natural NP and BPP problems for which minor algorithmic improvements over the trivial deterministic simulation already entail lower bounds such as NEXP is not in P/poly and LOGSPACE is not equal to NP. These results are especially interesting given that similar improvements have been found for many other hard problems. Optimistically, one might hope our results suggest a new path to lower bounds; pessimistically, they show that carrying out the seemingly modest program of finding slightly better algorithms for all search problems may be extremely difficult (if not impossible). We also prove unconditional superpolynomial time-space lower bounds for improving on exhaustive search.

Details

SODA Conference 2010 Conference Paper

On the Possibility of Faster SAT Algorithms

  • Mihai Patrascu
  • R. Ryan Williams

We describe reductions from the problem of determining the satisfiability of Boolean CNF formulas (CNF-SAT) to several natural algorithmic problems. We show that attaining any of the following bounds would improve the state of the art in algorithms for SAT: an O ( n k – ε ) algorithm for k -D ominating S et, for any k ≥ 3, a (computationally efficient) protocol for 3-party set disjointness with o ( m ) bits of communication, an n o ( d ) algorithm for d -SUM, an O ( n 2 – ε ) algorithm for 2-SAT formulas with m = n 1+ o (1) clauses, where two clauses may have unrestricted length, and an O (( n + m ) k – ε ) algorithm for HornSat with k unrestricted length clauses. One may interpret our reductions as new attacks on the complexity of SAT, or sharp lower bounds conditional on exponential hardness of SAT.

Details

FOCS Conference 2010 Conference Paper

Subcubic Equivalences between Path, Matrix and Triangle Problems

  • Virginia Vassilevska Williams
  • R. Ryan Williams

We say an algorithm on n × n matrices with entries in [-M, M] (or n-node graphs with edge weights from [-M, M]) is truly subcubic if it runs in O(n 3-δ - poly(log M)) time for some δ > 0. We define a notion of subcubic reducibility, and show that many important problems on graphs and matrices solvable in O(n 3 ) time are equivalent under subcubic reductions. Namely, the following weighted problems either all have truly subcubic algorithms, or none of them do: The all-pairs shortest paths problem (APSP). Detecting if a weighted graph has a triangle of negative total edge weight. Listing up to n 2. 99 negative triangles in an edge-weighted graph. Finding a minimum weight cycle in a graph of nonnegative edge weights. The replacement paths problem in an edge-weighted digraph. Finding the second shortest simple path between two nodes in an edge-weighted digraph. Checking whether a given matrix defines a metric. Verifying the correctness of a matrix product over the (min, +)-semiring. Therefore, if APSP cannot be solved in n3-ε time for any ε > 0, then many other problems also need essentially cubic time. In fact we show generic equivalences between matrix products over a large class of algebraic structures used in optimization, verifying a matrix product over the same structure, and corresponding triangle detection problems over the structure. These equivalences simplify prior work on subcubic algorithms for all-pairs path problems, since it now suffices to give appropriate subcubic triangle detection algorithms. Other consequences of our work are new combinatorial approaches to Boolean matrix multiplication over the (OR, AND)semiring (abbreviated as BMM). We show that practical advances in triangle detection would imply practical BMM algorithms, among other results. Building on our techniques, we give two new BMM algorithms: a derandomization of the recent combinatorial BMM algorithm of Bansal and Williams (FOCS'09), and an improved quantum algorithm for BMM.

Details

FOCS Conference 2009 Conference Paper

Regularity Lemmas and Combinatorial Algorithms

  • Nikhil Bansal 0001
  • R. Ryan Williams

We present new combinatorial algorithms for Boolean matrix multiplication (BMM) and preprocessing a graph to answer independent set queries. We give the first asymptotic improvements on combinatorial algorithms for dense BMM in many years, improving on the "Four Russians'' O(n 3 /(w log n)) bound for machine models with word size w. (For a pointer machine, we can set w = log n.) The algorithms utilize notions from Regularity Lemmas for graphs in a novel way. 1) We give two randomized combinatorial algorithms for BMM. The first algorithm is essentially a reduction from BMM to the Triangle Removal Lemma}. The best known bounds for the Triangle Removal Lemma only imply an O((n 3 log?)/(? w log n)\right) time algorithm for BMM where? = (log*n)? for some? > 0, but improvements on the Triangle Removal Lemma would yield corresponding runtime improvements. The second algorithm applies the Weak Regularity Lemma of Frieze and Kannan along with several information compression ideas, running in O(n 3 (log log n) 2 /(log n) 9/4 ) time with probability exponentially close to 1. When w? log n, it can be implemented in O(n 3 (log log n) 2 /(w log n) 7/6 )) time. Our results immediately imply improved combinatorial methods for CFG parsing, detecting triangle-freeness, and transitive closure. 2)Using Weak Regularity, we also give an algorithm for answering queries of the form is S? V an independent set? in a graph. Improving on prior work, we show how to randomly preprocess a graph in O(n 2+? }) time (for all? > 0) so that with high probability, all subsequent batches of log n independent set queries can be answered deterministically in O(n 2 (log log n) 2 /((log n) 5/4 )) time. When w? log n, w queries can be answered in O(n 2 (log log n) 2 /((log n) 7/6 ))\right) time. In addition to its nice applications, this problem is interesting in that it is not known how to do better than O(n 2 ) using "algebraic'' methods.

Details

STOC Conference 2007 Conference Paper

All-pairs bottleneck paths for general graphs in truly sub-cubic time

  • Virginia Vassilevska Williams
  • R. Ryan Williams
  • Raphael Yuster

In the all-pairs bottleneck paths (APBP) problem (a.k.a. all-pairs maximum capacity paths), one is given a directed graph with real non-negative capacities on its edges and is asked to determine, for all pairs of vertices s and t, the capacity of a single path for which a maximum amount of flow can be routed from s to t. The APBP problem was first studied in operations research, shortly after the introduction of maximum flows and all-pairs shortest paths. We present the first truly sub-cubic algorithm for APBP in general dense graphs. In particular, we give a procedure for computing the (max, min)-product of two arbitrary matrices over R ∪ (∞,-∞) in O(n 2+Ω/3 ) ≤ O(n 2.792 ) time, where n is the number of vertices and Ω is the exponent for matrix multiplication over rings. Using this procedure, an explicit maximum bottleneck path for any pair of nodes can be extracted in time linear in the length of the path.

Details

STOC Conference 2006 Conference Paper

Finding a maximum weight triangle in n 3-Delta time, with applications

  • Virginia Vassilevska Williams
  • R. Ryan Williams

We present the first truly sub-cubic algorithms for finding a maximum node-weighted triangle in directed and undirected graphs with arbitrary real weights. The first is an O(B • n 3+ω/2 ) = O(B • n 2.688 ) deterministic algorithm, where n is the number of nodes, ω is the matrix multiplication exponent, and B is the number of bits of precision. The second is a strongly polynomial randomized algorithm that runs in O(n 3+ω/2 log n) expected worst-case time. To achieve this, we show how to efficiently sample a weighted triangle uniformly at random, out of just those triangles whose total weight falls in some prescribed interval (W 1 ,W 2 ) for arbitrary weights W 1 and W 2 . Previous approaches to the problem resulted in time bounds with either an exponential dependence on B, or a runtime of the form Ω(n 3 /(log n) c ). The algorithms are easily extended to finding a maximum node-weighted induced subgraph on 3k nodes in Õ(n (3+ω) k/2) = O(n 2.688 k ) time.We give applications to a variety of problems, including a stable matching problem between buyers and sellers in computational economics, and discuss the possibility of extending our approach to a truly sub-cubic algorithm for computing all-pairs shortest paths on directed graphs with arbitrary weights.

Details

SAT Conference 2003 Conference Paper

On Computing k-CNF Formula Properties

  • R. Ryan Williams

Abstract The latest generation of SAT solvers (e. g. [10, 7]) generally have three key features: randomization of variable selection, backtracking search, and some form of clause learning. We present a simple algorithm with these three features and prove that for instances with constant Δ (where Δ is the clause-to-variable ratio) the algorithm indeed has good worst-case performance, not only for computing SAT/UNSAT but more general properties as well, such as maximum satisfiability and counting the number of satisfying assignments. In general, the algorithm can determine any property that is computable via self-reductions on the formula. One corollary of our findings is that for all fixed Δ and k ≥ 2, Max-k -SAT is solvable in O ( c n ) expected time for some c < 2, partially resolving a long-standing open problem in improved exponential time algorithms. For example, when Δ = 4. 2 and k = 3, Max-k -SAT is solvable in O (1. 8932 n ) worst-case expected time. We also improve the known time bounds for exact solution of #2 SAT and #3 SAT, and the bounds for k -SAT when k ≥ 5.

Details