Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > INAPPROXIMABILITY:
Reports tagged with Inapproximability:
TR00-062 | 25th August 2000

Hardness of approximate hypergraph coloring

We introduce the notion of covering complexity of a probabilistic
verifier. The covering complexity of a verifier on a given input is
the minimum number of proofs needed to satisfy'' the verifier on
every random string, i.e., on every random string, at least one of the
given proofs must be ... more >>>

TR03-035 | 21st May 2003
Eran Halperin, Guy Kortsarz, Robert Krauthgamer

Tight lower bounds for the asymmetric k-center problem

In the {\sc $k$-center} problem, the input is a bound $k$
and $n$ points with the distance between every two of them,
such that the distances obey the triangle inequality.
The goal is to choose a set of $k$ points to serve as centers,
so that the maximum distance ... more >>>

TR05-039 | 13th April 2005
Irit Dinur, Elchanan Mossel, Oded Regev

Conditional Hardness for Approximate Coloring

We study the approximate-coloring(q,Q) problem: Given a graph G, decide
whether \chi(G) \le q or \chi(G)\ge Q. We derive conditional
hardness for this problem for any constant 3\le q < Q. For q \ge
4, our result is based on Khot's 2-to-1 conjecture [Khot'02].
For q=3, we base our hardness ... more >>>

TR05-100 | 30th August 2005
David Zuckerman

Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number

A randomness extractor is an algorithm which extracts randomness from a low-quality random source, using some additional truly random bits. We construct new extractors which require only log n + O(1) additional random bits for sources with constant entropy rate. We further construct dispersers, which are similar to one-sided extractors, ... more >>>

TR05-101 | 20th September 2005
Guy Kindler, Ryan O'Donnell, Subhash Khot, Elchanan Mossel

Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?

In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX-CUT to within a factor of $\GW + \eps$, for all $\eps > 0$; here $\GW \approx .878567$ denotes the approximation ratio achieved by the Goemans-Williamson algorithm~\cite{GW95}. This implies that if the Unique ... more >>>

TR05-126 | 5th November 2005
Eric Allender, Lisa Hellerstein, Paul McCabe, Michael Saks

Minimizing DNF Formulas and AC0 Circuits Given a Truth Table

For circuit classes R, the fundamental computational problem, Min-R,
asks for the minimum R-size of a boolean function presented as a truth
table. Prominent examples of this problem include Min-DNF, and
Min-Circuit (also called MCSP). We begin by presenting a new reduction
proving that Min-DNF is NP-complete. It is significantly ... more >>>

TR06-032 | 25th February 2006
Vitaly Feldman

Optimal Hardness Results for Maximizing Agreements with Monomials

We consider the problem of finding a monomial (or a term) that maximizes the agreement rate with a given set of examples over the Boolean hypercube. The problem originates in learning and is referred to as {\em agnostic learning} of monomials. Finding a monomial with the highest agreement rate was ... more >>>

TR06-045 | 13th March 2006
Jan Arpe, Bodo Manthey

Approximability of Minimum AND-Circuits

Revisions: 1

Given a set of monomials, the Minimum AND-Circuit problem asks for a
circuit that computes these monomials using AND-gates of fan-in two and
being of minimum size. We prove that the problem is not polynomial time
approximable within a factor of less than 1.0051 unless P = NP, even if
more >>>

TR06-068 | 6th April 2006
Patrick Briest, Piotr Krysta

Buying Cheap is Expensive: Hardness of Non-Parametric Multi-Product Pricing

We investigate non-parametric unit-demand pricing problems, in which the goal is to find revenue maximizing prices for a set of products based on consumer profiles obtained, e.g., from an e-Commerce website. A consumer profile consists of a number of non-zero budgets and a ranking of all the products the consumer ... more >>>

TR06-088 | 9th July 2006
Per Austrin

Balanced Max 2-Sat might not be the hardest

We show that, assuming the Unique Games Conjecture, it is NP-hard to approximate Max 2-Sat within $\alpha_{LLZ}^{-}+\epsilon$, where $0.9401 < \alpha_{LLZ}^{-} < 0.9402$ is the believed approximation ratio of the algorithm of Lewin, Livnat and Zwick.

This result is surprising considering the fact that balanced instances of Max 2-Sat, i.e. ... more >>>

TR07-011 | 19th December 2006
Bodo Manthey

On Approximating Restricted Cycle Covers

A cycle cover of a graph is a set of cycles such that every vertex is
part of exactly one cycle. An L-cycle cover is a cycle cover in which
the length of every cycle is in the set L. The weight of a cycle cover
of an edge-weighted graph ... more >>>

TR09-107 | 28th October 2009
Kevin Dick, Chris Umans

Improved inapproximability factors for some $\Sigma_2^p$ minimization problems

We give improved inapproximability results for some minimization problems in the second level of the Polynomial-Time Hierarchy. Extending previous work by Umans [Uma99], we show that several variants of DNF minimization are $\Sigma_2^p$-hard to approximate to within factors of $n^{1/3-\epsilon}$ and $n^{1/2-\epsilon}$ (where the previous results achieved $n^{1/4 - \epsilon}$), ... more >>>

TR10-132 | 18th August 2010
Mahdi Cheraghchi, Johan Hastad, Marcus Isaksson, Ola Svensson

Approximating Linear Threshold Predicates

We study constraint satisfaction problems on the domain $\{-1,1\}$, where the given constraints are homogeneous linear threshold predicates. That is, predicates of the form $\mathrm{sgn}(w_1 x_1 + \cdots + w_n x_n)$ for some positive integer weights $w_1, \dots, w_n$. Despite their simplicity, current techniques fall short of providing a classification ... more >>>

TR13-115 | 27th August 2013
Daniele Micciancio

Locally Dense Codes

The Minimum Distance Problem (MDP), i.e., the computational task of evaluating (exactly or approximately) the minimum distance of a linear code, is a well known NP-hard problem in coding theory. A key element in essentially all known proofs that MDP is NP-hard is the construction of a combinatorial object that ... more >>>

TR13-125 | 11th September 2013
Venkatesan Guruswami, Euiwoong Lee

Complexity of approximating CSP with Balance / Hard Constraints

We study two natural extensions of Constraint Satisfaction Problems (CSPs). {\em Balance}-Max-CSP requires that in any feasible assignment each element in the domain is used an equal number of times. An instance of {\em Hard}-Max-CSP consists of {\em soft constraints} and {\em hard constraints}, and the goal is to maximize ... more >>>

TR14-051 | 12th April 2014
Subhash Khot, Rishi Saket

Hardness of Coloring $2$-Colorable $12$-Uniform Hypergraphs with $2^{(\log n)^{\Omega(1)}}$ Colors

We show that it is quasi-NP-hard to color $2$-colorable $12$-uniform hypergraphs with $2^{(\log n)^{\Omega(1) }}$ colors where $n$ is the number of vertices. Previously, Guruswami et al. [GHHSV14] showed that it is quasi-NP-hard to color $2$-colorable $8$-uniform hypergraphs with $2^{2^{\Omega(\sqrt{\log \log n})}}$ colors. Their result is obtained by composing a ... more >>>

TR15-062 | 15th April 2015
Sangxia Huang

$2^{(\log N)^{1/4-o(1)}}$ Hardness for Hypergraph Coloring

Revisions: 2

We show that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with $2^{(\log N)^{1/4-o(1)}}$ colors, where $N$ is the number of vertices. There has been much focus on hardness of hypergraph coloring recently. Guruswami, H{\aa}stad, Harsha, Srinivasan and Varma showed that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with ... more >>>

TR15-097 | 16th June 2015
Marek Karpinski

Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies

We present in this paper some of the recent techniques and methods for proving best up to now explicit approximation hardness bounds for metric symmetric and asymmetric Traveling Salesman Problem (TSP) as well as related problems of Shortest Superstring and Maximum Compression. We attempt to shed some light on the ... more >>>

TR16-116 | 26th July 2016
Subhash Khot, Rishi Saket

Approximating CSPs using LP Relaxation

This paper studies how well the standard LP relaxation approximates a $k$-ary constraint satisfaction problem (CSP) on label set $[L]$. We show that, assuming the Unique Games Conjecture, it achieves an approximation within $O(k^3\cdot \log L)$ of the optimal approximation factor. In particular we prove the following hardness result: let ... more >>>

TR17-141 | 19th September 2017
Joshua Brakensiek, Venkatesan Guruswami

A Family of Dictatorship Tests with Perfect Completeness for 2-to-2 Label Cover

We give a family of dictatorship tests with perfect completeness and low-soundness for 2-to-2 constraints. The associated 2-to-2 conjecture has been the basis of some previous inapproximability results with perfect completeness. However, evidence towards the conjecture in the form of integrality gaps even against weak semidefinite programs has been elusive. ... more >>>

ISSN 1433-8092 | Imprint