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