2026-07-21T03:15:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9905 2024-03-06T10:45:04Z ddc:004 open_access

Quasipolynomial Hitting Sets for Circuits with Restricted Parse Trees Saptharishi, Ramprasad Tengse, Anamay Unambiguous Circuits Read-once Oblivious ABPs Polynomial Identity Testing Lower Bounds Algebraic Circuit Complexity We study the class of non-commutative Unambiguous circuits or Unique-Parse-Tree (UPT) circuits, and a related model of Few-Parse-Trees (FewPT) circuits (which were recently introduced by Lagarde, Malod and Perifel [Guillaume Lagarde et al., 2016] and Lagarde, Limaye and Srinivasan [Guillaume Lagarde et al., 2017]) and give the following constructions: - An explicit hitting set of quasipolynomial size for UPT circuits, - An explicit hitting set of quasipolynomial size for FewPT circuits (circuits with constantly many parse tree shapes), - An explicit hitting set of polynomial size for UPT circuits (of known parse tree shape), when a parameter of preimage-width is bounded by a constant. The above three results are extensions of the results of [Manindra Agrawal et al., 2015], [Rohit Gurjar et al., 2015] and [Rohit Gurjar et al., 2016] to the setting of UPT circuits, and hence also generalize their results in the commutative world from read-once oblivious algebraic branching programs (ROABPs) to UPT-set-multilinear circuits. The main idea is to study shufflings of non-commutative polynomials, which can then be used to prove suitable depth reduction results for UPT circuits and thereby allow a careful translation of the ideas in [Manindra Agrawal et al., 2015], [Rohit Gurjar et al., 2015] and [Rohit Gurjar et al., 2016]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ramprasad Saptharishi and Anamay Tengse 2018 Is Part Of LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2018.6 urn:nbn:de:0030-drops-99050 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.6 eng https://creativecommons.org/licenses/by/3.0/legalcode