Session II.3 - Real-Number Complexity
Saturday, June 17, 17:00 ~ 17:30
On the Average-Case Complexity of Real Feasibility for Circuit Hypersurfaces
J. Maurice Rojas
Texas A&M University, USA - This email address is being protected from spambots. You need JavaScript enabled to view it.
Deciding whether even a single polynomial equation has a real solution is NP-hard, so it is natural to look for speed-ups. One speed-up comes from sparsity, but the necessary tools involve diophantine approximation, e.g., Baker's Theorem on linear forms in logarithms. Further improvements seem to require randomization,
So we propose a randomized version of Baker's Theorem which appears to be new. As a consequence, we can show that deciding real feasibility for n-variate (n+2)-nomials can be sped up if one averages over exponents. We also discuss some preliminary work on averaging over coefficients.
Joint work with Weixun Deng (Texas A&M University), Alperen Ergur (University of Texas at San Antonio), and Grigoris Paouris (Texas A&M University).