Multivariate quadratic equations
Solve a system of m quadratic equations in n variables over a specified finite field.
Boolean · classical · worst case
Degree at most 2 over F_2; n variables; polynomially many explicitly represented equations
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Improved Algorithms for Solving Polynomial Systems over GF(2) by Multiple Parity-CountingSODA 2021SourceBibTeX / details | 10 May 2020 | O(20.6943n) | Not stated in the checked source | PublishedSource checked |
| 2 | Solving Systems of Polynomial Equations over GF(2) by a Parity-Counting Self-ReductionICALP 2019SourceBibTeX / details | 4 Jul 2019 | O*(20.804n) | Not stated in the checked source | PublishedSource checked |
| 3 | Beating Brute Force for Systems of Polynomial Equations over Finite FieldsSODA 2017SourceBibTeX / details | 4 Jan 2017 | O(20.8765n) | Not stated in the checked source | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Degree at most 2 over F_2; n variables; polynomially many explicitly represented equations
- Computation
- Classical
- Rigor
- Provable
- Instances
- Arbitrary Boolean quadratic systems
- Cost scale
- 2^{c n + o(n)}
- Parameter
- n
- Description
- Degree at most 2 over F_2; n variables; polynomially many explicitly represented equations
- Comparison rules
- Compare randomized worst-case solution-finding bounds over F_2, suppressing polynomial factors. Do not mix algebraic regularity assumptions, fixed equation-density heuristics, or higher-degree bounds into this list.
- Tags
- binary field, worst-case, bounded error