Deterministic identity testing for sum of read-once oblivious arithmetic branching programs

DOI10.1007/s00037-016-0141-zzbMath1382.68110arXiv1411.7341OpenAlexW2569134273MaRDI QIDQ1686835

Rohit Gurjar, Arpita Korwar, Thomas Thierauf, Nitin Saxena

Publication date: 18 December 2017

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1411.7341

zbMATH Keywords

polynomial identity testinghitting-setssum of ROABPs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Related Items (6)

Unnamed Item ⋮ Unnamed Item ⋮ Improved Explicit Hitting-Sets for ROABPs ⋮ Lower bounds for arithmetic circuits via the Hankel matrix ⋮ Unnamed Item ⋮ Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds and separations for constant depth multilinear circuits
• Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
• A probabilistic remark on algebraic program testing
• Efficient algorithms for the transformation between different types of binary decision diagrams
• Deterministic polynomial identity testing in non-commutative models
• Polynomial identity testing for depth 3 circuits
• Arithmetic Circuits: A Chasm at Depth 3
• Progress on Polynomial Identity Testing-II
• Deterministic Black-Box Identity Testing $pi$-Ordered Algebraic Branching Programs
• An Almost Optimal Rank Bound for Depth-3 Identities
• Arithmetic Circuits: A survey of recent results and open questions
• Progress on Polynomial Identity Testing - II
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits
• Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn't Matter
• Blackbox Polynomial Identity Testing for Depth 3 Circuits
• Randomness efficient identity testing of multivariate polynomials
• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• Hitting sets for multilinear read-once algebraic branching programs, in any order
• On identity testing of tensors, low-rank recovery and compressed sensing
• Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
• Quasi-polynomial hitting-set for set-depth-Δ formulas
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Derandomizing polynomial identity tests means proving circuit lower bounds

This page was built for publication: Deterministic identity testing for sum of read-once oblivious arithmetic branching programs