Local maxima of quadratic Boolean functions

DOI10.1017/S0963548315000322MaRDI QIDQ5366909zbMATH OpenFDO

Authors Hunter Spink

Publication date 10 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Hypergraphs (05C65) Extremal set theory (05D05) Boolean functions (06E30)

Abstract: How many strict local maxima can a real quadratic function on ${0,1}^n$ have? Holzman conjectured a maximum of $nchooselfloorn/2floor$. The aim of this paper is to prove this conjecture. Our approach is via a generalization of Sperner's theorem that may be of independent interest.

Recommendations

• Quadratic functions with exponential number of local maxima
• On the number of local maxima in quadratic 0-1 programs
• The conjunctive complexity of quadratic Boolean functions
• Upper-bounds for quadratic 0-1 maximization
• scientific article; zbMATH DE number 4176831

Cites work

• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• On a lemma of Littlewood and Offord
• On a lemma of Littlewood and Offord on the distribution of certain sums
• Spectral properties of threshold functions

Cited in

(3)

• Quadratic functions with exponential number of local maxima
• On the number of local maxima in quadratic 0-1 programs
• scientific article; zbMATH DE number 706870 (Why is no real title available?)

This page was built for publication: Local maxima of quadratic Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5366909)