scientific article; zbMATH DE number 7716602

DOI10.4086/CJTCS.2023.002MaRDI QIDQ6176154zbMATH OpenFDO

Authors Joshua Brakensiek, Venkatesan Guruswami

Publication date 25 July 2023

Full work available at URL https://doi.org/10.4086/CJTCS.2023.002

zbMATH Keywords

2-to-2 conjecturedictatorship testhardness of approximation

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• 3-bit dictator testing: 1 vs. 5/8
• A proof of the CSP dichotomy conjecture
• A query efficient non-adaptive long code test with perfect completeness
• An improved dictatorship test with perfect completeness
• Analysis of Boolean Functions
• Approximation Algorithms for CSPs
• Approximation Resistance from Pairwise-Independent Subgroups
• Approximation resistance on satisfiable instances for predicates with few accepting inputs
• Classifying the Complexity of Constraints Using Finite Algebras
• Conditional Hardness for Approximate Coloring
• Conditional hardness for satisfiable 3-CSPs
• Hardness of finding independent sets in 2-colorable and almost 2-colorable hypergraphs
• scientific article; zbMATH DE number 5485536 (Why is no real title available?)
• scientific article; zbMATH DE number 3099315 (Why is no real title available?)
• Improved inapproximability results for maximum k-colorable subgraph
• Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
• Near-optimal algorithms for unique games
• Noise stability of functions with low influences: invariance and optimality
• On independent sets, 2-to-2 games, and Grassmann graphs
• On non-optimally expanding sets in Grassmann graphs
• On the NP-hardness of MAX-Not-2
• On the power of unique 2-prover 1-round games
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• SDP gaps for 2-to-1 and other Label-Cover variants
• SDP Integrality Gaps with Local ell₁-Embeddability
• Small-set expansion in shortcode graph and the 2-to-2 conjecture
• The jackknife estimate of variance
• The quest for strong inapproximability results with perfect completeness
• The Quest for Strong Inapproximability Results with Perfect Completeness
• The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into _1
• Towards a proof of the 2-to-1 games conjecture?
• Two New Inequalities
• UG-hardness to NP-hardness by losing half

Cited in

(1)

• SDPs and robust satisfiability of promise CSP

This page was built for publication:

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