Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.50
URN: urn:nbn:de:0030-drops-147433
URL: https://drops.dagstuhl.de/opus/volltexte/2021/14743/
Saha, Chandan ; Thankey, Bhargav
Hitting Sets for Orbits of Circuit Classes and Polynomial Families
| pdf-format: |
|
Abstract
The orbit of an n-variate polynomial f(π±) over a field π½ is the set {f(Aπ±+π) : A β GL(n,π½) and π β π½βΏ}. In this paper, we initiate the study of explicit hitting sets for the orbits of polynomials computable by several natural and well-studied circuit classes and polynomial families. In particular, we give quasi-polynomial time hitting sets for the orbits of:1) Low-individual-degree polynomials computable by commutative ROABPs. This implies quasi-polynomial time hitting sets for the orbits of the elementary symmetric polynomials.
2) Multilinear polynomials computable by constant-width ROABPs. This implies a quasi-polynomial time hitting set for the orbits of the family {IMM_{3,d}}_{d β β}, which is complete for arithmetic formulas.
3) Polynomials computable by constant-depth, constant-occur formulas. This implies quasi-polynomial time hitting sets for the orbits of multilinear depth-4 circuits with constant top fan-in, and also polynomial-time hitting sets for the orbits of the power symmetric and the sum-product polynomials.
4) Polynomials computable by occur-once formulas.
BibTeX - Entry
@InProceedings{saha_et_al:LIPIcs.APPROX/RANDOM.2021.50,
author = {Saha, Chandan and Thankey, Bhargav},
title = {{Hitting Sets for Orbits of Circuit Classes and Polynomial Families}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
pages = {50:1--50:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-207-5},
ISSN = {1868-8969},
year = {2021},
volume = {207},
editor = {Wootters, Mary and Sanit\`{a}, Laura},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14743},
URN = {urn:nbn:de:0030-drops-147433},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.50},
annote = {Keywords: Hitting Sets, Orbits, ROABPs, Rank Concentration}
}
| Keywords: | Hitting Sets, Orbits, ROABPs, Rank Concentration | |
| Seminar: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 15.09.2021 |
