2 citations · 2 across the 5 of their papers we have counts for
6 papers
An Improved Construction of Variety-Evasive Subspace Families
Robert Andrews, Abhibhav Garg
We study the question of explicitly constructing variety-evasive subspace families, a pseudorandom primitive introduced by Guo (Computational Complexity 2024) that generalizes both…
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…
Constant-Depth Arithmetic Circuits for Linear Algebra Problems
Robert Andrews, Avi Wigderson
We design polynomial size, constant depth (namely, ) arithmetic formulae for the greatest common divisor (GCD) of two polynomials, as well as the related problems of…