
Convex Influences
We introduce a new notion of influence for symmetric convex sets over Ga...
read it

Approximating Sumset Size
Given a subset A of the ndimensional Boolean hypercube 𝔽_2^n, the sumse...
read it

NearOptimal AverageCase Approximate Trace Reconstruction from Few Traces
In the standard trace reconstruction problem, the goal is to exactly rec...
read it

Quantitative Correlation Inequalities via Semigroup Interpolation
Most correlation inequalities for highdimensional functions in the lite...
read it

Polynomialtime trace reconstruction in the low deletion rate regime
In the trace reconstruction problem, an unknown source string x ∈{0,1}^n...
read it

Learning a mixture of two subspaces over finite fields
We study the problem of learning a mixture of two subspaces over 𝔽_2^n. ...
read it

Polynomialtime trace reconstruction in the smoothed complexity model
In the trace reconstruction problem, an unknown source string x ∈{0,1}^n...
read it

Reconstructing weighted voting schemes from partial information about their power indices
A number of recent works [Goldberg 2006; O'Donnell and Servedio 2011; De...
read it

An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs
We give the first polynomialtime approximation scheme (PTAS) for the st...
read it

Robust testing of lowdimensional functions
A natural problem in highdimensional inference is to decide if a classi...
read it

Testing noisy linear functions for sparsity
We consider the following basic inference problem: there is an unknown h...
read it

KruskalKatona for convex sets, with applications
The wellknown KruskalKatona theorem in combinatorics says that (under ...
read it

Reconstruction under outliers for Fouriersparse functions
We consider the problem of learning an unknown f with a sparse Fourier s...
read it

Learning from satisfying assignments under continuous distributions
What kinds of functions are learnable from their satisfying assignments?...
read it

Junta correlation is testable
The problem of tolerant junta testing is a natural and challenging probl...
read it

Density estimation for shiftinvariant multidimensional distributions
We study density estimation for classes of shiftinvariant distributions...
read it

Learning sparse mixtures of rankings from noisy information
We study the problem of learning an unknown mixture of k rankings over n...
read it

Learning Sums of Independent Random Variables with Sparse Collective Support
We study the learnability of sums of independent integer random variable...
read it

Is your function lowdimensional?
We study the problem of testing if a function depends on a small number ...
read it

Is your data lowdimensional?
We study the problem of testing if a function depends on a small number ...
read it

Boolean function analysis meets stochastic optimization: An approximation scheme for stochastic knapsack
The stochastic knapsack problem is the stochastic variant of the classic...
read it
Anindya De
is this you? claim profile