Multivariate quadratic equations
Solve a system of m quadratic equations in n variables over a specified finite field.
F_3 · classical · worst case
Fixed q=3, degree d=2, n variables, explicitly represented equations
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Solving Polynomial Equations Over Finite FieldsSODA 2025SourceBibTeX / details | 26 Oct 2024 | O*(30.696n) | Not stated in the checked source | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Fixed q=3, degree d=2, n variables, explicitly represented equations
- Computation
- Classical
- Rigor
- Provable
- Instances
- Arbitrary quadratic systems over F_3
- Cost scale
- 3^{c n + o(n)}
- Parameter
- n
- Description
- Fixed q=3, degree d=2, n variables, explicitly represented equations
- Comparison rules
- Normalize in base 3, not base 2. The coefficient is meaningful only for fixed q=3, degree 2. Compare decision or solution-finding guarantees explicitly; self-reduction is polynomial for fixed degree and field.
- Tags
- field size 3, worst-case, bounded error