research
∙
05/04/2023
Testing Convex Truncation
We study the basic statistical problem of testing whether normally distr...
share
research
∙
11/07/2022
Approximate Trace Reconstruction from a Single Trace
The well-known trace reconstruction problem is the problem of inferring ...
research
∙
06/15/2022
Reconstructing Ultrametric Trees from Noisy Experiments
The problem of reconstructing evolutionary trees or phylogenies is of gr...
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
∙
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
∙
10/06/2020
Learning a mixture of two subspaces over finite fields
We study the problem of learning a mixture of two subspaces over 𝔽_2^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
∙
06/23/2020
An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs
We give the first polynomial-time approximation scheme (PTAS) for the st...
research
∙
04/24/2020
Robust testing of low-dimensional functions
A natural problem in high-dimensional inference is to decide if a classi...
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/09/2019
Reconstruction under outliers for Fourier-sparse functions
We consider the problem of learning an unknown f with a sparse Fourier s...
research
∙
07/02/2019
Learning from satisfying assignments under continuous distributions
What kinds of functions are learnable from their satisfying assignments?...
research
∙
04/08/2019
Junta correlation is testable
The problem of tolerant junta testing is a natural and challenging probl...
research
∙
11/09/2018
Density estimation for shift-invariant multidimensional distributions
We study density estimation for classes of shift-invariant distributions...
research
∙
11/03/2018
Learning sparse mixtures of rankings from noisy information
We study the problem of learning an unknown mixture of k rankings over n...
research
∙
07/18/2018
Learning Sums of Independent Random Variables with Sparse Collective Support
We study the learnability of sums of independent integer random variable...
research
∙
06/26/2018
Is your function low-dimensional?
We study the problem of testing if a function depends on a small number ...
research
∙
06/26/2018
Is your data low-dimensional?
We study the problem of testing if a function depends on a small number ...
research
∙
12/04/2017