2019/03/06 by Chi-Ning Chou, Mrinal Kumar, Chou, Chi-Ning +3
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1903.02366
openalex publication_date 2019/03/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this note, we give a short, simple and almost completely self contained proof of a classical result of Kaltofen [Kal86, Kal87, Kal89] which shows that if an n variate degree d polynomial f can be computed by an arithmetic circuit of size s, then each of its factors can be computed by an arithmetic circuit of size at most \textsfpoly(s, n, d). However, unlike Kaltofen's argument, our proof does not directly give an efficient algorithm for computing the circuits for the factors of f.