Anindya De

Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime

Conference on Innovations in Theoretical Computer Science · 2021 · 5 citations

In the trace reconstruction problem, an unknown source string x ∈ {0,1}ⁿ is transmitted through a probabilistic deletion channel which independently deletes each bit with some fixed probability δ and concatenates the surviving bits, resulting in a trace of x. The problem is to reconstruct x given access to independent traces. Trace reconstruction of arbitrary (worst-case) strings is a challenging problem, with the current state of the art for poly(n)-time algorithms being the 2004 algorithm of B…

Testing Convex Truncation

Society for Industrial and Applied Mathematics eBooks · 2023-01-01 · 3 citations

We study the basic statistical problem of testing whether normally distributed n-dimensional data has been truncated, i.e. altered by only retaining points that lie in some unknown truncation set S ⊆ ℝn. As our main algorithmic results 1. We give a computationally efficient O(n)-sample algorithm that can distinguish the standard normal distribution N(0,In) from N(0,In) conditioned on an unknown and arbitrary convex set S. 2. We give a different computationally efficient O(n)-sample algorithm tha…

Detecting Low-Degree Truncation

2024-06-10 · 2 citations

We consider the following basic, and very broad, statistical problem: Given a known high-dimensional distribution D over ℝn and a collection of data points in ℝn, distinguish between the two possibilities that (i) the data was drawn from D, versus (ii) the data was drawn from D|S, i.e. from D subject to truncation by an unknown truncation set S ⊆ ℝn. We study this problem in the setting where D is a high-dimensional i.i.d. product distribution and S is an unknown degree-d polynomial threshold fu…

Quantitative correlation inequalities via extremal power series

Probability Theory and Related Fields · 2022-03-14 · 2 citations

Testing Intersecting and Union-Closed Families

arXiv (Cornell University) · 2023-11-18 · 1 citations

Inspired by the classic problem of Boolean function monotonicity testing, we investigate the testability of other well-studied properties of combinatorial finite set systems, specifically \emph{intersecting} families and \emph{union-closed} families. A function $f: \{0,1\}^n \to \{0,1\}$ is intersecting (respectively, union-closed) if its set of satisfying assignments corresponds to an intersecting family (respectively, a union-closed family) of subsets of $[n]$. Our main results are that -- in…