The Chow Parameters Problem
From MaRDI portal
Publication:2999860
DOI10.1137/090756466zbMath1217.94139OpenAlexW2063836706MaRDI QIDQ2999860
Ryan O'Donnell, Rocco A. Servedio
Publication date: 17 May 2011
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: http://epubs.siam.org/sicomp/resource/1/smjcat/v40/i1/p165_s1
learning theoryFourier coefficientsBoolean functionthreshold functioncritical indexGaussian random variableChow parameters1-RFA modelChow distancerandomized polynomial-time approximation scheme
Computational learning theory (68Q32) Fourier series in special orthogonal functions (Legendre polynomials, Walsh functions, etc.) (42C10)
Related Items
Biased halfspaces, noise sensitivity, and local Chernoff inequalities, The inverse problem for power distributions in committees, Fooling Polytopes, Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces, Improved approximation of linear threshold functions, The inverse Shapley value problem, Self-Predicting Boolean Functions, Unnamed Item, A generalization of a theorem of Rothschild and van Lint, A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry, A generalization of a theorem of Rothschild and van Lint, Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits, A Polynomial Lower Bound for Testing Monotonicity, A \#SAT algorithm for small constant-depth circuits with PTF gates
