Q5874535
type: Item
instance of: scholarly article
author: Bart M. P. Jansen
author: Michał Włodarczyk
publication date: 2023-02-07T00:00:00Z
full work available at URL: https://arxiv.org/abs/2002.03443
Mathematics Subject Classification ID: 68Wxx
zbMATH DE Number: 7651202
zbMATH Keywords: constraint satisfaction problem
zbMATH Keywords: kernelization
zbMATH Keywords: exponential time algorithms
MaRDI profile type: Publication
cites work: Q5875790
cites work: Solving MAX-\(r\)-SAT above a tight lower bound
cites work: Representing Boolean functions as polynomials modulo composite numbers
cites work: A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
cites work: Complexity of Counting CSP with Complex Weights
cites work: Best-case and worst-case sparsifiability of Boolean CSPs
cites work: A dichotomy theorem for maximum generalized satisfiability problems.
cites work: Complexity classifications of Boolean constraint satisfaction problems
cites work: Towards a characterization of constant-factor approximable finite-valued CSPs
cites work: The approximability of MAX CSP with fixed-value constraints
cites work: Kernelization
cites work: Q4993600
cites work: Sparsification upper and lower bounds for graph problems and not-all-equal SAT
cites work: Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials
cites work: Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
cites work: The approximability of constraint satisfaction problems
cites work: Parameterized complexity and kernelizability of max ones and exact ones problems
cites work: Preprocessing of Min Ones Problems: A Dichotomy
cites work: Q4607968
cites work: Approximation Algorithms for CSPs
cites work: Q5595902
cites work: On the degree of Boolean functions as real polynomials
cites work: A tight ω(loglog n)-bound on the time for parallel RAM's to compute nondegenerated boolean functions
cites work: A lower bound on the MOD 6 degree of the OR function
cites work: Polynomials with two values
cites work: Some consequences of non-uniform conditions on uniform classes
DOI: 10.4230/LIPICS.ESA.2020.63
description: scientific article; zbMATH DE number 7651202