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

kernelizationconstraint satisfaction problemexponential-time algorithms

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 3314813 (Why is no real title available?)
• scientific article; zbMATH DE number 7650431 (Why is no real title available?)
• 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
• Kernelization. Theory of parameterized preprocessing
• Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
• On the Hardness of Compressing Weights
• On the degree of Boolean functions as real polynomials
• 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 MAX CSP with fixed-value constraints
• The approximability of constraint satisfaction problems
• 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)