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?


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.