MQ / Boolean · classical · worst case

Improved Algorithms for Solving Polynomial Systems over GF(2) by Multiple Parity-Counting

Itai Dinur

SODA 2021

PublishedSource checked

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

Source / version date: 10 May 2020
Comparison variant: Boolean · classical · worst case
Cost scale: 2^{c n + o(n)}
success: Find a solution or decide none exists, with high probability
field: F_2

Assumptions and source notes

Worst-case randomized solution finding over F_2, degree at most 2. Rounded upper bound as stated in the abstract, not a numerical benchmark.

Source location

Abstract, arXiv:2005.04800v2
Version: Checked 2026-11-08; see linked source version/date

Primary source ↗

BibTeXDownload .bib

@misc{dinur20-mq,
  author = {Itai Dinur},
  title = {{Improved Algorithms for Solving Polynomial Systems over GF(2) by Multiple Parity-Counting}},
  year = {2021},
  url = {https://arxiv.org/abs/2005.04800},
  keywords = {MQ, parity counting, worst-case},
  cr_date = {2020-05-10},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {SODA 2021},
  cr_author_ids = {itai-dinur}
}