View abstract

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).

View abstract PDF