Algebraic approach to approximation

DOI10.1145/3661814.3662076MaRDI QIDQ6970270zbMATH OpenFDO

Authors Libor Barto, Silvia Butti, Alexandr Kazda, C. Viola, S. Zivny

Publication date 18 June 2025

Full work available at URL https://ora.ox.ac.uk/objects/uuid:3483586e-b5e6-41af-8809-c0da511e969e

zbMATH Keywords

algebraic approachapproximationconstraint satisfactionpolymorphisms

Mathematics Subject Classification ID

Operations and polynomials in algebraic structures, primal algebras (08A40) Applications of universal algebra in computer science (08A70) Computational aspects of satisfiability (68R07)

Cites work

• (2+)-Sat is NP-hard
• A dichotomy theorem for nonuniform CSPs
• A Parallel Repetition Theorem
• A proof of the CSP dichotomy conjecture
• Algebraic approach to approximation
• Algebraic Approach to Promise Constraint Satisfaction
• Algebraic properties of valued constraint satisfaction problem
• An algebraic theory of complexity for discrete optimization.
• Approximation Resistance from Pairwise-Independent Subgroups
• CLAP: A New Algorithm for Promise CSPs
• Classifying the Complexity of Constraints Using Finite Algebras
• Closure properties of constraints
• Combinatorial gap theorem and reductions between promise CSPs
• Complexity of infinite-domain constraint satisfaction
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Dichotomy for symmetric Boolean PCSPs
• Discrete temporal constraint satisfaction problems
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Galois theory for minors of finite functions
• scientific article; zbMATH DE number 5485536 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• Non-dichotomies in Constraint Satisfaction Complexity
• NP-hardness of almost coloring almost 3-colorable graphs
• On approximability of satisfiable k -CSPs: I
• On approximability of satisfiable k-CSPs. II
• On approximability of satisfiable k-CSPs. III
• On the descriptive complexity of temporal constraint satisfaction problems
• On the power of unique 2-prover 1-round games
• Probabilistic checking of proofs
• Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
• Proof verification and the hardness of approximation problems
• Pseudorandom sets in Grassmann graph have near-perfect expansion
• Robustly solvable constraint satisfaction problems
• Schaefer's theorem for graphs
• Some optimal inapproximability results
• The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains
• The complexity of finite-valued CSPs
• The complexity of general-valued CSPs
• The complexity of soft constraint satisfaction
• The complexity of temporal constraint satisfaction problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The PCP theorem by gap amplification
• The power of linear programming for general-valued CSPs
• The power of Sherali-Adams relaxations for general-valued CSPs
• The wonderland of reflections
• Tractability and learnability arising from algebras with few subpowers
• Varieties with few subalgebras of powers
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• When symmetries are not enough: a hierarchy of hard constraint satisfaction problems

Cited in

(3)

• Algebraic approach to approximation
• The Sherali-Adams and Weisfeiler-Leman hierarchies in (promise valued) constraint satisfaction problems
• Optimal inapproximability of promise equations over finite groups

This page was built for publication: Algebraic approach to approximation

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