scientific article; zbMATH DE number 7375981

DOI10.4230/LIPIcs.ICALP.2018.54zbMath1499.68390MaRDI QIDQ5002729

Nitin Saxena, Sumanta Ghosh, Michael A. Forbes

Publication date: 28 July 2021

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

derandomizationdiagonalconcentrationpolynomial identity testingdepth-3 circuitshitting-setcone-closed basis isolationlog-variate circuits

Mathematics Subject Classification ID

Randomized algorithms (68W20) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (6)

Absolute reconstruction for sums of powers of linear forms: degree 3 and beyond ⋮ Unnamed Item ⋮ Improved Explicit Hitting-Sets for ROABPs ⋮ Unnamed Item ⋮ Blackbox identity testing for sum of special ROABPs and its border class ⋮ Improved hitting set for orbit of ROABPs

Uses Software

• GitHub
• lowerbounds-survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A probabilistic remark on algebraic program testing
• PRIMES is in P
• 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
• Arithmetic Circuits: A Chasm at Depth 3
• Progress on Polynomial Identity Testing-II
• Geometric complexity theory V: Efficient algorithms for Noether normalization
• 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
• Progress on Polynomial Identity Testing - II
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Algebraic Independence over Positive Characteristic: New Criterion and Applications to Locally Low Algebraic Rank Circuits
• 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
• Randomness efficient identity testing of multivariate polynomials
• Bootstrapping variables in algebraic circuits
• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• Hitting sets for multilinear read-once algebraic branching programs, in any order
• Bipartite perfect matching is in quasi-NC
• Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
• On identity testing of tensors, low-rank recovery and compressed sensing
• Jacobian hits circuits
• 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

This page was built for publication: