research
∙
05/04/2023
Testing Convex Truncation
We study the basic statistical problem of testing whether normally distr...
share
research
∙
01/17/2023
Subset Sum in Time 2^n/2 / poly(n)
A major goal in the area of exact exponential algorithms is to give an a...
research
∙
11/07/2022
Approximate Trace Reconstruction from a Single Trace
The well-known trace reconstruction problem is the problem of inferring ...
research
∙
12/08/2021
The perils of being unhinged: On the accuracy of classifiers minimizing a noise-robust convex loss
van Rooyen et al. introduced a notion of convex loss functions being rob...
research
∙
10/27/2021
Average-Case Subset Balancing Problems
Given a set of n input integers, the Equal Subset Sum problem asks us to...
research
∙
09/07/2021
Convex Influences
We introduce a new notion of influence for symmetric convex sets over Ga...
research
∙
07/26/2021
Approximating Sumset Size
Given a subset A of the n-dimensional Boolean hypercube 𝔽_2^n, the sumse...
research
∙
07/24/2021
Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces
In the standard trace reconstruction problem, the goal is to exactly rec...
research
∙
07/22/2021
Fourier growth of structured 𝔽_2-polynomials and applications
We analyze the Fourier growth, i.e. the L_1 Fourier weight at level k (d...
research
∙
03/13/2021
Fooling Gaussian PTFs via Local Hyperconcentration
We give a pseudorandom generator that fools degree-d polynomial threshol...
research
∙
02/03/2021
On the Approximation Power of Two-Layer Networks of Random ReLUs
This paper considers the following question: how well can depth-two ReLU...
research
∙
12/22/2020
Quantitative Correlation Inequalities via Semigroup Interpolation
Most correlation inequalities for high-dimensional functions in the lite...
research
∙
12/04/2020
Polynomial-time trace reconstruction in the low deletion rate regime
In the trace reconstruction problem, an unknown source string x ∈{0,1}^n...
research
∙
08/27/2020
Polynomial-time trace reconstruction in the smoothed complexity model
In the trace reconstruction problem, an unknown source string x ∈{0,1}^n...
research
∙
07/19/2020
Reconstructing weighted voting schemes from partial information about their power indices
A number of recent works [Goldberg 2006; O'Donnell and Servedio 2011; De...
research
∙
11/03/2019
Testing noisy linear functions for sparsity
We consider the following basic inference problem: there is an unknown h...
research
∙
11/01/2019
Kruskal-Katona for convex sets, with applications
The well-known Kruskal-Katona theorem in combinatorics says that (under ...
research
∙
07/28/2019
A Lower Bound on Cycle-Finding in Sparse Digraphs
We consider the problem of finding a cycle in a sparse directed graph G ...
research
∙
07/12/2019
Efficient average-case population recovery in the presence of insertions and deletions
Several recent works have considered the trace reconstruction problem, i...
research
∙
07/02/2019
Learning from satisfying assignments under continuous distributions
What kinds of functions are learnable from their satisfying assignments?...
research
∙
04/11/2019
Beyond trace reconstruction: Population recovery from the deletion channel
Population recovery is the problem of learning an unknown distribution o...
research
∙
11/09/2018
Density estimation for shift-invariant multidimensional distributions
We study density estimation for classes of shift-invariant distributions...
research
∙
08/13/2018
Fooling Polytopes
We give a pseudorandom generator that fools m-facet polytopes over {0,1}...
research
∙
03/12/2018
Luby--Veličković--Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits
We study correlation bounds and pseudorandom generators for depth-two ci...
research
∙
02/13/2018
Distribution-free Junta Testing
We study the problem of testing whether an unknown n-variable Boolean fu...
research
∙
01/10/2018
Improved pseudorandom generators from pseudorandom multi-switching lemmas
We give the best known pseudorandom generators for two touchstone classe...
research
∙
01/10/2018
Deterministic search for CNF satisfying assignments in almost polynomial time
We consider the fundamental derandomization problem of deterministically...
research
∙
05/14/2013