Improved Explicit Hitting-Sets for ROABPs

DOI10.4230/lipics.approx/random.2020.4OpenAlexW3082044760MaRDI QIDQ6084347

Rohit Gurjar, Zeyu Guo

Publication date: 31 October 2023

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/12607/pdf/LIPIcs-APPROX4.pdf/

zbMATH Keywords

derandomizationpolynomial identity testingarithmetic branching programshitting-setROABP

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (2)

Blackbox identity testing for sum of special ROABPs and its border class ⋮ Improved hitting set for orbit of ROABPs

Cites Work

• Unnamed Item
• Unnamed Item
• Pseudorandom generators for space-bounded computation
• A probabilistic remark on algebraic program testing
• Universal classes of hash functions
• Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
• Deterministic polynomial identity testing in non-commutative models
• Pseudorandomness for network algorithms
• On recycling the randomness of states in space bounded computation
• Progress on Polynomial Identity Testing-II
• 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
• Hitting sets with near-optimal error for read-once branching programs
• 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

This page was built for publication: Improved Explicit Hitting-Sets for ROABPs