Quasi-polynomial hitting-set for set-depth-Δ formulas

DOI10.1145/2488608.2488649zbMath1293.94140arXiv1209.2333OpenAlexW1984806876MaRDI QIDQ5495802

Chandan Saha, Nitin Saxena, Manindra Agrawal

Publication date: 7 August 2014

Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1209.2333

zbMATH Keywords

Hadamard algebraidentity testinghitting-setlow-support rank concentrationset-multilinear formula

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30)

Related Items (14)

Derandomization and absolute reconstruction for sums of powers of linear forms ⋮ Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits ⋮ Subexponential size hitting sets for bounded depth multilinear formulas ⋮ Exact learning from an honest teacher that answers membership queries ⋮ Deterministic identity testing for sum of read-once oblivious arithmetic branching programs ⋮ Unnamed Item ⋮ Read-once polynomial identity testing ⋮ Improved Explicit Hitting-Sets for ROABPs ⋮ Unnamed Item ⋮ Blackbox identity testing for sum of special ROABPs and its border class ⋮ Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits ⋮ Geometric complexity theory V: Efficient algorithms for Noether normalization ⋮ Improved hitting set for orbit of ROABPs ⋮ Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits

This page was built for publication: Quasi-polynomial hitting-set for set-depth-Δ formulas