@article{1292, abstract = {We give explicit formulas and algorithms for the computation of the Thurston–Bennequin invariant of a nullhomologous Legendrian knot on a page of a contact open book and on Heegaard surfaces in convex position. Furthermore, we extend the results to rationally nullhomologous knots in arbitrary 3-manifolds.}, author = {Durst, Sebastian and Kegel, Marc and Klukas, Mirko D}, journal = {Acta Mathematica Hungarica}, number = {2}, pages = {441 -- 455}, publisher = {Springer}, title = {{Computing the Thurston–Bennequin invariant in open books}}, doi = {10.1007/s10474-016-0648-4}, volume = {150}, year = {2016}, } @article{1293, abstract = {For a graph G with p vertices the closed convex cone S⪰0(G) consists of all real positive semidefinite p×p matrices whose sparsity pattern is given by G, that is, those matrices with zeros in the off-diagonal entries corresponding to nonedges of G. The extremal rays of this cone and their associated ranks have applications to matrix completion problems, maximum likelihood estimation in Gaussian graphical models in statistics, and Gauss elimination for sparse matrices. While the maximum rank of an extremal ray in S⪰0(G), known as the sparsity order of G, has been characterized for different classes of graphs, we here study all possible extremal ranks of S⪰0(G). We investigate when the geometry of the (±1)-cut polytope of G yields a polyhedral characterization of the set of extremal ranks of S⪰0(G). For a graph G without K5 minors, we show that appropriately chosen normal vectors to the facets of the (±1)-cut polytope of G specify the off-diagonal entries of extremal matrices in S⪰0(G). We also prove that for appropriately chosen scalars the constant term of the linear equation of each facet-supporting hyperplane is the rank of its corresponding extremal matrix in S⪰0(G). Furthermore, we show that if G is series-parallel then this gives a complete characterization of all possible extremal ranks of S⪰0(G). Consequently, the sparsity order problem for series-parallel graphs can be solved in terms of polyhedral geometry.}, author = {Solus, Liam T and Uhler, Caroline and Yoshida, Ruriko}, journal = {Linear Algebra and Its Applications}, pages = {247 -- 275}, publisher = {Elsevier}, title = {{Extremal positive semidefinite matrices whose sparsity pattern is given by graphs without K5 minors}}, doi = {10.1016/j.laa.2016.07.026}, volume = {509}, year = {2016}, } @article{1295, abstract = {Voronoi diagrams and Delaunay triangulations have been extensively used to represent and compute geometric features of point configurations. We introduce a generalization to poset diagrams and poset complexes, which contain order-k and degree-k Voronoi diagrams and their duals as special cases. Extending a result of Aurenhammer from 1990, we show how to construct poset diagrams as weighted Voronoi diagrams of average balls.}, author = {Edelsbrunner, Herbert and Iglesias Ham, Mabel}, journal = {Electronic Notes in Discrete Mathematics}, pages = {169 -- 174}, publisher = {Elsevier}, title = {{Multiple covers with balls II: Weighted averages}}, doi = {10.1016/j.endm.2016.09.030}, volume = {54}, year = {2016}, } @article{1303, abstract = {In bright light, cone-photoreceptors are active and colour vision derives from a comparison of signals in cones with different visual pigments. This comparison begins in the retina, where certain retinal ganglion cells have 'colour-opponent' visual responses-excited by light of one colour and suppressed by another colour. In dim light, rod-photoreceptors are active, but colour vision is impossible because they all use the same visual pigment. Instead, the rod signals are thought to splice into retinal circuits at various points, in synergy with the cone signals. Here we report a new circuit for colour vision that challenges these expectations. A genetically identified type of mouse retinal ganglion cell called JAMB (J-RGC), was found to have colour-opponent responses, OFF to ultraviolet (UV) light and ON to green light. Although the mouse retina contains a green-sensitive cone, the ON response instead originates in rods. Rods and cones both contribute to the response over several decades of light intensity. Remarkably, the rod signal in this circuit is antagonistic to that from cones. For rodents, this UV-green channel may play a role in social communication, as suggested by spectral measurements from the environment. In the human retina, all of the components for this circuit exist as well, and its function can explain certain experiences of colour in dim lights, such as a 'blue shift' in twilight. The discovery of this genetically defined pathway will enable new targeted studies of colour processing in the brain.}, author = {Maximilian Jösch and Meister, Markus}, journal = {Nature}, number = {7598}, pages = {236 -- 239}, publisher = {Nature Publishing Group}, title = {{A neuronal circuit for colour vision based on rod-cone opponency}}, doi = {10.1038/nature17158}, volume = {532}, year = {2016}, } @article{1306, abstract = {Resolving patterns of synaptic connectivity in neural circuits currently requires serial section electron microscopy. However, complete circuit reconstruction is prohibitively slow and may not be necessary for many purposes such as comparing neuronal structure and connectivity among multiple animals. Here, we present an alternative strategy, targeted reconstruction of specific neuronal types. We used viral vectors to deliver peroxidase derivatives, which catalyze production of an electron-dense tracer, to genetically identify neurons, and developed a protocol that enhances the electron-density of the labeled cells while retaining the quality of the ultrastructure. The high contrast of the marked neurons enabled two innovations that speed data acquisition: targeted high-resolution reimaging of regions selected from rapidly-acquired lower resolution reconstruction, and an unsupervised segmentation algorithm. This pipeline reduces imaging and reconstruction times by two orders of magnitude, facilitating directed inquiry of circuit motifs.}, author = {Maximilian Jösch and Mankus, David and Yamagata, Masahito and Shahbazi, Ali and Schalek, Richard L and Suissa-Peleg, Adi and Meister, Markus and Lichtman, Jeff W and Scheirer, Walter J and Sanes, Joshua R}, journal = {eLife}, number = {2016JULY}, publisher = {eLife Sciences Publications}, title = {{Reconstruction of genetically identified neurons imaged by serial-section electron microscopy}}, doi = {10.7554/eLife.15015}, volume = {5}, year = {2016}, } @article{1315, abstract = {We prove optimal second order convergence of a modified lowest-order Brezzi-Douglas-Marini (BDM1) mixed finite element scheme for advection-diffusion problems in divergence form. If advection is present, it is known that the total flux is approximated only with first-order accuracy by the classical BDM1 mixed method, which is suboptimal since the same order of convergence is obtained if the computationally less expensive Raviart-Thomas (RT0) element is used. The modification that was first proposed by Brunner et al. [Adv. Water Res., 35 (2012),pp. 163-171] is based on the hybrid problem formulation and consists in using the Lagrange multipliers for the discretization of the advective term instead of the cellwise constant approximation of the scalar unknown.}, author = {Brunner, Fabian and Julian Fischer and Knabner, Peter}, journal = {SIAM Journal on Numerical Analysis}, number = {4}, pages = {2359 -- 2378}, publisher = {Society for Industrial and Applied Mathematics }, title = {{Analysis of a modified second-order mixed hybrid BDM1 finite element method for transport problems in divergence form}}, doi = {10.1137/15M1035379}, volume = {54}, year = {2016}, } @article{1317, abstract = {We analyze the behaviour of free boundaries in thin-film flow in the regime of strong slippage n∈[1,2) and in the regime of very weak slippage n∈,3) qualitatively and quantitatively. In the regime of strong slippage, we construct initial data which are bounded from above by the steady state but for which nevertheless instantaneous forward motion of the free boundary occurs. This shows that the initial behaviour of the free boundary is not determined just by the growth of the initial data at the free boundary. Note that this is a new phenomenon for degenerate parabolic equations which is specific for higher-order equations. Furthermore, this result resolves a controversy in the literature over optimality of sufficient conditions for the occurrence of a waiting time phenomenon. In contrast, in the regime of very weak slippage we derive lower bounds on free boundary propagation which are optimal in the sense that they coincide up to a constant factor with the known upper bounds. In particular, in this regime the growth of the initial data at the free boundary fully determines the initial behaviour of the interface.}, author = {Julian Fischer}, journal = {Annales de l'Institut Henri Poincare (C) Non Linear Analysis}, number = {5}, pages = {1301 -- 1327}, publisher = {Elsevier}, title = {{Behaviour of free boundaries in thin-film flow: The regime of strong slippage and the regime of very weak slippage}}, doi = {10.1016/j.anihpc.2015.05.001}, volume = {33}, year = {2016}, } @article{1318, abstract = {We develop a large-scale regularity theory of higher order for divergence-form elliptic equations with heterogeneous coefficient fields a in the context of stochastic homogenization. The large-scale regularity of a-harmonic functions is encoded by Liouville principles: The space of a-harmonic functions that grow at most like a polynomial of degree k has the same dimension as in the constant-coefficient case. This result can be seen as the qualitative side of a large-scale Ck,α-regularity theory, which in the present work is developed in the form of a corresponding Ck,α-“excess decay” estimate: For a given a-harmonic function u on a ball BR, its energy distance on some ball Br to the above space of a-harmonic functions that grow at most like a polynomial of degree k has the natural decay in the radius r above some minimal radius r0. Though motivated by stochastic homogenization, the contribution of this paper is of purely deterministic nature: We work under the assumption that for the given realization a of the coefficient field, the couple (φ, σ) of scalar and vector potentials of the harmonic coordinates, where φ is the usual corrector, grows sublinearly in a mildly quantified way. We then construct “kth-order correctors” and thereby the space of a-harmonic functions that grow at most like a polynomial of degree k, establish the above excess decay, and then the corresponding Liouville principle.}, author = {Julian Fischer and Otto, Felix}, journal = {Communications in Partial Differential Equations}, number = {7}, pages = {1108 -- 1148}, publisher = {Taylor & Francis}, title = {{A higher-order large scale regularity theory for random elliptic operators}}, doi = {10.1080/03605302.2016.1179318}, volume = {41}, year = {2016}, } @inproceedings{1319, abstract = {We present a novel optimization-based algorithm for the design and fabrication of customized, deformable input devices, capable of continuously sensing their deformation. We propose to embed piezoresistive sensing elements into flexible 3D printed objects. These sensing elements are then utilized to recover rich and natural user interactions at runtime. Designing such objects is a challenging and hard problem if attempted manually for all but the simplest geometries and deformations. Our method simultaneously optimizes the internal routing of the sensing elements and computes a mapping from low-level sensor readings to user-specified outputs in order to minimize reconstruction error. We demonstrate the power and flexibility of the approach by designing and fabricating a set of flexible input devices. Our results indicate that the optimization-based design greatly outperforms manual routings in terms of reconstruction accuracy and thus interaction fidelity.}, author = {Bächer, Moritz and Hepp, Benjamin and Pece, Fabrizio and Kry, Paul and Bickel, Bernd and Thomaszewski, Bernhard and Hilliges, Otmar}, location = {San Jose, California, USA}, pages = {3806 -- 3816}, publisher = {ACM}, title = {{DefSense: computational design of customized deformable input devices}}, doi = {10.1145/2858036.2858354}, year = {2016}, } @inproceedings{1320, abstract = {In recent years, several biomolecular systems have been shown to be scale-invariant (SI), i.e. to show the same output dynamics when exposed to geometrically scaled input signals (u → pu, p > 0) after pre-adaptation to accordingly scaled constant inputs. In this article, we show that SI systems-as well as systems invariant with respect to other input transformations-can realize nonlinear differential operators: when excited by inputs obeying functional forms characteristic for a given class of invariant systems, the systems' outputs converge to constant values directly quantifying the speed of the input.}, author = {Lang, Moritz and Sontag, Eduardo}, location = {Boston, MA, USA}, publisher = {IEEE}, title = {{Scale-invariant systems realize nonlinear differential operators}}, doi = {10.1109/ACC.2016.7526722}, volume = {2016-July}, year = {2016}, } @article{1321, abstract = {Most migrating cells extrude their front by the force of actin polymerization. Polymerization requires an initial nucleation step, which is mediated by factors establishing either parallel filaments in the case of filopodia or branched filaments that form the branched lamellipodial network. Branches are considered essential for regular cell motility and are initiated by the Arp2/3 complex, which in turn is activated by nucleation-promoting factors of the WASP and WAVE families. Here we employed rapid amoeboid crawling leukocytes and found that deletion of the WAVE complex eliminated actin branching and thus lamellipodia formation. The cells were left with parallel filaments at the leading edge, which translated, depending on the differentiation status of the cell, into a unipolar pointed cell shape or cells with multiple filopodia. Remarkably, unipolar cells migrated with increased speed and enormous directional persistence, while they were unable to turn towards chemotactic gradients. Cells with multiple filopodia retained chemotactic activity but their migration was progressively impaired with increasing geometrical complexity of the extracellular environment. These findings establish that diversified leading edge protrusions serve as explorative structures while they slow down actual locomotion.}, author = {Leithner, Alexander F and Eichner, Alexander and Müller, Jan and Reversat, Anne and Brown, Markus and Schwarz, Jan and Merrin, Jack and De Gorter, David and Schur, Florian and Bayerl, Jonathan and De Vries, Ingrid and Wieser, Stefan and Hauschild, Robert and Lai, Frank and Moser, Markus and Kerjaschki, Dontscho and Rottner, Klemens and Small, Victor and Stradal, Theresia and Sixt, Michael K}, journal = {Nature Cell Biology}, pages = {1253 -- 1259}, publisher = {Nature Publishing Group}, title = {{Diversified actin protrusions promote environmental exploration but are dispensable for locomotion of leukocytes}}, doi = {10.1038/ncb3426}, volume = {18}, year = {2016}, } @article{1322, abstract = {Direct reciprocity is a major mechanism for the evolution of cooperation. Several classical studies have suggested that humans should quickly learn to adopt reciprocal strategies to establish mutual cooperation in repeated interactions. On the other hand, the recently discovered theory of ZD strategies has found that subjects who use extortionate strategies are able to exploit and subdue cooperators. Although such extortioners have been predicted to succeed in any population of adaptive opponents, theoretical follow-up studies questioned whether extortion can evolve in reality. However, most of these studies presumed that individuals have similar strategic possibilities and comparable outside options, whereas asymmetries are ubiquitous in real world applications. Here we show with a model and an economic experiment that extortionate strategies readily emerge once subjects differ in their strategic power. Our experiment combines a repeated social dilemma with asymmetric partner choice. In our main treatment there is one randomly chosen group member who is unilaterally allowed to exchange one of the other group members after every ten rounds of the social dilemma. We find that this asymmetric replacement opportunity generally promotes cooperation, but often the resulting payoff distribution reflects the underlying power structure. Almost half of the subjects in a better strategic position turn into extortioners, who quickly proceed to exploit their peers. By adapting their cooperation probabilities consistent with ZD theory, extortioners force their co-players to cooperate without being similarly cooperative themselves. Comparison to non-extortionate players under the same conditions indicates a substantial net gain to extortion. Our results thus highlight how power asymmetries can endanger mutually beneficial interactions, and transform them into exploitative relationships. In particular, our results indicate that the extortionate strategies predicted from ZD theory could play a more prominent role in our daily interactions than previously thought.}, author = {Hilbe, Christian and Hagel, Kristin and Milinski, Manfred}, journal = {PLoS One}, number = {10}, publisher = {Public Library of Science}, title = {{Asymmetric power boosts extortion in an economic experiment}}, doi = {10.1371/journal.pone.0163867}, volume = {11}, year = {2016}, } @article{1323, abstract = {Mossy fiber synapses on CA3 pyramidal cells are 'conditional detonators' that reliably discharge postsynaptic targets. The 'conditional' nature implies that burst activity in dentate gyrus granule cells is required for detonation. Whether single unitary excitatory postsynaptic potentials (EPSPs) trigger spikes in CA3 neurons remains unknown. Mossy fiber synapses exhibit both pronounced short-term facilitation and uniquely large post-tetanic potentiation (PTP). We tested whether PTP could convert mossy fiber synapses from subdetonator into detonator mode, using a recently developed method to selectively and noninvasively stimulate individual presynaptic terminals in rat brain slices. Unitary EPSPs failed to initiate a spike in CA3 neurons under control conditions, but reliably discharged them after induction of presynaptic short-term plasticity. Remarkably, PTP switched mossy fiber synapses into full detonators for tens of seconds. Plasticity-dependent detonation may be critical for efficient coding, storage, and recall of information in the granule cell–CA3 cell network.}, author = {Vyleta, Nicholas and Borges Merjane, Carolina and Jonas, Peter M}, journal = {eLife}, publisher = {eLife Sciences Publications}, title = {{Plasticity-dependent, full detonation at hippocampal mossy fiber–CA3 pyramidal neuron synapses}}, doi = {10.7554/eLife.17977}, volume = {5}, year = {2016}, } @inproceedings{1324, abstract = {DEC-POMDPs extend POMDPs to a multi-agent setting, where several agents operate in an uncertain environment independently to achieve a joint objective. DEC-POMDPs have been studied with finite-horizon and infinite-horizon discounted-sum objectives, and there exist solvers both for exact and approximate solutions. In this work we consider Goal-DEC-POMDPs, where given a set of target states, the objective is to ensure that the target set is reached with minimal cost. We consider the indefinite-horizon (infinite-horizon with either discounted-sum, or undiscounted-sum, where absorbing goal states have zero-cost) problem. We present a new and novel method to solve the problem that extends methods for finite-horizon DEC-POMDPs and the RTDP-Bel approach for POMDPs. We present experimental results on several examples, and show that our approach presents promising results. Copyright }, author = {Chatterjee, Krishnendu and Chmelik, Martin}, booktitle = {Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling}, location = {London, United Kingdom}, pages = {88 -- 96}, publisher = {AAAI Press}, title = {{Indefinite-horizon reachability in Goal-DEC-POMDPs}}, volume = {2016-January}, year = {2016}, } @inproceedings{1325, abstract = {We study graphs and two-player games in which rewards are assigned to states, and the goal of the players is to satisfy or dissatisfy certain property of the generated outcome, given as a mean payoff property. Since the notion of mean-payoff does not reflect possible fluctuations from the mean-payoff along a run, we propose definitions and algorithms for capturing the stability of the system, and give algorithms for deciding if a given mean payoff and stability objective can be ensured in the system.}, author = {Brázdil, Tomáš and Forejt, Vojtěch and Kučera, Antonín and Novotny, Petr}, location = {Quebec City, Canada}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Stability in graphs and games}}, doi = {10.4230/LIPIcs.CONCUR.2016.10}, volume = {59}, year = {2016}, } @inproceedings{1326, abstract = {Energy Markov Decision Processes (EMDPs) are finite-state Markov decision processes where each transition is assigned an integer counter update and a rational payoff. An EMDP configuration is a pair s(n), where s is a control state and n is the current counter value. The configurations are changed by performing transitions in the standard way. We consider the problem of computing a safe strategy (i.e., a strategy that keeps the counter non-negative) which maximizes the expected mean payoff. }, author = {Brázdil, Tomáš and Kučera, Antonín and Novotny, Petr}, location = {Chiba, Japan}, pages = {32 -- 49}, publisher = {Springer}, title = {{Optimizing the expected mean payoff in Energy Markov Decision Processes}}, doi = {10.1007/978-3-319-46520-3_3}, volume = {9938}, year = {2016}, } @inproceedings{1327, abstract = {We consider partially observable Markov decision processes (POMDPs) with a set of target states and positive integer costs associated with every transition. The traditional optimization objective (stochastic shortest path) asks to minimize the expected total cost until the target set is reached. We extend the traditional framework of POMDPs to model energy consumption, which represents a hard constraint. The energy levels may increase and decrease with transitions, and the hard constraint requires that the energy level must remain positive in all steps till the target is reached. First, we present a novel algorithm for solving POMDPs with energy levels, developing on existing POMDP solvers and using RTDP as its main method. Our second contribution is related to policy representation. For larger POMDP instances the policies computed by existing solvers are too large to be understandable. We present an automated procedure based on machine learning techniques that automatically extracts important decisions of the policy allowing us to compute succinct human readable policies. Finally, we show experimentally that our algorithm performs well and computes succinct policies on a number of POMDP instances from the literature that were naturally enhanced with energy levels. }, author = {Brázdil, Tomáš and Chatterjee, Krishnendu and Chmelik, Martin and Gupta, Anchit and Novotny, Petr}, booktitle = {Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems}, location = {Singapore}, pages = {1465 -- 1466}, publisher = {ACM}, title = {{Stochastic shortest path with energy constraints in POMDPs}}, year = {2016}, } @article{1328, abstract = {Hole spins have gained considerable interest in the past few years due to their potential for fast electrically controlled qubits. Here, we study holes confined in Ge hut wires, a so-far unexplored type of nanostructure. Low-temperature magnetotransport measurements reveal a large anisotropy between the in-plane and out-of-plane g-factors of up to 18. Numerical simulations verify that this large anisotropy originates from a confined wave function of heavy-hole character. A light-hole admixture of less than 1% is estimated for the states of lowest energy, leading to a surprisingly large reduction of the out-of-plane g-factors compared with those for pure heavy holes. Given this tiny light-hole contribution, the spin lifetimes are expected to be very long, even in isotopically nonpurified samples.}, author = {Watzinger, Hannes and Kloeffel, Christoph and Vukusic, Lada and Rossell, Marta and Sessi, Violetta and Kukucka, Josip and Kirchschlager, Raimund and Lausecker, Elisabeth and Truhlar, Alisha and Glaser, Martin and Rastelli, Armando and Fuhrer, Andreas and Loss, Daniel and Katsaros, Georgios}, journal = {Nano Letters}, number = {11}, pages = {6879 -- 6885}, publisher = {American Chemical Society}, title = {{Heavy-hole states in germanium hut wires}}, doi = {10.1021/acs.nanolett.6b02715}, volume = {16}, year = {2016}, } @article{1329, abstract = {Daphnia species have become models for ecological genomics and exhibit interesting features, such as high phenotypic plasticity and a densely packed genome with many lineage-specific genes. They are also cyclic parthenogenetic, with alternating asexual and sexual cycles and environmental sex determination. Here, we present a de novo transcriptome assembly of over 32,000 D. galeata genes and use it to investigate gene expression in females and spontaneously produced males of two clonal lines derived from lakes in Germany and the Czech Republic. We find that only a low percentage (18%) of genes shows sex-biased expression and that there are many more female-biased gene (FBG) than male-biased gene (MBG). Furthermore, FBGs tend to be more conserved between species than MBGs in both sequence and expression. These patterns may be a consequence of cyclic parthenogenesis leading to a relaxation of purifying selection on MBGs. The two clonal lines show considerable differences in both number and identity of sex-biased genes, suggesting that they may have reproductive strategies differing in their investment in sexual reproduction. Orthologs of key genes in the sex determination and juvenile hormone pathways, which are thought to be important for the transition from asexual to sexual reproduction, are present in D. galeata and highly conserved among Daphnia species.}, author = {Huylmans, Ann K and López Ezquerra, Alberto and Parsch, John and Cordellier, Mathilde}, journal = {Genome Biology and Evolution}, number = {10}, pages = {3120 -- 3139}, publisher = {Oxford University Press}, title = {{De novo transcriptome assembly and sex-biased gene expression in the cyclical parthenogenetic Daphnia galeata}}, doi = {10.1093/gbe/evw221}, volume = {8}, year = {2016}, } @article{1330, abstract = {In this paper we investigate the existence of closed billiard trajectories in not necessarily smooth convex bodies. In particular, we show that if a body K ⊂ Rd has the property that the tangent cone of every non-smooth point q ∉ ∂K is acute (in a certain sense), then there is a closed billiard trajectory in K.}, author = {Akopyan, Arseniy and Balitskiy, Alexey}, journal = {Israel Journal of Mathematics}, number = {2}, pages = {833 -- 845}, publisher = {Springer}, title = {{Billiards in convex bodies with acute angles}}, doi = {10.1007/s11856-016-1429-z}, volume = {216}, year = {2016}, }