Blackbox identity testing for sum of special ROABPs and its border class
type: Item
instance of: scholarly article
title: Blackbox identity testing for sum of special ROABPs and its border class
author: Pranav Bisht
author: Nitin Saxena
published in: Computational Complexity
publication date: 2021-07-16T00:00:00Z
Mathematics Subject Classification ID: 68-XX
zbMATH DE Number: 7372272
zbMATH Keywords: identity test
zbMATH Keywords: hitting-set
zbMATH Keywords: ROABP
zbMATH Keywords: blackbox
zbMATH Keywords: log variate
zbMATH Keywords: width
zbMATH Keywords: diagonal
zbMATH Keywords: derandomization
zbMATH Keywords: homogeneous
zbMATH Keywords: sparsity
zbMATH Keywords: border complexity
describes a project that uses: lowerbounds-survey
describes a project that uses: GitHub
MaRDI profile type: Publication
full work available at URL: s00037-021-00209-y
OpenAlex ID: W3167871684
cites work: FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
cites work: Bootstrapping variables in algebraic circuits
cites work: Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
cites work: PRIMES is in P
cites work: Quasi-polynomial hitting-set for set-depth-Δ formulas
cites work: Computing Algebraic Formulas Using a Constant Number of Registers
cites work: On Algebraic Branching Programs of Small Width
cites work: A probabilistic remark on algebraic program testing
cites work: Q5002729
cites work: Hitting sets for multilinear read-once algebraic branching programs, in any order
cites work: Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing
cites work: A PSPACE construction of a hitting set for the closure of small algebraic circuits
cites work: Improved Explicit Hitting-Sets for ROABPs
cites work: Q5215662
cites work: Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
cites work: Q4601835
cites work: Derandomizing polynomial identity tests means proving circuit lower bounds
cites work: Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits
cites work: Randomness efficient identity testing of multivariate polynomials
cites work: Equivalence of polynomial identity testing and polynomial factorization
cites work: Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits
cites work: Matching is as easy as matrix inversion
cites work: Geometric complexity theory. I: An approach to the P vs. NP and related problems
cites work: Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties
cites work: Deterministic polynomial identity testing in non-commutative models
cites work: Q4636586
cites work: Diagonal Circuit Identity Testing and Lower Bounds
cites work: Progress on Polynomial Identity Testing - II
cites work: Progress on Polynomial Identity Testing-II
cites work: Fast Probabilistic Algorithms for Verification of Polynomial Identities
cites work: Improved Polynomial Identity Testing for Read-Once Formulas
cites work: Arithmetic Circuits: A survey of recent results and open questions
cites work: Q3851616
DOI: 10.1007/S00037-021-00209-Y
description: scientific article; zbMATH DE number 7372272