---
res:
  bibo_abstract:
  - "A Valued Constraint Satisfaction Problem (VCSP) provides a common framework that
    can express a wide range of discrete optimization problems. A VCSP instance is
    given by a finite set of variables, a finite domain of labels, and an objective
    function to be minimized. This function is represented as a sum of terms where
    each term depends on a subset of the variables. To obtain different classes of
    optimization problems, one can restrict all terms to come from a fixed set Γ of
    cost functions, called a language. \r\nRecent breakthrough results have established
    a complete complexity classification of such classes with respect to language
    Γ: if all cost functions in Γ satisfy a certain algebraic condition then all Γ-instances
    can be solved in polynomial time, otherwise the problem is NP-hard. Unfortunately,
    testing this condition for a given language Γ is known to be NP-hard. We thus
    study exponential algorithms for this meta-problem. We show that the tractability
    condition of a finite-valued language Γ can be tested in O(3‾√3|D|⋅poly(size(Γ)))
    time, where D is the domain of Γ and poly(⋅) is some fixed polynomial. We also
    obtain a matching lower bound under the Strong Exponential Time Hypothesis (SETH).
    More precisely, we prove that for any constant δ<1 there is no O(3‾√3δ|D|) algorithm,
    assuming that SETH holds.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Vladimir
      foaf_name: Kolmogorov, Vladimir
      foaf_surname: Kolmogorov
      foaf_workInfoHomepage: http://www.librecat.org/personId=3D50B0BA-F248-11E8-B48F-1D18A9856A87
  bibo_doi: 10.4230/LIPICS.ICALP.2019.77
  bibo_volume: 132
  dct_date: 2019^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/1868-8969
  - http://id.crossref.org/issn/978-3-95977-109-2
  dct_language: eng
  dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
  dct_title: Testing the complexity of a valued CSP language@
...