All reports by Author Ryan Williams:

__
TR21-165
| 21st November 2021
__

Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, Ryan Williams#### Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity

Revisions: 1

__
TR21-159
| 15th November 2021
__

Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams#### Constructive Separations and Their Consequences

__
TR20-150
| 7th October 2020
__

Lijie Chen, Xin Lyu, Ryan Williams#### Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization

__
TR20-065
| 2nd May 2020
__

Lijie Chen, Ce Jin, Ryan Williams#### Sharp Threshold Results for Computational Complexity

__
TR19-118
| 5th September 2019
__

Lijie Chen, Ce Jin, Ryan Williams#### Hardness Magnification for all Sparse NP Languages

__
TR19-075
| 25th May 2019
__

Lijie Chen, Dylan McKay, Cody Murray, Ryan Williams#### Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems

__
TR17-188
| 22nd December 2017
__

Cody Murray, Ryan Williams#### Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP

__
TR16-002
| 18th January 2016
__

Ryan Williams#### Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation

__
TR15-188
| 24th November 2015
__

Daniel Kane, Ryan Williams#### Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits

__
TR14-164
| 30th November 2014
__

Cody Murray, Ryan Williams#### On the (Non) NP-Hardness of Computing Circuit Complexity

__
TR13-108
| 9th August 2013
__

Rahul Santhanam, Ryan Williams#### New Algorithms for QBF Satisfiability and Implications for Circuit Complexity

Revisions: 1

__
TR12-107
| 30th August 2012
__

Brendan Juba, Ryan Williams#### Massive Online Teaching to Bounded Learners

__
TR12-059
| 14th May 2012
__

Rahul Santhanam, Ryan Williams#### Uniform Circuits, Lower Bounds, and QBF Algorithms

__
TR11-031
| 8th March 2011
__

Sam Buss, Ryan Williams#### Limits on Alternation-Trading Proofs for Time-Space Lower Bounds

__
TR08-076
| 17th June 2008
__

Ryan Williams#### Non-Linear Time Lower Bound for (Succinct) Quantified Boolean Formulas

__
TR07-036
| 6th April 2007
__

Ryan Williams#### Time-Space Tradeoffs for Counting NP Solutions Modulo Integers

__
TR04-032
| 5th February 2004
__

Ryan Williams#### A new algorithm for optimal constraint satisfaction and its implications

Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, Ryan Williams

In a Merlin-Arthur proof system, the proof verifier (Arthur) accepts valid proofs (from Merlin) with probability $1$, and rejects invalid proofs with probability arbitrarily close to $1$. The running time of such a system is defined to be the length of Merlin's proof plus the running time of Arthur. We ... more >>>

Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams

For a complexity class $C$ and language $L$, a constructive separation of $L \notin C$ gives an efficient algorithm (also called a refuter) to find counterexamples (bad inputs) for every $C$-algorithm attempting to decide $L$. We study the questions: Which lower bounds can be made constructive? What are the consequences ... more >>>

Lijie Chen, Xin Lyu, Ryan Williams

In certain complexity-theoretic settings, it is notoriously difficult to prove complexity separations which hold almost everywhere, i.e., for all but finitely many input lengths. For example, a classical open question is whether $\mathrm{NEXP} \subset \mathrm{i.o.-}\mathrm{NP}$; that is, it is open whether nondeterministic exponential time computations can be simulated on infinitely ... more >>>

Lijie Chen, Ce Jin, Ryan Williams

We establish several ``sharp threshold'' results for computational complexity. For certain tasks, we can prove a resource lower bound of $n^c$ for $c \geq 1$ (or obtain an efficient circuit-analysis algorithm for $n^c$ size), there is strong intuition that a similar result can be proved for larger functions of $n$, ... more >>>

Lijie Chen, Ce Jin, Ryan Williams

In the Minimum Circuit Size Problem (MCSP[s(m)]), we ask if there is a circuit of size s(m) computing a given truth-table of length n = 2^m. Recently, a surprising phenomenon termed as hardness magnification by [Oliveira and Santhanam, FOCS 2018] was discovered for MCSP[s(m)] and the related problem MKtP of ... more >>>

Lijie Chen, Dylan McKay, Cody Murray, Ryan Williams

Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems

A frontier open problem in circuit complexity is to prove P^NP is not in SIZE[n^k] for all k; this is a necessary intermediate step towards NP is not in P/poly. Previously, for several classes containing P^NP, including NP^NP, ZPP^NP, and ... more >>>

Cody Murray, Ryan Williams

We prove that if every problem in $NP$ has $n^k$-size circuits for a fixed constant $k$, then for every $NP$-verifier and every yes-instance $x$ of length $n$ for that verifier, the verifier's search space has an $n^{O(k^3)}$-size witness circuit: a witness for $x$ that can be encoded with a circuit ... more >>>

Ryan Williams

We present an efficient proof system for Multipoint Arithmetic Circuit Evaluation: for every arithmetic circuit $C(x_1,\ldots,x_n)$ of size $s$ and degree $d$ over a field ${\mathbb F}$, and any inputs $a_1,\ldots,a_K \in {\mathbb F}^n$,

$\bullet$ the Prover sends the Verifier the values $C(a_1), \ldots, C(a_K) \in {\mathbb F}$ and ...
more >>>

Daniel Kane, Ryan Williams

In order to formally understand the power of neural computing, we first need to crack the frontier of threshold circuits with two and three layers, a regime that has been surprisingly intractable to analyze. We prove the first super-linear gate lower bounds and the first super-quadratic wire lower bounds for ... more >>>

Cody Murray, Ryan Williams

The Minimum Circuit Size Problem (MCSP) is: given the truth table of a Boolean function $f$ and a size parameter $k$, is the circuit complexity of $f$ at most $k$? This is the definitive problem of circuit synthesis, and it has been studied since the 1950s. Unlike many problems of ... more >>>

Rahul Santhanam, Ryan Williams

We revisit the complexity of the satisfiability problem for quantified Boolean formulas. We show that satisfiability

of quantified CNFs of size $\poly(n)$ on $n$ variables with $O(1)$

quantifier blocks can be solved in time $2^{n-n^{\Omega(1)}}$ by zero-error

randomized algorithms. This is the first known improvement over brute force search in ...
more >>>

Brendan Juba, Ryan Williams

We consider a model of teaching in which the learners are consistent and have bounded state, but are otherwise arbitrary. The teacher is non-interactive and ``massively open'': the teacher broadcasts a sequence of examples of an arbitrary target concept, intended for every possible on-line learning algorithm to learn from. We ... more >>>

Rahul Santhanam, Ryan Williams

We explore the relationships between circuit complexity, the complexity of generating circuits, and circuit-analysis algorithms. Our results can be roughly divided into three parts:

1. Lower Bounds Against Medium-Uniform Circuits. Informally, a circuit class is ``medium uniform'' if it can be generated by an algorithmic process that is somewhat complex ... more >>>

Sam Buss, Ryan Williams

This paper characterizes alternation trading based proofs that satisfiability is not in the time and space bounded class $\DTISP(n^c, n^\epsilon)$, for various values $c<2$ and $\epsilon<1$. We characterize exactly what can be proved in the $\epsilon=0$ case with currently known methods, and prove the conjecture of Williams that $c=2\cos(\pi/7)$ is ... more >>>

Ryan Williams

We prove a model-independent non-linear time lower bound for a slight generalization of the quantified Boolean formula problem (QBF). In particular, we give a reduction from arbitrary languages in alternating time t(n) to QBFs describable in O(t(n)) bits by a reasonable (polynomially) succinct encoding. The reduction works for many reasonable ... more >>>

Ryan Williams

We prove the first time-space tradeoffs for counting the number of solutions to an NP problem modulo small integers, and also improve upon the known time-space tradeoffs for Sat. Let m be a positive integer, and define MODm-Sat to be the problem of determining if a given Boolean formula has ... more >>>

Ryan Williams

We present a novel method for exactly solving (in fact, counting solutions to) general constraint satisfaction optimization with at most two variables per constraint (e.g. MAX-2-CSP and MIN-2-CSP), which gives the first exponential improvement over the trivial algorithm; more precisely, it is a constant factor improvement in the base of ... more >>>