31 citations · 82 across the 22 of their papers we have counts for
Showing 2017 · cs.CCShow all
3 papers · 2 filters
cs.CC2017
Discovering the roots: Uniform closure results for algebraic classes under factoring
Pranjal Dutta, Nitin Saxena, Amit Sinhababu
Newton iteration (NI) is an almost 350 years old recursive formula that approximates a simple root of a polynomial quite rapidly. We generalize it to a matrix recurrence (allRootsN…
cs.CC2017★ 1 cited
Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good
Manindra Agrawal, Michael Forbes, Sumanta Ghosh +1
We show that if we can design poly()-time hitting-sets for circuits of size , where is arbitrarily small and the number of variables, or ar…
cs.CC2017
Irreducibility and r-th root finding over finite fields
Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal +1
Constructing -th nonresidue over a finite field is a fundamental computational problem. A related problem is to construct an irreducible polynomial of degree (where is…