SU\G(š¯”ø)/KĀ·U

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

Ilias Diakonikolas, Daniel M. Kane

Type: Preprint

Publication Date: 2018-11-07

Citations: 4

Locations

  • arXiv (Cornell University) - View

Similar Works

Action Title Year Authors
+ Degree-$d$ Chow Parameters Robustly Determine Degree-$d$ PTFs (and Algorithmic Applications) 2018 Ilias Diakonikolas
Daniel M. Kane
+ PDF Chat Degree-š¯‘‘ chow parameters robustly determine degree-š¯‘‘ PTFs (and algorithmic applications) 2019 Ilias Diakonikolas
Daniel M. Kane
+ PDF Chat Detecting Low-Degree Truncation 2024 Anindya De
Huan Li
Shivam Nadimpalli
Rocco A. Servedio
+ Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noise 2023 Shiwei Zeng
Jie Shen
+ Detecting Low-Degree Truncation 2024 Anindya De
Huan Li
Shivam Nadimpalli
Rocco A. Servedio
+ Average sensitivity and noise sensitivity of polynomial threshold functions 2009 Ilias Diakonikolas
Prasad Raghavendra
Rocco A. Servedio
Li-Yang Tan
+ Approximate resilience, monotonicity, and the complexity of agnostic learning 2014 Dana Dachman-Soled
Vitaly Feldman
Li-Yang Tan
Andrew Wan
Karl Wimmer
+ Low-degree learning and the metric entropy of polynomials 2022 Alexandros Eskenazis
Paata Ivanisvili
Lauritz Streck
+ PDF Chat Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces 2014 Anindya De
Ilias Diakonikolas
Vitaly Feldman
Rocco A. Servedio
+ PDF Chat Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs 2024 Ilias Diakonikolas
Daniel M. Kane
Vasilis Kontonis
Sihan Liu
Nikos Zarifis
+ Algorithmic polynomials 2018 Alexander A. Sherstov
+ PDF Chat None 2014 Ilias Diakonikolas
Rocco A. Servedio
Li-Yang Tan
Andrew Wan
+ Super Non-singular Decompositions of Polynomials and Their Application to Robustly Learning Low-Degree PTFs 2024 Ilias Diakonikolas
D. Kane
Vasilis Kontonis
Sihan Liu
Nikos Zarifis
+ Learning low-degree functions from a logarithmic number of random queries 2021 Alexandros Eskenazis
Paata Ivanisvili
+ Efficient deterministic approximate counting for low-degree polynomial threshold functions 2013 Anindya De
Rocco A. Servedio
+ Hardness Amplification and the Approximate Degree of Constant-Depth Circuits 2013 Mark Bun
Justin Thaler
+ PDF Chat Hilbert Functions and Low-Degree Randomness Extractors 2024 Alexander Golovnev
Zeyu Guo
Pooya Hatami
Satyajeet Nagargoje
Chao Yan
+ Efficient deterministic approximate counting for low degree polynomial threshold functions. 2013 Anindya De
Rocco A. Servedio
+ Inverse Conjecture for the Gowers norm is false. 2007 Shachar Lovett
Roy Meshulam
Alex Samorodnitsky
+ Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces 2012 Anindya De
Ilias Diakonikolas
Vitaly Feldman
Rocco A. Servedio

Works That Cite This (3)

Action Title Year Authors
+ Recent Advances in Algorithmic High-Dimensional Robust Statistics 2019 Ilias Diakonikolas
Daniel M. Kane
+ PDF Chat Degree-š¯‘‘ chow parameters robustly determine degree-š¯‘‘ PTFs (and algorithmic applications) 2019 Ilias Diakonikolas
Daniel M. Kane
+ On the Complexity of the Inverse Semivalue Problem for Weighted Voting Games 2018 Ilias Diakonikolas
Chrystalla Pavlou

Works Cited by This (29)

Action Title Year Authors
+ PDF Chat Deterministic Approximate Counting for Juntas of Degree-2 Polynomial Threshold Functions 2014 Anindya De
Ilias Diakonikolas
Rocco A. Servedio
+ Analysis of Boolean Functions 2014 Ryan Oā€™Donnell
+ On the Number of Real Roots of a Random Algebraic Equation 1938 J. E. Littlewood
A. C. Offord
+ PDF Chat On a lemma of Littlewood and Offord 1945 P. Erdős
+ Truth functions realizable by single threshold organs 1961 Calvin C. Elgot
+ PDF Chat Agnostic Learning of Monomials by Halfspaces Is Hard 2012 Vitaly Feldman
Venkatesan Guruswami
Prasad Raghavendra
Yi Wu
+ Enumeration of Threshold Functions of Eight Variables 1970 Saburo Muroga
Takashi Tsuboi
C.R. Baugh
+ PDF Chat The correct exponent for the Gotsmanā€“Linial Conjecture 2014 Daniel M. Kane
+ 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