<p>It's not clear if this is directly useful, but lower bounds are known for depth-3 circuits computing an <span class="math-container">$n$</span>-variate version of your function over <span class="math-container">$\mathrm{GF}(p)$</span> for <span class="math-container">$p \neq 2$</span>. See <a href="https://www.cs.tau.ac.il/~shpilka/publications/SY10.pdf" rel="nofollow noreferrer">Theorem 3.7 in the survey of Shpilka and Yehudayoff</a> for details and references.</p>

<p>I don't believe lower bounds of the form <span class="math-container">$\omega(\log d)$</span> are known for general circuits computing an explicit univariate polynomial of degree <span class="math-container">$d$</span>, so proving an <span class="math-container">$\omega(\log p)$</span> lower bound for your problem will likely be difficult.</p>

CC BY-SA 4.0
2019-10-07T02:26:38.770Z
Thank you for the response.  While it doesn't directly apply to the problem I mentioned here, there is a bounty of references in that survey that we will investigate.  We looked at trying to tie the problem to evaluating polynomials of degree $d$, but this seemed difficult due to things like the possibility of repeated squaring.
A Lost Cryptographer
CC BY-SA 4.0
2019-10-07T03:00:45.427Z
I believe these are referenced in Shpilka-Yehudayoff, but [Bürgisser-Clausen-Shokrollahi's _Algebraic Complexity Theory_](https://www.springer.com/gp/book/9783540605829) and chapter 8 of [Bürgisser's _Completeness and Reduction in Algebraic Complexity_](https://www.springer.com/gp/book/9783540667520) touch more on the complexity of univariate polynomials. Unfortunately, I'm not familiar enough with BCS to point towards something concretely useful. Hopefully something in these turns out to be useful.
Robert Andrews
CC BY-SA 4.0
2019-10-06T18:49:25.847Z
2019-10-06T18:49:25.847Z
Robert Andrews
<p>Let <span class="math-container">$p$</span> be a prime.  Suppose we consider the function <span class="math-container">$f: GF\left(p \right) \rightarrow \left\{0, 1 \right\}$</span> where <span class="math-container">$f(x) = x \bmod 2$</span> for all.</p>

<p>The question is the following:  are there any known circuit bounds or results on computing <span class="math-container">$f$</span> using <strong>arithmetic circuits</strong> over <span class="math-container">$GF(p)$</span>?  </p>

<p>In other words, we'd like to evaluate <span class="math-container">$f$</span> using only field additions and multiplications.  </p>

<p>It's simple to do this with arithmetic circuits of size <span class="math-container">$O \left(p \right)$</span> and also probably straightforward to show that it cannot be done with arithmetic circuits of size <span class="math-container">$o\left( \log p \right)$</span>.  However, it has been difficult for us to say anything concrete other than these simple bounds.  Any literature or references on this problem (or similar types of problem) would be greatly appreciated!  Thanks!       </p>

CC BY-SA 4.0
2019-10-05T03:10:57.957Z
What is your notion of $x\mod 2$ here? My understanding is it must depend on the underlying representative (for example, in $\mathbb{F}_5$, $0\mod 2\neq 5\mod 2$, even though $0,5\in\overline{0}$).
Mark Schultz-Wu
CC BY-SA 4.0
2019-10-05T07:41:45.153Z
Thanks for the response!  Sorry I was not more precise in asking this question.  If we continue the analogy of working over the integers $\mod p$, let's assume that $x \in \left[0, p - 1 \right]$.  This avoids the issue you mention above.
A Lost Cryptographer
CC BY-SA 4.0
2019-10-07T20:41:05.250Z
It seems that a circuit with $O(p^{1/2 + \varepsilon})$ gates is achievable by multipoint evaluation of $\prod\limits_{i=0}^{B-1} (x - 2i)$ for $B \approx \sqrt{p}$. I can write a full answer if this interests you.
Kaban-5
CC BY-SA 4.0
2019-10-08T05:14:30.777Z
That's a clever trick.  Thank you for pointing it out.  I think you explained it well enough already--no need for a full answer.  I am very curious, though, if that's the best you can do or if there is something better.  At least for me, anything better would be quite surprising (and very cool).
A Lost Cryptographer
<arithmetic-circuits>
Arithmetic circuits over $GF(p)$ for computing $x \bmod 2$ given input $x \in GF(p)$
A Lost Cryptographer
# Arithmetic circuits over $GF(p)$ for computing $x \bmod 2$ given input $x \in GF(p)$

(Asked by: username_0 on 2019-10-04)

Let $p$ be a prime. Suppose we consider the function $f: GF\left(p \right) \rightarrow \left\{0, 1 \right\}$ where $f(x) = x \bmod 2$ for all.

The question is the following: are there any known circuit bounds or results on computing $f$ using **arithmetic circuits** over $GF(p)$?

In other words, we'd like to evaluate $f$ using only field additions and multiplications.

It's simple to do this with arithmetic circuits of size $O \left(p \right)$ and also probably straightforward to show that it cannot be done with arithmetic circuits of size $o\left( \log p \right)$. However, it has been difficult for us to say anything concrete other than these simple bounds. Any literature or references on this problem (or similar types of problem) would be greatly appreciated! Thanks!

**Tags:** arithmetic-circuits

> **Comments:**
> **username_1**: What is your notion of $x\mod 2$ here? My understanding is it must depend on the underlying representative (for example, in $\mathbb{F}_5$, $0\mod 2\neq 5\mod 2$, even though $0,5\in\overline{0}$).  
> **username_0**: Thanks for the response!  Sorry I was not more precise in asking this question.  If we continue the analogy of working over the integers $\mod p$, let's assume that $x \in \left[0, p - 1 \right]$.  This avoids the issue you mention above.  
> **username_2**: It seems that a circuit with $O(p^{1/2 + \varepsilon})$ gates is achievable by multipoint evaluation of $\prod\limits_{i=0}^{B-1} (x - 2i)$ for $B \approx \sqrt{p}$. I can write a full answer if this interests you.  
> **username_0**: That's a clever trick.  Thank you for pointing it out.  I think you explained it well enough already--no need for a full answer.  I am very curious, though, if that's the best you can do or if there is something better.  At least for me, anything better would be quite surprising (and very cool).  

---

## 1 answers

### Answer by username_3 on 2019-10-06. Score: 2

It's not clear if this is directly useful, but lower bounds are known for depth-3 circuits computing an $n$-variate version of your function over $\mathrm{GF}(p)$ for $p \neq 2$. See [Theorem 3.7 in the survey of Shpilka and Yehudayoff](https://www.cs.tau.ac.il/~shpilka/publications/SY10.pdf) for details and references.

I don't believe lower bounds of the form $\omega(\log d)$ are known for general circuits computing an explicit univariate polynomial of degree $d$, so proving an $\omega(\log p)$ lower bound for your problem will likely be difficult.

> **Comments:**
> **username_0**: Thank you for the response.  While it doesn't directly apply to the problem I mentioned here, there is a bounty of references in that survey that we will investigate.  We looked at trying to tie the problem to evaluating polynomials of degree $d$, but this seemed difficult due to things like the possibility of repeated squaring.  
> **username_3**: I believe these are referenced in Shpilka-Yehudayoff, but [Bürgisser-Clausen-Shokrollahi's _Algebraic Complexity Theory_](https://www.springer.com/gp/book/9783540605829) and chapter 8 of [Bürgisser's _Completeness and Reduction in Algebraic Complexity_](https://www.springer.com/gp/book/9783540667520) touch more on the complexity of univariate polynomials. Unfortunately, I'm not familiar enough with BCS to point towards something concretely useful. Hopefully something in these turns out to be useful.  

---

