Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > HITTING SET:
Reports tagged with Hitting Set:
TR01-094 | 3rd December 2001
Jonas Holmerin

#### Vertex Cover on 4-regular Hyper-graphs is Hard to Approximate Within 2 - \epsilon

We prove that Minimum vertex cover on 4-regular hyper-graphs (or
in other words, hitting set where all sets have size exactly 4),
is hard to approximate within 2 - \epsilon.
We also prove that the maximization version, in which we
are allowed to pick ... more >>>

TR02-027 | 30th April 2002
Irit Dinur, Venkatesan Guruswami, Subhash Khot

#### Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-\epsilon)

Given a $k$-uniform hypergraph, the E$k$-Vertex-Cover problem is
to find a minimum subset of vertices that hits'' every edge. We
show that for every integer $k \geq 5$, E$k$-Vertex-Cover is
NP-hard to approximate within a factor of $(k-3-\epsilon)$, for
an arbitrarily small constant $\epsilon > 0$.

This almost matches the ... more >>>

TR04-073 | 9th July 2004
Henning Fernau

#### A Top-Down Approach to Search-Trees: Improved Algorithmics for 3-Hitting Set

In this paper, we show how to systematically
improve on parameterized algorithms and their
analysis, focusing on search-tree based algorithms
for d-Hitting Set, especially for d=3.
We concentrate on algorithms which are easy to implement,
in contrast with the highly sophisticated algorithms
which have been elsewhere designed to ... more >>>

TR06-072 | 25th February 2006
Henning Fernau

#### Parameterized Algorithms for Hitting Set: the Weighted Case

We are going to analyze simple search tree algorithms
for Weighted d-Hitting Set. Although the algorithms are simple, their analysis is technically rather involved. However, this approach allows us to even improve on elsewhere published algorithm running time estimates for the more restricted case of (unweighted) d-Hitting Set.

... more >>>

TR10-063 | 12th April 2010
Venkatesan Guruswami, Yuan Zhou

#### Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set}

Revisions: 1

We study the approximability of two natural Boolean constraint satisfaction problems: Horn satisfiability and exact hitting set. Under the Unique Games conjecture, we prove the following optimal inapproximability and approximability results for finding an assignment satisfying as many constraints as possible given a {\em
near-satisfiable} instance.

\begin{enumerate}
\item ... more >>>

TR10-088 | 17th May 2010
Jiri Sima, Stanislav Zak

#### A Polynomial Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3

The relationship between deterministic and probabilistic computations is one of the central issues in complexity theory. This problem can be tackled by constructing polynomial time hitting set generators which, however, belongs to the hardest problems in computer science even for severely restricted computational models. In our work, we consider read-once ... more >>>

TR13-034 | 2nd March 2013
Louay Bazzi, Nagi Nahas

#### Small-bias is not enough to hit read-once CNF

Small-bias probability spaces have wide applications in pseudorandomness which naturally leads to the study of their limitations. Constructing a polynomial complexity hitting set for read-once CNF formulas is a basic open problem in pseudorandomness. We show in this paper that this goal is not achievable using small-bias spaces. Namely, we ... more >>>

TR15-006 | 6th January 2015

#### Dense Testers: Almost Linear Time and Locally Explicit Constructions

We develop a new notion called {\it $(1-\epsilon)$-tester for a
set $M$ of functions} $f:A\to C$. A $(1-\epsilon)$-tester
for $M$ maps each element $a\in A$ to a finite number of
elements $B_a=\{b_1,\ldots,b_t\}\subset B$ in a smaller
sub-domain $B\subset A$ where for every $f\in M$ if
$f(a)\not=0$ then $f(b)\not=0$ for at ... more >>>

TR15-155 | 22nd September 2015
Venkatesan Guruswami, Euiwoong Lee

#### Nearly Optimal NP-Hardness of Unique Coverage

The {\em Unique Coverage} problem, given a universe $V$ of elements and a collection $E$ of subsets of $V$, asks to find $S \subseteq V$ to maximize the number of $e \in E$ that intersects $S$ in {\em exactly one} element. When each $e \in E$ has cardinality at most ... more >>>

TR18-036 | 21st February 2018
Michael Forbes, Sumanta Ghosh, Nitin Saxena

#### Towards blackbox identity testing of log-variate circuits

Derandomization of blackbox identity testing reduces to extremely special circuit models. After a line of work, it is known that focusing on circuits with constant-depth and constantly many variables is enough (Agrawal,Ghosh,Saxena, STOC'18) to get to general hitting-sets and circuit lower bounds. This inspires us to study circuits with few ... more >>>

TR18-063 | 5th April 2018
William Hoza, David Zuckerman

#### Simple Optimal Hitting Sets for Small-Success $\mathbf{RL}$

Revisions: 1

We give a simple explicit hitting set generator for read-once branching programs of width $w$ and length $r$ with known variable order. Our generator has seed length $O\left(\frac{\log(wr) \log r}{\max\{1, \log \log w - \log \log r\}} + \log(1/\varepsilon)\right)$. This seed length improves on recent work by Braverman, Cohen, and ... more >>>

TR19-146 | 31st October 2019
Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau

#### Dynamic Kernels for Hitting Sets and Set Packing

Computing kernels for the hitting set problem (the problem of
finding a size-$k$ set that intersects each hyperedge of a
hypergraph) is a well-studied computational problem. For hypergraphs
with $m$ hyperedges, each of size at most~$d$, the best algorithms
can compute kernels of size $O(k^d)$ in ... more >>>

TR20-016 | 17th February 2020
Kuan Cheng, William Hoza

#### Hitting Sets Give Two-Sided Derandomization of Small Space

Revisions: 1

A hitting set is a "one-sided" variant of a pseudorandom generator (PRG), naturally suited to derandomizing algorithms that have one-sided error. We study the problem of using a given hitting set to derandomize algorithms that have two-sided error, focusing on space-bounded algorithms. For our first result, we show that if ... more >>>

TR20-039 | 25th March 2020
Pranjal Dutta, Nitin Saxena, Thomas Thierauf

#### Lower bounds on the sum of 25th-powers of univariates lead to complete derandomization of PIT

We consider the univariate polynomial $f_d:=(x+1)^d$ when represented as a sum of constant-powers of univariate polynomials. We define a natural measure for the model, the support-union, and conjecture that it is $\Omega(d)$ for $f_d$.

We show a stunning connection of the conjecture to the two main problems in algebraic ... more >>>

TR21-062 | 29th April 2021
Vishwas Bhargava, Sumanta Ghosh

#### Improved Hitting Set for Orbit of ROABPs

Revisions: 2

The orbit of an $n$-variate polynomial $f(\mathbf{x})$ over a field $\mathbb{F}$ is the set $\{f(A \mathbf{x} + b)\,\mid\, A\in \mathrm{GL}({n,\mathbb{F}})\mbox{ and }\mathbf{b} \in \mathbb{F}^n\}$, and the orbit of a polynomial class is the union of orbits of all the polynomials in it. In this paper, we give improved constructions of ... more >>>

ISSN 1433-8092 | Imprint