On approximability of satisfiable k-CSPs. II

DOI10.1145/3564246.3585120MaRDI QIDQ6499254

Dor Minzer, Subhash A. Khot, Amey Bhangale

Publication date: 8 May 2024

zbMATH Keywords

constraint satisfaction problemshardness of approximation

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Progression-free sets in \(\mathbb{Z}_4^n\) are exponentially small
• On large subsets of \(\mathbb{F}_q^n\) with no three-term arithmetic progression
• Noise stability of functions with low influences: invariance and optimality
• A density version of a geometric Ramsey theorem
• On subsets of finite Abelian groups with no 3-term arithmetic progressions
• Gaussian bounds for noise correlation of functions
• Multiple recurrence in quasirandom groups
• MIXING FOR PROGRESSIONS IN NONABELIAN GROUPS
• New bounds on cap sets
• Quasirandom Groups
• On the power of unique 2-prover 1-round games
• On sets of integers containing k elements in arithmetic progression
• Mixing for three-term progressions in finite simple groups
• [https://portal.mardi4nfdi.de/wiki/Publication:4645045 Product Space Models of Correlation: Between Noise Stability and Additive Combinatorics]
• On Certain Sets of Integers
• Optimal inapproximability of satisfiable k-LIN over non-abelian groups

This page was built for publication: On approximability of satisfiable k-CSPs. II