10 citations · 14 across the 10 of their papers we have counts for
5 papers · 1 filter
Near-Maximum Circuit Lower Bounds for Exponential Time with Merlin-Arthur Queries
Hanlin Ren, Ryan Williams
We prove a near-maximum () circuit lower bound for the complexity class , corresponding to exponential time with access to a promis…
Simulating Time With Square-Root Space
R. Ryan Williams
We show that for all functions , every multitape Turing machine running in time can be simulated in space only . This is a substantial improvem…
Constructive Separations and Their Consequences
Lijie Chen, Ce Jin, Rahul Santhanam +1
For a complexity class and language , a constructive separation of gives an efficient algorithm (also called a refuter) to find counterexamples (bad inputs) for…
Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials
R. Ryan Williams
We consider the problem of representing Boolean functions exactly by "sparse" linear combinations (over ) of functions from some "simple" class . In particula…
The Orthogonal Vectors Conjecture for Branching Programs and Formulas
Daniel Kane, Ryan Williams
In the Orthogonal Vectors (OV) problem, we wish to determine if there is an orthogonal pair of vectors among Boolean vectors in dimensions. The OV Conjecture (OVC) posits t…