4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What do you mean by equivalence exactly? Do you want to test whether the functions computed by the two circuits are the same? $\endgroup$ – Bruno Apr 4 '14 at 12:28
  • $\begingroup$ Does your class of circuits fit into the framework for polynomial identity testing? $\endgroup$ – András Salamon Apr 4 '14 at 12:30
  • $\begingroup$ 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. $\endgroup$ – Bruno Apr 4 '14 at 12:33
  • 2
    $\begingroup$ I think this paper is related: Deterministically testing sparse polynomial identities of unbounded degree. Another question: Are you interested in deterministic or randomized algorithms? $\endgroup$ – Bruno Apr 4 '14 at 15:16
  • 1
    $\begingroup$ If you're unsure, you should start with the randomized versions, since they are generally much, much simpler. $\endgroup$ – Geoffrey Irving Apr 4 '14 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.