Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces
From MaRDI portal
Publication:3189646
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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
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