Optimal polynomial-time compression for Boolean Max CSP

DOI10.4230/LIPICS.ESA.2020.63MaRDI QIDQ5874535zbMATH OpenFDO

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

Publication date 7 February 2023

Full work available at URL https://arxiv.org/abs/2002.03443

zbMATH Keywords

kernelizationconstraint satisfaction problemexponential time algorithms

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Optimal sparsification for some binary CSPs using low-degree polynomials
• Optimal sparsification for some binary CSPs using low-degree polynomials
• Best-case and worst-case sparsifiability of Boolean CSPs
• Best-case and worst-case sparsifiability of Boolean CSPs

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 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 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 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
• Solving MAX-\(r\)-SAT above a tight lower bound
• Some consequences of non-uniform conditions on uniform classes
• 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

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 Q5874535)