Testing systems of real quadratic equations for approximate solutions

Abstract

Consider systems of equations $q_i(x)=0$, where $q_i:{\mathbb{R}}^n⟶\mathbb{R}$, $i=1,\dots ,m$, are quadratic forms. Our goal is to tell efficiently systems with many non-trivial solutions or near-solutions $x\ne 0$ from systems that are far from having a solution. For that, we pick a delta-shaped penalty function $F:\mathbb{R}⟶[0,1]$ with $F(0)=1$ and $F(y)<1$ for $y\ne 0$ and compute the expectation of $F(q_1(x))\cdots F(q_m(x))$ for a random $x$ sampled from the standard Gaussian measure in ${\mathbb{R}}^n$. We choose $F(y)=y^{-2}{\sin }^{2}y$ and show that the expectation can be approximated within relative error $0<\epsilon <1$ in quasi-polynomial time $(m+n{)}^{O(\ln (m+n)-\ln \epsilon )}$, provided each form $q_i$ depends on not more than $r$ real variables, has common variables with at most $r-1$ other forms and satisfies $|q_i(x)|\le \gamma \Vert x{\Vert }^2/r$, where $\gamma >0$ is an absolute constant. This allows us to distinguish between "easily solvable" and "badly unsolvable" systems in some non-trivial situations.

Corrected several typos

References in corpus (3)

• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Computing the Top Betti Numbers of Semi-algebraic Sets Defined by Quadratic Inequalities in Polynomial Time
• Gromov's waist of non-radial Gaussian measures and radial non-Gaussian measures