On approximability of satisfiable k-CSPs. III

DOI10.1145/3564246.3585121MaRDI QIDQ6499255FDOQ6499255

Authors: Amey Bhangale, Subhash Khot, Dor Minzer 

Publication date: 8 May 2024

zbMATH Keywords

constraint satisfaction problemshardness of approximationlinearity testdirect product test

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
• Analysis of Boolean Functions
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• Self-testing/correcting with applications to numerical problems
• Linearity testing in characteristic two
• Gaussian bounds for noise correlation of functions
• Noise stability of functions with low influences: invariance and optimality
• Direct sum testing (extended abstract)
• Clustering in the Boolean hypercube in a list decoding regime
• Breaking the \(\epsilon\)-soundness bound of the linearity test over GF(2)
• Analyzing Boolean functions on the biased hypercube via higher-dimensional agreement tests
• New direct-product testers and 2-query PCPs
• Cube vs. Cube Low Degree Test.
• Tolerant Linearity Testing and Locally Testable Codes
• Exponentially small soundness for the direct product Z-test

Cited In (1)

• Complexity theory. Abstracts from the workshop held June 2--7, 2024

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

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