William Matthews

For the most up to date version of this page and for more information, please see my web site at UCSD.

Papers

A Satisfiability Algorithm for AC⁰

R. Impagliazzo, W. Matthews, and R. Paturi, 2011, manuscript to be submitted (email me if you are interested)
Uniquely Satisfiable k-SAT Instances with Almost Minimal Occurrences of Each Variable

W. Matthews and R. Paturi, SAT, 369-374, LNCS 6175, 2010
Improved Algorithms for Unique Games via Divide and Conquer

S. Arora, R. Impagliazzo, W. Matthews, and D. Steurer, ECCC, Report TR10-041, 2010