Recent results in hardness of approximation

DOI10.1007/3-540-58218-5_21zbMath1502.68131OpenAlexW1515281623MaRDI QIDQ5054764

Johan T. Håstad

Publication date: 9 December 2022

Published in: Algorithm Theory — SWAT '94 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-58218-5_21

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

On the hardness of allocating frequencies for hybrid networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Non-deterministic exponential time has two-prover interactive protocols
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Average case completeness
• Optimization, approximation, and complexity classes
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Improved non-approximability results
• Average Case Complete Problems
• The Knowledge Complexity of Interactive Proof Systems
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• On the complexity of approximating the independent set problem
• Efficient probabilistically checkable proofs and applications to approximations
• The complexity of theorem-proving procedures