Recent results in hardness of approximation

DOI10.1007/3-540-58218-5_21MaRDI QIDQ5054764zbMATH OpenOpenAlexFDO

Authors Johan Hastad

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)

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256635 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• Approximation algorithms for combinatorial problems
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Average Case Complete Problems
• Average case completeness
• Efficient probabilistically checkable proofs and applications to approximations
• Improved non-approximability results
• Non-deterministic exponential time has two-prover interactive protocols
• On the complexity of approximating the independent set problem (extended abstract)
• On the ratio of optimal integral and fractional covers
• Optimization, approximation, and complexity classes
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• The Knowledge Complexity of Interactive Proof Systems
• The complexity of theorem-proving procedures

Cited in

(2)

• On the hardness of allocating frequencies for hybrid networks
• On the hardness of allocating frequencies for hybrid networks

This page was built for publication: Recent results in hardness of approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5054764)