scientific article; zbMATH DE number 7651202

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

Title of this publication is not available (Why is that?)

zbMATH Keywords

kernelizationconstraint satisfaction problemexponential time algorithms

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

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
• Title not available (Why is that?)
• 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
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication:

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