Hardness of fully dense problems

Nir Ailon, Noga Alon

Research output: Contribution to journalArticlepeer-review

24 Scopus citations


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
Issue number8
StatePublished - Aug 2007
Externally publishedYes

All Science Journal Classification (ASJC) codes

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


  • Dense problems
  • NP-hardness


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

Cite this