"...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

• N. Vyas and R. R. Williams. On Oracles and Algorithmic Methods for Proving Lower Bounds. [pdf]
  In 14th Annual Innovations in Theoretical Computer Science Conference (ITCS 2023).
Summary: This paper is 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, in multiple strong ways, how the algorithmic method for proving circuit lower bounds (using circuit-analysis algorithms to prove circuit lower bounds) does not relativize. On the one hand, this is bad news for the algorithmic method: it would be more general if we could say that circuit-analysis algorithms (with oracles) imply lower bounds for functions (with oracles). On the other hand, since we can actually use the method to prove lower bounds, perhaps the relativization barrier was unavoidable...

• R. Fagin, J. Lenchner, N. Vyas, and R. R. Williams. On the Number of Quantifiers as a Complexity Measure. [LIPICS]
  In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022).
Summary: We considered the number of quantifiers needed to express a given task as a measure of complexity, proving several new upper bounds and lower bounds on this measure. For example, it is well-established that $s$-$t$ connectivity with distance at most $k$ (over the vocabulary of graphs) needs at least $\log_2 k$ quantifiers (from lower-bounding the quantifier rank). We prove a new upper bound of $3 \log_3(k)+O(1) \leq 1.893 \log_2(n) + O(1)$. It is an interesting open problem to close the gap between the upper and lower bound.
• L. Chen, C. Jin, R. R. Williams, and H. Wu. Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions [arXiv]
  In 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2022).
Summary: An amazing algorithm of Beame, Clifford, and Machmouchi (FOCS'13) shows how to solve Element Distinctness in $\tilde{O}(n^{1.5})$ time and $poly(\log n)$ space using access to a random oracle, i.e., random/direct access to the bits of a long random bitstring. This paper shows how to solve Element Distinctness with typical (one-way) access to a random bit string; no random oracle is required. The algorithmic result is a triumph of the three student co-authors, with only very minor assistance from me. Warning: The paper is very long!
• S. Akmal, L. Chen, C. Jin, M. Raj, and R. R. Williams. Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity [ECCC]
  In 13th Annual Innovations in Theoretical Computer Science Conference (ITCS 2022).
Summary: We give essentially optimal Merlin-Arthur protocols for several core fine-grained problems, including 3-SUM, APSP, and Zero-Weight 4-Cycle. We also give interesting new Merlin-Arthur protocols for $k$-SAT and QBF. There's a lot of Merlin-Arthur goodness in here, so if you like your proofs verified with randomness, you might like this.
• B. Chapman and R. R. Williams. Smaller ACC0 Circuits For Symmetric Functions [arXiv]
  In 13th Annual Innovations in Theoretical Computer Science Conference (ITCS 2022).
Summary: Surprisingly (at least to me) we show that depth-3 circuits with modular counting gates can compute any symmetric Boolean function in subexponential size. More precisely, for every $\varepsilon > 0$ there is a constant $m > 2$ such that depth-3 circuits with $MOD_m$ gates can compute any symmetric function in $O(2^{n^{\varepsilon}})$ size. We generalize this result to a size-depth tradeoff upper bound, and we prove that the dependence on modulus and depth in our size bound is essentially optimal under a natural conjecture about $TC0$. Perhaps the most surprising thing about this paper is that we did not have to discover any radically new math to prove these statements; we only had to apply known number-theoretic tools in just the right ways.

• A. Mudigonda and R. R. Williams. Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers [lipics]
  In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021).
Summary: We extend time-space tradeoffs for SAT to lower bounds for simulating linear-time Merlin-Arthur protocols, and lower bounds for linear-time Quantum Merlin-Arthur protocols. So I learned a little quantum, which is nice.
• A. Golovnev, A. S. Kulikov, and R. R. Williams. Circuit Depth Reductions [lipics]
  In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021).
Summary: We show how to convert various computational models (circuits and formulas) into "low-depth" ones. For example, one result in this paper is that every $3.9n$-size circuit over the arbitrary fan-in two basis can be simulated by a depth-three circuit of size $2^{n-o(n)}$ with bottom fan-in $16$. Therefore, strong enough lower bounds against depth-three circuits (with constant bottom fan-in) would yield lower bounds against arbitrary circuits. The proofs are extraordinarily non-relativizing BTW, good luck fitting an oracle in there.
• C. Jin, N. Vyas, and R. R. Williams. Fast Low-Space Algorithms for Subset Sum [pdf]
  In 32st ACM-SIAM Symposium on Discrete Algorithms (SODA 2021).
Summary: The classical dynamic programming algorithm for Subset Sum with target $t$ takes about $nt$ time and $\Omega(t)$ space. We present several methods that can drastically reduce the space complexity (for example polylogarithmic in t and n), while retaining a similar running time.
• B. Chapman and R. R. Williams. Black-Box Hypotheses and Lower Bounds [LIPIcs]
  In Mathematical Foundations of Computer Science (MFCS 2021)
Summary: The Black-Box Hypothesis (a.k.a. "Scaled-Down Rice's Theorem Hypothesis") was first proposed by Barak et al. (CRYPTO'01) in their groundbreaking paper formalizing program obfuscation. It posits that every "semantic" property of functions with polynomial-size circuits that can be efficiently decided given the description of the circuit, can also be decided given only black-box access to the circuit. We study extensions of this hypothesis, where the circuit "boxes" being studied and the "analysts" studying circuits can vary in their own complexity, and show how known lower bounds can imply variants of the black-box hypothesis in an automatic way.
• L. Chen, C. Jin, R. Santhanam, and R. R. Williams. Constructive Separations and Their Consequences [ECCC]
  In 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS 2021)
Summary: This paper tries to address questions of the form "what would a proof of $P \neq PSPACE$ have to look like?" Let ${\cal A}$ be a class of algorithms. Informally, we say that a lower bound $f \notin {\cal A}$ is $P$-constructive if, given any "weak" algorithm $A$, there is a polynomial-time algorithm $R_A$ which (on the string $1^n$) prints an $n$-bit input $x$ such that $f(x) \neq A(x)$. (That is, we can efficiently "refute" any algorithm using another algorithm.) Building on [GST05], we show that essentially all major separation problems regarding polynomial time are $P$-constructive, and making many simple known lower bounds $P$-constructive would in fact imply strong circuit lower bound and derandomization consequences. Therefore, "constructivity" is a property that we want lower bounds to have (it's kind of the opposite of a complexity barrier).
• S. Akmal and R. Williams. MAJORITY-3SAT (and Related Problems) in Polynomial Time [arXiv]
  In 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS 2021)
Summary: CNF-SAT and 3SAT are $NP$-complete, DNF-TAUTOLOGY and 3DNF-TAUTOLOGY are $coNP$-complete, Quantified-CNF-SAT and Quantified-3SAT are $PSPACE$ complete, ... it seems that 3CNFs and 3DNFs are just as powerful at expressing hard problems as unrestricted CNF and DNF. Great. Well, it had been known for 40 years that MAJORITY-CNF-SAT is $PP$-complete, meaning that we cannot efficiently determine whether at least half of a given CNF's assignments are satisfying, unless $P=NP$ and in fact $\#SAT$ is in $FP$. However, the complexity of MAJORITY-3SAT (where we determine if at least half of a given 3CNF's assignments are satisfying) had remained open. Shyan and I show that MAJORITY-3SAT is actually solvable in linear time! And a similar fast algorithm exists for any fraction (besides $\frac{1}{2}$) and any constant clause width $k$ (besides 3)! And other generalizations hold too! Could all this hint at, maybe, $P=NP$? Or maybe it's just that $k$CNFs aren't so great at expressing certain properties? (Huge spoiler: it's the second one.)

• L. Chen, X. Lyu, and R. R. Williams. Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization [ECCC]
  In 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS 2020).
Summary: This paper (finally!) shows that from non-trivial circuit-analysis algorithms, one can derive circuit complexity lower bounds that hold for all but finitely many inputs. (Previously, such lower bounds for $ACC$ were only known to hold for infinitely many input lengths. Which doesn't make intuitive sense, because the circuit-analysis algorithms for $ACC$ work on all inputs.) Psychologically this is a huge advance; thanks to Xin and Lijie for helping make this possible!
• L. Chen, C. Jin, and R. R. Williams. Sharp threshold results for computational complexity [ECCC]
  In 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020).
Summary: This paper is great, but Virginia says I have to leave the office now, so I will write a real summary later.
• N. Vyas and R. R. Williams. Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms [lipics]
  In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Invited to special issue of Theory of Computing Systems.
  
Summary: We show how slightly faster-than-2^n #SAT algorithms for a circuit class ${\cal C}$ actually implies lower bounds for circuit classes that are stronger than ${\cal C}$, namely $f \circ {\cal C}$ for what we call ``sparse'' symmetric functions $f$. (An example of a sparse symmetric function is EXACT or EMAJ, which outputs 1 if and only if the sum of the input bits equals a desired value.) Subsequent work by Chen and Ren (STOC 2020) shows how #SAT (and CAPP) algorithms for ${\cal C}$ implies MAJORITY of ${\cal C}$ lower bounds.
• J. Alman, T. M. Chan, and R. R. Williams. Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions [pdf]
  In 30th ACM-SIAM Symposium on Discrete Algorithms (SODA 2020).
  

• L. Chen, C. Jin, and R. R. Williams. Hardness Magnification for All Sparse NP Languages [ECCC]
  In 60th IEEE Symposium on Foundations of Computer Science (FOCS 2019).
  Summary: We show how very weak lower bounds on any sparse $NP$ problem (just slightly improving the state-of-the-art) would imply fixed-polynomial circuit lower bounds for $NP$. We also show (among other results) that a $n^{3+\epsilon}$ size formula lower bound for solving the search version of $MCSP[2^{o(n)}]$ would imply major lower bounds such as $\#P \not\subset NC$.

• A. Bjorklund, P. Kaski, and R. R. Williams. Solving systems of polynomial equations over GF(2) by a parity-counting self-reduction [DROPS]
  In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019).
  Summary: We improve on the known exact algorithms for solving systems of degree-$d$ equations over the field of two elements.

• A. Bjorklund and R. R. Williams. Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors [DROPS]
  In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019).
  Summary: We show how a known reduction for computing permanents can be used to obtain a deterministic $2^{n-n/O(r)}$ time algorithm for computing permanents over arbitrary rings of $r$ elements, along with other results. The key insight is a reduction to a new fine-grained problem called "dissimilar vectors" (basically equivalent to orthogonal vectors).

• N. Vyas and R. R. Williams. On Super Strong ETH [full version submitted to JAIR]
  In 22nd International Conference on Theory and Applications of Satisfiability Testing (SAT 2019).
  Best Paper Award. Invited to JAIR special issue.
  Summary: The Super Strong ETH, proposed in 2015, posits that all correct worst-case $k$-SAT algorithms must take at least $2^{n-n/\Theta(k)}$ time --- this bound is achieved simultaneously by local search, backtracking, dynamic programming, and algebraic methods. We prove the hypothesis is false for random $k$-SAT (aggressive random restarts with unit propagation works with high probability) and we show the hypothesis is equivalent to the version for Unique-$k$-SAT.

• L. Chen, D. M. McKay, C. D. Murray, and R. R. Williams. Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems [ECCC]
  In 34th Computational Complexity Conference (CCC 2019).
  Summary: Some canonical circuit lower bounds follow from using Karp-Lipton thms. But is this the "right" way to prove such results? We show in interesting open cases such as $P^{NP}$, proving circuit lower bounds is in fact equivalent to proving a Karp-Lipton theorem sufficient for the lower bound. We also establish some (weak) hardness magnification results, such as: "if there is a polynomially-sparse problem in $NP$ which does not have $n^{1.001}$-size circuits, then $NEXP$ does not have $2^{o(n)}$-size circuits."

• L. Chen and R. R. Williams. Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity [DROPS]
  In 34th Computational Complexity Conference (CCC 2019).
  Summary: We further tighten the connections between non-trivial CAPP algorithms and circuit lower bounds against nondeterministic time classes. Two interesting byproducts are: (1) "If the probability of acceptance of MAJ of MAJ circuits of polynomial-size can be additively approximated in $2^n/n^{\omega(1)}$ time, then $NEXP$ does not have depth-two linear threshold circuits with arbitrary weights." (2) All lower bounds from the CCC'18 paper on "sums of simple functions" can be extended to "approximate sums of simple functions", so e.g. depth-two neural networks of fixed-polynomial size cannot approximately compute all $NP$ functions.

• D. M. McKay, C. D. Murray, and R. R. Williams. Weak Lower Bounds on Resource-Bounded Compression Imply Strong Separations of Complexity Classes [camera-ready pdf]
  In 51st ACM Symposium on Theory of Computing (STOC 2019).
  Summary: Problems such as the Minimum Circuit Size Problem on polynomial-size circuits are widely believed (under cryptographic assumptions) to not have polynomial-size circuits. We show that extremely modest-looking lower bounds on problems of this kind (e.g., a time-space product lower bound of $\Omega(N \cdot (\log N)^c)$ for all $c > 0$, or a circuit size lower bound of $\Omega(N \cdot (\log N)^c)$ for all $c > 0$) would already imply major complexity class separations such as $P \neq NP$ or $NP \not\subset P/poly$. Our results extend and strengthen "hardness magnification" results of previous authors.

• L. Chen and R. R. Williams. An Equivalence Class for Orthogonal Vectors [arXiv]
  In 29th ACM-SIAM Symposium on Discrete Algorithms (SODA 2019).
  Summary: We show that the simple Orthogonal Vectors problem is fine-grained equivalent to several other fundamental point problems, such as finding a pair of vectors with maximum inner product, finding a pair that $100$-approximates the maximum inner product, approximating the bichromatic closest pair in the $\ell_1$ and $\ell_2$ norms, and approximating the furthest pair in $\ell_1$ and $\ell_2$ norms. Thus we get an equivalence between approximation and exact solutions for several fine-grained problems. We also give some equivalences for data structure problems, and apply our reductions to give a some new algorithms.

• D. M. McKay and R. R. Williams. Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle [DROPS]
  In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019).
  Summary: Among several other results, we show that the problem of printing a satisfying assignment to a given Boolean formula requires time-space product at least $n^{2-o(1)}$, even in a model of computation that has random access to a sequence of random bits (a random oracle).

• D. M. Kane and R. R. Williams. The Orthogonal Vectors Conjecture for Branching Programs and Formulas [DROPS]
  In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019).
  Summary: We prove the Orthogonal Vectors conjecture when the computational model is a Boolean formula with symmetric function gates of unbounded fan-in and when the model is a branching program. That is, we prove quadratic-size lower bounds for solving Orthogonal Vectors in these models.

• R. R. Williams. Some Estimated Likelihoods for Computational Complexity [pdf]
  Invited paper in the Springer LNCS 10,000 volume.
  Summary: Most of my opinions about complexity theory, collected in one PDF. Wowee!

• R. R. Williams. Limits on Representing Boolean Functions by Linear Combinations of Simple Functions: Thresholds, ReLUs, and Low-Degree Polynomials [DROPS]
  In 33rd Computational Complexity Conference (CCC 2018).
  Summary: We find functions in $NP$ that do not have depth-two neural nets with sign (or ReLU) activation functions of size $n^k$, for any constant $k \geq 1$. We prove similar results for representing Boolean functions with real-valued linear combinations of low-degree polynomials over a finite field. Both are special cases of a general framework (building on the STOC'18 paper) which shows how to lift non-trivial $\#SAT$ algorithms for a class ${\mathcal C}$ to lower bounds for linear combinations of functions from ${\cal C}$.

• C. D. Murray and R. R. Williams. Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP [pdf]
  In 50th ACM Symposium on Theory of Computing (STOC 2018). Invited to special issue of SICOMP (2020).
  Also available on ECCC.
  Summary: We significantly weaken the complexity of hard functions obtained through the "circuit SAT algorithms to circuit lower bounds" framework that has been developed over the last several years, in a generic way.

• R. Williams. Counting Solutions to Polynomial Systems via Reductions [pdf]
  In 1st Symposium on Simplicity in Algorithms (SOSA 2018).

• A. Lincoln, V. Vassilevska W., and R. Williams. Tight Hardness for Shortest Cycles and Paths in Sparse Graphs [conference version]
  In 28th ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).

• R. Williams. On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity in Computational Geometry. [conference version] [arXiv]
  In 28th ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).

• A. Bjorklund, P. Kaski, and R. Williams. Generalized Kakeya Sets for Polynomial Evaluation and Faster Computation of Fermionants [pdf]
  In 12th International Sympsium on Parameterized and Exact Computation (IPEC 2017).
  Summary: We show how a generalized notion of Kakeya sets (and their construction) can be used to evaluate a multivariate polynomial on many points faster than the naive algorithm by organizing the evaluation in a new way; we use this to improve the best known algorithm for computing the permanent of an n by n matrix over the integers (as well as a generalization of the permanent, called the fermionant).

• A. Abboud, A. Rubinstein, and R. Williams. Distributed PCP Theorems for Hardness of Approximation in P [pdf]
  In 58th IEEE Symposium on Foundations of Computer Science (FOCS 2017) .
  Summary: Given a set of $n$ Boolean vectors in $d$ dimensions, how efficiently can one find a pair that has approximately maximum inner product? Can it be done in $n^{2-\epsilon} poly(d)$ time? We show that for many similarity search problems (find a pair of points minimizing or maximizing a certain measure) these problems cannot even be approximately solved in truly sub-quadratic time, under the Strong Exponential Time Hypothesis (in fact, the Orthogonal Vectors Conjecture suffices). The starting point is a new distributed four-party communication model of probabilistically checkable proofs, and (following Aaronson and Wigderson) an efficient protocol for verifying inner products in this model.

• C. D. Murray and R. Williams. Easiness Amplification and Uniform Circuit Lower Bounds [lipics]
  In 32nd Computational Complexity Conference (CCC 2017).
  Summary: Hardness amplification studies the task: given a function that is ``somewhat hard'' for a computational model, construct a similar function that is much harder. Here, the necessary resource bound of the computational model is being amplified. In what we call ``easiness amplification'' one starts by assuming that a somewhat-hard function is easy (in some sense) and shows that a class of seemingly harder functions are also easy (in a similar sense). Here, the class of easy functions is being amplified while the resources needed remain about the same; a canonical example is if $P=NP$ then $PH=P$. In this paper, we give an easiness amplification theorem for circuit complexity, and use it to prove unconditional circuit lower bounds for natural functions in $P$.

• J. Alman and R. Williams. Probabilistic Rank and Matrix Rigidity [arXiv]
  In 49th ACM Symposium on Theory of Computing (STOC 2017).
  Summary: Hadamard matrices ain't rigid enough to prove lower bounds on them. Sign-rank rigidity lower bounds imply lower bounds for depth-two linear threshold circuits. The "randomized mod-p communication complexity" of Inner Product Modulo 2 is "equivalent" to the rigidity of Walsh-Hadamard over ${\mathbb F}_p$.

• K. G. Larsen and R. Williams. Faster Online Matrix-Vector Multiplication [arXiv]
  In 27th ACM-SIAM Symposium on Discrete Algorithms (SODA 2017).
  Summary: The Online Matrix-Vector Conjecture roughly says that there is no algorithm which can compute $n$ Boolean $n \times n$ matrix-vector multiplications on-line, in $O(n^{1.999})$ amortized time per vector. We show that the conjecture is false in the cell-probe model, obtaining $O(n^{7/4})$ time per vector. We also derive a uniform algorithm which, after seeing only $2^{\omega(\sqrt{\log n})}$ vectors, computes all subsequent matrix-vector multiplications in $n^2/2^{\Omega(\sqrt{\log n})}$ time.

• D. Lokshtanov, R. Paturi, S. Tamaki, R. Williams, and H. Yu. Beating Brute Force for Systems of Polynomial Equations over Finite Fields [pdf]
  In 27th ACM-SIAM Symposium on Discrete Algorithms (SODA 2017).
  Summary: For small fields of order $q$, we show how to solve an arbitrary system of polynomial equations of degree at most $k$, in time $q^{n-n/O(k)}$ unconditionally (no unproven algebraic assumptions). For large fields we also get an improvement, but the form of the bound is not as nice. We also give some extensions, for example to depth-four ($\Pi \Sigma \Pi \Sigma$) circuits over $\mathbb{F}_2$.

• J. Gao, R. Impagliazzo, A. Kolkolova, and R. Williams. Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications [pdf]
  In 27th ACM-SIAM Symposium on Discrete Algorithms (SODA 2017).
  Summary: We consider the Orthogonal Vectors (OV) problem defined on *sparse* instances (with $m$ 1s in all vectors). Surprisingly, we find that this problem is *complete* for all first-order properties on sparse structures (in contrast with the LICS 2014 paper below), in the sense that faster algorithms for OV imply faster algorithms for all other first-order properties. We also use prior algorithms for OV to get a generic algorithmic improvement on solving all first-order properties on sparse structures.

• J. Alman, T. M. Chan, and R. Williams. Polynomial Representations of Threshold Functions and Algorithmic Applications [arXiv]
  In 57th IEEE Symposium on Foundations of Computer Science (FOCS 2016)
  Summary: Josh and I derandomize our probabilistic polynomials from FOCS'15 (and enlist the powers of T. M. Chan) to combine them with Chebyshev polynomials, obtaining surprisingly low-degree constructions of "probabilistic polynomial threshold functions". These lead to faster algorithms for MAX-SAT and other Circuit-SAT variants, Offline Hamming Nearest (and Furthest) Neighbors, Offline Approximate Nearest (and Furthest) Neighbors, and new lower bounds for circuits with linear threshold gates.

• A. Lincoln, V. Vassilevska Williams, J. R. Wang, and R. Williams. Deterministic Time-Space Trade-Offs for k-SUM [LIPIcs]
  In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
  Summary: Given any $3$-SUM algorithm running in sub-quadratic time, we show how to convert it into a sub-quadratic time algorithm that also uses about $n^{1/2}$ space. Similar results hold for the general $k$-SUM problem.

• R. Williams. Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Computation. [ECCC]
  In 31st Conference on Computational Complexity (CCC 2016)
  Summary: The Strong ETH (roughly) says that $CNF$-$SAT$ can't be solved in $(2-\epsilon)^n$ time for any $\epsilon > 0$. The Nondeterministic SETH says that $CNF$-$UNSAT$ can't be proved by proofs of $(2-\epsilon)^n$ size in $(2-\epsilon)^n$ time. The Merlin-Arthur SETH and Arthur-Merlin SETH extend these hardness hypotheses to probabilistic proof systems. We refute the latter two hypotheses, as a corollary of a general result about proofs of batch computation: given an arithmetic circuit $C$ on $n$ variables computing a polynomial of degree $d$, and $K$ inputs to evaluate $C$ on, there is a non-interactive proof system where a Prover can convince a randomized Verifier of the values of $C$ on the $K$ inputs, using only $\tilde{O}(K\cdot n \cdot d + |C|)$ time. This yields several results, such as a Merlin-Arthur proof system for $\#SAT$ on $2^{o(n)}$-size formulas, with proofs of about $2^{n/2}$ size that are verifiable in about that much time.

• A. Abboud, T. D. Hansen, V. Vassilevska Williams, and R. Williams. Simulating Branching Programs With Edit Distance: A Polylog Shaved is a Lower Bound Made [arXiv]
  In 48th ACM Symposium on Theory of Computing (STOC 2016).
  Summary: We show how an $n^{2-\epsilon}$ time algorithm for Edit Distance would have significant implications beyond refuting the Strong Exponential Time Hypothesis (Backurs and Indyk, STOC'15). For example, one could solve satisfiability of $o(n)$ depth circuits in $(2-\delta)^n$ time for some $\delta > 0$. The reduction framework is powerful enough that even shaving sufficiently large polylog factors from the $n^2$ time bound of Edit Distance would imply new $NC^1$ circuit lower bounds.

• D. M. Kane and R. Williams. Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-2 and Depth-3 Threshold Circuits [ECCC]
  In 48th ACM Symposium on Theory of Computing (STOC 2016).
  Summary: We give an explicit function in $P$ for which every majority of depth-two linear threshold circuits (with unbounded weights) needs about $n^{1.5}$ gates and $n^{2.5}$ wires, simultaneously. We also show that Andreev's function (computable by a depth-three majority circuit of $O(n)$ size) requires about the same gate and wire lower bound to be computed with depth-two linear threshold circuits. A key tool is the Littlewood-Offord Lemma, which we use to analyze the effect of random restrictions on the inputs of low-depth threshold circuits.

• T. M. Chan and R. Williams. Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky [pdf]
  In 26th ACM-SIAM Symposium on Discrete Algorithms (SODA 2016). Invited to special issue of TALG.
  Summary: We show how to solve the dense case of all-pairs shortest paths deterministically in $n^3/2^{\Omega(log^{1/2} n)}$ time, analogous to the randomized algorithm of STOC'14. We also derandomize the algorithms based on orthogonal vectors from SODA'15. Modifying the ideas, we can also count the number of satisfying assignments to a $k$-CNF in $2^{n(1-1/O(k))}$ time. Learn about the power of small-biased sets and modulus-amplifying polynomials in algorithms!

• J. Alman and R. Williams. Probabilistic Polynomials and Hamming Nearest Neighbors [pdf]
  In 56th IEEE Symposium on Foundations of Computer Science (FOCS 2015).
  Summary: We prove that every symmetric Boolean function on $n$ variables can be simulated by a probabilistic polynomial (over any field) with error at most $\varepsilon$ and degree at most $O(\sqrt{n \log(1/\varepsilon)})$. This matches the old lower bound of Razborov and Smolensky for the MAJORITY function. We apply this polynomial construction to obtain a sub-quadratic algorithm for computing Nearest Neighbors in the Hamming metric: given a database of $n$ Boolean vectors in $c \log n$ dimensions, and given $n$ query vectors in $c \log n$ dimensions, we can exactly compute the nearest neighbor in the Hamming metric for all $n$ queries in only $n^{2-1/O(c \log^2 c)}$ randomized time. This is ``truly subquadratic'' for $O(\log n)$ dimensions.

• D. Van Gucht, R. Williams, D. Woodruff, and Q. Zhang. The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication [pdf]
  In 34th ACM Symposium on Principles of Database Systems (PODS 2015)
  Summary: There are quite a few results in this paper, but here are my favorites... Suppose Alice holds a Boolean $m \times n$ matrix, Bob holds a Boolean $m \times n$ matrix, and the (Boolean) product of these matrices has at most $k$ nonzeroes. We show the randomized communication complexity of matrix multiplication is only $\tilde{O}(\sqrt{k}\cdot n)$, and this is tight up to polylogarithmic factors. We apply an algorithmic version of this result to show how to compute the transitive closure of a graph with $\tilde{O}(n)$ edges in the output, in randomized $\tilde{O}(n^{1.5})$ time.

• C. Murray and R. Williams. On the (Non) NP-Hardness of Computing Circuit Complexity [journal version] [conference version]
  Theory of Computing Volume 13 (2017) Article 4 pp. 1-22, 2017
  Also in 30th Conference on Computational Complexity (CCC 2015)
  Summary: We study the Minimum Circuit Size Problem (MCSP), which is to determine the circuit complexity of a function given its truth table. The question of whether MCSP is NP-hard has been notoriously open for decades. We make progress in two ways: we show that for very restricted reductions that MCSP is provably not NP-hard, and for general reductions we prove that NP-hardness of MCSP would imply breakthrough separations in complexity theory. So, at the very least, if MCSP is NP-hard then the proof must be very different from known NP-hardness reductions.

• B. Chapman and R. Williams. The Circuit-Input Game, Natural Proofs, and Testing Circuits With Data [pdf]
  In Innovations in Theoretical Computer Science (ITCS 2015).
  Summary: We extend theorems on succinct strategies for zero-sum games to prove two results in circuit complexity. One, ``natural properties useful against self-checking circuits are equivalent to circuit lower bounds.'' Two, there is a theory of testing circuits via ``data complexity'' which is dual to that of circuit complexity: upper bounds on data complexity for testing are equivalent to lower bounds on circuit complexity.

• A. Abboud, R. Williams, and H. Yu. More Applications of the Polynomial Method in Algorithm Design [pdf]
  In 25th ACM-SIAM Symposium on Discrete Algorithms (SODA 2015).
  Summary: Building on the recent APSP algorithm (STOC 2014), we apply the polynomial method from low-depth circuit complexity to solve a number of combinatorial problems faster, such as orthogonal vectors, symmetric CSP, longest common substring with don't cares, etc.

• V. Vassilevska Williams, J. R. Wang, R. Williams, and H. Yu. Finding Four-Node Subgraphs in Triangle Time [pdf]
  In 25th ACM-SIAM Symposium on Discrete Algorithms (SODA 2015).
  Summary: For every four-node subgraph $H$ which is not the four-node clique or four-node independent set, we give a randomized algorithm for detecting an induced copy of $H$ in an $n$-node graph in $n^{\omega}$ time, where $\omega$ < $2.373$. We also extend the approach to sparse graphs, and derandomize the algorithm for the case of diamonds.

• R. Santhanam and R. Williams. Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity [pdf]
  In 25th ACM-SIAM Symposium on Discrete Algorithms (SODA 2015).
  Summary: We show how to improve over the $2^n$ cost of exhaustive search for many general cases of the Quantified Boolean Formula problem, and show in the remaining cases that similar algorithms would imply significant lower bounds for polynomial-size log-depth circuits.

• R. Williams. The Polynomial Method in Circuit Complexity Applied to Algorithm Design [pdf]
  In the 34th Foundations of Software Technology and Theoretical Computer Science Conference (FSTTCS 2014).
  Summary: A high-level survey of how circuit complexity methods have recently been applied to speed up polynomial-time algorithms.

• A. Abboud, K. Lewi, and R. Williams. Losing Weight by Gaining Edges [pdf]
  In European Symposium on Algorithms (ESA 2014).
  Summary: We give a randomized FPT reduction from k-SUM to k-Clique, which implies that k-SUM is W[1]-complete under such reductions. This reduction is one instance of a general technique for converting weighted problems into unweighted problems with pairwise constraints. There are a few other interesting applications to weighted problems.

• R. Williams. Algorithms for Circuits and Circuits for Algorithms: Connecting the Tractable and Intractable
  Two invited survey articles (one for mathematicians and one for complexity theorists), in:
  • Proceedings of the International Congress of Mathematicians (ICM 2014) [ICM 2014 version, pdf]
  • and 29th IEEE Conference on Computational Complexity (CCC 2014) [CCC 2014 version, pdf]
  Summary: The title of these papers highlights an emerging duality between two basic topics in algorithms and complexity theory. The papers survey two generic subjects (one in algorithms and one in complexity) and the connections that have been developed between them, focusing on connections between non-trivial circuit-analysis algorithms and proofs of circuit complexity lower bounds.

• R. Williams. Faster Decision of First-Order Graph Properties [pdf]
  In 23rd EACSL Conference on Computer Science Logic and 29th ACM-IEEE Symposium on Logic in Computer Science (CSL-LICS 2014).
  Summary: We show that for every first-order sentence of $k \geq 9$ variables in prenex normal form describing a graph property, one can decide if a given $n$-node graph satisfies the sentence in $n^{k-1+o(1)}$ time. (The previous best known algorithm was the trivial $O(n^k)$ time algorithm.) We observe using prior work that this running time is optimal, assuming the strong exponential time hypothesis.

• R. Williams. New Algorithms and Lower Bounds for Circuits With Linear Threshold Gates [arxiv]
  In 46th ACM Symposium on Theory of Computing (STOC 2014).
  Summary: We show that quasi-polynomial size ACC circuits augmented with arbitrary linear threshold gates at the bottom layer cannot simulate $\mathsf{NEXP}$, and give algorithmic results on the rapid evaluation of low-depth threshold circuits.

• R. Williams. Faster All-Pairs Shortest Paths via Circuit Complexity. [arxiv]
  In 46th ACM Symposium on Theory of Computing (STOC 2014).
  Summary: We show that the dense case of all-pairs shortest paths can be solved in $n^3/\log^k n$ time for all constants $k$. In particular, we reduce the problem of computing a min-plus matrix product to a small number of $\mathbb F_2$ matrix multiplications, using the Razborov-Smolensky method for converting low-depth $AC^0[\oplus]$ circuits into low-degree polynomials.

• R. Williams and H. Yu. Finding Orthogonal Vectors in Discrete Structures. [pdf]
  In 24th ACM-SIAM Symposium on Discrete Algorithms (SODA 2014).
  Summary: Given a discrete structure ${\cal S}$ (such as a ring or field) and a collection of $n$ vectors from ${\cal S}^d$, we consider the problem of finding a pair of vectors with inner product over ${\cal S}$. (The obvious algorithm takes $O(n^2 \cdot d)$ time.) We find that for every finite field, this problem is ``easy'' for low-dimensional vectors: it can be solved in $O(n\cdot poly(d))$ time, where the degree of the poly factor depends on the field. For structures such as ${\mathbb Z}_6$, the problem is surprisingly hard assuming the Strong ETH. Our algorithms are obtained by formulating a communication complexity version of the problem, and proving upper and lower bounds for it.

• R. Williams. Towards NEXP versus BPP?. [pdf]
  Invited paper in 8th International Computer Science Symposium in Russia (CSR 2013)
  Summary: We consider two hypotheses and show that either would imply $NEXP \neq BPP$, an infamous open problem in complexity theory. One hypothesis is a natural extension of our earlier work connecting Circuit SAT algorithms to $NEXP \not\subset P/poly$: e.g., if every polynomial-time samplable distribution ${\cal D}$ of circuits admits a slightly faster (than exhaustive search) algorithm for Circuit SAT that succeeds on a small measure of inputs from ${\cal D}$, then $NEXP \neq BPP$ follows.

• R. Santhanam and R. Williams. On Medium-Uniformity and Circuit Lower Bounds. Final conference version: [pdf]
  In 28th IEEE Conference on Computational Complexity (CCC 2013)
  Invited to the special issue for CCC'13. Journal version: [pdf]
  Summary: We study connections between ``medium-uniform'' circuits (where the complexity of generating a circuit is neither high nor low). There are two threads of results: one thread is a collection of new lower bounds such as $P$ does not have $P$-uniform circuits of size $n^k$, and another thread shows how to convert non-uniform assumptions into medium-uniform ones. For instance, if $NC^1$ is in non-uniform $TC^0$, then there is a subpolynomial-space algorithm which given any $NC^1$ circuit will generate an equivalent $TC^0$ one. This latter connection simplifies and strengthens the known implications between faster algorithms for circuit analysis and circuit lower bounds.

• R. Williams. Natural Proofs versus Derandomization. Draft of journal version: [pdf]
  In 45th ACM Symposium on Theory of Computing (STOC 2013)
  Invited to the special issue for STOC'13.
  Summary: A "natural proof" of a circuit lower bound satisfies three axioms: constructivity, largeness, and usefulness. It is widely believed that natural proofs are insufficient for proving strong circuit lower bounds. Which of the three axioms should "un-natural proofs" try to avoid? Usefulness is unavoidable, and heuristic arguments have been given for both constructivity and largeness. We show that the existence of circuit lower bounds for NEXP functions is equivalent to the existence of constructive proofs useful against the respective circuit class. We also show that there are no natural properties useful against a circuit class if and only if a particular form of strong derandomization is possible. These characterizations lead to several new theorems, including (NEXP/1 $\cap$ coNEXP/1) does not have $n^{\log n}$ size ACC circuits, and new unconditional derandomizations.

• B. Juba and R. Williams. Massive Online Teaching to Bounded Learners. [pdf]
  In Innovations in Theoretical Computer Science (ITCS 2013).
  Summary: Suppose you want to teach all consistent learners implementable with size-$s$ circuits a single concept, by broadcasting examples of the concept to all learners at once. Can one attain provable worst-case learning guarantees for every such learner? One of our results is that a randomly chosen sequence of examples will lead to $O(n\cdot s^2)$ mistakes for every learner, whp. In contrast, we also prove that a deterministic $2^{n}$-time generated sequence leading to less than $2^n$ mistakes would imply circuit lower bounds, namely $EXP \not\subset P/poly$.

• L. Hemaspaandra and R. Williams. An Atypical Survey of Typical-Case Heuristic Algorithms.
  Invited article in SIGACT News, December 2012. [arXiv]
  Summary: The survey is atypical, what else can I say? Read it now and believe me later. If you're interested in SAT solving, I would recommend reading Section 4.

• S. Buss and R. Williams. Limits on Alternation-Trading Proofs for Time-Space Lower Bounds.
  In 27th IEEE Conference on Computational Complexity (CCC 2012).
  Full version in Computational Complexity 24(3): 533-600 (2015); see ECCC.
  Summary: We show that new techniques are provably necessary in order to prove any better time-space lower bounds for the satisfiability problem. That is, the method of "alternation-trading proofs" used to establish that SAT cannot be solved in $n^{2\cos(\pi/7)}$ time and $n^{o(1)}$ space cannot prove an $n^{2\cos(\pi/7)+\varepsilon}$ time lower bound, for every $\varepsilon > 0$.

• R. J. Lipton and R. Williams. Amplifying Lower Bounds Against Polynomial Time With Applications.
  In 27th IEEE Conference on Computational Complexity (CCC 2012).
  Invited to the special issue for CCC'12. Journal version: [pdf]
  Summary: We exhibit a self-reduction for the P-complete Circuit Evaluation problem and give several consequences. In the full version, we focus on applications to the problem of separating PSPACE and P-uniform NC (a necessary step towards separating PSPACE from P). Our main result is that there is no $n^{2-\varepsilon}$-time algorithm that can print NC circuits solving the Quantified Boolean Formula problem. (Extending this to all polynomial-time algorithms would separate PSPACE from P-uniform NC.)

• R. Williams. A Casual Tour Around a Circuit Complexity Bound.
  Invited article in SIGACT News, September 2011. [arXiv]
  Summary: I try to motivate the proof that NEXP lacks nonuniform ACC circuits of polynomial size, by describing it from the perspective of someone trying to discover it. Breezy intuitions and pondering fill the pages. I hope you find it useful.

• E.J. Kim and R. Williams. Improved Parameterized Algorithms for Above Average Constraint Satisfaction.
  In 6th International Symposium on Parameterized and Exact Computation (IPEC 2011). [arXiv]
  Summary: We show (for example) how to satisfy at least $7m/8 + k$ clauses of any given 3-CNF formula (or report that it cannot be done), in $2^{O(k)}\cdot poly(m)$ time. This leads to a new framework for "hybrid algorithms" (proposed in SODA'06): for every $\varepsilon > 0$, there is a polynomial-time algorithm which, on every MAX 3SAT instance $F$, either outputs a $(7/8+O(\varepsilon))$-approximation to $F$, or outputs "TRY SOLVING." In the latter case, we provide a $2^{\varepsilon n}$ time algorithm which provably determines an optimal satisfying assignment to $F$. So we either "solve subexponentially" or "approximate better than worst-case."

• R. Williams. Non-Uniform ACC Circuit Lower Bounds.
  In 26th IEEE Conference on Computational Complexity (CCC 2011). Journal of the ACM 61(1), Article 2 (January 2014).
  [preliminary JACM version] ['Full' version] [Conference version] [Slides from the conference talk, in pptx]
  Best Paper Award, invited to the special issue for CCC'11 (regretfully declined).
  Summary: NEXP (Nondeterministic Exponential Time) does not have quasi-polynomial size ACC circuits, and related results.

• B. Kimelfeld, J. Vondrak, and R. Williams. Maximizing conjunctive views in deletion propagation.
  In ACM Symposium on Principles of Database Systems (PODS 2011), 187--198, 2011.
  Summary: We study a problem in database maintenance: suppose after a database query, one discovers some undesirable displayed results (perhaps they are erroneous); we would like to remove tuples from the database so that the undesirable result disappears but we maximize the number of other remaining results. This problem is ridiculously hard---so hard that it is not too hard to characterize those queries for which it can be approximated nontrivially (under $P \neq NP$).

• V. Vassilevska Williams and R. Williams. Subcubic Equivalences Between Path, Matrix, and Triangle Problems.
  In 51st IEEE Symposium on Foundations of Computer Science (FOCS 2010).
  A preliminary version: [pdf]
  Summary: We show that many long-studied problems with natural cubic time algorithms are all equivalent under a new notion of "subcubic reducibility" -- meaning that either all of them require about cubic time or none of them do. There are several surprises: for example, finding a negative edge-weighted triangle in truly subcubic time implies that all-pairs shortest paths is in truly subcubic time(!). Compare with our STOC'06 paper, which gives a truly subcubic algorithm for the triangle problem in the node-weighted case.

• J. Blocki and R. Williams. Resolving the complexity of some data privacy problems.
  In 37th International Colloquium on Automata, Languages, and Programming (ICALP 2010).
  Full version: [arXiv]
  Summary: We resolve several remaining open problems about the complexity of optimal K-anonymity and L-diversity.

• R. Impagliazzo and R. Williams. Communication complexity with synchronized clocks.
  In 25th IEEE Conference on Computational Complexity (CCC 2010).
  Conference version: [pdf]
  Summary: Russell and I play games with clocks and bits.

• R. Williams. Improving exhaustive search implies superpolynomial lower bounds.
  In 42nd ACM Symposium on Theory of Computing (STOC 2010).
  SIAM Journal on Computing 42(3):1218--1244, 2013. Special issue for STOC'10.
  Full version (draft): [pdf]
  Selected as a Notable Article in Computing 2013 by ACM Computing Reviews.

  

  
  Summary: Even very tiny improvements on exhaustive search would imply major lower bounds in computational complexity. For example, suppose you are given a Boolean circuit and wish to approximate the fraction of satisfying assignments within a fixed constant, say 1/6. If we are allowed randomness, this fraction can be approximated in essentially linear time. One result we show is that any deterministic algorithm with even a slight improvement over exhaustive search (which tries all assignments to the circuit) would imply NEXP does not have polynomial size circuits. Later in 2011, these ideas were extended to prove that NEXP does not have quasi-polynomial size ACC circuits.

• R. Williams. Alternation-Trading Proofs, Linear Programming, and Lower Bounds.
  In 27th Symposium on Theoretical Aspects of Computer Science (STACS 2010).
  Full version for ACM Transactions on Computation Theory (draft): [pdf]
  Some Maple code for proof searches can be found HERE (as a text file) and HERE (as a Maple worksheet).
  Summary: My computer proves time-space lower bounds for SAT and other problems. I conjecture that it (my computer) is doing the best possible with the current framework of ideas. Finally in CCC'12, Sam Buss and I proved the conjecture.

• M. Pătraşcu and R. Williams. On the Possibility of Faster SAT Algorithms.
  In 20th ACM-SIAM Symposium on Discrete Algorithms (SODA 2010).
  Full version: [pdf]
  Summary: We study several conjectures, and show that any one of them would imply that the "Strong Exponential Time Hypothesis" (informally, that CNF-SAT is not solvable in $1.999^n$) is false.

• N. Bansal and R. Williams. Regularity Lemmas and Combinatorial Algorithms.
  In 50th IEEE Symposium on Foundations of Computer Science (FOCS 2009).
  Conference version: [pdf]
  Full version (draft): [pdf]
  Summary: It's well-known that regularity lemmas (such as Szemeredi's) reveal surprising facts about graphs. We use them to give interesting new algorithms for Boolean matrix multiplication.

• L. Fortnow, R. Santhanam, and R. Williams. Fixed Polynomial Size Circuit Lower Bounds.
  In 24th IEEE Conference on Computational Complexity (CCC 2009). [pdf]
  Summary: We study several questions surrounding the existence of "fixed-polynomial" size circuit lower bounds for various complexity classes. Along the way, we study the natural notion of "oblivious witnesses" for problems.

• S. Diehl, D. van Melkebeek, and R. Williams. An Improved Time-Space Lower Bound for Tautologies.
  In International Computing and Combinatorics Conference (COCOON 2009).
  Invited to the special issue of Journal of Combinatorial Optimization for COCOON'09.
  Draft of journal version: [pdf]

• I. Koutis and R. Williams. Limits and applications of group algebras for parameterized problems.
  In 36th International Colloquium on Automata, Languages, and Programming (ICALP 2009).
  Conference version: [pdf]
  Erratum: there's a bug in the algorithm for k-leaf (Thm 2.3).
  Full version in ACM Trans. Algorithms 12(3): 31 (2016).
  Draft: [pdf]

• V. Vassilevska and R. Williams. Finding, Minimizing, and Counting Weighted Subgraphs.
  In 41st ACM Symposium on Theory of Computing (STOC 2009).
  Full version: [pdf]
  

• R. Williams. Finding Paths of Length k in O*(2^k) Time.
  Information Processing Letters 109(6):315--318, 2009. [arXiv]
  

• R. Williams. Applying Practice to Theory.
  Invited article in SIGACT News, December 2008. [arXiv]
  

• R. Williams. Maximum 2-satisfiability. Invited article in Encyclopedia of Algorithms, 2008. [pdf]
  

• R. Williams. Non-Linear Time Lower Bound for (Succinct) Quantified Boolean Formulas. ECCC [pdf]
  

• G. Blelloch, V. Vassilevska, and R. Williams. A New Combinatorial Approach to Sparse Graph Problems. [pdf]
  In 35th International Colloquium on Automata, Languages, and Programming (ICALP 2008).
  

• R. Williams. Algorithms and Resource Requirements for Fundamental Problems. Ph.D Thesis. [pdf]
  NOTE: My thesis improves upon several of the below papers, namely ICALP'04, CCC'05, and CCC'07. It gives an overview of time-space tradeoff lower bounds, introduces an automated theorem-proving strategy for discovering new lower bounds, generalizes my exact algorithm for 2-CSP in several ways, and shows how algorithmic progress on some problems in parameterized complexity would yield new algorithms for the satisfiability problem (which eventually turned into the SODA'10 paper with Patrascu).
  

• V. Vassilevska, R. Williams, and R. Yuster. All-Pairs Bottleneck Paths For General Graphs in Truly Sub-Cubic Time.
  In 39th ACM Symposium on Theory of Computing (STOC 2007). [pdf]
  

• R. Williams. Time-Space Tradeoffs for Counting NP Solutions Modulo Integers.
  In 22th IEEE Conference on Computational Complexity (CCC 2007).
  Journal of Computational Complexity 17(2), 2008. [pdf] Slides: [pdf]
  Invited to the special issue for CCC'07, received a Ron Book Prize for Best Student Paper.

• R. Williams. Matrix-Vector Multiplication in Sub-Quadratic Time (Some Preprocessing Required).
  In 17th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007). Full version: [pdf] Slides: [pdf]

• V. Vassilevska, R. Williams, and R. Yuster. Finding the smallest H-subgraph in real weighted graphs and related problems.
  In 33rd International Colloquium on Automata, Languages, and Programming (ICALP 2006). [pdf]
  Journal version to apper in ACM Transactions on Algorithms [arXiv].
  

• V. Vassilevska and R. Williams. Finding a Maximum Weight Triangle in O(n^(3-delta)) Time, With Applications.
  In 38th ACM Symposium on Theory of Computing (STOC 2006). [pdf]
  

• V. Vassilevska, R. Williams, and S. L. M. Woo. Confronting Hardness Using a Hybrid Approach.
  In 16th ACM-SIAM Symposium on Discrete Algorithms (SODA 2006). [pdf]

• R. Williams. Parallelizing Time With Polynomial Circuits.
  In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2005).
  Invited to the special issue for SPAA'05.
  Full version in Theory of Computing Systems, 2009. [pdf] Slides: [pdf]
  

• R. Williams. Better Time-Space Lower Bounds for SAT and Related Problems.[pdf] Slides: [pdf]
  In 20th IEEE Conference on Computational Complexity (CCC 2005).
  Full version in Journal of Computational Complexity 15(4), 2006.
  Invited to the special issue for CCC'05, received Ron Book Prize for Best Student Paper.
  NOTE: This work is basically obsolete. Essentially all results here have been improved in my Ph.D Thesis and the paper "Alternation-Trading Proofs, Linear Programming, and Lower Bounds" in STACS 2010.

• Carla Gomes and Ryan Williams. Approximation Algorithms.
  Book chapter in: Introduction to Optimization, Decision Support and Search Methodologies, Burke and Kendall (eds.), Springer.

• R. Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. [pdf]
  Theoretical Computer Science 348(2-3): 357--365, 2005.
  Preliminary version in International Colloquium on Automata, Languages, and Programming (ICALP 2004).
  Invited to the special issue for ICALP'04, received Best Student ICALP Paper Award.
  NOTE: This work is basically obsolete. Essentially all results in this paper have been improved in Chapter 6 of my Ph.D. thesis.
• A. Meyerson and R. Williams. On The Complexity of Optimal K-Anonymity. [pdf]
  In ACM Symposium on Principles of Database Systems (PODS 2004).

• R. Williams. On Computing k-CNF Formula Properties. [ps] [pdf]
  Older version in International Conference on Theory and Applications of Satisfiability Testing (SAT 2003).

• R. Williams, C. Gomes, and B. Selman. Backdoors To Typical Case Complexity. [ps][pdf]
  In International Joint Conference on Artificial Intelligence (IJCAI 2003).
  Slides available here.

• C. Gomes, and B. Selman, and R. Williams. On the connections between backdoors and heavy-tails on combinatorial search. [ps]
  In International Conference on Theory and Applications of Satisfiability Testing (SAT 2003).
  

• R. Williams. Algorithms for Quantified Boolean Formulas. [pdf]
  In 13th ACM-SIAM Symposium on Discrete Algorithms (SODA 2002). The above version is slightly revised from the original, correcting some typos.
  

• R. Williams. Defying Hardness With a Hybrid Approach. [pdf] CMU Technical Report CMU-CS-04-159, August 2004.
• A. Meyerson and R. Williams. General k-Anonymization is Hard. [ps] [pdf] CMU Technical Report CMU-CS-03-113.
• R. Williams. Abstract Complexity in Reflexive Type Theory. [ps]
  Accepted in Implicit Computational Complexity (ICC 2002). Unfortunately, I could not attend.
• Access Complexity. [pdf] The title stems from the emphasis on the accessibility of mass storage in characterizing complexity classes. Senior thesis in mathematics. Advisors: Juris Hartmanis and Anil Nerode. (Note: If you actually read this, please beware of bugs, typos, etc.)
• Brute-Force Search and Oracle-Based Computations. [ps] Spin-off of the thesis which discusses a deterministic "brute-force" search model that captures exactly P^{NP}, with implications. Unpublished manuscript.
• Space Efficient Reversible Simulations. [pdf]
  Work done while at a DIMACS REU and the PCMI Summer School at Institute for Advanced Study, Summer 2000. Please note that the above paper is more recent than the paper on my (very old) DIMACS page. Buhrman, Tromp and Vitanyi independently found similar results, though they are a bit less general. For this reason, I'll only post the work here. Below is their ICALP paper, which cites the above.
  H. Buhrman, J. Tromp, P. Vitanyi. Time and Space Bounds for Reversible Simulation. ICALP 2001.