Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits

DOI10.1137/140975103zbMath1327.68339arXiv1406.7535OpenAlexW1760203663MaRDI QIDQ5254013

Rohit Gurjar, Arpita Korwar, Nitin Saxena, Manindra Agrawal

Publication date: 8 June 2015

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

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

zbMATH Keywords

ROABPPIT\(\Delta\)-distancebasis isolationsum of set-multilinear

Mathematics Subject Classification ID

Related Items (18)

Subexponential size hitting sets for bounded depth multilinear formulas ⋮ Deterministic identity testing for sum of read-once oblivious arithmetic branching programs ⋮ A deterministic parallel reduction from weighted matroid intersection search to decision ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Read-once polynomial identity testing ⋮ Improved Explicit Hitting-Sets for ROABPs ⋮ Unnamed Item ⋮ Lower bounds for matrix factorization ⋮ Blackbox identity testing for sum of special ROABPs and its border class ⋮ Lower bounds for arithmetic circuits via the Hankel matrix ⋮ Compressed Decision Problems in Hyperbolic Groups. ⋮ Derandomizing Isolation in Space-Bounded Settings ⋮ Unnamed Item ⋮ Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees ⋮ Lower bounds for matrix factorization ⋮ Improved hitting set for orbit of ROABPs ⋮ On the power of algebraic branching programs of width two

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• On computing the determinant in small parallel time using a small number of processors
• Pseudorandom generators for space-bounded computation
• A probabilistic remark on algebraic program testing
• Deterministic polynomial identity testing in non-commutative models
• A case of depth-3 identity testing, sparse factorization and duality
• Polynomial identity testing for depth 3 circuits
• Arithmetic Circuits: A Chasm at Depth 3
• Progress on Polynomial Identity Testing-II
• Pseudorandomness for Regular Branching Programs via Fourier Analysis
• Deterministic Black-Box Identity Testing $pi$-Ordered Algebraic Branching Programs
• The Power of Depth 2 Circuits over Algebras
• An Almost Optimal Rank Bound for Depth-3 Identities
• On the Power of Algebraic Branching Programs of Width Two
• Arithmetic Circuits: A survey of recent results and open questions
• Primality and identity testing via Chinese remaindering
• Diagonal Circuit Identity Testing and Lower Bounds
• Progress on Polynomial Identity Testing - II
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Computing Algebraic Formulas Using a Constant Number of Registers
• 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
• Pseudorandomness from Shrinkage
• Hitting sets for multilinear read-once algebraic branching programs, in any order
• From sylvester-gallai configurations to rank bounds
• On identity testing of tensors, low-rank recovery and compressed sensing
• Jacobian hits circuits
• Pseudorandom generators for group products
• 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

This page was built for publication: Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits