@article{261, abstract = {Let G = SL(2, R) ⋉R2 and Γ = SL(2, Z) ⋉Z2. Building on recent work of Strömbergsson, we prove a rate of equidistribution for the orbits of a certain one-dimensional unipotent flow of Γ\G, which projects to a closed horocycle in the unit tangent bundle to the modular surface. We use this to answer a question of Elkies and McMullen by making effective the convergence of the gap distribution of √n mod 1.}, author = {Timothy Browning and Vinogradov, Ilya}, journal = {Journal of the London Mathematical Society}, number = {1}, pages = {61 -- 84}, publisher = {John Wiley and Sons Ltd}, title = {{Effective ratner theorem for SL (2, R) ⋉R2 and gaps in √n modulo 1}}, doi = {10.1112/jlms/jdw025}, volume = {94}, year = {2016}, } @article{262, abstract = {For any number field we calculate the exact proportion of rational numbers which are everywhere locally a norm but not globally a norm from the number field.}, author = {Timothy Browning and Newton, Rachel}, journal = {Mathematika}, number = {2}, pages = {337 -- 347}, publisher = {Cambridge University Press}, title = {{The proportion of failures of the Hasse norm principle}}, doi = {10.1112/S0025579315000261}, volume = {62}, year = {2016}, } @article{263, abstract = {We count rational points of bounded height on the Cayley ruled cubic surface and interpret the result in the context of general conjectures due to Batyrev and Tschinkel.}, author = {de la Bretèche, Régis and Timothy Browning and Salberger, Per}, journal = {European Journal of Mathematics}, number = {1}, pages = {55 -- 72}, publisher = {Springer Nature}, title = {{Counting rational points on the Cayley ruled cubic}}, doi = {10.1007/s40879-015-0049-1}, volume = {2}, year = {2016}, } @article{264, abstract = {Given a family of varieties over a number field, we determine conditions under which there is a Brauer-Manin obstruction to weak approximation for 100% of the fibres which are everywhere locally soluble.}, author = {Bright, Maritn J and Timothy Browning and Loughran, Daniel}, journal = {Compositio Mathematica}, number = {7}, pages = {1435 -- 1475}, publisher = {Cambridge University Press}, title = {{Failures of weak approximation in families}}, doi = {10.1112/S0010437X16007405}, volume = {152}, year = {2016}, } @inproceedings{1068, abstract = {Games on graphs provide the appropriate framework to study several central problems in computer science, such as verification and synthesis of reactive systems. One of the most basic objectives for games on graphs is the liveness (or Büchi) objective that given a target set of vertices requires that some vertex in the target set is visited infinitely often. We study generalized Büchi objectives (i.e., conjunction of liveness objectives), and implications between two generalized Büchi objectives (known as GR(1) objectives), that arise in numerous applications in computer-aided verification. We present improved algorithms and conditional super-linear lower bounds based on widely believed assumptions about the complexity of (A1) combinatorial Boolean matrix multiplication and (A2) CNF-SAT. We consider graph games with n vertices, m edges, and generalized Büchi objectives with k conjunctions. First, we present an algorithm with running time O(k*n^2), improving the previously known O(k*n*m) and O(k^2*n^2) worst-case bounds. Our algorithm is optimal for dense graphs under (A1). Second, we show that the basic algorithm for the problem is optimal for sparse graphs when the target sets have constant size under (A2). Finally, we consider GR(1) objectives, with k_1 conjunctions in the antecedent and k_2 conjunctions in the consequent, and present an O(k_1 k_2 n^{2.5})-time algorithm, improving the previously known O(k_1*k_2*n*m)-time algorithm for m > n^{1.5}. }, author = {Chatterjee, Krishnendu and Dvorák, Wolfgang and Henzinger, Monika H and Loitzenbauer, Veronika}, location = {Krakow, Poland}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Conditionally optimal algorithms for generalized Büchi Games}}, doi = {10.4230/LIPIcs.MFCS.2016.25}, volume = {58}, year = {2016}, } @inproceedings{1069, abstract = {The Continuous Skolem Problem asks whether a real-valued function satisfying a linear differen- tial equation has a zero in a given interval of real numbers. This is a fundamental reachability problem for continuous linear dynamical systems, such as linear hybrid automata and continuous- time Markov chains. Decidability of the problem is currently open – indeed decidability is open even for the sub-problem in which a zero is sought in a bounded interval. In this paper we show decidability of the bounded problem subject to Schanuel’s Conjecture, a unifying conjecture in transcendental number theory. We furthermore analyse the unbounded problem in terms of the frequencies of the differential equation, that is, the imaginary parts of the characteristic roots. We show that the unbounded problem can be reduced to the bounded problem if there is at most one rationally linearly independent frequency, or if there are two rationally linearly independent frequencies and all characteristic roots are simple. We complete the picture by showing that de- cidability of the unbounded problem in the case of two (or more) rationally linearly independent frequencies would entail a major new effectiveness result in Diophantine approximation, namely computability of the Diophantine-approximation types of all real algebraic numbers.}, author = {Chonev, Ventsislav K and Ouaknine, Joël and Worrell, James}, location = {Rome, Italy}, publisher = {Schloss Dagstuhl- Leibniz-Zentrum fur Informatik}, title = {{On the skolem problem for continuous linear dynamical systems}}, doi = {10.4230/LIPIcs.ICALP.2016.100}, volume = {55}, year = {2016}, } @inproceedings{1070, abstract = {We present a logic that extends CTL (Computation Tree Logic) with operators that express synchronization properties. A property is synchronized in a system if it holds in all paths of a certain length. The new logic is obtained by using the same path quantifiers and temporal operators as in CTL, but allowing a different order of the quantifiers. This small syntactic variation induces a logic that can express non-regular properties for which known extensions of MSO with equality of path length are undecidable. We show that our variant of CTL is decidable and that the model-checking problem is in Delta_3^P = P^{NP^NP}, and is DP-hard. We analogously consider quantifier exchange in extensions of CTL, and we present operators defined using basic operators of CTL* that express the occurrence of infinitely many synchronization points. We show that the model-checking problem remains in Delta_3^P. The distinguishing power of CTL and of our new logic coincide if the Next operator is allowed in the logics, thus the classical bisimulation quotient can be used for state-space reduction before model checking. }, author = {Chatterjee, Krishnendu and Doyen, Laurent}, location = {Rome, Italy}, publisher = {Schloss Dagstuhl- Leibniz-Zentrum fur Informatik}, title = {{Computation tree logic for synchronization properties}}, doi = {10.4230/LIPIcs.ICALP.2016.98}, volume = {55}, year = {2016}, } @inproceedings{1071, abstract = {We consider data-structures for answering reachability and distance queries on constant-treewidth graphs with n nodes, on the standard RAM computational model with wordsize W=Theta(log n). Our first contribution is a data-structure that after O(n) preprocessing time, allows (1) pair reachability queries in O(1) time; and (2) single-source reachability queries in O(n/log n) time. This is (asymptotically) optimal and is faster than DFS/BFS when answering more than a constant number of single-source queries. The data-structure uses at all times O(n) space. Our second contribution is a space-time tradeoff data-structure for distance queries. For any epsilon in [1/2,1], we provide a data-structure with polynomial preprocessing time that allows pair queries in O(n^{1-\epsilon} alpha(n)) time, where alpha is the inverse of the Ackermann function, and at all times uses O(n^epsilon) space. The input graph G is not considered in the space complexity. }, author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Pavlogiannis, Andreas}, location = {Aarhus, Denmark}, publisher = {Schloss Dagstuhl- Leibniz-Zentrum fur Informatik}, title = {{Optimal reachability and a space time tradeoff for distance queries in constant treewidth graphs}}, doi = {10.4230/LIPIcs.ESA.2016.28}, volume = {57}, year = {2016}, } @inproceedings{10746, abstract = {Vortex states in superconducting (SC) structures, their dynamics and ways to manipulate them are topics of great interest. We report a new method of magnetic force microscopy (MFM) that allows the study of vortex states in mesoscopic SC samples. For the case of a SC ring, which is biased to a half-integer flux quantum, the flux modulation through the ring caused by the motion of the magnetic tip drives the ring between two consecutive fluxoid states. The corresponding current switching in the ring produces strong position-dependent forces on the cantilever. In the regime where the frequency of the thermally activated jumps between fluxoid states is close to the frequency of the cantilever, large changes in the cantilever frequency and dissipation are observed. This effect may be understood as a stochastic resonance (SR) process. These changes in the cantilever’s mechanical properties are used to “image” the barrier energies between fluxoid states. Additionally, SR imaging of the barrier energies are used to study the effect of the locally applied magnetic field from the MFM tip on the barrier heights. We report the results of measurements for Al rings. Further, the same imaging technique can be applied to more sophisticated SC structures such as arrays of Josephson junctions.}, author = {Polshyn, Hryhoriy and Naibert, Tyler and Chua, Victor and Budakian, Raffi}, booktitle = {APS March Meeting 2016}, issn = {0003-0503}, location = {Baltimore, MD, United States}, number = {2}, publisher = {American Physical Society}, title = {{Study of vortex states and dynamics in mesoscopic superconducting samples with MFM}}, volume = {61}, year = {2016}, } @inproceedings{10747, abstract = {Vortex interactions are key to explaining the behavior of many two dimensional superconducting systems. We report on the development of a technique to locally probe vortex interactions in a 2D array of Josephson junctions. Scanning a magnetic tip attached to an ultra-soft cantilever over the array produces changes in the frequency of the cantilever along certain lines, forming geometric patterns in the scans. Different tip-surface separations and external magnetic fields produce a number of different patterns. These patterns correspond to tip locations in which two configurations of vortices in the lattice have degenerate energies. By imaging the locations of these degeneracies, information on the local vortex interactions may be obtained.}, author = {Naibert, Tyler and Polshyn, Hryhoriy and Wolin, Brian and Durkin, Malcolm and Garrido Menacho, Rita and Shem, Ian Mondragon and Chua, Victor and Hughes, Taylor and Mason, Nadya and Budakian, Raffi}, booktitle = {APS March Meeting 2016}, issn = {0003-0503}, location = {Baltimore, MD, United States}, number = {2}, publisher = {American Physical Society}, title = {{Stochastic resonance magnetic force microscopy imaging of Josephson arrays}}, volume = {61}, year = {2016}, } @article{1081, abstract = {The asymmetric localization of proteins in the plasma membrane domains of eukaryotic cells is a fundamental manifestation of cell polarity that is central to multicellular organization and developmental patterning. In plants, the mechanisms underlying the polar localization of cargo proteins are still largely unknown and appear to be fundamentally distinct from those operating in mammals. Here, we present a systematic, quantitative comparative analysis of the polar delivery and subcellular localization of proteins that characterize distinct polar plasma membrane domains in plant cells. The combination of microscopic analyses and computational modeling revealed a mechanistic framework common to diverse polar cargos and underlying the establishment and maintenance of apical, basal, and lateral polar domains in plant cells. This mechanism depends on the polar secretion, constitutive endocytic recycling, and restricted lateral diffusion of cargos within the plasma membrane. Moreover, our observations suggest that polar cargo distribution involves the individual protein potential to form clusters within the plasma membrane and interact with the extracellular matrix. Our observations provide insights into the shared cellular mechanisms of polar cargo delivery and polarity maintenance in plant cells.}, author = {Łangowski, Łukasz and Wabnik, Krzysztof T and Li, Hongjiang and Vanneste, Steffen and Naramoto, Satoshi and Tanaka, Hirokazu and Friml, Jirí}, journal = {Cell Discovery}, publisher = {Nature Publishing Group}, title = {{Cellular mechanisms for cargo delivery and polarity maintenance at different polar domains in plant cells}}, doi = {10.1038/celldisc.2016.18}, volume = {2}, year = {2016}, } @inproceedings{10810, abstract = {The main goal of the SCP-ECG standard is to address ECG data and related metadata structuring, semantics and syntax, with the objective of facilitating interoperability and thus supporting and promoting the exchange of the relevant information for unary and serial ECG diagnosis. Starting with version V3.0, the standard now also provides support for the storage of continuous, long-term ECG recordings and affords a repository for selected ECG sequences and the related metadata to accommodate stress tests, drug trials and protocol-based ECG recordings. The global and per-lead measurements sections have been extended and three new sections have been introduced for storing beat-by-beat and/or spike-by-spike measurements and annotations. The used terminology and the provided measurements and annotations have been harmonized with the ISO/IEEE 11073-10102 Annotated ECG standard. Emphasis has also been put on harmonizing the Universal Statement Codes with the CDISC and the categorized AHA statement codes and similarly the drug and implanted devices codes with the ATC and NASPE/BPEG codes. }, author = {Rubel, Paul and Pani, Danilo and Schlögl, Alois and Fayn, Jocelyne and Badilini, Fabio and Macfarlane, Peter and Varri, Alpo}, booktitle = {2016 Computing in Cardiology Conference}, issn = {2325-887X}, location = {Vancouver, Canada}, pages = {309--312}, publisher = {Computing in Cardiology}, title = {{SCP-ECG V3.0: An enhanced standard communication protocol for computer-assisted electrocardiography}}, doi = {10.22489/cinc.2016.090-500}, volume = {43}, year = {2016}, } @inproceedings{1082, abstract = {In many applications, it is desirable to extract only the relevant aspects of data. A principled way to do this is the information bottleneck (IB) method, where one seeks a code that maximises information about a relevance variable, Y, while constraining the information encoded about the original data, X. Unfortunately however, the IB method is computationally demanding when data are high-dimensional and/or non-gaussian. Here we propose an approximate variational scheme for maximising a lower bound on the IB objective, analogous to variational EM. Using this method, we derive an IB algorithm to recover features that are both relevant and sparse. Finally, we demonstrate how kernelised versions of the algorithm can be used to address a broad range of problems with non-linear relation between X and Y.}, author = {Chalk, Matthew J and Marre, Olivier and Tkacik, Gasper}, location = {Barcelona, Spain}, pages = {1965--1973}, publisher = {Neural Information Processing Systems}, title = {{Relevant sparse codes with variational information bottleneck}}, volume = {29}, year = {2016}, } @article{1083, abstract = { Cholecystokinin-expressing interneurons (CCK-INs) mediate behavior state-dependent inhibition in cortical circuits and themselves receive strong GABAergic input. However, it remains unclear to what extent GABABreceptors (GABABRs) contribute to their inhibitory control. Using immunoelectron microscopy, we found that CCK-INs in the rat hippocampus possessed high levels of dendritic GABABRs and KCTD12 auxiliary proteins, whereas postsynaptic effector Kir3 channels were present at lower levels. Consistently, whole-cell recordings revealed slow GABABR-mediated inhibitory postsynaptic currents (IPSCs) in most CCK-INs. In spite of the higher surface density of GABABRs in CCK-INs than in CA1 principal cells, the amplitudes of IPSCs were comparable, suggesting that the expression of Kir3 channels is the limiting factor for the GABABR currents in these INs. Morphological analysis showed that CCK-INs were diverse, comprising perisomatic-targeting basket cells (BCs), as well as dendrite-targeting (DT) interneurons, including a previously undescribed DT type. GABABR-mediated IPSCs in CCK-INs were large in BCs, but small in DT subtypes. In response to prolonged activation, GABABR-mediated currents displayed strong desensitization, which was absent in KCTD12-deficient mice. This study highlights that GABABRs differentially control CCK-IN subtypes, and the kinetics and desensitization of GABABR-mediated currents are modulated by KCTD12 proteins. }, author = {Booker, Sam and Althof, Daniel and Gross, Anna and Loreth, Desiree and Müller, Johanna and Unger, Andreas and Fakler, Bernd and Varro, Andrea and Watanabe, Masahiko and Gassmann, Martin and Bettler, Bernhard and Shigemoto, Ryuichi and Vida, Imre and Kulik, Ákos}, journal = {Cerebral Cortex}, number = {3}, pages = {2318 -- 2334}, publisher = {Oxford University Press}, title = {{KCTD12 auxiliary proteins modulate kinetics of GABAB receptor-mediated inhibition in Cholecystokinin-containing interneurons}}, doi = {10.1093/cercor/bhw090}, volume = {27}, year = {2016}, } @article{1088, abstract = {Cell geometry is tightly coupled to gene expression patterns within the tissue microenvironment. This perspective synthesizes evidence that the 3D organization of chromosomes is a critical intermediate for geometric control of genomic programs. Using a combination of experiments and modeling we outline approaches to decipher the mechano-genomic code that governs cellular homeostasis and reprogramming.}, author = {Uhler, Caroline and Shivashankar, G V}, journal = {BioArchitecture}, number = {4}, pages = {76 -- 84}, publisher = {Taylor & Francis}, title = {{Geometric control and modeling of genome reprogramming}}, doi = {10.1080/19490992.2016.1201620}, volume = {6}, year = {2016}, } @inproceedings{1090, abstract = { While weighted automata provide a natural framework to express quantitative properties, many basic properties like average response time cannot be expressed with weighted automata. Nested weighted automata extend weighted automata and consist of a master automaton and a set of slave automata that are invoked by the master automaton. Nested weighted automata are strictly more expressive than weighted automata (e.g., average response time can be expressed with nested weighted automata), but the basic decision questions have higher complexity (e.g., for deterministic automata, the emptiness question for nested weighted automata is PSPACE-hard, whereas the corresponding complexity for weighted automata is PTIME). We consider a natural subclass of nested weighted automata where at any point at most a bounded number k of slave automata can be active. We focus on automata whose master value function is the limit average. We show that these nested weighted automata with bounded width are strictly more expressive than weighted automata (e.g., average response time with no overlapping requests can be expressed with bound k=1, but not with non-nested weighted automata). We show that the complexity of the basic decision problems (i.e., emptiness and universality) for the subclass with k constant matches the complexity for weighted automata. Moreover, when k is part of the input given in unary we establish PSPACE-completeness.}, author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Otop, Jan}, location = {Krakow; Poland}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Nested weighted limit-average automata of bounded width}}, doi = {10.4230/LIPIcs.MFCS.2016.24}, volume = {58}, year = {2016}, } @inproceedings{1093, abstract = {We introduce a general class of distances (metrics) between Markov chains, which are based on linear behaviour. This class encompasses distances given topologically (such as the total variation distance or trace distance) as well as by temporal logics or automata. We investigate which of the distances can be approximated by observing the systems, i.e. by black-box testing or simulation, and we provide both negative and positive results. }, author = {Daca, Przemyslaw and Henzinger, Thomas A and Kretinsky, Jan and Petrov, Tatjana}, location = {Quebec City; Canada}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Linear distances between Markov chains}}, doi = {10.4230/LIPIcs.CONCUR.2016.20}, volume = {59}, year = {2016}, } @inbook{1094, abstract = {Immunogold labeling of freeze-fracture replicas has recently been used for high-resolution visualization of protein localization in electron microscopy. This method has higher labeling efficiency than conventional immunogold methods for membrane molecules allowing precise quantitative measurements. However, one of the limitations of freeze-fracture replica immunolabeling is difficulty in keeping structural orientation and identifying labeled profiles in complex tissues like brain. The difficulty is partly due to fragmentation of freeze-fracture replica preparations during labeling procedures and limited morphological clues on the replica surface. To overcome these issues, we introduce here a grid-glued replica method combined with SEM observation. This method allows histological staining before dissolving the tissue and easy handling of replicas during immunogold labeling, and keeps the whole replica surface intact without fragmentation. The procedure described here is also useful for matched double-replica analysis allowing further identification of labeled profiles in corresponding P-face and E-face.}, author = {Harada, Harumi and Shigemoto, Ryuichi}, booktitle = {High-Resolution Imaging of Cellular Proteins}, issn = {1611-3349}, pages = {203 -- 216}, publisher = {Springer}, title = {{Immunogold protein localization on grid-glued freeze-fracture replicas}}, doi = {10.1007/978-1-4939-6352-2_12}, volume = {1474}, year = {2016}, } @inproceedings{1095, abstract = { The semantics of concurrent data structures is usually given by a sequential specification and a consistency condition. Linearizability is the most popular consistency condition due to its simplicity and general applicability. Nevertheless, for applications that do not require all guarantees offered by linearizability, recent research has focused on improving performance and scalability of concurrent data structures by relaxing their semantics. In this paper, we present local linearizability, a relaxed consistency condition that is applicable to container-type concurrent data structures like pools, queues, and stacks. While linearizability requires that the effect of each operation is observed by all threads at the same time, local linearizability only requires that for each thread T, the effects of its local insertion operations and the effects of those removal operations that remove values inserted by T are observed by all threads at the same time. We investigate theoretical and practical properties of local linearizability and its relationship to many existing consistency conditions. We present a generic implementation method for locally linearizable data structures that uses existing linearizable data structures as building blocks. Our implementations show performance and scalability improvements over the original building blocks and outperform the fastest existing container-type implementations. }, author = {Haas, Andreas and Henzinger, Thomas A and Holzer, Andreas and Kirsch, Christoph and Lippautz, Michael and Payer, Hannes and Sezgin, Ali and Sokolova, Ana and Veith, Helmut}, booktitle = {Leibniz International Proceedings in Informatics}, location = {Quebec City; Canada}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Local linearizability for concurrent container-type data structures}}, doi = {10.4230/LIPIcs.CONCUR.2016.6}, volume = {59}, year = {2016}, } @article{1096, author = {Schwayer, Cornelia and Sikora, Mateusz K and Slovakova, Jana and Kardos, Roland and Heisenberg, Carl-Philipp J}, journal = {Developmental Cell}, number = {6}, pages = {493 -- 506}, publisher = {Cell Press}, title = {{Actin rings of power}}, doi = {10.1016/j.devcel.2016.05.024}, volume = {37}, year = {2016}, }