Hardness of fully dense problems

Nir Ailon, Noga Alon

Research output: Contribution to journalArticlepeer-review

21 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1117-1129
Number of pages13
JournalInformation and Computation
Volume205
Issue number8
DOIs
StatePublished - Aug 2007
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Keywords

  • Dense problems
  • NP-hardness

Fingerprint Dive into the research topics of 'Hardness of fully dense problems'. Together they form a unique fingerprint.

Cite this