FactorLibrary: From Polynomials to Circuits via Recursive Subgoals
This work addresses the hard combinatorial problem of minimal circuit discovery for algebraic complexity theorists, but the results are limited to small circuits (complexity ≤8) and the approach is incremental.
FactorLibrary formulates the problem of finding minimal arithmetic circuits for polynomials over finite fields as a reinforcement learning task, using reusable subgoals to manage the combinatorial search space. The PPO+MCTS top-down agent achieved a 91.8% success rate in finding certified optimal circuits up to complexity 8.
Finding minimal arithmetic circuits for polynomials over finite fields is a combinatorially hard problem central to algebraic complexity theory. We formulate it as a reinforcement learning problem in two directions, bottom-up and top-down. To address the challenge of a fast-growing combinatorial search space, we introduce FactorLibrary, which stores factorizable subexpressions that serve as reusable subgoals across training episodes. We trained a bottom-up agent with Gumbel-PPO-MCTS and two top-down agents with PPO+MCTS and SAC. The PPO+MCTS top-down agent exhibited the most stable performance, finding certified optimal circuits up to complexity $8$ with a success rate of $91.8\%$.