Multivariate quadratic equations
Solve a system of m quadratic equations in n variables over a specified finite field.
Boolean · classical · algebraic assumptions
m=n quadratic equations over F_2 satisfying the source algebraic hypotheses
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | On the Complexity of Solving Quadratic Boolean SystemsJournal of Complexity 2013SourceBibTeX / details | 29 Dec 2011 | O(20.792n) expected | Not stated in the checked source | PublishedSource checked |
Comparison definition & assumptions
- Regime
- m=n quadratic equations over F_2 satisfying the source algebraic hypotheses
- Computation
- Classical
- Rigor
- Conditional
- Instances
- Algebraic regularity assumptions
- Cost scale
- 2^{c n + o(n)}
- Parameter
- n
- Description
- m=n quadratic equations over F_2 satisfying the source algebraic hypotheses
- Comparison rules
- The source must state its algebraic hypotheses. Expected Las Vegas and deterministic guarantees are recorded in the entry. These are not unconditional worst-case bounds.
- Tags
- binary field, semi-regularity, m=n