Explicit Optimal Hardness via Gaussian Stability Results

DOI10.1145/2505766zbMath1322.68265arXiv1202.5258OpenAlexW1991298678MaRDI QIDQ2947585

Anindya De, Elchanan Mossel

Publication date: 24 September 2015

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1202.5258

zbMATH Keywords

unique games conjecturedictatorship testGaussian stability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

This page was built for publication: Explicit Optimal Hardness via Gaussian Stability Results