Improved hitting set for orbit of ROABPs
From MaRDI portal
Publication:2087774
DOI10.1007/s00037-022-00230-9OpenAlexW3165372501MaRDI QIDQ2087774
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
orbitpolynomial identity testinghitting setcone concentrationrank concentrationread once algebraic branching program
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Read-once polynomial identity testing
- Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
- A probabilistic remark on algebraic program testing
- Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits
- PRIMES is in P
- Deterministic polynomial identity testing in non-commutative models
- A case of depth-3 identity testing, sparse factorization and duality
- Algebraic independence and blackbox identity testing
- A bijective proof of Muir's identity and the Cauchy-Binet formula
- Polynomial identity testing for depth 3 circuits
- Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing
- An Almost Optimal Rank Bound for Depth-3 Identities
- Arithmetic Circuits: A survey of recent results and open questions
- Diagonal Circuit Identity Testing and Lower Bounds
- Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits
- Progress on Polynomial Identity Testing - II
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn't Matter
- Linear matroid intersection is in quasi-NC
- Testing Equivalence of Polynomials under Shifts
- Blackbox Polynomial Identity Testing for Depth 3 Circuits
- Randomness efficient identity testing of multivariate polynomials
- Ideals, Varieties, and Algorithms
- Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
- Bipartite perfect matching is in quasi-NC
- Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
- From sylvester-gallai configurations to rank bounds
- Jacobian hits circuits
- Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
- Quasi-polynomial hitting-set for set-depth-Δ formulas
- The Factorization of Linear Graphs
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Improved Explicit Hitting-Sets for ROABPs
