Relations between average case complexity and approximation complexity

2002/05/19 by Uriel Feige · 370 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Algorithms and Data Compression #Approximation algorithm #Bipartite graph #Bisection #Boolean satisfiability problem #Clique #Combinatorics #Complexity and Algorithms in Graphs #Computational complexity theory #Computer science #Discrete mathematics #Graph #Hardness of approximation #Mathematics #Satisfiability #Subgraph isomorphism problem #Time complexity

paper · doi:10.1145/509907.509985

openalex publication_date 2002/05/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

We investigate relations between average case complexity and the complexity of approximation. Our preliminary findings indicate that this is a research direction that leads to interesting insights. Under the assumption that refuting 3SAT is hard on average on a natural distribution, we derive hardness of approximation results for min bisection, dense k-subgraph, max bipartite clique and the 2-catalog segmentation problem. No NP-hardness of approximation results are currently known for these problems.

Citations

• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms

Cited by

• From average case complexity to improper learning complexity
• A new point of NP-hardness for unique games
• SIGACT News Complexity Theory Column 76
• Detecting High Log-Densities -- an O(n¹/4) Approximation for Densest\n k-Subgraph
• Computational hardness assumption [wikipedia]