Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > HITTING SETS:
Reports tagged with Hitting Sets:
TR98-049 | 10th July 1998
Dimitris Fotakis, Paul Spirakis

#### Random Walks, Conditional Hitting Sets and Partial Derandomization

In this work we use random walks on expanders in order to
relax the properties of hitting sets required for partially
derandomizing one-side error algorithms. Building on a well-known
probability amplification technique [AKS87,CW89,IZ89], we use
random walks on expander graphs of subexponential (in the
random bit complexity) size so as ... more >>>

TR10-055 | 31st March 2010
Eric Allender

#### Avoiding Simplicity is Complex

Revisions: 2

It is a trivial observation that every decidable set has strings of length $n$ with Kolmogorov complexity $\log n + O(1)$ if it has any strings of length $n$ at all. Things become much more interesting when one asks whether a similar property holds when one
considers *resource-bounded* Kolmogorov complexity. ... more >>>

TR11-133 | 4th October 2011
Maurice Jansen, Rahul Santhanam

#### Marginal Hitting Sets Imply Super-Polynomial Lower Bounds for Permanent

Suppose $f$ is a univariate polynomial of degree $r=r(n)$ that is computed by a size $n$ arithmetic circuit.
It is a basic fact of algebra that a nonzero univariate polynomial of degree $r$ can vanish on at most $r$ points. This implies that for checking whether $f$ is identically zero, ... more >>>

TR12-133 | 21st October 2012
Noga Alon, Gil Cohen

#### On Rigid Matrices and Subspace Polynomials

Revisions: 1

We introduce a class of polynomials, which we call \emph{subspace polynomials} and show that the problem of explicitly constructing a rigid matrix can be reduced to the problem of explicitly constructing a small hitting set for this class. We prove that small-bias sets are hitting sets for the class of ... more >>>

TR12-158 | 14th November 2012

#### Optimal Hitting Sets for Combinatorial Shapes

We consider the problem of constructing explicit Hitting sets for Combinatorial Shapes, a class of statistical tests first studied by Gopalan, Meka, Reingold, and Zuckerman (STOC 2011). These generalize many well-studied classes of tests, including symmetric functions and combinatorial rectangles. Generalizing results of Linial, Luby, Saks, and Zuckerman (Combinatorica 1997) ... more >>>

TR21-015 | 15th February 2021
Chandan Saha, Bhargav Thankey

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

Revisions: 2

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 >>>

TR22-102 | 15th July 2022
Venkatesan Guruswami, Xin Lyu, Xiuhan Wang

#### Range Avoidance for Low-depth Circuits and Connections to Pseudorandomness

In the range avoidance problem, the input is a multi-output Boolean circuit with more outputs than inputs, and the goal is to find a string outside its range (which is guaranteed to exist). We show that well-known explicit construction questions such as finding binary linear codes achieving the Gilbert-Varshamov bound ... more >>>

ISSN 1433-8092 | Imprint