Consider systems of equations q_i(x)=0, where q_i: {\Bbb R}^n \longrightarrow {\Bbb R}, i=1, \ldots, m, are quadratic forms. We want to be able 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  penalty function F: {\Bbb R} \longrightarrow [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 {\Bbb 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)| \leq \gamma \|x\|^2/r, where \gamma >0 is an absolute constant  .
Consider systems of equations q_i(x)=0, where q_i: {\Bbb R}^n \longrightarrow {\Bbb R}, i=1, \ldots, 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: {\Bbb R} \longrightarrow [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 {\Bbb 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)| \leq \gamma \|x\|^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 .
R
We want to be able to
Our goal is to
R
near solutions
near-solutions
A
delta-shaped
A
. This allows us to distinguish between "easily solvable" and "badly unsolvable" systems in some non-trivial situations