A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions

Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, Andrew Wan

Type: Preprint

Publication Date: 2009-01-01

Citations: 5

DOI: https://doi.org/10.48550/arxiv.0909.4727

View Publication

Locations

arXiv (Cornell University) - View
Edinburgh Research Explorer (University of Edinburgh) - View - PDF
Edinburgh Research Explorer (University of Edinburgh) - View - PDF
DataCite API - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial Threshold Functions	2010	Ilias Diakonikolas Rocco A. Servedio Li-Yang Tan Andrew Wan
+ PDF Chat	None	2014	Ilias Diakonikolas Rocco A. Servedio Li-Yang Tan Andrew Wan
+	Improved Approximation of Linear Threshold Functions	2009	Ilias Diakonikolas Rocco A. Servedio
+	Polynomial Representations of Threshold Functions and Algorithmic Applications	2016	Josh Alman M Chan Timothy Williams Ryan
+	Average sensitivity and noise sensitivity of polynomial threshold functions	2009	Ilias Diakonikolas Prasad Raghavendra Rocco A. Servedio Li-Yang Tan
+	Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness	2009	Ido Ben‐Eliezer Shachar Lovett Ariel Yadin
+	Polynomial Representations of Threshold Functions and Algorithmic Applications	2016	Josh Alman Timothy M. Chan Ryan Williams
+	Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness	2009	Ido Ben‐Eliezer Shachar Lovett Ariel Yadin
+	Efficient deterministic approximate counting for low-degree polynomial threshold functions	2013	Anindya De Rocco A. Servedio
+ PDF Chat	Degree-𝑑 chow parameters robustly determine degree-𝑑 PTFs (and algorithmic applications)	2019	Ilias Diakonikolas Daniel M. Kane
+	Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials	2018	Ryan Williams
+	Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials	2018	Ryan Williams
+ PDF Chat	Lower Bound on Weights of Large Degree Threshold Functions	2013	Vladimir V. Podolskii
+	On the weight and density bounds of polynomial threshold functions	2020	Erhan Öztop Minoru Asada
+ PDF Chat	Improved Approximation of Linear Threshold Functions	2012	Ilias Diakonikolas Rocco A. Servedio
+	Polynomial Threshold Functions for Decision Lists	2022	Vladimir V. Podolskii Nikolay V. Proskurin
+	Deterministic Approximate Counting for Juntas of Degree-$2$ Polynomial Threshold Functions	2013	Anindya De Ilias Diakonikolas Rocco A. Servedio
+ PDF Chat	None	2013	Alexander A. Sherstov
+	Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0.	2019	Alexander A. Sherstov Pei Wu
+ PDF Chat	Polynomial Threshold Functions for Decision Lists	2022	Vladimir V. Podolskii Nikolay V. Proskurin

Works That Cite This (5)

Action	Title	Year	Authors
+	Bounded Independence Fools Degree-2 Threshold Functions	2009	Ilias Diakonikolas Daniel M. Kane Jelani Nelson
+	A Noisy-Influence Regularity Lemma for Boolean Functions	2016	Chris Jones
+	Guaranteed Rank Minimization via Singular Value Projection	2009	Raghu Meka Prateek Jain Inderjit S. Dhillon
+	Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness	2009	Ido Ben‐Eliezer Shachar Lovett Ariel Yadin
+ PDF Chat	Bounding the Sensitivity of Polynomial Threshold Functions	2014	Prahladh Harsha Adam R. Klivans Raghu Meka

Works Cited by This (15)

Action	Title	Year	Authors
+ PDF Chat	Spectral properties of threshold functions	1994	Craig Gotsman Nathan Linial
+ PDF Chat	Distributional and $L^{q}$ norm inequalities for polynomials over convex bodies in ${\Bbb R}^n$	2001	Anthony Carbery James Wright
+ PDF Chat	Harmonic Analysis of Polynomial Threshold Functions	1990	Jehoshua Bruck
+	The influence of variables on Boolean functions	1988	J. Kahn Gil Kalai Nathan Linial
+	On the fourier tails of bounded functions over the discrete cube	2006	Irit Dinur Ehud Friedgut Guy Kindler Ryan O’Donnell
+	REGULAR PARTITIONS OF GRAPHS	1975	Endre Szemerédi
+ PDF Chat	The Intersection of Two Halfspaces Has High Threshold Degree	2009	Alexander A. Sherstov
+	Logarithmic Sobolev Inequalities	1975	Leonard Gross
+ PDF Chat	Structure and Randomness in Combinatorics	2007	Terence Tao
+	Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness	2009	Ido Ben‐Eliezer Shachar Lovett Ariel Yadin