<p>Has there been any research done on proving sparsity lower bounds for probabilistic polynomials (over the Reals) for Majority?</p>
<p>A probabilistic polynomial is a distribution of polynomials <span class="math-container">$D$</span> such that for any <span class="math-container">$x$</span> and some  parameter <span class="math-container">$\epsilon$</span>,</p>
<p><span class="math-container">$Pr_{p \sim D}[p(x) = Maj(x)] &gt; 1-\epsilon.$</span></p>
<p>And <span class="math-container">$p$</span> doesn't have to give a boolean output on the input it makes a mistake on.</p>
<p>To give some context, there are <span class="math-container">$\Theta(\sqrt n)$</span> probabilistic degree  bounds for Majority and Parity.</p>
<p>However the proofs of the lower bounds fail in the context of sparsity. Note Parity can be computed by a polynomial with sparsity 1 and degree <span class="math-container">$n$</span>, when we consider inputs over <span class="math-container">$\{-1,1\}$</span>.</p>
<p>A related notion is Polynomial Threshold Function (which is a function that outputs the sign of a real polynomial). There is a linear (and hence sparse) PTF that computes Majority (simply take <span class="math-container">$\sum_i x_i$</span>). For parity, the same linear PTF can approximate with error <span class="math-container">$\sim 1/\sqrt n$</span>.</p>
<p>So my question is can we leverage the fact that most outputs will be boolean in a probabilistic polynomial to derive any sparsity lower bounds for functions that are far from any sparse boolean function, like Majority?</p>

CC BY-SA 4.0
2022-06-29T01:49:24.427Z
Indeed we did some research a few years ago, and got what I thought were interesting results... but we were unable to publish in a conference. So we put the work aside and haven't returned to it yet. The main difficulty is that, unlike degree, the sparsity can depend very much on the basis (the elements you use for true and for false) as you note. We were able to show some fairly strong sparsity lower bounds for computing AC0 functions with {0,a} where a != 0, but not as much for {1,-1} in comparison.
Ryan Williams
CC BY-SA 4.0
2022-06-29T16:24:24.447Z
Thank you for the response, that sounds fascinating! Would it be possible to take a look at those results? If so, I can email you (or whatever you prefer).
AnonTCS
CC BY-SA 4.0
2022-06-30T20:54:10.163Z
Sure feel free to email me, rrw@mit
Ryan Williams
CC BY-SA 4.0
2022-07-06T15:16:25.603Z
emailed! thanks
AnonTCS
<cc.complexity-theory><circuit-complexity><polynomials>
Sparsity Bounds for Probabilistic Polynomials
AnonTCS
# Sparsity Bounds for Probabilistic Polynomials

(Asked by: username_0 on 2022-06-28)

Has there been any research done on proving sparsity lower bounds for probabilistic polynomials (over the Reals) for Majority?

A probabilistic polynomial is a distribution of polynomials $D$ such that for any $x$ and some parameter $\epsilon$,

$Pr\_{p \sim D}[p(x) = Maj(x)] > 1-\epsilon.$

And $p$ doesn't have to give a boolean output on the input it makes a mistake on.

To give some context, there are $\Theta(\sqrt n)$ probabilistic degree bounds for Majority and Parity.

However the proofs of the lower bounds fail in the context of sparsity. Note Parity can be computed by a polynomial with sparsity 1 and degree $n$, when we consider inputs over $\{-1,1\}$.

A related notion is Polynomial Threshold Function (which is a function that outputs the sign of a real polynomial). There is a linear (and hence sparse) PTF that computes Majority (simply take $\sum\_i x\_i$). For parity, the same linear PTF can approximate with error $\sim 1/\sqrt n$.

So my question is can we leverage the fact that most outputs will be boolean in a probabilistic polynomial to derive any sparsity lower bounds for functions that are far from any sparse boolean function, like Majority?

**Tags:** cc.complexity-theory, circuit-complexity, polynomials
> **Comments:**
> **username_1**: Indeed we did some research a few years ago, and got what I thought were interesting results... but we were unable to publish in a conference. So we put the work aside and haven't returned to it yet. The main difficulty is that, unlike degree, the sparsity can depend very much on the basis (the elements you use for true and for false) as you note. We were able to show some fairly strong sparsity lower bounds for computing AC0 functions with {0,a} where a != 0, but not as much for {1,-1} in comparison.  
> **username_0**: Thank you for the response, that sounds fascinating! Would it be possible to take a look at those results? If so, I can email you (or whatever you prefer).  
> **username_1**: Sure feel free to email me, rrw@mit  
> **username_0**: emailed! thanks  

---

## 0 answers

