# Tag Info

Accepted

### Low-depth arithmetic complexity of the product of $k$ matrices

I am not sure about specifically depth-three lower bounds, but there has been a lot of depth-4 (and 5) lower bounds, usually assuming other constraints as well. For instance (and without any claim of ...

### Reference request: Arithmetic circuit complexity

In addition to the references already mentioned, you could check out Xi Chen, Neeraj Kayal and Avi Wigderson (2011), Partial Derivatives in Arithmetic Complexity and Beyond, Foundations and Trends®...

### Reference request: Arithmetic circuit complexity

This depends on what you want to do. For more structural questions there is a relatively recent survey by Meena Mahajan: Meena Mahajan: Algebraic Complexity Classes. There is also the book by ...
Accepted

### Lower bound for constant degree monotone arithmetic circuits

The Nisan--Wigderson polynomials are one example. That is, let $$\mathrm{NW}_{n,m,d}(\vec{x}) := \sum_{\substack{p(t) \in \mathbb{F}_m[t] \\ \deg(p) \le d}} x_{1,p(1)} \cdots x_{n,p(n)}.$$ Let $k$ ...
Accepted

### Has there been a study of circuits operating on arrays?

Not really an answer, but would've been too long a comment. The result of Ben-Or and Cleve that arithmetic formulas can be simulated by branching programs of width 3, works over arbitrary non-...

### Optimal evaluation of polynomials / rational functions

In Knuth Vol II Theorem E on page 494 he presents an algorithm that can evaluate a polynomial using $\frac{n}{2} + 2$ multiplications. The theoretical minimum is $\frac{n}{2}$, assuming generic ...

### Arithmetic circuits over $GF(p)$ for computing $x \bmod 2$ given input $x \in GF(p)$

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 ...

### How to build comparison operator (comparator) in an arithmetic circuit

I believe this is generally done in MPC by converting the sharing of the field element to some sharing more amenable to comparison. See this (section 6.3), or chapter 9 in Secure Multiparty ...
1 vote
Accepted

### doubt in the proof of reducing any arithmetic circuit to log(d) depth, where d is the degree of the polynomial it is computing

See that $w\in \mathcal{F}_m$ so $\deg(w)\geq m$ but $\deg(w_L),\deg(w_R)<m$. So if $\deg(w_L)=\deg(w_R)=m-1$ then $\deg(w)$ becomes $2m-2$. If $m$ is large enough then $2m-2 >m$. Hence we can ...
1 vote
Accepted

### Is homogeneity required in Hyafil's arithmetic circuit decomposition theorem when applied to monotone circuits?

No, homogeneity is not required when applying this theorem to monotone circuits, and in fact homogeneity is a quite technical restriction that can be removed even in the general case by weakening the ...

Only top scored, non community-wiki answers of a minimum length are eligible