5 papers
Quasipolynomial Trace Reconstruction
Arnav Burudgunte, Paul Valiant, Hongao Wang
We show that trace reconstruction on n-bit strings is possible using a quasipolynomial number of traces, for any retention probability p that is at least inverse polylogarithmic in…
The Median is Easier than it Looks: Approximation with a Constant-Depth, Linear-Width ReLU Network
Abhigyan Dutta, Itay Safran, Paul Valiant
We study the approximation of the median of inputs using ReLU neural networks. We present depth-width tradeoffs under several settings, culminating in a constant-depth, linear-…
New Bounds for Circular Trace Reconstruction
Arnav Burudgunte, Paul Valiant, Hongao Wang
The ''trace reconstruction'' problem asks, given an unknown binary string and a channel that repeatedly returns ''traces'' of with each bit randomly deleted with some proba…
A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities
Joey Rivkin, Gregory Valiant, Paul Valiant
We introduce the following natural generalization of trace reconstruction, parameterized by a deletion probability and length : There is a length string of pro…
Depth Separations in Neural Networks: Separating the Dimension from the Accuracy
Itay Safran, Daniel Reichman, Paul Valiant
We prove an exponential size separation between depth 2 and depth 3 neural networks (with real inputs), when approximating a -Lipschitz target function to constant…