# Degree-d Chow Parameters Robustly Determine Degree-d PTFs (and Algorithmic Applications)

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Nov 2018.

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

- [Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs](https://mlsanity.com/paper/2404.00529/) (2024)
- [PTF Testing Lower Bounds for Non-Gaussian Component Analysis](https://mlsanity.com/paper/2511.19398/) (2025)
- [A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube](https://mlsanity.com/paper/2511.07244/) (2025)
- [Iterative Chow Filtering for Learning with Distribution Shift](https://mlsanity.com/paper/2605.17251/) (2026)

## Abstract (arXiv)

The degree-d Chow parameters of a Boolean function f: -1,1n → ℝ are its degree at most d Fourier coefficients. It is well-known that degree-d Chow parameters uniquely characterize degree-d polynomial threshold functions (PTFs) within the space of all bounded functions. In this paper, we prove a robust version of this theorem: For f any Boolean degree-d PTF and g any bounded function, if the degree-d Chow parameters of f are close to the degree-d Chow parameters of g in ℓ2-norm, then f is close to g in ℓ1-distance. Notably, our bound relating the two distances is completely independent of the dimension n. That is, we show that Boolean degree-d PTFs are em robustly identifiable from their degree-d Chow parameters. Results of this form had been shown for the d=1 case~citeOS11:chow, DeDFS14, but no non-trivial bound was previously known for d >1. Our robust identifiability result gives the following algorithmic applications: First, we show that Boolean degree-d PTFs can be efficiently approximately reconstructed from approximations to their degree-d Chow parameters. This immediately implies that degree-d PTFs are efficiently learnable in the uniform distribution d-RFA model~citeBenDavidDichterman:98. As a byproduct of our approach, we also obtain the first low integer-weight approximations of degree-d PTFs, for d>1. As our second application, our robust identifiability result gives the first efficient algorithm, with dimension-independent error guarantees, for malicious learning of Boolean degree-d PTFs under the uniform distribution.