3 papers
cs.CC2025
Modular composition & polynomial GCD in the border of small, shallow circuits
Robert Andrews, Mrinal Kumar, Shanthanu S. Rai
Modular composition is the problem of computing the coefficient vector of the polynomial , given as input the coefficient vectors of univariate polynomials ,…
cs.CC2025
On Closure Properties of Read-Once Oblivious Algebraic Branching Programs
Jules Armand, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen +3
We investigate the closure properties of read-once oblivious Algebraic Branching Programs (roABPs) under various natural algebraic operations and prove the following. - Non-closure…
cs.CC2025
Algebraic Pseudorandomness in
Robert Andrews
We study the arithmetic complexity of hitting set generators, which are pseudorandom objects used for derandomization of the polynomial identity testing problem. We give new explic…