93 citations · 183 across the 19 of their papers we have counts for
Showing 2015Show all
3 papers · 1 filter
cs.CC2015★ 1 cited
Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits
Daniel M. 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 surprisin…
cs.CC2015★ 1 cited
Simulating Branching Programs with Edit Distance and Friends or: A Polylog Shaved is a Lower Bound Made
Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams +1
A recent and active line of work achieves tight lower bounds for fundamental problems under the Strong Exponential Time Hypothesis (SETH). A celebrated result of Backurs and Indyk…
cs.DS2015★ 93 cited
Probabilistic Polynomials and Hamming Nearest Neighbors
Josh Alman, Ryan Williams
We show how to compute any symmetric Boolean function on variables over any field (as well as the integers) with a probabilistic polynomial of degree an…