Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DEGREE-D CHOW PARAMETERS:
Reports tagged with Degree-d Chow Parameters:
TR18-189 | 8th November 2018
Ilias Diakonikolas, Daniel Kane

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

The degree-$d$ Chow parameters of a Boolean function $f: \bn \to \R$ 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 ... more >>>




ISSN 1433-8092 | Imprint