On approximability of satisfiable k-CSPs. III

DOI10.1145/3564246.3585121MaRDI QIDQ6499255zbMATH OpenFDO

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

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)