MQ / Boolean · classical · algebraic assumptions

On the Complexity of Solving Quadratic Boolean Systems

Magali Bardet · Jean-Charles Faugère · Bruno Salvy · Pierre-Jean Spaenlehauer

Journal of Complexity 2013

PublishedSource checked

Time bound: O(2^0.792n) expected
Space bound: Not stated in the checked source

Source / version date: 29 Dec 2011
Comparison variant: Boolean · classical · algebraic assumptions
Cost scale: 2^{c n + o(n)}
success: Las Vegas; expected time
equations: m=n
field: F_2

Assumptions and source notes

For m=n, the Las Vegas bound is conditional on the stated algebraic assumptions. The same paper also gives a deterministic 0.841 bound; it is not a separate improvement in the unrestricted randomized-time list.

Source location

Abstract, arXiv v2; compare algebraic hypotheses in the paper
Version: Checked 2026-11-08; see linked source version/date

Primary source ↗

BibTeXDownload .bib

@misc{bfss11,
  author = {Magali Bardet and Jean-Charles Faugère and Bruno Salvy and Pierre-Jean Spaenlehauer},
  title = {{On the Complexity of Solving Quadratic Boolean Systems}},
  year = {2013},
  doi = {10.1016/j.jco.2012.07.001},
  url = {https://arxiv.org/abs/1112.6263},
  keywords = {MQ, BooleanSolve, Boolean systems},
  cr_date = {2011-12-29},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {Journal of Complexity 29(1):53–75},
  cr_author_ids = {magali-bardet; jean-charles-faugere; bruno-salvy; pierre-jean-spaenlehauer}
}