4 papers · 1 filter
Hilbert's Nullstellensatz is in the Counting Hierarchy
Robert Andrews, Abhibhav Garg, Éric Schost
We show that Hilbert's Nullstellensatz, the problem of deciding if a system of multivariate polynomial equations has a solution in the algebraic closure of the underlying field, li…
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 ,…
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…
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…