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

• 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]
  To appear in 28th IEEE Conference on Computational Complexity (CCC 2013)
  Invited to the special issue for CCC'13.
  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 strengthenens the known implications between faster algorithms for circuit analysis and circuit lower bounds.

• R. Williams. Natural Proofs versus Derandomization. Draft of full version: [pdf]
  To appear 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; heuristic arguments have been given for both constructivity and largeness. We show NEXP circuit lower bounds are equivalent to the existence of constructive proofs useful against that circuit class. We also show that there are no natural properties useful against a circuit class if and only if a particular sort of derandomization is possible. These characterizations lead to several new theorems, including NEXP $\cap$ coNEXP does not have $n^{\log n}$ size ACC circuits, and new unconditional derandomizations.

• B. Juba and R. Williams. Massive Online Teaching to Bounded Learners. Latest version: [pdf]
  To appear 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 you get 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 implies 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.

• 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 available on ECCC.
  Summary: We provably need new ideas in order to prove better time-space lower bounds for the satisfiability problem... srsly.

• 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 (new!): [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 idle 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).
  [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).
  Invited to the special issue for STOC'10.
  Full version (draft): [pdf]
  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 draft (with less bugs): [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.