On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction

DOI10.1145/2422436.2422460zbMath1361.68104OpenAlexW2098180694MaRDI QIDQ2986870

Guy Kindler, Boaz Barak, David Steurer

Publication date: 16 May 2017

Published in: Proceedings of the 4th conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2422436.2422460

zbMATH Keywords

constraint satisfaction problemshardness of approximationaverage-case complexityunique games conjecturesemi-definite program

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

On the Complexity of Random Satisfiability Problems with Planted Solutions ⋮ Cryptographic hardness of random local functions. Survey ⋮ Algebraic Attacks against Random Local Functions and Their Countermeasures ⋮ The Complexity of Public-Key Cryptography

Cites Work

• Teachability in computational learning
• Measuring teachability using variants of the teaching dimension
• Teaching a smarter learner.
• Occam's razor
• Pseudorandom generators for space-bounded computation
• On the power of inductive inference from good examples
• A model of interactive teaching
• Learning from different teachers
• On the limits of efficient teachability
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• On the complexity of teaching
• On specifying Boolean functions by labelled examples
• Recent Developments in Algorithmic Teaching
• A theory of the learnable
• Teaching Randomized Learners
• Algorithmic Learning Theory
• A theory of goal-oriented communication
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction