Improved hitting set for orbit of ROABPs

DOI10.1007/S00037-022-00230-9MaRDI QIDQ2087774zbMATH OpenOpenAlexFDO

Authors Vishwas Bhargava, Sumanta Ghosh

Publication date 21 October 2022

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-022-00230-9

zbMATH Keywords

orbitpolynomial identity testinghitting setcone concentrationrank concentrationread once algebraic branching program

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30)

Recommendations

• Hitting sets for orbits of circuit classes and polynomial families
• Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
• Identity testing for constant-width, and commutative, read-once oblivious ABPs
• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits

Cites work

• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 3698383 (Why is no real title available?)
• scientific article; zbMATH DE number 2079409 (Why is no real title available?)
• scientific article; zbMATH DE number 6829282 (Why is no real title available?)
• scientific article; zbMATH DE number 7204283 (Why is no real title available?)
• scientific article; zbMATH DE number 7250153 (Why is no real title available?)
• A bijective proof of Muir's identity and the Cauchy-Binet formula
• A case of depth-3 identity testing, sparse factorization and duality
• A probabilistic remark on algebraic program testing
• Algebraic independence and blackbox identity testing
• Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits
• An almost optimal rank bound for depth-3 identities
• Arithmetic circuits with locally low algebraic rank
• Arithmetic circuits: a survey of recent results and open questions
• Bipartite perfect matching is in quasi-NC
• Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
• Blackbox Polynomial Identity Testing for Depth 3 Circuits
• Blackbox identity testing for bounded top-fanin depth-3 circuits: the field doesn't matter
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
• Deterministic polynomial identity testing in non-commutative models
• Diagonal Circuit Identity Testing and Lower Bounds
• Explicit Noether normalization for simultaneous conjugation via polynomial identity testing
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• From sylvester-gallai configurations to rank bounds
• Hardness-randomness tradeoffs for bounded depth arithmetic circuits
• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• Ideals, Varieties, and Algorithms
• Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
• Improved Explicit Hitting-Sets for ROABPs
• Jacobian hits circuits: hitting-sets, lower bounds for depth-\(D\) occur-\(k\) formulas \& depth-\(3\) transcendence degree-\(k\) circuits
• Linear matroid intersection is in quasi-NC
• Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
• PRIMES is in P
• Polynomial identity testing for depth 3 circuits
• Progress on polynomial identity testing
• Quasi-polynomial hitting-set for set-depth-\({\Delta}\) formulas
• Randomness efficient identity testing of multivariate polynomials
• Read-once polynomial identity testing
• Testing equivalence of polynomials under shifts
• The Factorization of Linear Graphs
• Towards blackbox identity testing of log-variate circuits

Cited in

(1)

• Hitting sets for orbits of circuit classes and polynomial families

This page was built for publication: Improved hitting set for orbit of ROABPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2087774)