Improved hitting set for orbit of ROABPs
type: Item
instance of: scholarly article
title: Improved hitting set for orbit of ROABPs
author: Vishwas Bhargava
author: Sumanta Ghosh
published in: Computational Complexity
publication date: 2022-10-21T00:00:00Z
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 7605018
zbMATH Keywords: polynomial identity testing
zbMATH Keywords: hitting set
zbMATH Keywords: read once algebraic branching program
zbMATH Keywords: orbit
zbMATH Keywords: rank concentration
zbMATH Keywords: cone concentration
MaRDI profile type: Publication
full work available at URL: s00037-022-00230-9
OpenAlex ID: W3165372501
cites work: Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
cites work: PRIMES is in P
cites work: Jacobian hits circuits
cites work: Quasi-polynomial hitting-set for set-depth-Δ formulas
cites work: Algebraic independence and blackbox identity testing
cites work: Q5121901
cites work: Ideals, Varieties, and Algorithms
cites work: A probabilistic remark on algebraic program testing
cites work: Testing Equivalence of Polynomials under Shifts
cites work: Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
cites work: Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits
cites work: Bipartite perfect matching is in quasi-NC
cites work: Q5002729
cites work: Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing
cites work: Improved Explicit Hitting-Sets for ROABPs
cites work: Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
cites work: Q4601835
cites work: Linear matroid intersection is in quasi-NC
cites work: Derandomizing polynomial identity tests means proving circuit lower bounds
cites work: Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
cites work: Blackbox Polynomial Identity Testing for Depth 3 Circuits
cites work: Polynomial identity testing for depth 3 circuits
cites work: Randomness efficient identity testing of multivariate polynomials
cites work: Q5368901
cites work: Q4471369
cites work: Q3891767
cites work: Q5111163
cites work: Q4601834
cites work: Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits
cites work: Deterministic polynomial identity testing in non-commutative models
cites work: A case of depth-3 identity testing, sparse factorization and duality
cites work: Diagonal Circuit Identity Testing and Lower Bounds
cites work: Progress on Polynomial Identity Testing - II
cites work: An Almost Optimal Rank Bound for Depth-3 Identities
cites work: Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn't Matter
cites work: From sylvester-gallai configurations to rank bounds
cites work: Fast Probabilistic Algorithms for Verification of Polynomial Identities
cites work: Read-once polynomial identity testing
cites work: Arithmetic Circuits: A survey of recent results and open questions
cites work: The Factorization of Linear Graphs
cites work: A bijective proof of Muir's identity and the Cauchy-Binet formula
cites work: Q3851616
DOI: 10.1007/S00037-022-00230-9
description: scientific article; zbMATH DE number 7605018