<p>We are given a polynomial function <span class="math-container">$f:\{0,1\}^n\to\mathbb{R}$</span> with <span class="math-container">$\text{deg}(f)\leq d$</span> (<span class="math-container">$d$</span> is constant), and <span class="math-container">$\epsilon&gt;0$</span>; <span class="math-container">$f$</span> here is presented by its coefficients (the degree is constant, so there are <span class="math-container">$\mathrm{poly}(n)$</span> coefficients). Can we devise an interactive proof system such that the prover can convince the verifier whether there exists a positive-definite polynomial function <span class="math-container">$g:\{0,1\}^n\to\mathbb{R}^+$</span>, such that <span class="math-container">$\|f-g\|_2&lt;\epsilon$</span> (or any other norms)?</p>
<p>The degree of <span class="math-container">$f$</span> is constant, so for any input <span class="math-container">$x$</span> the verifier can calculate <span class="math-container">$f(x)$</span> in polynomial time. The verifier can randomly generate inputs to verify. But what witness can show <span class="math-container">$f$</span> isn't close to positive functions or not? Any related research, literature or ideas are welcomed.</p>

CC BY-SA 4.0
2023-08-29T20:15:36.637Z
How do you define a polynomial from $\{0,1\}^n$ to $\mathbb{R}$? You can define polynomials over the field $\mathbb{F}_2^n$, but how do you map to the reals?
lamontap
CC BY-SA 4.0
2023-08-29T20:19:34.017Z
Also, as a hint to your question, is your problem solvable in polynomial space? IP is equal to PSPACE, so as long as you don't care about the prover being efficient this would give an answer to your question.
lamontap
CC BY-SA 4.0
2023-08-30T02:29:17.623Z
@lamontap First question: you can refer to https://www.cs.tau.ac.il/~amnon/Classes/2016-PRG/Analysis-Of-Boolean-Functions.pdf Theorem 1.1 We only consider the case where the domain is $\{0,1\}^n$ For the second hint, actually I don't know how to solve it in poly space
qmww987
CC BY-SA 4.0
2023-08-30T15:06:33.350Z
Assuming that the real numbers $f(x)$ and $g(x)$ can be represented using a polynomial number of bits for every $x\in\{0,1\}^n$, you can compute $\sqrt{\sum_x (f(x)-g(x))^2}$ in polynomial space by keeping a partial sum and iterating over $x$.
lamontap
CC BY-SA 4.0
2023-08-31T09:02:39.167Z
@lamontap $g(x)$ may not be low-degree so it may not to be represented by polynomial number of bits
qmww987
<boolean-functions><interactive-proofs>
Testing positivity of a function by an IP system?
qmww987
# Testing positivity of a function by an IP system?

(Asked by: username_0 on 2023-08-18)

We are given a polynomial function $f:\{0,1\}^n\to\mathbb{R}$ with $\text{deg}(f)\leq d$ ($d$ is constant), and $\epsilon>0$; $f$ here is presented by its coefficients (the degree is constant, so there are $\mathrm{poly}(n)$ coefficients). Can we devise an interactive proof system such that the prover can convince the verifier whether there exists a positive-definite polynomial function $g:\{0,1\}^n\to\mathbb{R}^+$, such that $\|f-g\|\_2<\epsilon$ (or any other norms)?

The degree of $f$ is constant, so for any input $x$ the verifier can calculate $f(x)$ in polynomial time. The verifier can randomly generate inputs to verify. But what witness can show $f$ isn't close to positive functions or not? Any related research, literature or ideas are welcomed.

**Tags:** boolean-functions, interactive-proofs

> **Comments:**
> **username_1**: How do you define a polynomial from $\{0,1\}^n$ to $\mathbb{R}$? You can define polynomials over the field $\mathbb{F}_2^n$, but how do you map to the reals?  
> **username_1**: Also, as a hint to your question, is your problem solvable in polynomial space? IP is equal to PSPACE, so as long as you don't care about the prover being efficient this would give an answer to your question.  
> **username_0**: @username_1 First question: you can refer to https://www.cs.tau.ac.il/~amnon/Classes/2016-PRG/Analysis-Of-Boolean-Functions.pdf Theorem 1.1 We only consider the case where the domain is $\{0,1\}^n$ For the second hint, actually I don't know how to solve it in poly space  
> **username_1**: Assuming that the real numbers $f(x)$ and $g(x)$ can be represented using a polynomial number of bits for every $x\in\{0,1\}^n$, you can compute $\sqrt{\sum_x (f(x)-g(x))^2}$ in polynomial space by keeping a partial sum and iterating over $x$.  
> **username_0**: @username_1 $g(x)$ may not be low-degree so it may not to be represented by polynomial number of bits  

---

## 0 answers

