TY - JOUR
T1 - Hardness of fully dense problems
AU - Ailon, Nir
AU - Alon, Noga
N1 - Funding Information:
∗ Corresponding author. E-mail addresses: [email protected] (N. Ailon), [email protected] (N. Alon). 1 Work done while author was a student at the Department of Computer Science, Princeton University, Princeton, NJ, USA. 2 Research supported in part by the Israel Science Foundation, by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University and by the Von Neumann Fund.
PY - 2007/8
Y1 - 2007/8
N2 - In the past decade, there has been a stream of work in designing approximation schemes for dense instances of NP-Hard problems. These include the work of Arora, Karger and Karpinski from 1995 and that of Frieze and Kannan from 1996. We address the problem of proving hardness results for (fully) dense problems, which has been neglected despite the fruitful effort put in upper bounds. In this work, we prove hardness results of dense instances of a broad family of CSP problems, as well as a broad family of ranking problems which we refer to as CSP-Rank. Our techniques involve a construction of a pseudorandom hypergraph coloring, which generalizes the well-known Paley graph, recently used by Alon to prove hardness of feedback arc-set in tournaments.
AB - In the past decade, there has been a stream of work in designing approximation schemes for dense instances of NP-Hard problems. These include the work of Arora, Karger and Karpinski from 1995 and that of Frieze and Kannan from 1996. We address the problem of proving hardness results for (fully) dense problems, which has been neglected despite the fruitful effort put in upper bounds. In this work, we prove hardness results of dense instances of a broad family of CSP problems, as well as a broad family of ranking problems which we refer to as CSP-Rank. Our techniques involve a construction of a pseudorandom hypergraph coloring, which generalizes the well-known Paley graph, recently used by Alon to prove hardness of feedback arc-set in tournaments.
KW - Dense problems
KW - NP-hardness
UR - http://www.scopus.com/inward/record.url?scp=84855202447&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84855202447&partnerID=8YFLogxK
U2 - 10.1016/j.ic.2007.02.006
DO - 10.1016/j.ic.2007.02.006
M3 - Article
AN - SCOPUS:84855202447
SN - 0890-5401
VL - 205
SP - 1117
EP - 1129
JO - Information and Computation
JF - Information and Computation
IS - 8
ER -