# Practical algorithms for finding small arithmetic circuits

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?

• Apparently the keyword I was missing was "reconstruction". This link may be the answer I was looking for cs.technion.ac.il/~shpilka/publications/SY10.pdf. Jul 18, 2014 at 1:00
• isnt this closely connected to polynomial identity testing (which has much active research)? also could it have any connections to boolean circuit simplification also?
– vzn
Jul 19, 2014 at 15:49