6 citations · 9 across the 4 of their papers we have counts for
7 papers
Computing faster with a full memory: Catalytic algorithms break time-space lower bounds
Adelmo Morrison Orozco, Nathan Sheffield, Ryan Williams
We show that adding "catalytic space" (which starts full and must have its original contents restored at the end of computation) provably speeds up time-and-space-bounded computati…
A Theory for Probabilistic Polynomial-Time Reasoning
Lijie Chen, Jiatu Li, Igor C. Oliveira +1
In this work, we propose a new bounded arithmetic theory, denoted , designed to formalize a broad class of probabilistic arguments commonly used in theoretical computer scie…
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of SAT Algorithms
Nikhil Vyas, Ryan Williams
We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in…
Distributed PCP Theorems for Hardness of Approximation in P
Amir Abboud, Aviad Rubinstein, Ryan Williams
We present a new distributed model of probabilistically checkable proofs (PCP). A satisfying assignment to a CNF formula is shared between two parties, where…
Probabilistic Rank and Matrix Rigidity
Josh Alman, Ryan Williams
We consider a notion of probabilistic rank and probabilistic sign-rank of a matrix, which measures the extent to which a matrix can be probabilistically represented by low-rank mat…
Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation
Ryan Williams
We present an efficient proof system for Multipoint Arithmetic Circuit Evaluation: for every arithmetic circuit of size and degree over a field ${\mathb…
A Casual Tour Around a Circuit Complexity Bound
Ryan Williams
I will discuss the recent proof that the complexity class NEXP (nondeterministic exponential time) lacks nonuniform ACC circuits of polynomial size. The proof will be described fro…