MQ / Boolean · classical · worst case

Solving Systems of Polynomial Equations over GF(2) by a Parity-Counting Self-Reduction

Andreas Björklund · Petteri Kaski · Ryan Williams

ICALP 2019

PublishedSource checked

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

Source / version date: 4 Jul 2019
Comparison variant: Boolean · classical · worst case
Cost scale: 2^{c n + o(n)}
success: Randomized; parity-counting self-reduction

Assumptions and source notes

Worst-case bound for all Boolean quadratic systems. Date is the verified ICALP publication date.

Source location

Abstract; official publication date 2019-07-04
Version: Checked 2026-11-08; see linked source version/date

Primary source ↗

BibTeXDownload .bib

@misc{bkw19-mq,
  author = {Andreas Björklund and Petteri Kaski and Ryan Williams},
  title = {{Solving Systems of Polynomial Equations over GF(2) by a Parity-Counting Self-Reduction}},
  year = {2019},
  doi = {10.4230/LIPIcs.ICALP.2019.26},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.26},
  keywords = {MQ, parity counting, polynomial method},
  cr_date = {2019-07-04},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {ICALP 2019},
  cr_author_ids = {andreas-bjorklund; petteri-kaski; ryan-williams}
}