@article{2271,
abstract = {A class of valued constraint satisfaction problems (VCSPs) is characterised by a valued constraint language, a fixed set of cost functions on a finite domain. Finite-valued constraint languages contain functions that take on rational costs and general-valued constraint languages contain functions that take on rational or infinite costs. An instance of the problem is specified by a sum of functions from the language with the goal to minimise the sum. This framework includes and generalises well-studied constraint satisfaction problems (CSPs) and maximum constraint satisfaction problems (Max-CSPs).
Our main result is a precise algebraic characterisation of valued constraint languages whose instances can be solved exactly by the basic linear programming relaxation (BLP). For a general-valued constraint language Γ, BLP is a decision procedure for Γ if and only if Γ admits a symmetric fractional polymorphism of every arity. For a finite-valued constraint language Γ, BLP is a decision procedure if and only if Γ admits a symmetric fractional polymorphism of some arity, or equivalently, if Γ admits a symmetric fractional polymorphism of arity 2.
Using these results, we obtain tractability of several novel and previously widely-open classes of VCSPs, including problems over valued constraint languages that are: (1) submodular on arbitrary lattices; (2) bisubmodular (also known as k-submodular) on arbitrary finite domains; (3) weakly (and hence strongly) tree-submodular on arbitrary trees. },
author = {Kolmogorov, Vladimir and Thapper, Johan and Živný, Stanislav},
journal = {SIAM Journal on Computing},
number = {1},
pages = {1 -- 36},
publisher = {SIAM},
title = {{The power of linear programming for general-valued CSPs}},
doi = {10.1137/130945648},
volume = {44},
year = {2015},
}
@article{256,
abstract = {We show that a non-singular integral form of degree d is soluble over the integers if and only if it is soluble over ℝ and over ℚp for all primes p, provided that the form has at least (d - 1/2 √d)2d variables. This improves on a longstanding result of Birch.},
author = {Timothy Browning and Prendiville, Sean M},
journal = {Journal fur die Reine und Angewandte Mathematik},
number = {731},
publisher = {Walter de Gruyter},
title = {{Improvements in Birch's theorem on forms in many variables}},
doi = {10.1515/crelle-2014-0122},
volume = {2017},
year = {2015},
}
@article{257,
abstract = {For suitable pairs of diagonal quadratic forms in eight variables we use the circle method to investigate the density of simultaneous integer solutions and relate this to the problem of estimating linear correlations among sums of two squares.},
author = {Timothy Browning and Munshi, Ritabrata},
journal = {Forum Mathematicum},
number = {4},
pages = {2025 -- 2050},
publisher = {Walter de Gruyter GmbH},
title = {{Pairs of diagonal quadratic forms and linear correlations among sums of two squares}},
doi = {10.1515/forum-2013-6024},
volume = {27},
year = {2015},
}
@inbook{258,
abstract = {Given a number field k and a projective algebraic variety X defined over k, the question of whether X contains a k-rational point is both very natural and very difficult. In the event that the set X(k) of k-rational points is not empty, one can also ask how the points of X(k) are distributed. Are they dense in X under the Zariski topology? Are they dense in the set.},
author = {Browning, Timothy D},
booktitle = {Arithmetic and Geometry},
pages = {89 -- 113},
publisher = {Cambridge University Press},
title = {{A survey of applications of the circle method to rational points}},
doi = {10.1017/CBO9781316106877.009},
year = {2015},
}
@article{259,
abstract = {The Hasse principle and weak approximation is established for non-singular cubic hypersurfaces X over the function field },
author = {Timothy Browning and Vishe, Pankaj},
journal = {Geometric and Functional Analysis},
number = {3},
pages = {671 -- 732},
publisher = {Birkhäuser},
title = {{Rational points on cubic hypersurfaces over F_q(t) }},
doi = {10.1007/s00039-015-0328-5},
volume = {25},
year = {2015},
}