Local maxima of quadratic Boolean functions

DOI10.1017/S0963548315000322zbMATH Open1372.05226arXiv1310.1570MaRDI QIDQ5366909FDOQ5366909

Authors: Hunter Spink 

Publication date: 10 October 2017

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

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Spectral properties of threshold functions
• On a lemma of Littlewood and Offord on the distribution of certain sums
• On a lemma of Littlewood and Offord

Cited In (2)

• Title not available (Why is that?)
• Quadratic functions with exponential number of local maxima

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)