Saha, Chandan ;
Thankey, Bhargav
Hitting Sets for Orbits of Circuit Classes and Polynomial Families
Abstract
The orbit of an nvariate 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 wellstudied circuit classes and polynomial families. In particular, we give quasipolynomial time hitting sets for the orbits of:
1) Lowindividualdegree polynomials computable by commutative ROABPs. This implies quasipolynomial time hitting sets for the orbits of the elementary symmetric polynomials.
2) Multilinear polynomials computable by constantwidth ROABPs. This implies a quasipolynomial time hitting set for the orbits of the family {IMM_{3,d}}_{d β β}, which is complete for arithmetic formulas.
3) Polynomials computable by constantdepth, constantoccur formulas. This implies quasipolynomial time hitting sets for the orbits of multilinear depth4 circuits with constant top fanin, and also polynomialtime hitting sets for the orbits of the power symmetric and the sumproduct polynomials.
4) Polynomials computable by occuronce 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:150:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772075},
ISSN = {18688969},
year = {2021},
volume = {207},
editor = {Wootters, Mary and Sanit\`{a}, Laura},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14743},
URN = {urn:nbn:de:0030drops147433},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.50},
annote = {Keywords: Hitting Sets, Orbits, ROABPs, Rank Concentration}
}
15.09.2021
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 