@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},
}
@article{260,
author = {Timothy Browning and Dietmann, Rainer and Heath-Brown, Roger},
journal = {Journal of the Institute of Mathematics of Jussieu},
number = {4},
publisher = {Cambridge University Press},
title = {{Erratum Rational points on intersections of cubic and quadric hypersurfaces}},
doi = {10.1017/S1474748014000279},
volume = {14},
year = {2015},
}
@article{802,
abstract = {Glycoinositolphosphoceramides (GIPCs) are complex sphingolipids present at the plasma membrane of various eukaryotes with the important exception of mammals. In fungi, these glycosphingolipids commonly contain an alpha-mannose residue (Man) linked at position 2 of the inositol. However, several pathogenic fungi additionally synthesize zwitterionic GIPCs carrying an alpha-glucosamine residue (GlcN) at this position. In the human pathogen Aspergillus fumigatus, the GlcNalpha1,2IPC core (where IPC is inositolphosphoceramide) is elongated to Manalpha1,3Manalpha1,6GlcNalpha1,2IPC, which is the most abundant GIPC synthesized by this fungus. In this study, we identified an A. fumigatus N-acetylglucosaminyltransferase, named GntA, and demonstrate its involvement in the initiation of zwitterionic GIPC biosynthesis. Targeted deletion of the gene encoding GntA in A. fumigatus resulted in complete absence of zwitterionic GIPC; a phenotype that could be reverted by episomal expression of GntA in the mutant. The N-acetylhexosaminyltransferase activity of GntA was substantiated by production of N-acetylhexosamine-IPC in the yeast Saccharomyces cerevisiae upon GntA expression. Using an in vitro assay, GntA was furthermore shown to use UDP-N-acetylglucosamine as donor substrate to generate a glycolipid product resistant to saponification and to digestion by phosphatidylinositol-phospholipase C as expected for GlcNAcalpha1,2IPC. Finally, as the enzymes involved in mannosylation of IPC, GntA was localized to the Golgi apparatus, the site of IPC synthesis.},
author = {Engel, Jakob and Schmalhorst, Philipp S and Kruger, Anke and Muller, Christina and Buettner, Falk and Routier, Françoise},
journal = {Glycobiology},
number = {12},
pages = {1423 -- 1430},
publisher = {Oxford University Press},
title = {{Characterization of an N-acetylglucosaminyltransferase involved in Aspergillus fumigatus zwitterionic glycoinositolphosphoceramide biosynthesis}},
doi = {10.1093/glycob/cwv059},
volume = {25},
year = {2015},
}
@article{814,
abstract = {Human immunodeficiency virus type 1 (HIV-1) assembly proceeds in two stages. First, the 55 kilodalton viral Gag polyprotein assembles into a hexameric protein lattice at the plasma membrane of the infected cell, inducing budding and release of an immature particle. Second, Gag is cleaved by the viral protease, leading to internal rearrangement of the virus into the mature, infectious form. Immature and mature HIV-1 particles are heterogeneous in size and morphology, preventing high-resolution analysis of their protein arrangement in situ by conventional structural biology methods. Here we apply cryo-electron tomography and sub-tomogram averaging methods to resolve the structure of the capsid lattice within intact immature HIV-1 particles at subnanometre resolution, allowing unambiguous positioning of all Î±-helices. The resulting model reveals tertiary and quaternary structural interactions that mediate HIV-1 assembly. Strikingly, these interactions differ from those predicted by the current model based on in vitro-assembled arrays of Gag-derived proteins from Mason-Pfizer monkey virus. To validate this difference, we solve the structure of the capsid lattice within intact immature Mason-Pfizer monkey virus particles. Comparison with the immature HIV-1 structure reveals that retroviral capsid proteins, while having conserved tertiary structures, adopt different quaternary arrangements during virus assembly. The approach demonstrated here should be applicable to determine structures of other proteins at subnanometre resolution within heterogeneous environments.},
author = {Florian Schur and Hagen, Wim J and Rumlová, Michaela and Ruml, Tomáš and Müller B and Kraüsslich, Hans Georg and Briggs, John A},
journal = {Nature},
number = {7535},
pages = {505 -- 508},
publisher = {Nature Publishing Group},
title = {{Structure of the immature HIV-1 capsid in intact virus particles at 8.8 Å resolution}},
doi = {10.1038/nature13838},
volume = {517},
year = {2015},
}
@article{815,
abstract = {The polyprotein Gag is the primary structural component of retroviruses. Gag consists of independently folded domains connected by flexible linkers. Interactions between the conserved capsid (CA) domains of Gag mediate formation of hexameric protein lattices that drive assembly of immature virus particles. Proteolytic cleavage of Gag by the viral protease (PR) is required for maturation of retroviruses from an immature form into an infectious form. Within the assembled Gag lattices of HIV-1 and Mason- Pfizer monkey virus (M-PMV), the C-terminal domain of CA adopts similar quaternary arrangements, while the N-terminal domain of CA is packed in very different manners. Here, we have used cryo-electron tomography and subtomogram averaging to study in vitro-assembled, immature virus-like Rous sarcoma virus (RSV) Gag particles and have determined the structure of CA and the surrounding regions to a resolution of ~8 Å. We found that the C-terminal domain of RSV CA is arranged similarly to HIV-1 and M-PMV, whereas the N-terminal domain of CA adopts a novel arrangement in which the upstream p10 domain folds back into the CA lattice. In this position the cleavage site between CA and p10 appears to be inaccessible to PR. Below CA, an extended density is consistent with the presence of a six-helix bundle formed by the spacer-peptide region. We have also assessed the affect of lattice assembly on proteolytic processing by exogenous PR. The cleavage between p10 and CA is indeed inhibited in the assembled lattice, a finding consistent with structural regulation of proteolytic maturation.
},
author = {Schur, Florian and Dick, Robert and Hagen, Wim and Vogt, Volker and Briggs, John},
journal = {Journal of Virology},
number = {20},
pages = {10294 -- 10302},
publisher = {ASM},
title = {{The structure of immature virus like Rous sarcoma virus gag particles reveals a structural role for the p10 domain in assembly}},
doi = {10.1128/JVI.01502-15},
volume = {89},
year = {2015},
}
@unpublished{8183,
abstract = {We study conditions under which a finite simplicial complex $K$ can be mapped to $\mathbb R^d$ without higher-multiplicity intersections. An almost $r$-embedding is a map $f: K\to \mathbb R^d$ such that the images of any $r$
pairwise disjoint simplices of $K$ do not have a common point. We show that if $r$ is not a prime power and $d\geq 2r+1$, then there is a counterexample to the topological Tverberg conjecture, i.e., there is an almost $r$-embedding of
the $(d+1)(r-1)$-simplex in $\mathbb R^d$. This improves on previous constructions of counterexamples (for $d\geq 3r$) based on a series of papers by M. \"Ozaydin, M. Gromov, P. Blagojevi\'c, F. Frick, G. Ziegler, and the second and fourth present authors. The counterexamples are obtained by proving the following algebraic criterion in codimension 2: If $r\ge3$ and if $K$ is a finite $2(r-1)$-complex then there exists an almost $r$-embedding $K\to \mathbb R^{2r}$ if and only if there exists a general position PL map $f:K\to \mathbb R^{2r}$ such that the algebraic intersection number of the $f$-images of any $r$ pairwise disjoint simplices of $K$ is zero. This result can be restated in terms of cohomological obstructions or equivariant maps, and extends an analogous codimension 3 criterion by the second and fourth authors. As another application we classify ornaments $f:S^3 \sqcup S^3\sqcup S^3\to \mathbb R^5$ up to ornament
concordance. It follows from work of M. Freedman, V. Krushkal and P. Teichner that the analogous criterion for $r=2$ is false. We prove a lemma on singular higher-dimensional Borromean rings, yielding an elementary proof of the counterexample.},
author = {Avvakumov, Sergey and Mabillard, Isaac and Skopenkov, A. and Wagner, Uli},
booktitle = {arXiv},
title = {{Eliminating higher-multiplicity intersections, III. Codimension 2}},
year = {2015},
}