## 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. document.getElementById('cloakb764e2ecb257b2df44737499b777910d').innerHTML = ''; var prefix = '&#109;a' + 'i&#108;' + '&#116;o'; var path = 'hr' + 'ef' + '='; var addyb764e2ecb257b2df44737499b777910d = 'jm&#97;&#117;r&#105;c&#101;r&#111;j&#97;s' + '&#64;'; addyb764e2ecb257b2df44737499b777910d = addyb764e2ecb257b2df44737499b777910d + 'gm&#97;&#105;l' + '&#46;' + 'c&#111;m'; var addy_textb764e2ecb257b2df44737499b777910d = 'jm&#97;&#117;r&#105;c&#101;r&#111;j&#97;s' + '&#64;' + 'gm&#97;&#105;l' + '&#46;' + 'c&#111;m';document.getElementById('cloakb764e2ecb257b2df44737499b777910d').innerHTML += '<a ' + path + '\'' + prefix + ':' + addyb764e2ecb257b2df44737499b777910d + '\'>'+addy_textb764e2ecb257b2df44737499b777910d+'<\/a>';

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