3 citations · 4 across the 2 of their papers we have counts for
4 papers
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…
Context-Aware System Synthesis, Task Assignment, and Routing
Jason Ziglar, Ryan Williams, Alfred Wicks
The design and organization of complex robotic systems traditionally requires laborious trial-and-error processes to ensure both hardware and software components are correctly conn…
Deterministic Time-Space Tradeoffs for k-SUM
Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang +1
Given a set of numbers, the -SUM problem asks for a subset of numbers that sums to zero. When the numbers are integers, the time and space complexity of -SUM is generally…