On the Intersection of a Sparse Curve and a Low-degree Curve: A Polynomial Version of the Lost Theor
summary
Proves a concrete polynomial bound in d and t on the number of real solutions (and real connected components) of a system f(x,y)=0 with deg(f) ≤ d and g(x,y) t-sparse, improving prior exponential estimates. Method splits x-line into ≤ d^2 intervals with ≤ d algebraic branches via cylindrical algebraic decomposition, then bounds roots of substituted sums by counting zeros of specific Wronskians; the final count is an explicit polynomial function of d and t rather than exp(like) growth.
AI-written summary · about
chapters (18)
- 0:00Intro
- 0:28Descartes' rule
- 1:57Bezout's Theorem
- 3:23An initial case
- 4:10Fewnomial bounds
- 5:27Improvement
- 5:53Intersection of a trinomial curve with a sparse curve
- 7:02Sevostyanov's problem
- 7:50Stronger hypothesis
- 9:01From the lemma to the theorem
- 10:16Outline of the proof
- 10:54Cylindrical algebraic decomposition
- 11:51To bound the number of roots of a sum
- 12:20The key of the proof: the Wronskian
- 13:27From sum to Wronskians
- 16:46What remains to be done
- 17:43Bounds for W
- 20:57Perspectives
related talks
47mHardness Amplification and the Approximate Degree of Constant-Depth Circuits
01h 01mTrue Complexity of Multilinear Systems
01h 00mOrbit Closures
55mLower Bounds Against PC With Extension Variables
20mFast and Optimal Extraction for Sparse Equality Graphs
17mSatisfiability Algorithms Based on Concentrated Shrinkage
37mPolynomial Identity Testing via Evaluation of Rational Functions
14mFast Linear Programming through Transprecision Computing on Small and Sparse Data