On XOR lemmas for the weight of polynomial threshold functions

DOI10.1016/J.IC.2019.104439zbMath1435.68220OpenAlexW2969420622WikidataQ124916951 ScholiaQ124916951MaRDI QIDQ2280318

Shoma Tate, Kazuyuki Amano

Publication date: 18 December 2019

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2019.104439

zbMATH Keywords

computational complexityinteger programmingBoolean functionsPTF

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Combinatorics in computer science (68R05) Boolean functions (06E30) Boolean functions (94D10)

Related Items (2)

Combined weight and density bounds on the polynomial threshold function representation of Boolean functions ⋮ Special issue: selected papers of the 10th international conference on language and automata theory and applications, LATA 2016

Uses Software

• Gurobi

Cites Work

• Unnamed Item
• Learning intersections and thresholds of halfspaces
• Unconditional lower bounds for learning intersections of halfspaces
• Majority gates vs. general weighted threshold gates
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• Boosting a weak learning algorithm by majority
• Threshold circuits of bounded depth
• Extremal properties of polynomial threshold functions
• New Upper Bounds on the Average PTF Density of Boolean Functions
• An Upper Bound on the Minimum Number of Monomials Required to Separate Dichotomies of {−1, 1}ⁿ
• Harmonic Analysis of Polynomial Threshold Functions
• On Tensor Powers of Integer Programs
• Minimal Sign Representation of Boolean Functions: Algorithms and Exact Results for Low Dimensions
• The Intersection of Two Halfspaces Has High Threshold Degree
• Probability and Computing
• New degree bounds for polynomial threshold functions

This page was built for publication: On XOR lemmas for the weight of polynomial threshold functions