<p>This question has a somewhat trivial answer because the polynomial <span class="math-container">$x^{2^s}$</span> requires <span class="math-container">$s$</span> multiplications, so you can just take <span class="math-container">$h = x_1^{2^{f(n)}}$</span>. This is one of the reasons why in algebraic complexity we almost always talk about families with polynomially bounded degree.</p>
<p>For a less trivial statement, we can use the same strategy as in the Boolean settings, but instead of simple counting, in algebraic complexity we use dimension counting.</p>
<p>Main idea: in a circuit computing a non-constant function has <span class="math-container">$s$</span> gates, then it has at most <span class="math-container">$s$</span> constants. By fixing the structure of the circuit and varying the constants we see that the set of all polynomials computed by the fixed circuit (which is a Zariski constructible set by Chevalley's theorem) has dimension at most <span class="math-container">$s$</span>. There is only finite number of circuits of complexity <span class="math-container">$s$</span>, so the set of all polynomials with complexity <span class="math-container">$s$</span> has dimension at most <span class="math-container">$s$</span>. Comparing <span class="math-container">$s$</span> with the dimension of the set of polynomials with given degree and number of variables, we can get a statement about the existence of hard polynomials.</p>

CC BY-SA 4.0
2023-10-31T11:35:56.307Z
2023-10-31T11:35:56.307Z
Vladimir Lysikov
<p>The answers to the following question -</p>
<p><a href="https://cstheory.stackexchange.com/questions/5110/hierarchy-theorem-for-circuit-size">Hierarchy theorem for circuit size</a></p>
<p>give a &quot;circuit hierarchy theorem&quot; for boolean circuits. Does there exist a similar hierarchy theorem for arithmetic circuits? In particular, for <span class="math-container">$f(n) &gt;&gt; g(n)$</span> (for some notion of &gt;&gt;) does there exist a family of polynomials <span class="math-container">$h(x_1, \cdots, x_n) \in \mathbb{F}(x_1, \cdots x_n)$</span>, <span class="math-container">$n \geq 1$</span>, computable by arithmetic circuits of size <span class="math-container">$f(n)$</span> but not by arithmetic circuits of size <span class="math-container">$g(n)$</span>?</p>

CC BY-SA 4.0
2023-05-21T03:59:27.603Z
I think an idea similar to the second answer works.
ramseysdream111
<lower-bounds><algebraic-complexity><hierarchy-theorems>
Arithmetic Circuit Hierarchy?
ramseysdream111
# Arithmetic Circuit Hierarchy?

(Asked by: username_0 on 2023-05-19)

The answers to the following question -

[Hierarchy theorem for circuit size](https://cstheory.stackexchange.com/questions/5110/hierarchy-theorem-for-circuit-size)

give a "circuit hierarchy theorem" for boolean circuits. Does there exist a similar hierarchy theorem for arithmetic circuits? In particular, for $f(n) >> g(n)$ (for some notion of >>) does there exist a family of polynomials $h(x\_1, \cdots, x\_n) \in \mathbb{F}(x\_1, \cdots x\_n)$, $n \geq 1$, computable by arithmetic circuits of size $f(n)$ but not by arithmetic circuits of size $g(n)$?

**Tags:** lower-bounds, algebraic-complexity, hierarchy-theorems

> **Comments:**
> **username_0**: I think an idea similar to the second answer works.  

---

## 1 answers

### Answer by username_1 on 2023-10-31. Score: 1

This question has a somewhat trivial answer because the polynomial $x^{2^s}$ requires $s$ multiplications, so you can just take $h = x\_1^{2^{f(n)}}$. This is one of the reasons why in algebraic complexity we almost always talk about families with polynomially bounded degree.

For a less trivial statement, we can use the same strategy as in the Boolean settings, but instead of simple counting, in algebraic complexity we use dimension counting.

Main idea: in a circuit computing a non-constant function has $s$ gates, then it has at most $s$ constants. By fixing the structure of the circuit and varying the constants we see that the set of all polynomials computed by the fixed circuit (which is a Zariski constructible set by Chevalley's theorem) has dimension at most $s$. There is only finite number of circuits of complexity $s$, so the set of all polynomials with complexity $s$ has dimension at most $s$. Comparing $s$ with the dimension of the set of polynomials with given degree and number of variables, we can get a statement about the existence of hard polynomials.


---

