<p>I have a multivariate integer polynomial $f : \mathbb{Z}^n \to \mathbb{Z}$ given as either as a circuit or as a list of monomials.  I am interested in practical (though obviously exponential time) algorithms for finding smaller circuit representations of $f$.</p>

<p>The application is finding succinct representations of geometric predicates obtained by factoring other geometric predicates.  Typically the input is a predicate with a succinct circuit, and for geometric reasons the factors are likely to have succinct circuits as well even if factoring algorithms produce monomials.  The first predicates I want simplified have degrees up to 8 and minimal circuit size in the low 10s.  Somewhat expensive is okay: I can afford to wait a day for the answer.</p>

<p><strong>Three questions</strong>:</p>

<ol>
<li><p>For the promise problem where we know a succinct circuit of given size exists, what is the best worst case algorithm?  Is it possible to do significantly better than enumerate-all-circuits?</p></li>
<li><p>Are there practical circuit simplification algorithms which are both incremental and complete, in that they start with simple transformations (removing partial common factors, etc.) but are guaranteed to eventually find the minimal circuit?</p></li>
<li><p>Do the lifting techniques used to reducing polynomial factoring and irreducibility testing to bivariate polynomials extend to finding circuits in any useful way?</p></li>
</ol>

CC BY-SA 3.0
2014-07-18T01:00:06.357Z
Apparently the keyword I was missing was "reconstruction".  This link may be the answer I was looking for http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf.
Geoffrey Irving
CC BY-SA 3.0
2014-07-19T15:49:35.943Z
isnt this closely connected to [polynomial identity testing](http://en.m.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma#Comparison_of_two_polynomials) (which has much active research)? also could it have any connections to boolean circuit simplification also?
vzn
<arithmetic-circuits><succinct>
Practical algorithms for finding small arithmetic circuits
Geoffrey Irving
# Practical algorithms for finding small arithmetic circuits

(Asked by: username_0 on 2014-07-18)

I have a multivariate integer polynomial $f : \mathbb{Z}^n \to \mathbb{Z}$ given as either as a circuit or as a list of monomials. I am interested in practical (though obviously exponential time) algorithms for finding smaller circuit representations of $f$.

The application is finding succinct representations of geometric predicates obtained by factoring other geometric predicates. Typically the input is a predicate with a succinct circuit, and for geometric reasons the factors are likely to have succinct circuits as well even if factoring algorithms produce monomials. The first predicates I want simplified have degrees up to 8 and minimal circuit size in the low 10s. Somewhat expensive is okay: I can afford to wait a day for the answer.

**Three questions**:

1. For the promise problem where we know a succinct circuit of given size exists, what is the best worst case algorithm? Is it possible to do significantly better than enumerate-all-circuits?
2. Are there practical circuit simplification algorithms which are both incremental and complete, in that they start with simple transformations (removing partial common factors, etc.) but are guaranteed to eventually find the minimal circuit?
3. Do the lifting techniques used to reducing polynomial factoring and irreducibility testing to bivariate polynomials extend to finding circuits in any useful way?

**Tags:** arithmetic-circuits, succinct
> **Comments:**
> **username_0**: Apparently the keyword I was missing was "reconstruction".  This link may be the answer I was looking for http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf.  
> **username_1**: isnt this closely connected to [polynomial identity testing](http://en.m.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma#Comparison_of_two_polynomials) (which has much active research)? also could it have any connections to boolean circuit simplification also?  

---

## 0 answers

