Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > RYAN WILLIAMS:
All reports by Author Ryan Williams:

TR23-186 | 28th November 2023
Ce Jin, Ryan Williams, Nathaniel Young

A VLSI Circuit Model Accounting For Wire Delay

Given the need for ever higher performance, and the failure of CPUs to keep providing single-threaded performance gains, engineers are increasingly turning to highly-parallel custom VLSI chips to implement expensive computations. In VLSI design, the gates and wires of a logical circuit are placed on a 2-dimensional chip with a ... more >>>


TR23-184 | 22nd November 2023
Gabriel Bathie, Ryan Williams

Towards Stronger Depth Lower Bounds

A fundamental problem in circuit complexity is to find explicit functions that require large depth to compute. When considering the natural DeMorgan basis of $\{\text{OR},\text{AND}\}$, where negations incur no cost, the best known depth lower bounds for an explicit function in NP have the form $(3-o(1))\log_2 n$, established by H{\aa}stad ... more >>>


TR23-171 | 15th November 2023
Shuichi Hirahara, Rahul Ilango, Ryan Williams

Beating Brute Force for Compression Problems

A compression problem is defined with respect to an efficient encoding function $f$; given a string $x$, our task is to find the shortest $y$ such that $f(y) = x$. The obvious brute-force algorithm for solving this compression task on $n$-bit strings runs in time $O(2^{\ell} \cdot t(n))$, where $\ell$ ... more >>>


TR23-082 | 1st June 2023
Ryan Williams

Self-Improvement for Circuit-Analysis Problems

Many results in fine-grained complexity reveal intriguing consequences from solving various SAT problems even slightly faster than exhaustive search. We prove a ``self-improving'' (or ``bootstrapping'') theorem for Circuit-SAT, $\#$Circuit-SAT, and its fully-quantified version: solving one of these problems faster for ``large'' circuit sizes implies a significant speed-up for ``smaller'' circuit ... more >>>


TR23-038 | 28th March 2023
Rahul Ilango, Jiatu Li, Ryan Williams

Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic

The range avoidance problem (denoted by Avoid) asks to find a string outside of the range of a given circuit $C:\{0,1\}^n\to\{0,1\}^m$, where $m>n$. Although at least half of the strings of length $m$ are correct answers, it is not clear how to deterministically find one. Recent results of Korten (FOCS'21) ... more >>>


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

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


TR21-159 | 15th November 2021
Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams

Constructive Separations and Their Consequences

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


TR20-150 | 7th October 2020
Lijie Chen, Xin Lyu, Ryan Williams

Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization

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


TR20-065 | 2nd May 2020
Lijie Chen, Ce Jin, Ryan Williams

Sharp Threshold Results for Computational Complexity

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


TR19-118 | 5th September 2019
Lijie Chen, Ce Jin, Ryan Williams

Hardness Magnification for all Sparse NP Languages

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


TR19-075 | 25th May 2019
Lijie Chen, Dylan McKay, Cody Murray, Ryan Williams

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

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


TR17-188 | 22nd December 2017
Cody Murray, Ryan Williams

Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP

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


TR16-002 | 18th January 2016
Ryan Williams

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

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


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

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


TR14-164 | 30th November 2014
Cody Murray, Ryan Williams

On the (Non) NP-Hardness of Computing Circuit Complexity

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


TR13-108 | 9th August 2013
Rahul Santhanam, Ryan Williams

New Algorithms for QBF Satisfiability and Implications for Circuit Complexity

Revisions: 1

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


TR12-107 | 30th August 2012
Brendan Juba, Ryan Williams

Massive Online Teaching to Bounded Learners

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


TR12-059 | 14th May 2012
Rahul Santhanam, Ryan Williams

Uniform Circuits, Lower Bounds, and QBF Algorithms

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


TR11-031 | 8th March 2011
Sam Buss, Ryan Williams

Limits on Alternation-Trading Proofs for Time-Space Lower Bounds

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


TR08-076 | 17th June 2008
Ryan Williams

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

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


TR07-036 | 6th April 2007
Ryan Williams

Time-Space Tradeoffs for Counting NP Solutions Modulo Integers

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


TR04-032 | 5th February 2004
Ryan Williams

A new algorithm for optimal constraint satisfaction and its implications

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




ISSN 1433-8092 | Imprint