<p>I have a very specific problem that appears to be close to equivalence testing for arithmetic circuits (checking whether the computed functions are the same). </p>

<p>Since I'm completely new to the field, I'm asking for some references, hopefully as close as possible to my concrete problem.</p>

<p>I want to find out the complexity of comparing two arithmetic circuits (directed graphs with addition and multiplication nodes). My concrete problem has the following particularities.</p>

<ul>
<li>There is only one input variable. Thus the circuits encode a function $\mathbb{N} \to \mathbb{N}$. Are there any results about a constant number of input variables?</li>
<li>There might appear leafs of the form $c^n$ with $n$ being the input variable and $c \in \mathbb{N}$ some constant.</li>
</ul>

<p>I'm happy with both surveys or original works about such equivalence problems. Books are also ok, but I prefer material that's downloadable.</p>

CC BY-SA 3.0
2014-04-04T12:28:40.553Z
What do you mean by *equivalence* exactly? Do you want to test whether the functions computed by the two circuits are the same?
Bruno
CC BY-SA 3.0
2014-04-04T12:30:41.930Z
Does your class of circuits fit into the framework for polynomial identity testing?
András Salamon
CC BY-SA 3.0
2014-04-04T12:33:53.040Z
Suppose there is no $c^n$ input, so that the function represented by a circuit is a polynomial. Do you have an *a priori* bound on the degree of this polynomial? Because you can test equality in time polynomial in this degree (say $d$), by testing equality on $(d+1)$ input values.
Bruno
CC BY-SA 3.0
2014-04-04T12:40:12.837Z
@Bruno Yes, I mean checking whether the computed functions are the same. And I have no bound on the degree.
ziggystar
CC BY-SA 3.0
2014-04-04T15:16:13.967Z
I think this paper is related: [Deterministically testing sparse polynomial identities of unbounded degree](http://www.sciencedirect.com/science/article/pii/S0020019008003049).

Another question: Are you interested in deterministic or randomized algorithms?
Bruno
CC BY-SA 3.0
2014-04-04T16:08:26.947Z
I have a look at this paper, thank you. Currently I'm just trying to obtain an understanding of the problem, and I will start with looking at deterministic algorithms.
ziggystar
CC BY-SA 3.0
2014-04-04T16:22:58.040Z
If you're unsure, you should start with the randomized versions, since they are generally much, much simpler.
Geoffrey Irving
<reference-request><arithmetic-circuits>
Complexity of equivalence testing of arithmetic circuits
ziggystar
# Complexity of equivalence testing of arithmetic circuits

(Asked by: username_0 on 2014-04-04)

I have a very specific problem that appears to be close to equivalence testing for arithmetic circuits (checking whether the computed functions are the same).

Since I'm completely new to the field, I'm asking for some references, hopefully as close as possible to my concrete problem.

I want to find out the complexity of comparing two arithmetic circuits (directed graphs with addition and multiplication nodes). My concrete problem has the following particularities.

* There is only one input variable. Thus the circuits encode a function $\mathbb{N} \to \mathbb{N}$. Are there any results about a constant number of input variables?
* There might appear leafs of the form $c^n$ with $n$ being the input variable and $c \in \mathbb{N}$ some constant.

I'm happy with both surveys or original works about such equivalence problems. Books are also ok, but I prefer material that's downloadable.

**Tags:** reference-request, arithmetic-circuits

> **Comments:**
> **username_1**: What do you mean by *equivalence* exactly? Do you want to test whether the functions computed by the two circuits are the same?  
> **username_2**: Does your class of circuits fit into the framework for polynomial identity testing?  
> **username_1**: Suppose there is no $c^n$ input, so that the function represented by a circuit is a polynomial. Do you have an *a priori* bound on the degree of this polynomial? Because you can test equality in time polynomial in this degree (say $d$), by testing equality on $(d+1)$ input values.  
> **username_0**: @username_1 Yes, I mean checking whether the computed functions are the same. And I have no bound on the degree.  
> **username_1**: I think this paper is related: [Deterministically testing sparse polynomial identities of unbounded degree](http://www.sciencedirect.com/science/article/pii/S0020019008003049).  Another question: Are you interested in deterministic or randomized algorithms?  
> **username_0**: I have a look at this paper, thank you. Currently I'm just trying to obtain an understanding of the problem, and I will start with looking at deterministic algorithms.  
> **username_3**: If you're unsure, you should start with the randomized versions, since they are generally much, much simpler.  

---

## 0 answers

