Search papers, labs, and topics across Lattice.
This paper addresses the challenging problem of finding minimal arithmetic circuits for polynomials over finite fields by formulating it as a reinforcement learning task, utilizing both bottom-up and top-down approaches. The authors introduce FactorLibrary, a novel mechanism that stores reusable factorizable subexpressions to manage the combinatorial explosion of potential solutions. Their experiments reveal that the top-down agent using PPO+MCTS achieves a remarkable 91.8% success rate in identifying certified optimal circuits of complexity up to 8.
FactorLibrary enables a 91.8% success rate in finding optimal polynomial circuits, revolutionizing how we tackle combinatorial complexity in algebra.
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\%$.
