Blackbox identity testing for sum of special ROABPs and its border class

DOI10.1007/s00037-021-00209-yOpenAlexW3167871684MaRDI QIDQ2041244

Nitin Saxena, Pranav Bisht

Publication date: 16 July 2021

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-021-00209-y

zbMATH Keywords

blackboxwidthderandomizationdiagonalhomogeneoussparsityidentity testborder complexityhitting-setlog variateROABP

Mathematics Subject Classification ID

Computer science (68-XX)

Uses Software

• GitHub
• lowerbounds-survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matching is as easy as matrix inversion
• A probabilistic remark on algebraic program testing
• PRIMES is in P
• Deterministic polynomial identity testing in non-commutative models
• Equivalence of polynomial identity testing and polynomial factorization
• Geometric Complexity Theory I: An Approach to thePvs.NPand Related Problems
• Progress on Polynomial Identity Testing-II
• Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing
• Arithmetic Circuits: A survey of recent results and open questions
• Diagonal Circuit Identity Testing and Lower Bounds
• Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties
• Improved Polynomial Identity Testing for Read-Once Formulas
• Progress on Polynomial Identity Testing - II
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Computing Algebraic Formulas Using a Constant Number of Registers
• Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits
• On Algebraic Branching Programs of Small Width
• Randomness efficient identity testing of multivariate polynomials
• Bootstrapping variables in algebraic circuits
• A PSPACE construction of a hitting set for the closure of small algebraic circuits
• Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits
• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• Hitting sets for multilinear read-once algebraic branching programs, in any order
• Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
• Quasi-polynomial hitting-set for set-depth-Δ formulas
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Improved Explicit Hitting-Sets for ROABPs

This page was built for publication: Blackbox identity testing for sum of special ROABPs and its border class