In reverse chronological order. Please note the
articles' copyrights are held by their respective publishers.
2010
V. Vassilevska Williams and R. Williams. Triangle detection versus matrix multiplication: a study of truly
subcubic reducibility. [pdf]
Summary: We show that the problems of detecting a triangle in a graph, multiplying matrices over a min-semiring,
verifying a matrix product over the same semiring, and the corresponding all-pairs path problems are all
inherently related in their time complexities. There are several surprises here:
for example, finding a minimum 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 gave a truly subcubic algorithm for the triangle problem in
the node-weighted case.
R. Williams. Improving exhaustive search implies superpolynomial lower bounds. [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.
R. Williams. Alternation-Trading Proofs, Linear Programming, and Lower Bounds.
To appear in the 27th Symposium on Theoretical Aspects of Computer Science (STACS 2010).
Full version (draft): [pdf]
An older version that is more focused on computer searches (entitled "Automated Proofs of Time Lower Bounds") can be found here: [pdf]
M. Pătraşcu and R. Williams. On the Possibility of Faster SAT Algorithms. To appear in 20th ACM-SIAM Symposium on Discrete Algorithms (SODA 2010). Preliminary full version: [pdf] Full version: in the works.
R. Impagliazzo and R. Williams. Communication Complexity With Synchronized Clocks. In preparation.
2009
N. Bansal and R. Williams. Regularity Lemmas and Combinatorial Algorithms. In IEEE Symposium on Foundations of Computer Science (FOCS 2009). Camera-ready: [pdf] Full version: in the works.
L. Fortnow, R. Santhanam, and R. Williams. Fixed Polynomial Size Circuit Lower Bounds. In IEEE Conference on Computational Complexity (CCC 2009). [pdf]
S. Diehl, D. van Melkebeek, and R. Williams. An Improved Time-Space Lower Bound for Tautologies. In International Computing and Combinatorics Conference (COCOON 2009). Draft of journal version: [pdf]
I. Koutis and R. Williams. Limits and applications of group algebras for parameterized problems. In International Colloquium on Automata, Languages, and Programming (ICALP 2009). Conference version: [pdf] Full version coming soon...
V. Vassilevska and R. Williams. Finding, Minimizing, and Counting Weighted Subgraphs. In ACM Symposium on Theory of Computing (STOC 2009). Full version: [pdf]
R. Williams. Finding Paths of Length k in O*(2^k) Time.IPL 109(6):315--318, 2009.[link to arxiv]
2008
R. Williams. Applying Practice to Theory.SIGACT News December 2008. [link to arxiv]
R. Williams. Maximum 2-satisfiability. 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 International Colloquium on Automata, Languages, and Programming (ICALP 2008).
2007
R. Williams. Algorithms and Resource Requirements for Fundamental Problems. Ph.D Thesis. [pdf]
NOTE: My thesis improves upon many of the below papers. 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 from ICALP'04 in several ways, and shows how algorithmic progress on some problems in parameterized complexity would yield new algorithms for the satisfiability problem. Enjoy...
V. Vassilevska, R. Williams, and R. Yuster. All-Pairs Bottleneck Paths For General Graphs in Truly Sub-Cubic Time.
In ACM Symposium on Theory of Computing (STOC 2007).
[pdf]
R. Williams. Time-Space Tradeoffs for Counting NP Solutions Modulo Integers.
In IEEE Conference on Computational Complexity (CCC 2007). Journal of Computational Complexity 17(2), 2008. [pdf] Slides: [pdf]
Received Ronald Book Prize for Best Student Paper.
R. Williams. Matrix-Vector Multiplication in Sub-Quadratic Time
(Some Preprocessing Required). In 18th ACM-SIAM
Symposium on Discrete Algorithms (SODA 2007). Full version: [pdf] Slides: [pdf]
2006
V. Vassilevska, R. Williams, and R. Yuster. Finding the smallest H-subgraph in real weighted graphs and related problems. In International Colloquium on Automata, Languages, and Programming (ICALP 2006).
[pdf] Journal version to apper in ACM Transactions on Algorithms. Preprint available on arXiv.
V. Vassilevska and R. Williams. Finding a Maximum Weight Triangle in O(n^(3-delta)) Time, With Applications. In 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 17th ACM-SIAM
Symposium on Discrete Algorithms (SODA 2006). [pdf]
Preliminary version: CMU
Technical Report CMU-CS-05-125, April 2005. [pdf] [ps]
2005
V. Shkapenyuk, R. Williams, S. Harizopoulos, and A. Ailamaki. Deadlock Resolution in Pipelined Query Graphs. [pdf]
CMU Technical Report CMU-CS-05-122, March 2005.
R. Williams. Parallelizing Time With Polynomial Circuits. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2005).
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 IEEE Conference on Computational Complexity (CCC 2005). Received Ronald Book Prize for Best Student Paper.
Full version in Journal of Computational Complexity 15(4), 2006.
Note: most results in the above have been improved in my more recent paper: "Alternation-Trading Proofs, Linear Programming, and Lower Bounds".
Carla Gomes and Ryan Williams. Approximation Algorithms. Book chapter in:
Introduction to Optimization, Decision Support and Search
Methodologies, Burke and Kendall (eds.), Springer.
2004
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).
(Received Best Student ICALP Paper Award)
A. Meyerson and R. Williams. On The Complexity of Optimal
K-Anonymity. [pdf] In ACM Symposium on
Principles of Database Systems (PODS 2004).
2003
R. Williams. On Computing k-CNF Formula Properties. New(er) version: [ps] [pdf] Older version in International Conference on Theory and Applications of Satisfiability
Testing (SAT
2003), Springer-Verlag Lecture
Notes in Computer Science, Volume 2919, 2004.
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).
2002
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.
The Junk Drawer: Old Manuscripts, Tech Reports, etc.
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.
Improved algorithms for advanced reasoning and search. [html] Presentation at BOOM 2002, Cornell.
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.) Here
is an advertisement for the thesis, as presented at BOOM 2001.
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.
A counting class based on polynomial space that collapses to #P.
[html] Presented
at BOOM99, Cornell.
C. Akkoc, J. Klemmack, I. Lai, G. Mitchell, J. Moore, A. Smith, R.
Williams, J. Wuu. Alice in solution land. Mathematics and Computer
Education, 32:3, Sept. 1998.