118 citations · 218 across the 20 of their papers we have counts for
23 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 prob…
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…
Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian, and Beyond Moments
Trung Dang, Jasper C. H. Lee, Maoyuan Song +1
There is growing interest in improving our algorithmic understanding of fundamental statistical problems such as mean estimation, driven by the goal of understanding the limits of…