Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces

DOI10.1145/2590772zbMath1295.68140arXiv1206.0985OpenAlexW2567790317MaRDI QIDQ3189646

Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco A. Servedio

Publication date: 12 September 2014

Published in: Journal of the ACM, Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1206.0985

zbMATH Keywords

Fourier analysisBoolean functionthreshold functionChow parameters

Mathematics Subject Classification ID

Related Items (7)

The inverse problem for power distributions in committees ⋮ A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting ⋮ The inverse Shapley value problem ⋮ Quantum algorithms on Walsh transform and Hamming distance for Boolean functions ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• On the design of voting games.
• Heuristic and exact solutions to the inverse power index problem for small voting bodies
• Refinement of the upper bound of the constant in the central limit theorem
• On subspaces spanned by random selections of \(\pm 1\) vectors
• Regular simple games
• Learning with restricted focus of attention
• Toward efficient agnostic learning
• On restricted-focus-of-attention learnability of Boolean functions
• Different ways to represent weighted majority games
• Voting power in the governance of the international monetary fund
• Vector analysis of threshold functions
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• The inverse Shapley value problem
• Every linear threshold function has a low-weight approximator
• The Chow Parameters Problem
• Testing Halfspaces
• On the inverse power index problem
• Majority Decision Functions of up to Six Variables
• A Bound on the Precision Required to Estimate a Boolean Perceptron from Its Average Satisfying Assignment
• Harmonic Analysis of Polynomial Threshold Functions
• Agnostically Learning Halfspaces
• A Characterization of Weighted Voting
• Mathematical Properties of the Banzhaf Power Index
• The application of Chow parameters and Rademacher-Walsh matrices in the synthesis of binary functions
• The Counting Vector of a Simple Game
• Agnostic Learning of Monomials by Halfspaces Is Hard
• A geometric test-synthesis procedure for a threshold device
• Bounded Independence Fools Halfspaces
• An Approach to Single-Threshold-Element Synthesis
• Counting with Majority-Logic Networks
• Enumeration of Threshold Functions of Eight Variables
• Chow Parameters in Threshold Logic
• Approximating Linear Threshold Predicates

This page was built for publication: Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces