An Almost Optimal Rank Bound for Depth-3 Identities

DOI10.1137/090770679zbMath1216.68133OpenAlexW2015679114MaRDI QIDQ2999861

C. Seshadhri, Nitin Saxena

Publication date: 17 May 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: http://epubs.siam.org/sicomp/resource/1/smjcat/v40/i1/p200_s1

zbMATH Keywords

derandomizationpolynomial identity testingdepth-3 circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Related Items (10)

On enumerating monomials and other combinatorial structures by polynomial interpolation ⋮ Deterministic identity testing for sum of read-once oblivious arithmetic branching programs ⋮ Deterministic polynomial identity tests for multilinear bounded-read formulae ⋮ Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in ⋮ Read-once polynomial identity testing ⋮ Algebraic Independence and Blackbox Identity Testing ⋮ Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits ⋮ Unnamed Item ⋮ Improved hitting set for orbit of ROABPs ⋮ Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits

This page was built for publication: An Almost Optimal Rank Bound for Depth-3 Identities