Faster Satisfiability Algorithms for Systems of Polynomial Equations over Finite Fields and ACC^0[p]
Talkat Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms · on Friday, 2015-11-06·
summary
Randomized algorithm solves SysPol_q on degree-k instances in time q^{n (1 - 1/O(q^k))}, giving 0.868765^n for GF(2), and for prime q the counting version gets a matching deterministic bound. Key ingredients are the polynomial method, low-degree probabilistic-polynomial approximations built from small-biased spaces and modulus-amplifying polynomials, fast evaluation of multilinear polynomials, and a combinatorial degree reduction* that turns unbounded-degree GF(2) inputs with S monomials into many degree-k instances; current algorithms use exponential space.
AI-written summary · about
chapters (8)
- 0:00Start
- 4:47Previous Algorithms
- 10:37Optimality of Our Results
- 15:57Basic Idea
- 22:03Analysis of Our Algorithm
- 23:06On Deterministic Algorithms
- 24:06Our Algorithm for unbounded degree
- 27:37Future Directions
related talks
56mSatisfiability Algorithms II
01h 09mCircuit Analysis Algorithms
01h 07mComputational Complexity of Polynomial Time Problems: Introduction
01h 07mSatisfiability Algorithms I
58mCircuit Complexity and Connections I
01h 10mProof of NEXP Not in ACC
10mQuery, Communication and Discrepancy
58mExponential-Time Algorithms