Optimal polynomial-time compression for Boolean Max CSP

DOI10.1145/3624704MaRDI QIDQ7022393zbMATH OpenFDO

Authors Bart M. P. Jansen, Michał Włodarczyk

Publication date 25 February 2025

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1145/3624704

zbMATH Keywords

constraint satisfaction problemexponential-time algorithmskernelization

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07) Analysis of algorithms (68W40)

Cites work

• A dichotomy theorem for maximum generalized satisfiability problems.
• A dichotomy theorem for nonuniform CSPs
• A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
• A lower bound on the MOD 6 degree of the OR function
• A proof of the CSP dichotomy conjecture
• A tight ω(loglog n)-bound on the time for parallel RAM's to compute nondegenerated boolean functions
• Approximation Algorithms for CSPs
• Best-case and worst-case sparsifiability of Boolean CSPs
• Complexity classifications of Boolean constraint satisfaction problems
• Complexity of counting CSP with complex weights
• scientific article; zbMATH DE number 3314813 (Why is no real title available?)
• scientific article; zbMATH DE number 7650431 (Why is no real title available?)
• Kernelization. Theory of parameterized preprocessing
• Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
• On the degree of Boolean functions as real polynomials
• On the Hardness of Compressing Weights
• Optimal sparsification for some binary CSPs using low-degree polynomials
• Parameterized complexity and kernelizability of max ones and exact ones problems
• Parameterized constraint satisfaction problems: a survey
• Polynomials with two values
• Preprocessing of min ones problems: a dichotomy
• Representing Boolean functions as polynomials modulo composite numbers
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Solving MAX-\(r\)-SAT above a tight lower bound
• Some consequences of non-uniform conditions on uniform classes
• Sparsification of SAT and CSP Problems via Tractable Extensions
• Sparsification upper and lower bounds for graph problems and not-all-equal SAT
• The approximability of constraint satisfaction problems
• The approximability of MAX CSP with fixed-value constraints
• Tight hardness for shortest cycles and paths in sparse graphs
• Towards a characterization of constant-factor approximable finite-valued CSPs

Cited in

(1)

• A near-optimal kernel for a coloring problem

This page was built for publication: Optimal polynomial-time compression for Boolean Max CSP

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