Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1912.10221 · Journal of Scientific Computing

Discrete Dynamical System Approaches for Boolean Polynomial Optimization

Yi-Shuai Niu, Roland Glowinski

Published Jun 30, 2022• 8 citations
arXivHTMLPDF
DOI
10.1007/s10915-022-01882-z

Related papers

Approximation Algorithms for Discrete Polynomial Optimization

Simai He, Zhening Li, Shuzhong Zhang

Journal of the Operations Research Society of China•Feb 19, 2013•24 citations

Testing Booleanity and the Uncertainty Principle

Tom Gur, Omer Tamuz

Let f:{-1,1}^n -> R be a real function on the hypercube, given by its discrete Fourier expansion, or, equivalently, represented as a multilinear polynomial. We say that it is Boolean if its image is in {-1,1}. We show that every function on the hypercube with a sparse Fourier expansion must either be Boolean or far from Boolean. In particular, we show that a multilinear polynomial with at most k terms must either be Boolean, or output values different than -1 or 1 for a fraction of at least 2/(k+2)^2 of its domain. It follows that given oracle access to f, together with the guarantee that its representation as a multilinear polynomial has at most k terms, one can test Booleanity using O(k^2) queries. We show an Ω(k) queries lower bound for this problem. Our proof crucially uses Hirschman's entropic version of Heisenberg's uncertainty principle.

arXiv:1204.0944•Chicago Journal of Theoretical Computer Science•Apr 4, 2012•4 citations

Efficient linear reformulations for binary polynomial optimization problems

Sourour Elloumi, Zoé Verchère

Computers & Operations Research•Apr 5, 2023•5 citations

Approximate maximum-likelihood estimation using semidefinite programming

J. Dahl, Bernard H. Fleury, Lieven Vandenberghe

We consider semidefinite relaxations of a quadratic optimization problem with polynomial constraints. This is an extension of quadratic problems with Boolean variables. Such combinatorial problems cannot, in general, be solved in polynomial time. Semidefinite relaxation has been proposed as a promising technique to give provable good bounds on certain Boolean quadratic problems in polynomial time. We formulate the extensions from Boolean variables to quarternary variables using (i) a polynomial relaxation or (ii) standard semidefinite relaxations of a linear transformation of Boolean variables. We compare the two different relaxation approaches analytically. The relaxations can all be expressed as semidefinite programs, which can be solved efficiently using e.g. interior point methods. Applications of our results include maximum likelihood estimation in communication systems, which we explore in simulations in order to compare the quality of the different relaxations with optimal solutions.

IEEE International Conference on Acoustics Speech and Signal Processing•Mar 22, 2004•9 citations

Constructions of Depth-2 Majority Circuits for Comparison and Addition using Linear Block Codes

Noga Alon, Jehoshua Bruck

We address the problem of computing the COMPARISON and ADDITION functions of two n-bit numbers using circuits of (nonmonotone) MAJORITY gates. Given n Boolean variables sl,. . . ,2;, E { -1, l}, a non-monotone MAJORITY gate (in the va.riables 2,) is a Boolean function whose value is the sign of E~z;, where each E, is either 1 or -1. We construct a.n explicit sparse polynomial whose sign computes the COMPAR,ISON function of two integers. Similar polynomials are constructed for computing all the bits of the summation of the two integers. This supplies explicit constructions of depth-2 polynomial-size circuits computing these functions, which use only non-monotone MAJORITY gates. These constructions are optimal in terms of the depth and can be used to obtain the best known explicit constructions of MAJORITY circuits for other functions like the product of two n-bit numbers and the maximum of n n-bit numbers (see [3] and [SI). A crucial ingredient in our a.pproach is the construction of a discrete version of a sparse polynomial-one that has a, large absolute value for a single a.ssignment and extremely small absolute values for all other assignments. We construct sparse delta polynomials using generator matrices of certain linear block codes. In the rest of this summa.ry we sketch the ideas rehted to the construction for the COMPARISON function. More details a.nd related results appea.r in [I].

IEEE International Symposium on Information Theory (ISIT)•Aug 24, 2005•0 citations

Quantum Algorithms for Discrete Optimization

Sergio Boixo, Rolando D. Somma

•Jan 1, 2015•0 citations
Let f:{-1,1}^n -> R be a real function on the hypercube, given by its discrete Fourier expansion, or, equivalently, represented as a multilinear polynomial. We say that it is Boolean if its image is in {-1,1}. We show that every function on the hypercube with a sparse Fourier expansion must either be Boolean or far from Boolean. In particular, we show that a multilinear polynomial with at most k terms must either be Boolean, or output values different than -1 or 1 for a fraction of at least 2/(k+2)^2 of its domain. It follows that given oracle access to f, together with the guarantee that its representation as a multilinear polynomial has at most k terms, one can test Booleanity using O(k^2) queries. We show an Ω(k) queries lower bound for this problem. Our proof crucially uses Hirschman's entropic version of Heisenberg's uncertainty principle.
We consider semidefinite relaxations of a quadratic optimization problem with polynomial constraints. This is an extension of quadratic problems with Boolean variables. Such combinatorial problems cannot, in general, be solved in polynomial time. Semidefinite relaxation has been proposed as a promising technique to give provable good bounds on certain Boolean quadratic problems in polynomial time. We formulate the extensions from Boolean variables to quarternary variables using (i) a polynomial relaxation or (ii) standard semidefinite relaxations of a linear transformation of Boolean variables. We compare the two different relaxation approaches analytically. The relaxations can all be expressed as semidefinite programs, which can be solved efficiently using e.g. interior point methods. Applications of our results include maximum likelihood estimation in communication systems, which we explore in simulations in order to compare the quality of the different relaxations with optimal solutions.
We address the problem of computing the COMPARISON and ADDITION functions of two n-bit numbers using circuits of (nonmonotone) MAJORITY gates. Given n Boolean variables sl,. . . ,2;, E { -1, l}, a non-monotone MAJORITY gate (in the va.riables 2,) is a Boolean function whose value is the sign of E~z;, where each E, is either 1 or -1. We construct a.n explicit sparse polynomial whose sign computes the COMPAR,ISON function of two integers. Similar polynomials are constructed for computing all the bits of the summation of the two integers. This supplies explicit constructions of depth-2 polynomial-size circuits computing these functions, which use only non-monotone MAJORITY gates. These constructions are optimal in terms of the depth and can be used to obtain the best known explicit constructions of MAJORITY circuits for other functions like the product of two n-bit numbers and the maximum of n n-bit numbers (see [3] and [SI). A crucial ingredient in our a.pproach is the construction of a discrete version of a sparse polynomial-one that has a, large absolute value for a single a.ssignment and extremely small absolute values for all other assignments. We construct sparse delta polynomials using generator matrices of certain linear block codes. In the rest of this summa.ry we sketch the ideas rehted to the construction for the COMPARISON function. More details a.nd related results appea.r in [I].