# Detecting Low-Degree Truncation

arXiv: https://arxiv.org/abs/2402.08133 · HTML: https://mlsanity.com/paper/2402.08133/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Feb 2024.

## Built on by (most cited first, 7 of 7)

- [Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians](https://mlsanity.com/paper/2410.01656/) (2024)
- [Transfer Learning Beyond Bounded Density Ratios](https://mlsanity.com/paper/2403.11963/) (2024)
- [Smoothed Analysis of Learning from Positive Samples](https://mlsanity.com/paper/2504.10428/) (2025)
- [Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning](https://mlsanity.com/paper/2502.16355/) (2025)
- [Learning High-dimensional Gaussians from Censored Data](https://mlsanity.com/paper/2504.19446/) (2025)
- [New Statistical and Computational Results for Learning Junta Distributions](https://mlsanity.com/paper/2505.05819/) (2025)
- [Mean Testing under Truncation beyond Gaussian](https://mlsanity.com/paper/2605.01335/) (2026)

## Abstract (arXiv)

We consider the following basic, and very broad, statistical problem: Given a known high-dimensional distribution cal D over ℝn and a collection of data points in ℝn, distinguish between the two possibilities that (i) the data was drawn from cal D, versus (ii) the data was drawn from cal D|S, i.e. from cal D subject to truncation by an unknown truncation set S subseteq ℝn. We study this problem in the setting where cal D is a high-dimensional i.i.d. product distribution and S is an unknown degree-d polynomial threshold function (one of the most well-studied types of Boolean-valued function over ℝn). Our main results are an efficient algorithm when cal D is a hypercontractive distribution, and a matching lower bound: bullet For any constant d, we give a polynomial-time algorithm which successfully distinguishes cal D from cal D|S using O(nd/2) samples (subject to mild technical conditions on cal D and S); bullet Even for the simplest case of cal D being the uniform distribution over +1, -1n, we show that for any constant d, any distinguishing algorithm for degree-d polynomial threshold functions must use Omega(nd/2) samples.