"...the young man or woman writing today has forgotten the problems of the human heart in conflict with itself which alone can make good writing because only that is worth writing about, worth the agony and the sweat." -- William Faulkner, 1950

• R. R. Williams. Simulating Time With Square-Root Space. [ECCC] [youtube]
  In 57th ACM Symposium on Theory of Computing (STOC 2025). Best Paper Award.
Summary: I show that time-$T$ multitape Turing machines can be simulated in about ~ $\sqrt{T}$ space. This result is a complete shock (to me); I think most researchers would have bet against time-$T$ being simulated in space $T^{0.99}$. As a consequence, circuits of $n$ gates can be evaluated in only $n \cdot poly(\log n)$ space, and there are natural problems in linear space which require $n^{1.99}$ time to be solved. The mainidea is to give a surprise-preserving reduction from time-$T$ simulation to the surprising low-space usage of Cook and Mertz's Tree Evaluation algorithm.
• D. Doron, E. Pyne, R. Tell, and R. R. Williams. When Connectivity Is Hard, Random Walks Are Easy (With Non-Determinism). [pdf]
  In 57th ACM Symposium on Theory of Computing (STOC 2025).
Summary: Among other results, we show an interesting win-win theorem for space-bounded computation: there are two algorithms $A$ and $B$ such that for every directed graph $G$ on $n$ nodes and $s,t$, either $A(G)$ outputs the transitive closure of $G$ in polynomial time and polylog space, or $B(G)$ outputs a good approximation of the $n$-step random walk matrix in nondeterministic logspace. Having one algorithm that achieves one of these tasks on all graphs would be a significant breakthrough.
• J. Alman, A. Chattopadhyay, and R. Williams. Sparsity Lower Bounds for Probabilistic Polynomials. [LIPIcs]
  In 16th Annual Innovations in Theoretical Computer Science Conference (ITCS 2025).
Summary: The best-known algorithms for several prominent fine-grained problems (including the Orthogonal Vectors problem) use the polynomial method: after some self-reduction (reducing the problem into a small number of instances of the same problem), we translate the reduced problems into a polynomial evaluation problem, then we evaluate the polynomial on many points in a more efficient way. We show that existing probabilistic polynomial constructions for computing basic functions like Orthogonal Vectors are optimal in a sense, proving tight lower bounds on the number of monomials necessary for representing such functions. (There is still a potential loophole, but it seems difficult to exploit that.)

• R. Williams. The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds. [ECCC]
  In 66th Annual Symposium on Foundations of Computer Science (FOCS 2024). Invited to the special issue for FOCS.
Summary: The Orthogonal Vectors Conjecture is one of the primary hardness hypotheses in fine-grained complexity. I show that the Orthogonal Vectors Conjecture implies non-uniform circuit complexity results; this is surprising, because the conjecture is about the hardness of uniform algorithms, and it is typically much more difficult to prove non-uniform lower bounds compared to uniform ones. For example, the Orthogonal Vectors Conjecture implies that 2-CNF formulas on $n$ variables do not have non-uniform depth-two exact threshold circuits of size $2^{o(n)}$. This new connection implies new forms of ``win-win'' circuit lower bounds. Using practical SAT/SMT solvers, I suggest a new way to attack the Orthogonal Vectors Conjecture (and possibly refute it). That is, we can potentially use practical SAT/SMT solvers to improve the worst-case complexity of SAT!
• S. Hirahara, R. Ilango, and R. R. Williams. Beating Brute Force for Compression Problems [ECCC] [Quanta magazine]
  In 56th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2024).
Summary: Given any string, we can determine if there is a short program of at most $\ell$ bits long which will efficiently print the string in time $t$, using substantially more efficient circuits than the obvious brute-force method. In particular, brute-force gives us circuits of about $2^{\ell}\cdot t$ size, and we show that there are circuits of about $2^{4\ell/5} \cdot t$ size. Our tools are hashing tricks and circuit tricks: one component is to show that the Fiat-Naor data structure for function inversion (designed for random-access models of computation) can be implemented non-trivially with standard Boolean circuits. Note that Mazor and Pass proved similar results in ITCS'24.
• R. Williams. Self-Improvement for Circuit Analysis Problems [ECCC] [pdf]
  In 56th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2024).
Summary: This paper describes a phenomenon that I call "self-improvement": given a circuit analysis algorithm (SAT, $\#$SAT, QSAT) that is ``somewhat efficient'' (say, running in $1000^k + n^{1+o(1)}$ time on circuits of size $n$ with $k$ inputs), one can apply the algorithm to itself in a non-trivial way, to obtain more efficient algorithms (running in $(1.0001)^k + n^{1+o(1)}$ time, for example, which would contradict the Exponential Time Hypothesis). This phenomenon has interesting implications for both circuit complexity and fine-grained complexity. For example, I use it to show that the Circuit Evaluation problem requires $n^{1.1}$ size depth-two symmetric circuits (in the uniform setting).
• G. Bathie and R. R. Williams. Towards Stronger Depth Lower Bounds. [LIPIcs]
  In 15th Annual Innovations in Theoretical Computer Science Conference (ITCS 2024).
Summary: The best known depth lower bounds for an explicit function in $NP$ have the form $(3-o(1))\log_2 n$. Similarly, the best formula size lower bound is only $n^{3-o(1)}$. We make progress on the problem of improving this factor of 3, in two different ways. First, we show that slightly faster $\#$SAT algorithms for formulas of size only $n^{2+2\varepsilon}$ would imply new lower bounds against formulas of $n^{3+\varepsilon}$ size, for any $\varepsilon > 0$. This is interesting in that the circuit-analysis algorithm only has to work for ``small'' formulas, in order to achieve a lower bound for ``large'' formulas. Second, we prove that the SAT problem requires uniform NAND circuits of depth at least $4 \cos(\pi/7) \log_2 n \geq 3.603 \log_2 n$. (Recall that the best-known time lower bound for solving SAT with $n^{o(1)}$-space algorithms is $n^{2\cos(\pi/7)} \geq n^{1.801}$, proved in CCC'07.)
• C. Jin, R. R. Williams, and N. Young. A VLSI Circuit Model Accounting for Wire Delay. [LIPIcs]
  In 15th Annual Innovations in Theoretical Computer Science Conference (ITCS 2024).
Summary: Engineers are increasingly turning to highly-parallel custom VLSI chips to implement expensive computations. Motivated by this development, we revisit the theory of VLSI. In VLSI design, the gates and wires of a logical circuit are placed on a 2-dimensional chip with a small number of layers. Traditional VLSI models use gate delay to measure the time complexity of the chip, ignoring the lengths of wires. However, as technology has advanced, wire delay has also become an important mmeasure. We define and study the wire-delay VLSI model for this purpose, proving nearly tight upper and lower bounds on the time delay of chips for solving several basic problems.

• L. Chen, R. Tell, and R. R. Williams. Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization [ECCC]
  In 64th Annual Symposium on Foundations of Computer Science (FOCS 2023).
Summary: Following up on the notion of ``constructive separations'' from our FOCS'21 paper, we identify several equivalences between the tasks of efficiently derandomizing randomized algorithms, and efficiently producing ``bad'' inputs which witness that a lower bound is true. Our work unifies several previous works which show equivalences between derandomization and constructive lower bounds.
• S. Akmal, V. Vassilevska Williams, R. R. Williams, Z. Xu. Faster Detours in Undirected Graphs [LIPIcs]
  In 31st Annual European Symposium on Algorithms (ESA 2023).
Summary: In this paper we study $k$-Detour (and $k$-Longest Detour) on undirected graphs. Given a graph $G$, nodes $s$ and $t$, and a positive integer $k$, we want to know if there is a simple path from $s$ to $t$ of exactly (or at least) length $d + k$, where $d$ is the shortest distance from $s$ to $t$. We give faster randomized and deterministic algorithms for these problems, as a function of the parameter $k$.
• R. Ilango, J. Li, and R. R. Williams. Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic [ECCC]
  In 55th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2023).
Summary: The "Range Avoidance" problem asks, given a circuit $C$ with more output bits than input bits, to find a string not in the range of the circuit. Randomly sampling strings will work with decent probability; is there a deterministic polynomial time algorithm? The main result of this paper is that, assuming Indistinguishability Obfuscation and $NP \neq coNP$, the answer is no! This is rather counterintuitive, considering that it is also believed that every randomized algorithm can be made deterministic.
• R. Williams. The Power of Constructing Bad Inputs. [EATCS website]
  Bulletin of the EATCS No. 139, February 2023.
Summary: A lower bound, showing that a function $f$ cannot be computed by some class $C$ of algorithms, necessarily shows that for every algorithm $A$ in $C$, there must exist a “bad” input $x$ such that $f(x) \neq A(x)$. We consider the computational complexity of generating such bad inputs for a given $f$ and class $C$, and we study how the complexity of this task relates to existing (and major open problems in) lower bounds.
• N. Vyas and R. R. Williams. On Oracles and Algorithmic Methods for Proving Lower Bounds. [ECCC] [youtube] [conference version (warning: has a bug!)]
  In 14th Annual Innovations in Theoretical Computer Science Conference (ITCS 2023).
Summary: This paper is really two sub-papers. The first sub-paper studies the problem of proving circuit lower bounds via algorithms for a problem called Missing String: given a list of $m$ strings of length $n$, with $m < 2^n$, find a string not on the list. We show in multiple ways how algorithms for Missing String can translate directly into lower bounds (intuitively, Missing String generalizes diagonalization in a natural way: if the list contains all "easy" functions, then algorithms for finding a string not on the list correspond to algorithmic ways to choose a "hard" function). The second sub-paper shows how the algorithmic method for proving circuit lower bounds (using circuit-analysis algorithms to prove circuit lower bounds) does not relativize in one particular way.
Important note: there is a bug in Theorem 1.10 of the conference version. See the ECCC version for a correction. It turns out the negation of Theorem 1.10 is true, and there is a relativizing proof from derandomization to circuit lower bounds! We are grateful to Jiatu Li for his help.
• L. Chen, R. R. Williams, and T. Yang. Black-Box Constructive Proofs Are Unavoidable. [LIPIcs]
  In 14th Annual Innovations in Theoretical Computer Science Conference (ITCS 2023).
Summary: In prior work ("Natural Proofs Versus Derandomization", STOC'13), we showed that there exist poly-time computable Boolean function properties useful against $P/poly$ if and only if $NEXP$ is not contained in $P/poly$. Our main result here is that the equivalence is extended in a rather strong way using probabilistically checkable proofs, to show that there are Boolean function properties computable polylogarithmic randomized time that are useful against $P/poly$, if and only if $NEXP$ is not in $P/poly$.