11 citations · 18 across the 12 of their papers we have counts for
4 papers · 2 filters
An Improved Line-Point Low-Degree Test
Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi +1
We prove that the most natural low-degree test for polynomials over finite fields is ``robust'' in the high-error regime for linear-sized fields. Specifically we consider the ``loc…
Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits
Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi
For every constant , we design a subexponential time deterministic algorithm that takes as input a multivariate polynomial given as a constant depth algebraic circuit over t…
Recursive Error Reduction for Regular Branching Programs
Eshan Chattopadhyay, Jyun-Jie Liao
In a recent work, Chen, Hoza, Lyu, Tal and Wu (FOCS 2023) showed an improved error reduction framework for the derandomization of regular read-once branching programs (ROBPs). Thei…
Determinants vs. Algebraic Branching Programs
Abhranil Chatterjee, Mrinal Kumar, Ben Lee Volk
We show that for every homogeneous polynomial of degree , if it has determinantal complexity at most , then it can be computed by a homogeneous algebraic branching program (A…