Optimal polynomial-time compression for Boolean Max CSP
From MaRDI portal
Publication:5874535
DOI10.4230/LIPICS.ESA.2020.63MaRDI QIDQ5874535FDOQ5874535
Authors: Bart M. P. Jansen, Michał Włodarczyk 
Publication date: 7 February 2023
Full work available at URL: https://arxiv.org/abs/2002.03443
Recommendations
Cites Work
- Title not available (Why is that?)
- Complexity classifications of Boolean constraint satisfaction problems
- Solving MAX-\(r\)-SAT above a tight lower bound
- Representing Boolean functions as polynomials modulo composite numbers
- On the degree of Boolean functions as real polynomials
- Some consequences of non-uniform conditions on uniform classes
- A dichotomy theorem for maximum generalized satisfiability problems.
- The approximability of constraint satisfaction problems
- Polynomials with two values
- Preprocessing of min ones problems: a dichotomy
- A lower bound on the MOD 6 degree of the OR function
- Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
- The approximability of MAX CSP with fixed-value constraints
- Approximation Algorithms for CSPs
- A tight ω(loglog n)-bound on the time for parallel RAM's to compute nondegenerated boolean functions
- Tight hardness for shortest cycles and paths in sparse graphs
- Sparsification upper and lower bounds for graph problems and not-all-equal SAT
- Optimal sparsification for some binary CSPs using low-degree polynomials
- Best-case and worst-case sparsifiability of Boolean CSPs
- Kernelization. Theory of parameterized preprocessing
- Complexity of counting CSP with complex weights
- Towards a characterization of constant-factor approximable finite-valued CSPs
- A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
- Parameterized complexity and kernelizability of max ones and exact ones problems
- Parameterized constraint satisfaction problems: a survey
- Title not available (Why is that?)
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)
