CircuitBuilder: From Polynomials to Circuits via Reinforcement Learning
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912972180291584 |
|---|---|
| author | Zhang, Weikun K. Pandey, Rohan Mehta, Bhaumik Jin, Kaijie Morato, Naomi Ganapule, Archit Zeng, Michael Ruofan Alper, Jarod |
| author_facet | Zhang, Weikun K. Pandey, Rohan Mehta, Bhaumik Jin, Kaijie Morato, Naomi Ganapule, Archit Zeng, Michael Ruofan Alper, Jarod |
| contents | Motivated by auto-proof generation and Valiant's VP vs. VNP conjecture, we study the problem of discovering efficient arithmetic circuits to compute polynomials, using addition and multiplication gates. We formulate this problem as a single-player game, where an RL agent attempts to build the circuit within a fixed number of operations. We implement an AlphaZero-style training loop and compare two approaches: Proximal Policy Optimization with Monte Carlo Tree Search (PPO+MCTS) and Soft Actor-Critic (SAC). SAC achieves the highest success rates on two-variable targets, while PPO+MCTS scales to three variables and demonstrates steady improvement on harder instances. These results suggest that polynomial circuit synthesis is a compact, verifiable setting for studying self-improving search policies. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_17075 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | CircuitBuilder: From Polynomials to Circuits via Reinforcement Learning Zhang, Weikun K. Pandey, Rohan Mehta, Bhaumik Jin, Kaijie Morato, Naomi Ganapule, Archit Zeng, Michael Ruofan Alper, Jarod Machine Learning Artificial Intelligence Computational Complexity 68Q06, 68T05, 68Q15, 68W30 Motivated by auto-proof generation and Valiant's VP vs. VNP conjecture, we study the problem of discovering efficient arithmetic circuits to compute polynomials, using addition and multiplication gates. We formulate this problem as a single-player game, where an RL agent attempts to build the circuit within a fixed number of operations. We implement an AlphaZero-style training loop and compare two approaches: Proximal Policy Optimization with Monte Carlo Tree Search (PPO+MCTS) and Soft Actor-Critic (SAC). SAC achieves the highest success rates on two-variable targets, while PPO+MCTS scales to three variables and demonstrates steady improvement on harder instances. These results suggest that polynomial circuit synthesis is a compact, verifiable setting for studying self-improving search policies. |
| title | CircuitBuilder: From Polynomials to Circuits via Reinforcement Learning |
| topic | Machine Learning Artificial Intelligence Computational Complexity 68Q06, 68T05, 68Q15, 68W30 |
| url | https://arxiv.org/abs/2603.17075 |