Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ORBITS:
Reports tagged with Orbits:
TR21-015 | 15th February 2021
Chandan Saha, Bhargav Thankey

#### Hitting Sets for Orbits of Circuit Classes and Polynomial Families

The orbit of an $n$-variate polynomial $f(\mathbf{x})$ over a field $\mathbb{F}$ is the set $\mathrm{orb}(f) := \{f(A\mathbf{x}+\mathbf{b}) : A \in \mathrm{GL}(n,\mathbb{F}) \ \mathrm{and} \ \mathbf{b} \in \mathbb{F}^n\}$. This paper studies explicit hitting sets for the orbits of polynomials computable by certain well-studied circuit classes. This version of the hitting set ... more >>>

ISSN 1433-8092 | Imprint