ECCC-Report TR17-135https://eccc.weizmann.ac.il/report/2017/135Comments and Revisions published for TR17-135en-usThu, 26 Oct 2017 11:39:20 +0300
Revision 1
| Quasi-polynomial Hitting Sets for Circuits with Restricted Parse Trees |
Ramprasad Saptharishi,
Anamay Tengse
https://eccc.weizmann.ac.il/report/2017/135#revision1We 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 [LMP16] and Lagarde, Limaye and Srinivasan [LLS17]) 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 [AGKS15], [GKST15] and [GKS16] 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 [AGKS15], [GKST15] and [GKS16].Thu, 26 Oct 2017 11:39:20 +0300https://eccc.weizmann.ac.il/report/2017/135#revision1
Paper TR17-135
| Quasi-polynomial Hitting Sets for Circuits with Restricted Parse Trees |
Ramprasad Saptharishi,
Anamay Tengse
https://eccc.weizmann.ac.il/report/2017/135We 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 [LMP16] and Lagarde, Limaye and Srinivasan [LLS17]) 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 [AGKS15], [GKST15] and [GKS16] 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 [AGKS15], [GKST15] and [GKS16].Sun, 10 Sep 2017 15:44:50 +0300https://eccc.weizmann.ac.il/report/2017/135