31 citations · 82 across the 22 of their papers we have counts for
Showing 2008 · cs.CCShow all
3 papers · 2 filters
cs.CC2008
An Almost Optimal Rank Bound for Depth-3 Identities
Nitin Saxena, C. Seshadhri
We show that the rank of a depth-3 circuit (over any field) that is simple, minimal and zero is at most k^3\log d. The previous best rank bound known was 2^{O(k^2)}(\log d)^{k-2} b…
cs.CC2008
Trading GRH for algebra: algorithms for factoring polynomials and related structures
Gábor Ivanyos, Marek Karpinski, Lajos Rónyai +1
In this paper we develop techniques that eliminate the need of the Generalized Riemann Hypothesis (GRH) from various (almost all) known results about deterministic polynomial facto…
cs.CC2008
Schemes for Deterministic Polynomial Factoring
Gábor Ivanyos, Marek Karpinski, Nitin Saxena
In this work we relate the deterministic complexity of factoring polynomials (over finite fields) to certain combinatorial objects we call m-schemes. We extend the known conditiona…