Beating Brute Force for Systems of Polynomial Equations over Finite Fields

Daniel Lokshtanov · Ramamohan Paturi · Suguru Tamaki · Ryan Williams · Huacheng Yu

SODA 2017

Time bound

O(2^0.8765n)

Space bound

Not stated in the checked source

Source / version date

4 Jan 2017

Comparison variant

Boolean · classical · worst case

Cost scale

2^{c n + o(n)}

success

Randomized

date-basis

Published online 4 January 2017

Assumptions and source notes

Randomized worst-case bound for quadratic equations over F_2. Date is the publisher’s online publication date, not a claimed first-preprint date.

Source location

Publisher abstract and publication history
Version: Checked 2026-11-08; see linked source version/date

Primary source ↗

@misc{lptwy17,
  author = {Daniel Lokshtanov and Ramamohan Paturi and Suguru Tamaki and Ryan Williams and Huacheng Yu},
  title = {{Beating Brute Force for Systems of Polynomial Equations over Finite Fields}},
  year = {2017},
  doi = {10.1137/1.9781611974782.143},
  url = {https://epubs.siam.org/doi/abs/10.1137/1.9781611974782.143},
  keywords = {MQ, polynomial method, finite fields},
  cr_date = {2017-01-04},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {SODA 2017},
  cr_author_ids = {daniel-lokshtanov; ramamohan-paturi; suguru-tamaki; ryan-williams; huacheng-yu}
}