@inproceedings{2218, abstract = {While fixing concurrency bugs, program repair algorithms may introduce new concurrency bugs. We present an algorithm that avoids such regressions. The solution space is given by a set of program transformations we consider in the repair process. These include reordering of instructions within a thread and inserting atomic sections. The new algorithm learns a constraint on the space of candidate solutions, from both positive examples (error-free traces) and counterexamples (error traces). From each counterexample, the algorithm learns a constraint necessary to remove the errors. From each positive examples, it learns a constraint that is necessary in order to prevent the repair from turning the trace into an error trace. We implemented the algorithm and evaluated it on simplified Linux device drivers with known bugs.}, author = {Cerny, Pavol and Henzinger, Thomas A and Radhakrishna, Arjun and Ryzhyk, Leonid and Tarrach, Thorsten}, isbn = {978-331908866-2}, location = {Vienna, Austria}, pages = {568 -- 584}, publisher = {Springer}, title = {{Regression-free synthesis for concurrency}}, doi = {10.1007/978-3-319-08867-9_38}, volume = {8559}, year = {2014}, } @inproceedings{2167, abstract = {Model-based testing is a promising technology for black-box software and hardware testing, in which test cases are generated automatically from high-level specifications. Nowadays, systems typically consist of multiple interacting components and, due to their complexity, testing presents a considerable portion of the effort and cost in the design process. Exploiting the compositional structure of system specifications can considerably reduce the effort in model-based testing. Moreover, inferring properties about the system from testing its individual components allows the designer to reduce the amount of integration testing. In this paper, we study compositional properties of the ioco-testing theory. We propose a new approach to composition and hiding operations, inspired by contract-based design and interface theories. These operations preserve behaviors that are compatible under composition and hiding, and prune away incompatible ones. The resulting specification characterizes the input sequences for which the unit testing of components is sufficient to infer the correctness of component integration without the need for further tests. We provide a methodology that uses these results to minimize integration testing effort, but also to detect potential weaknesses in specifications. While we focus on asynchronous models and the ioco conformance relation, the resulting methodology can be applied to a broader class of systems.}, author = {Daca, Przemyslaw and Henzinger, Thomas A and Krenn, Willibald and Nickovic, Dejan}, booktitle = {IEEE 7th International Conference on Software Testing, Verification and Validation}, isbn = {978-1-4799-2255-0}, issn = {2159-4848}, location = {Cleveland, USA}, publisher = {IEEE}, title = {{Compositional specifications for IOCO testing}}, doi = {10.1109/ICST.2014.50}, year = {2014}, } @inproceedings{2063, abstract = {We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems.We focus on qualitative properties forMDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability. We introduce a new simulation relation to capture the refinement relation ofMDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.We present an automated technique for assume-guarantee style reasoning for compositional analysis ofMDPs with qualitative properties by giving a counterexample guided abstraction-refinement approach to compute our new simulation relation. We have implemented our algorithms and show that the compositional analysis leads to significant improvements.}, author = {Chatterjee, Krishnendu and Chmelik, Martin and Daca, Przemyslaw}, location = {Vienna, Austria}, pages = {473 -- 490}, publisher = {Springer}, title = {{CEGAR for qualitative analysis of probabilistic systems}}, doi = {10.1007/978-3-319-08867-9_31}, volume = {8559}, year = {2014}, } @article{2001, abstract = {Antibiotics affect bacterial cell physiology at many levels. Rather than just compensating for the direct cellular defects caused by the drug, bacteria respond to antibiotics by changing their morphology, macromolecular composition, metabolism, gene expression and possibly even their mutation rate. Inevitably, these processes affect each other, resulting in a complex response with changes in the expression of numerous genes. Genome‐wide approaches can thus help in gaining a comprehensive understanding of bacterial responses to antibiotics. In addition, a combination of experimental and theoretical approaches is needed for identifying general principles that underlie these responses. Here, we review recent progress in our understanding of bacterial responses to antibiotics and their combinations, focusing on effects at the levels of growth rate and gene expression. We concentrate on studies performed in controlled laboratory conditions, which combine promising experimental techniques with quantitative data analysis and mathematical modeling. While these basic research approaches are not immediately applicable in the clinic, uncovering the principles and mechanisms underlying bacterial responses to antibiotics may, in the long term, contribute to the development of new treatment strategies to cope with and prevent the rise of resistant pathogenic bacteria.}, author = {Mitosch, Karin and Bollenbach, Tobias}, journal = {Environmental Microbiology Reports}, number = {6}, pages = {545 -- 557}, publisher = {Wiley}, title = {{Bacterial responses to antibiotics and their combinations}}, doi = {10.1111/1758-2229.12190}, volume = {6}, year = {2014}, } @inproceedings{2082, abstract = {NMAC is a mode of operation which turns a fixed input-length keyed hash function f into a variable input-length function. A practical single-key variant of NMAC called HMAC is a very popular and widely deployed message authentication code (MAC). Security proofs and attacks for NMAC can typically be lifted to HMAC. NMAC was introduced by Bellare, Canetti and Krawczyk [Crypto'96], who proved it to be a secure pseudorandom function (PRF), and thus also a MAC, assuming that (1) f is a PRF and (2) the function we get when cascading f is weakly collision-resistant. Unfortunately, HMAC is typically instantiated with cryptographic hash functions like MD5 or SHA-1 for which (2) has been found to be wrong. To restore the provable guarantees for NMAC, Bellare [Crypto'06] showed its security based solely on the assumption that f is a PRF, albeit via a non-uniform reduction. - Our first contribution is a simpler and uniform proof for this fact: If f is an ε-secure PRF (against q queries) and a δ-non-adaptively secure PRF (against q queries), then NMAC f is an (ε+ℓqδ)-secure PRF against q queries of length at most ℓ blocks each. - We then show that this ε+ℓqδ bound is basically tight. For the most interesting case where ℓqδ ≥ ε we prove this by constructing an f for which an attack with advantage ℓqδ exists. This also violates the bound O(ℓε) on the PRF-security of NMAC recently claimed by Koblitz and Menezes. - Finally, we analyze the PRF-security of a modification of NMAC called NI [An and Bellare, Crypto'99] that differs mainly by using a compression function with an additional keying input. This avoids the constant rekeying on multi-block messages in NMAC and allows for a security proof starting by the standard switch from a PRF to a random function, followed by an information-theoretic analysis. We carry out such an analysis, obtaining a tight ℓq2/2 c bound for this step, improving over the trivial bound of ℓ2q2/2c. The proof borrows combinatorial techniques originally developed for proving the security of CBC-MAC [Bellare et al., Crypto'05].}, author = {Gazi, Peter and Pietrzak, Krzysztof Z and Rybar, Michal}, editor = {Garay, Juan and Gennaro, Rosario}, location = {Santa Barbara, USA}, number = {1}, pages = {113 -- 130}, publisher = {Springer}, title = {{The exact PRF-security of NMAC and HMAC}}, doi = {10.1007/978-3-662-44371-2_7}, volume = {8616}, year = {2014}, } @article{1912, abstract = {Kupffer's vesicle (KV) is the zebrafish organ of laterality, patterning the embryo along its left-right (LR) axis. Regional differences in cell shape within the lumen-lining KV epithelium are essential for its LR patterning function. However, the processes by which KV cells acquire their characteristic shapes are largely unknown. Here, we show that the notochord induces regional differences in cell shape within KV by triggering extracellular matrix (ECM) accumulation adjacent to anterior-dorsal (AD) regions of KV. This localized ECM deposition restricts apical expansion of lumen-lining epithelial cells in AD regions of KV during lumen growth. Our study provides mechanistic insight into the processes by which KV translates global embryonic patterning into regional cell shape differences required for its LR symmetry-breaking function.}, author = {Compagnon, Julien and Barone, Vanessa and Rajshekar, Srivarsha and Kottmeier, Rita and Pranjic-Ferscha, Kornelija and Behrndt, Martin and Heisenberg, Carl-Philipp J}, journal = {Developmental Cell}, number = {6}, pages = {774 -- 783}, publisher = {Cell Press}, title = {{The notochord breaks bilateral symmetry by controlling cell shapes in the Zebrafish laterality organ}}, doi = {10.1016/j.devcel.2014.11.003}, volume = {31}, year = {2014}, } @article{2084, abstract = {Receptor tyrosine kinases (RTKs) are a large family of cell surface receptors that sense growth factors and hormones and regulate a variety of cell behaviours in health and disease. Contactless activation of RTKs with spatial and temporal precision is currently not feasible. Here, we generated RTKs that are insensitive to endogenous ligands but can be selectively activated by low-intensity blue light. We screened light-oxygen-voltage (LOV)-sensing domains for their ability to activate RTKs by light-activated dimerization. Incorporation of LOV domains found in aureochrome photoreceptors of stramenopiles resulted in robust activation of the fibroblast growth factor receptor 1 (FGFR1), epidermal growth factor receptor (EGFR) and rearranged during transfection (RET). In human cancer and endothelial cells, light induced cellular signalling with spatial and temporal precision. Furthermore, light faithfully mimicked complex mitogenic and morphogenic cell behaviour induced by growth factors. RTKs under optical control (Opto-RTKs) provide a powerful optogenetic approach to actuate cellular signals and manipulate cell behaviour.}, author = {Grusch, Michael and Schelch, Karin and Riedler, Robert and Gschaider-Reichhart, Eva and Differ, Christopher and Berger, Walter and Inglés Prieto, Álvaro and Janovjak, Harald L}, journal = {EMBO Journal}, number = {15}, pages = {1713 -- 1726}, publisher = {Wiley-Blackwell}, title = {{Spatio-temporally precise activation of engineered receptor tyrosine kinases by light}}, doi = {10.15252/embj.201387695}, volume = {33}, year = {2014}, } @inproceedings{2157, abstract = {We show that the following algorithmic problem is decidable: given a 2-dimensional simplicial complex, can it be embedded (topologically, or equivalently, piecewise linearly) in ℝ3? By a known reduction, it suffices to decide the embeddability of a given triangulated 3-manifold X into the 3-sphere S3. The main step, which allows us to simplify X and recurse, is in proving that if X can be embedded in S3, then there is also an embedding in which X has a short meridian, i.e., an essential curve in the boundary of X bounding a disk in S3 nX with length bounded by a computable function of the number of tetrahedra of X.}, author = {Matoušek, Jiří and Sedgwick, Eric and Tancer, Martin and Wagner, Uli}, booktitle = {Proceedings of the Annual Symposium on Computational Geometry}, location = {Kyoto, Japan}, pages = {78 -- 84}, publisher = {ACM}, title = {{Embeddability in the 3 sphere is decidable}}, doi = {10.1145/2582112.2582137}, year = {2014}, } @inproceedings{10894, abstract = {PHAT is a C++ library for the computation of persistent homology by matrix reduction. We aim for a simple generic design that decouples algorithms from data structures without sacrificing efficiency or user-friendliness. This makes PHAT a versatile platform for experimenting with algorithmic ideas and comparing them to state of the art implementations.}, author = {Bauer, Ulrich and Kerber, Michael and Reininghaus, Jan and Wagner, Hubert}, booktitle = {ICMS 2014: International Congress on Mathematical Software}, isbn = {9783662441985}, issn = {1611-3349}, location = {Seoul, South Korea}, pages = {137--143}, publisher = {Springer Berlin Heidelberg}, title = {{PHAT – Persistent Homology Algorithms Toolbox}}, doi = {10.1007/978-3-662-44199-2_24}, volume = {8592}, year = {2014}, } @misc{5428, abstract = {Simulation is an attractive alternative for language inclusion for automata as it is an under-approximation of language inclusion, but usually has much lower complexity. For non-deterministic automata, while language inclusion is PSPACE-complete, simulation can be computed in polynomial time. Simulation has also been extended in two orthogonal directions, namely, (1) fair simulation, for simulation over specified set of infinite runs; and (2) quantitative simulation, for simulation between weighted automata. Again, while fair trace inclusion is PSPACE-complete, fair simulation can be computed in polynomial time. For weighted automata, the (quantitative) language inclusion problem is undecidable for mean-payoff automata and the decidability is open for discounted-sum automata, whereas the (quantitative) simulation reduce to mean-payoff games and discounted-sum games, which admit pseudo-polynomial time algorithms. In this work, we study (quantitative) simulation for weighted automata with Büchi acceptance conditions, i.e., we generalize fair simulation from non-weighted automata to weighted automata. We show that imposing Büchi acceptance conditions on weighted automata changes many fundamental properties of the simulation games. For example, whereas for mean-payoff and discounted-sum games, the players do not need memory to play optimally; we show in contrast that for simulation games with Büchi acceptance conditions, (i) for mean-payoff objectives, optimal strategies for both players require infinite memory in general, and (ii) for discounted-sum objectives, optimal strategies need not exist for both players. While the simulation games with Büchi acceptance conditions are more complicated (e.g., due to infinite-memory requirements for mean-payoff objectives) as compared to their counterpart without Büchi acceptance conditions, we still present pseudo-polynomial time algorithms to solve simulation games with Büchi acceptance conditions for both weighted mean-payoff and weighted discounted-sum automata.}, author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Otop, Jan and Velner, Yaron}, issn = {2664-1690}, pages = {26}, publisher = {IST Austria}, title = {{Quantitative fair simulation games}}, doi = {10.15479/AT:IST-2014-315-v1-1}, year = {2014}, } @article{1887, author = {Cremer, Sylvia}, journal = {Zoologie}, pages = {23 -- 30}, publisher = {Deutsche Zoologische Gesellschaft}, title = {{Gemeinsame Krankheitsabwehr in Ameisengesellschaften}}, year = {2014}, } @article{2175, abstract = {The cerebral cortex, the seat of our cognitive abilities, is composed of an intricate network of billions of excitatory projection and inhibitory interneurons. Postmitotic cortical neurons are generated by a diverse set of neural stem cell progenitors within dedicated zones and defined periods of neurogenesis during embryonic development. Disruptions in neurogenesis can lead to alterations in the neuronal cytoarchitecture, which is thought to represent a major underlying cause for several neurological disorders, including microcephaly, autism and epilepsy. Although a number of signaling pathways regulating neurogenesis have been described, the precise cellular and molecular mechanisms regulating the functional neural stem cell properties in cortical neurogenesis remain unclear. Here, we discuss the most up-to-date strategies to monitor the fundamental mechanistic parameters of neuronal progenitor proliferation, and recent advances deciphering the logic and dynamics of neurogenesis.}, author = {Postiglione, Maria P and Hippenmeyer, Simon}, issn = {1748-6971}, journal = {Future Neurology}, number = {3}, pages = {323 -- 340}, publisher = {Future Science Group}, title = {{Monitoring neurogenesis in the cerebral cortex: an update}}, doi = {10.2217/fnl.14.18}, volume = {9}, year = {2014}, } @article{1913, abstract = {Deposits of phosphorylated tau protein and convergence of pathology in the hippocampus are the hallmarks of neurodegenerative tauopathies. Thus we aimed to evaluate whether regional and cellular vulnerability patterns in the hippocampus distinguish tauopathies or are influenced by their concomitant presence. Methods: We created a heat map of phospho-tau (AT8) immunoreactivity patterns in 24 hippocampal subregions/layers in individuals with Alzheimer's disease (AD)-related neurofibrillary degeneration (n = 40), Pick's disease (n = 8), progressive supranuclear palsy (n = 7), corticobasal degeneration (n = 6), argyrophilic grain disease (AGD, n = 18), globular glial tauopathy (n = 5), and tau-astrogliopathy of the elderly (n = 10). AT8 immunoreactivity patterns were compared by mathematical analysis. Results: Our study reveals disease-specific hot spots and regional selective vulnerability for these disorders. The pattern of hippocampal AD-related tau pathology is strongly influenced by concomitant AGD. Mathematical analysis reveals that hippocampal involvement in primary tauopathies is distinguishable from early-stage AD-related neurofibrillary degeneration. Conclusion: Our data demonstrate disease-specific AT8 immunoreactivity patterns and hot spots in the hippocampus even in tauopathies, which primarily do not affect the hippocampus. These hot spots can be shifted to other regions by the co-occurrence of tauopathies like AGD. Our observations support the notion that globular glial tauopathies and tau-astrogliopathy of the elderly are distinct entities.}, author = {Milenković, Ivan and Petrov, Tatjana and Kovács, Gábor}, issn = {1420-8008}, journal = {Dementia and Geriatric Cognitive Disorders}, number = {5-6}, pages = {375 -- 388}, publisher = {Karger Publishers}, title = {{Patterns of hippocampal tau pathology differentiate neurodegenerative dementias}}, doi = {10.1159/000365548}, volume = {38}, year = {2014}, } @inproceedings{1507, abstract = {The Wigner-Dyson-Gaudin-Mehta conjecture asserts that the local eigenvalue statistics of large real and complex Hermitian matrices with independent, identically distributed entries are universal in a sense that they depend only on the symmetry class of the matrix and otherwise are independent of the details of the distribution. We present the recent solution to this half-century old conjecture. We explain how stochastic tools, such as the Dyson Brownian motion, and PDE ideas, such as De Giorgi-Nash-Moser regularity theory, were combined in the solution. We also show related results for log-gases that represent a universal model for strongly correlated systems. Finally, in the spirit of Wigner’s original vision, we discuss the extensions of these universality results to more realistic physical systems such as random band matrices.}, author = {Erdös, László}, booktitle = {Proceedings of the International Congress of Mathematicians}, location = {Seoul, Korea}, pages = {214 -- 236}, publisher = {International Congress of Mathematicians}, title = {{Random matrices, log-gases and Hölder regularity}}, volume = {3}, year = {2014}, } @inproceedings{8044, abstract = {Many questions concerning models in quantum mechanics require a detailed analysis of the spectrum of the corresponding Hamiltonian, a linear operator on a suitable Hilbert space. Of particular relevance for an understanding of the low-temperature properties of a system is the structure of the excitation spectrum, which is the part of the spectrum close to the spectral bottom. We present recent progress on this question for bosonic many-body quantum systems with weak two-body interactions. Such system are currently of great interest, due to their experimental realization in ultra-cold atomic gases. We investigate the accuracy of the Bogoliubov approximations, which predicts that the low-energy spectrum is made up of sums of elementary excitations, with linear dispersion law at low momentum. The latter property is crucial for the superfluid behavior the system.}, author = {Seiringer, Robert}, booktitle = {Proceeding of the International Congress of Mathematicans}, isbn = {9788961058063}, location = {Seoul, South Korea}, pages = {1175--1194}, publisher = {International Congress of Mathematicians}, title = {{Structure of the excitation spectrum for many-body quantum systems}}, volume = {3}, year = {2014}, } @inproceedings{2160, abstract = {Transfer learning has received a lot of attention in the machine learning community over the last years, and several effective algorithms have been developed. However, relatively little is known about their theoretical properties, especially in the setting of lifelong learning, where the goal is to transfer information to tasks for which no data have been observed so far. In this work we study lifelong learning from a theoretical perspective. Our main result is a PAC-Bayesian generalization bound that offers a unified view on existing paradigms for transfer learning, such as the transfer of parameters or the transfer of low-dimensional representations. We also use the bound to derive two principled lifelong learning algorithms, and we show that these yield results comparable with existing methods.}, author = {Pentina, Anastasia and Lampert, Christoph}, location = {Beijing, China}, pages = {991 -- 999}, publisher = {ML Research Press}, title = {{A PAC-Bayesian bound for Lifelong Learning}}, volume = {32}, year = {2014}, } @phdthesis{1403, abstract = {A variety of developmental and disease related processes depend on epithelial cell sheet spreading. In order to gain insight into the biophysical mechanism(s) underlying the tissue morphogenesis we studied the spreading of an epithelium during the early development of the zebrafish embryo. In zebrafish epiboly the enveloping cell layer (EVL), a simple squamous epithelium, spreads over the yolk cell to completely engulf it at the end of gastrulation. Previous studies have proposed that an actomyosin ring forming within the yolk syncytial layer (YSL) acts as purse string that through constriction along its circumference pulls on the margin of the EVL. Direct biophysical evidence for this hypothesis has however been missing. The aim of the thesis was to understand how the actomyosin ring may generate pulling forces onto the EVL and what cellular mechanism(s) may facilitate the spreading of the epithelium. Using laser ablation to measure cortical tension within the actomyosin ring we found an anisotropic tension distribution, which was highest along the circumference of the ring. However the low degree of anisotropy was incompatible with the actomyosin ring functioning as a purse string only. Additionally, we observed retrograde cortical flow from vegetal parts of the ring into the EVL margin. Interpreting the experimental data using a theoretical distribution that models the tissues as active viscous gels led us to proposen that the actomyosin ring has a twofold contribution to EVL epiboly. It not only acts as a purse string through constriction along its circumference, but in addition constriction along the width of the ring generates pulling forces through friction-resisted cortical flow. Moreover, when rendering the purse string mechanism unproductive EVL epiboly proceeded normally indicating that the flow-friction mechanism is sufficient to drive the process. Aiming to understand what cellular mechanism(s) may facilitate the spreading of the epithelium we found that tension-oriented EVL cell divisions limit tissue anisotropy by releasing tension along the division axis and promote epithelial spreading. Notably, EVL cells undergo ectopic cell fusion in conditions in which oriented-cell division is impaired or the epithelium is mechanically challenged. Taken together our study of EVL epiboly suggests a novel mechanism of force generation for actomyosin rings through friction-resisted cortical flow and highlights the importance of tension-oriented cell divisions in epithelial morphogenesis.}, author = {Behrndt, Martin}, pages = {91}, publisher = {IST Austria}, title = {{Forces driving epithelial spreading in zebrafish epiboly}}, year = {2014}, } @inbook{1888, abstract = {Im Rahmen meiner Arbeit mit der kollektiven Krankheitsabwehr in Ameisengesellschaften interessiert mich vor allem, wie sich die Kolonien als Ganzes gegen Krankheiten wehren können. Warum ist dieses Thema der Krankheitsdynamik in Gruppen so wichtig? Ein Vergleich von solitär lebenden Individuen mit Individuen, die in sozialen Gruppen zusammenleben, zeigt die Kosten und die Vorteile des Gruppenlebens: Einerseits haben Individuen in sozialen Gruppen aufgrund der hohen Dichte, in der die Tiere zusammenleben, den hohen Interaktionsraten, die sie miteinander haben, und der engen Verwandtschaft, die sie verbindet, ein höheres Ansteckungsrisiko. Andererseits kann die individuelle Krankheitsabwehr durch die kollektive Abwehr in den Gruppen ergänzt werden.}, author = {Cremer, Sylvia}, booktitle = {Soziale Insekten in einer sich wandelnden Welt}, issn = {2366-2875}, pages = {65 -- 72}, publisher = {Verlag Dr. Friedrich Pfeil}, title = {{Soziale Immunität: Wie sich der Staat gegen Pathogene wehrt Bayerische Akademie der Wissenschaften}}, volume = {43}, year = {2014}, } @unpublished{2012, abstract = {The classical sphere packing problem asks for the best (infinite) arrangement of non-overlapping unit balls which cover as much space as possible. We define a generalized version of the problem, where we allow each ball a limited amount of overlap with other balls. We study two natural choices of overlap measures and obtain the optimal lattice packings in a parameterized family of lattices which contains the FCC, BCC, and integer lattice.}, author = {Iglesias Ham, Mabel and Kerber, Michael and Uhler, Caroline}, booktitle = {arXiv}, title = {{Sphere packing with limited overlap}}, doi = {10.48550/arXiv.1401.0468}, year = {2014}, } @article{14301, abstract = {DNA has become a prime material for assembling complex three-dimensional objects that promise utility in various areas of application. However, achieving user-defined goals with DNA objects has been hampered by the difficulty to prepare them at arbitrary concentrations and in user-defined solution conditions. Here, we describe a method that solves this problem. The method is based on poly(ethylene glycol)-induced depletion of species with high molecular weight. We demonstrate that our method is applicable to a wide spectrum of DNA shapes and that it achieves excellent recovery yields of target objects up to 97 %, while providing efficient separation from non-integrated DNA strands. DNA objects may be prepared at concentrations up to the limit of solubility, including the possibility for bringing DNA objects into a solid phase. Due to the fidelity and simplicity of our method we anticipate that it will help to catalyze the development of new types of applications that use self-assembled DNA objects.}, author = {Stahl, Evi and Martin, Thomas and Praetorius, Florian M and Dietz, Hendrik}, issn = {1521-3773}, journal = {Angewandte Chemie International Edition}, number = {47}, pages = {12949--12954}, publisher = {Wiley}, title = {{Facile and scalable preparation of pure and dense DNA origami solutions}}, doi = {10.1002/ange.201405991}, volume = {126}, year = {2014}, } @article{7699, author = {Sweeney, Lora Beatrice Jaeger and Kelley, Darcy B}, issn = {0959-4388}, journal = {Current Opinion in Neurobiology}, number = {10}, pages = {34--41}, publisher = {Elsevier}, title = {{Harnessing vocal patterns for social communication}}, doi = {10.1016/j.conb.2014.06.006}, volume = {28}, year = {2014}, } @article{2281, abstract = {We consider two-dimensional Bose-Einstein condensates with attractive interaction, described by the Gross-Pitaevskii functional. Minimizers of this functional exist only if the interaction strength a satisfies {Mathematical expression}, where Q is the unique positive radial solution of {Mathematical expression} in {Mathematical expression}. We present a detailed analysis of the behavior of minimizers as a approaches a*, where all the mass concentrates at a global minimum of the trapping potential.}, author = {Guo, Yujin and Seiringer, Robert}, journal = {Letters in Mathematical Physics}, number = {2}, pages = {141 -- 156}, publisher = {Springer}, title = {{On the mass concentration for Bose-Einstein condensates with attractive interactions}}, doi = {10.1007/s11005-013-0667-9}, volume = {104}, year = {2014}, } @article{2257, abstract = {Maximum entropy models are the least structured probability distributions that exactly reproduce a chosen set of statistics measured in an interacting network. Here we use this principle to construct probabilistic models which describe the correlated spiking activity of populations of up to 120 neurons in the salamander retina as it responds to natural movies. Already in groups as small as 10 neurons, interactions between spikes can no longer be regarded as small perturbations in an otherwise independent system; for 40 or more neurons pairwise interactions need to be supplemented by a global interaction that controls the distribution of synchrony in the population. Here we show that such “K-pairwise” models—being systematic extensions of the previously used pairwise Ising models—provide an excellent account of the data. We explore the properties of the neural vocabulary by: 1) estimating its entropy, which constrains the population's capacity to represent visual information; 2) classifying activity patterns into a small set of metastable collective modes; 3) showing that the neural codeword ensembles are extremely inhomogenous; 4) demonstrating that the state of individual neurons is highly predictable from the rest of the population, allowing the capacity for error correction.}, author = {Tkacik, Gasper and Marre, Olivier and Amodei, Dario and Schneidman, Elad and Bialek, William and Berry, Michael}, issn = {1553734X}, journal = {PLoS Computational Biology}, number = {1}, publisher = {Public Library of Science}, title = {{Searching for collective behavior in a large network of sensory neurons}}, doi = {10.1371/journal.pcbi.1003408}, volume = {10}, year = {2014}, } @article{15161, abstract = {The copper-catalyzed diboration of ketones followed by an acid-catalyzed elimination leads to the formation of 1,1-disubstituted and trisubstituted vinyl boronate esters with moderate to good yields and selectivity. Addition of tosic acid to the crude diboration products provides the corresponding vinyl boronate esters upon elimination. The trisubstituted vinyl boronate esters are formed as the (Z)-olefin isomer, which was established by subjecting the products to a Suzuki–Miyaura coupling reaction to obtain alkenes of known geometry.}, author = {Guan, Weiye and Michael, Alicia Kathleen and McIntosh, Melissa L. and Koren-Selfridge, Liza and Scott, John P. and Clark, Timothy B.}, issn = {1520-6904}, journal = {The Journal of Organic Chemistry}, keywords = {Organic Chemistry}, number = {15}, pages = {7199--7204}, publisher = {American Chemical Society}, title = {{Stereoselective formation of trisubstituted vinyl boronate esters by the acid-mediated elimination of α-hydroxyboronate esters}}, doi = {10.1021/jo500773t}, volume = {79}, year = {2014}, } @article{1999, abstract = {Selection for disease control is believed to have contributed to shape the organisation of insect societies — leading to interaction patterns that mitigate disease transmission risk within colonies, conferring them ‘organisational immunity’. Recent studies combining epidemiological models with social network analysis have identified general properties of interaction networks that may hinder propagation of infection within groups. These can be prophylactic and/or induced upon pathogen exposure. Here we review empirical evidence for these two types of organisational immunity in social insects and describe the individual-level behaviours that underlie it. We highlight areas requiring further investigation, and emphasise the need for tighter links between theory and empirical research and between individual-level and collective-level analyses.}, author = {Stroeymeyt, Nathalie and Casillas Perez, Barbara E and Cremer, Sylvia}, journal = {Current Opinion in Insect Science}, number = {1}, pages = {1 -- 15}, publisher = {Elsevier}, title = {{Organisational immunity in social insects}}, doi = {10.1016/j.cois.2014.09.001}, volume = {5}, year = {2014}, } @article{10384, abstract = {Recent studies aimed at investigating artificial analogs of bacterial colonies have shown that low-density suspensions of self-propelled particles confined in two dimensions can assemble into finite aggregates that merge and split, but have a typical size that remains constant (living clusters). In this Letter, we address the problem of the formation of living clusters and crystals of active particles in three dimensions. We study two systems: self-propelled particles interacting via a generic attractive potential and colloids that can move toward each other as a result of active agents (e.g., by molecular motors). In both cases, fluidlike “living” clusters form. We explain this general feature in terms of the balance between active forces and regression to thermodynamic equilibrium. This balance can be quantified in terms of a dimensionless number that allows us to collapse the observed clustering behavior onto a universal curve. We also discuss how active motion affects the kinetics of crystal formation.}, author = {Mognetti, B. M. and Šarić, Anđela and Angioletti-Uberti, S. and Cacciuto, A. and Valeriani, C. and Frenkel, D.}, issn = {1079-7114}, journal = {Physical Review Letters}, keywords = {general physics and astronomy}, number = {24}, publisher = {American Physical Society}, title = {{Living clusters and crystals from low-density suspensions of active colloids}}, doi = {10.1103/physrevlett.111.245702}, volume = {111}, year = {2013}, } @article{10386, abstract = {In this paper we review recent numerical and theoretical developments of particle self-assembly on fluid and elastic membranes and compare them to available experimental realizations. We discuss the problem and its applications in biology and materials science, and give an overview of numerical models and strategies to study these systems across all length-scales. As this is a very broad field, this review focuses exclusively on surface-driven aggregation of nanoparticles that are at least one order of magnitude larger than the surface thickness and are adsorbed onto it. In this regime, all chemical details of the surface can be ignored in favor of a coarse-grained representation, and the collective behavior of many particles can be monitored and analyzed. We review the existing literature on how the mechanical properties and the geometry of the surface affect the structure of the particle aggregates and how these can drive shape deformation on the surface.}, author = {Šarić, Anđela and Cacciuto, Angelo}, issn = {1744-6848}, journal = {Soft Matter}, keywords = {condensed matter physics, general chemistry}, number = {29}, publisher = {Royal Society of Chemistry}, title = {{Self-assembly of nanoparticles adsorbed on fluid and elastic membranes}}, doi = {10.1039/c3sm50188d}, volume = {9}, year = {2013}, } @article{10385, abstract = {We show how self-assembly of sticky nanoparticles can drive radial collapse of thin-walled nanotubes. Using numerical simulations, we study the transition as a function of the geometric and elastic parameters of the nanotube and the binding strength of the nanoparticles. We find that it is possible to derive a simple scaling law relating all these parameters, and estimate bounds for the onset conditions leading to the collapse of the nanotube. We also study the reverse process – the nanoparticle release from the folded state – and find that the stability of the collapsed state can be greatly improved by increasing the bending rigidity of the nanotubes. Our results suggest ways to strengthen the mechanical properties of nanotubes, but also indicate that the control of nanoparticle self-assembly on these nanotubes can lead to nanoparticle-laden responsive materials.}, author = {Napoli, Joseph A. and Šarić, Anđela and Cacciuto, Angelo}, issn = {1744-6848}, journal = {Soft Matter}, keywords = {condensed matter physics, general chemistry}, number = {37}, pages = {8881--8886}, publisher = {Royal Society of Chemistry}, title = {{Collapsing nanoparticle-laden nanotubes}}, doi = {10.1039/c3sm51495a}, volume = {9}, year = {2013}, } @article{10396, abstract = {Stimfit is a free cross-platform software package for viewing and analyzing electrophysiological data. It supports most standard file types for cellular neurophysiology and other biomedical formats. Its analysis algorithms have been used and validated in several experimental laboratories. Its embedded Python scripting interface makes Stimfit highly extensible and customizable.}, author = {Schlögl, Alois and Jonas, Peter M and Schmidt-Hieber, C. and Guzman, S. J.}, issn = {1862-278X}, journal = {Biomedical Engineering / Biomedizinische Technik}, keywords = {biomedical engineering, data analysis, free software}, location = {Graz, Austria}, number = {SI-1-Track-G}, publisher = {De Gruyter}, title = {{Stimfit: A fast visualization and analysis environment for cellular neurophysiology}}, doi = {10.1515/bmt-2013-4181}, volume = {58}, year = {2013}, } @inproceedings{10749, abstract = {Fluxoid quantization provides a direct means to study phase coherence. In cuprate superconductors, there have been observations which suggest that phase coherent superconducting fluctuations may persist at temperatures significantly above Tc. The focus of this work is to study the vortex states in mesoscopic cuprate superconducting samples to directly probe phase coherence over a wide range of temperatures. We present cantilever torque susceptometry measurements of micron and sub-micron size Bi2212 rings and disks. The high sensitivity of this technique allowed observation of transitions between different fluxoid states of a single ring, and the discrete vortex states of micron size disks. The dependence of magnetic susceptibility on diameter and wall thickness of the ring was investigated. Measurements were made at different values of the in-plane magnetic field, and over a wide range of temperatures.}, author = {Polshyn, Hryhoriy and Budakian, Raffi and Gu, Genda}, booktitle = {APS March Meeting 2013}, issn = {0003-0503}, location = {Baltimore, MD, United States}, number = {1}, publisher = {American Physical Society}, title = {{Cantilever micro-susceptometry of mesoscopic Bi2212 samples}}, volume = {58}, year = {2013}, } @article{10895, abstract = {Due to their sessile lifestyles, plants need to deal with the limitations and stresses imposed by the changing environment. Plants cope with these by a remarkable developmental flexibility, which is embedded in their strategy to survive. Plants can adjust their size, shape and number of organs, bend according to gravity and light, and regenerate tissues that were damaged, utilizing a coordinating, intercellular signal, the plant hormone, auxin. Another versatile signal is the cation, Ca2+, which is a crucial second messenger for many rapid cellular processes during responses to a wide range of endogenous and environmental signals, such as hormones, light, drought stress and others. Auxin is a good candidate for one of these Ca2+-activating signals. However, the role of auxin-induced Ca2+ signaling is poorly understood. Here, we will provide an overview of possible developmental and physiological roles, as well as mechanisms underlying the interconnection of Ca2+ and auxin signaling. }, author = {Vanneste, Steffen and Friml, Jiří}, issn = {2223-7747}, journal = {Plants}, keywords = {Plant Science, Ecology, Ecology, Evolution, Behavior and Systematics}, number = {4}, pages = {650--675}, publisher = {MDPI}, title = {{Calcium: The missing link in auxin action}}, doi = {10.3390/plants2040650}, volume = {2}, year = {2013}, } @inproceedings{10898, abstract = {A prominent remedy to multicore scalability issues in concurrent data structure implementations is to relax the sequential specification of the data structure. We present distributed queues (DQ), a new family of relaxed concurrent queue implementations. DQs implement relaxed queues with linearizable emptiness check and either configurable or bounded out-of-order behavior or pool behavior. Our experiments show that DQs outperform and outscale in micro- and macrobenchmarks all strict and relaxed queue as well as pool implementations that we considered.}, author = {Haas, Andreas and Lippautz, Michael and Henzinger, Thomas A and Payer, Hannes and Sokolova, Ana and Kirsch, Christoph M. and Sezgin, Ali}, booktitle = {Proceedings of the ACM International Conference on Computing Frontiers - CF '13}, isbn = {978-145032053-5}, location = {Ischia, Italy}, number = {5}, publisher = {ACM Press}, title = {{Distributed queues in shared memory: Multicore performance and scalability through quantitative relaxation}}, doi = {10.1145/2482767.2482789}, year = {2013}, } @inbook{10899, author = {Barton, Nicholas H}, booktitle = {Encyclopedia of Biodiversity}, isbn = {978-0-12-384720-1}, keywords = {Adaptive landscape, Cline, Coalescent process, Gene flow, Hybrid zone, Local adaptation, Natural selection, Neutral theory, Population structure, Speciation}, pages = {508--515}, publisher = {Elsevier}, title = {{Differentiation}}, doi = {10.1016/b978-0-12-384719-5.00031-9}, year = {2013}, } @article{11086, abstract = {Faithful execution of developmental gene expression programs occurs at multiple levels and involves many different components such as transcription factors, histone-modification enzymes, and mRNA processing proteins. Recent evidence suggests that nucleoporins, well known components that control nucleo-cytoplasmic trafficking, have wide-ranging functions in developmental gene regulation that potentially extend beyond their role in nuclear transport. Whether the unexpected role of nuclear pore proteins in transcription regulation, which initially has been described in fungi and flies, also applies to human cells is unknown. Here we show at a genome-wide level that the nuclear pore protein NUP98 associates with developmentally regulated genes active during human embryonic stem cell differentiation. Overexpression of a dominant negative fragment of NUP98 levels decreases expression levels of NUP98-bound genes. In addition, we identify two modes of developmental gene regulation by NUP98 that are differentiated by the spatial localization of NUP98 target genes. Genes in the initial stage of developmental induction can associate with NUP98 that is embedded in the nuclear pores at the nuclear periphery. Alternatively, genes that are highly induced can interact with NUP98 in the nuclear interior, away from the nuclear pores. This work demonstrates for the first time that NUP98 dynamically associates with the human genome during differentiation, revealing a role of a nuclear pore protein in regulating developmental gene expression programs.}, author = {Liang, Yun and Franks, Tobias M. and Marchetto, Maria C. and Gage, Fred H. and HETZER, Martin W}, issn = {1553-7404}, journal = {PLoS Genetics}, keywords = {Cancer Research, Genetics (clinical), Genetics, Molecular Biology, Ecology, Evolution, Behavior and Systematics}, number = {2}, publisher = {Public Library of Science}, title = {{Dynamic association of NUP98 with the human genome}}, doi = {10.1371/journal.pgen.1003308}, volume = {9}, year = {2013}, } @article{11087, abstract = {Intracellular proteins with long lifespans have recently been linked to age-dependent defects, ranging from decreased fertility to the functional decline of neurons. Why long-lived proteins exist in metabolically active cellular environments and how they are maintained over time remains poorly understood. Here, we provide a system-wide identification of proteins with exceptional lifespans in the rat brain. These proteins are inefficiently replenished despite being translated robustly throughout adulthood. Using nucleoporins as a paradigm for long-term protein persistence, we found that nuclear pore complexes (NPCs) are maintained over a cell’s life through slow but finite exchange of even its most stable subcomplexes. This maintenance is limited, however, as some nucleoporin levels decrease during aging, providing a rationale for the previously observed age-dependent deterioration of NPC function. Our identification of a long-lived proteome reveals cellular components that are at increased risk for damage accumulation, linking long-term protein persistence to the cellular aging process.}, author = {Toyama, Brandon H. and Savas, Jeffrey N. and Park, Sung Kyu and Harris, Michael S. and Ingolia, Nicholas T. and Yates, John R. and HETZER, Martin W}, issn = {0092-8674}, journal = {Cell}, keywords = {General Biochemistry, Genetics and Molecular Biology}, number = {5}, pages = {971--982}, publisher = {Elsevier}, title = {{Identification of long-lived proteins reveals exceptional stability of essential cellular structures}}, doi = {10.1016/j.cell.2013.07.037}, volume = {154}, year = {2013}, } @article{11085, abstract = {During mitotic exit, missegregated chromosomes can recruit their own nuclear envelope (NE) to form micronuclei (MN). MN have reduced functioning compared to primary nuclei in the same cell, although the two compartments appear to be structurally comparable. Here we show that over 60% of MN undergo an irreversible loss of compartmentalization during interphase due to NE collapse. This disruption of the MN, which is induced by defects in nuclear lamina assembly, drastically reduces nuclear functions and can trigger massive DNA damage. MN disruption is associated with chromatin compaction and invasion of endoplasmic reticulum (ER) tubules into the chromatin. We identified disrupted MN in both major subtypes of human non-small-cell lung cancer, suggesting that disrupted MN could be a useful objective biomarker for genomic instability in solid tumors. Our study shows that NE collapse is a key event underlying MN dysfunction and establishes a link between aberrant NE organization and aneuploidy.}, author = {Hatch, Emily M. and Fischer, Andrew H. and Deerinck, Thomas J. and HETZER, Martin W}, issn = {0092-8674}, journal = {Cell}, keywords = {General Biochemistry, Genetics and Molecular Biology}, number = {1}, pages = {47--60}, publisher = {Elsevier}, title = {{Catastrophic nuclear envelope collapse in cancer cell micronuclei}}, doi = {10.1016/j.cell.2013.06.007}, volume = {154}, year = {2013}, } @article{11088, abstract = {The crowded intracellular environment poses a formidable challenge to experimental and theoretical analyses of intracellular transport mechanisms. Our measurements of single-particle trajectories in cytoplasm and their random-walk interpretations elucidate two of these mechanisms: molecular diffusion in crowded environments and cytoskeletal transport along microtubules. We employed acousto-optic deflector microscopy to map out the three-dimensional trajectories of microspheres migrating in the cytosolic fraction of a cellular extract. Classical Brownian motion (BM), continuous time random walk, and fractional BM were alternatively used to represent these trajectories. The comparison of the experimental and numerical data demonstrates that cytoskeletal transport along microtubules and diffusion in the cytosolic fraction exhibit anomalous (nonFickian) behavior and posses statistically distinct signatures. Among the three random-walk models used, continuous time random walk provides the best representation of diffusion, whereas microtubular transport is accurately modeled with fractional BM.}, author = {Regner, Benjamin M. and Vučinić, Dejan and Domnisoru, Cristina and Bartol, Thomas M. and HETZER, Martin W and Tartakovsky, Daniel M. and Sejnowski, Terrence J.}, issn = {0006-3495}, journal = {Biophysical Journal}, keywords = {Biophysics}, number = {8}, pages = {1652--1660}, publisher = {Elsevier}, title = {{Anomalous diffusion of single particles in cytoplasm}}, doi = {10.1016/j.bpj.2013.01.049}, volume = {104}, year = {2013}, } @article{11083, abstract = {Nuclear pore complex (NPC) proteins are known for their critical roles in regulating nucleocytoplasmic traffic of macromolecules across the nuclear envelope. However, recent findings suggest that some nucleoporins (Nups), including Nup98, have additional functions in developmental gene regulation. Nup98, which exhibits transcription-dependent mobility at the NPC but can also bind chromatin away from the nuclear envelope, is frequently involved in chromosomal translocations in a subset of patients suffering from acute myeloid leukemia (AML). A common paradigm suggests that Nup98 translocations cause aberrant transcription when they are recuited to aberrant genomic loci. Importantly, this model fails to account for the potential loss of wild type (WT) Nup98 function in the presence of Nup98 translocation mutants. Here we examine how the cell might regulate Nup98 nucleoplasmic protein levels to control transcription in healthy cells. In addition, we discuss the possibility that dominant negative Nup98 fusion proteins disrupt the transcriptional activity of WT Nup98 in the nucleoplasm to drive AML.}, author = {Franks, Tobias M. and HETZER, Martin W}, issn = {0962-8924}, journal = {Trends in Cell Biology}, keywords = {Cell Biology}, number = {3}, pages = {112--117}, publisher = {Elsevier}, title = {{The role of Nup98 in transcription regulation in healthy and diseased cells}}, doi = {10.1016/j.tcb.2012.10.013}, volume = {23}, year = {2013}, } @article{11084, abstract = {Protein turnover is an effective way of maintaining a functional proteome, as old and potentially damaged polypeptides are destroyed and replaced by newly synthesized copies. An increasing number of intracellular proteins, however, have been identified that evade this turnover process and instead are maintained over a cell's lifetime. This diverse group of long-lived proteins might be particularly prone to accumulation of damage and thus have a crucial role in the functional deterioration of key regulatory processes during ageing.}, author = {Toyama, Brandon H. and HETZER, Martin W}, issn = {1471-0072}, journal = {Nature Reviews Molecular Cell Biology}, keywords = {Cell Biology, Molecular Biology}, pages = {55--61}, publisher = {Springer Nature}, title = {{Protein homeostasis: Live long, won't prosper}}, doi = {10.1038/nrm3496}, volume = {14}, year = {2013}, } @article{115, abstract = {We present the design and performance characterization of a new experimental technique for measuring individual particle charges in large ensembles of macroscopic grains. The measurement principle is qualitatively similar to that used in determining the elementary charge by Millikan in that it follows individual particle trajectories. However, by taking advantage of new technology we are able to work with macroscopic grains and achieve several orders of magnitude better resolution in charge to mass ratios. By observing freely falling grains accelerated in a horizontal electric field with a co-falling, high-speed video camera, we dramatically increase particle tracking time and measurement precision. Keeping the granular medium under vacuum, we eliminate air drag, leaving the electrostatic force as the primary source of particle accelerations in the co-moving frame. Because the technique is based on direct imaging, we can distinguish between different particle types during the experiment, opening up the possibility of studying charge transfer processes between different particle species. For the ∼300 μm diameter grains reported here, we achieve an average acceleration resolution of ∼0.008 m/s2, a force resolution of ∼500 pN, and a median charge resolution ∼6× 104 elementary charges per grain (corresponding to surface charge densities ∼1 elementary charges per μm2). The primary source of error is indeterminacy in the grain mass, but with higher resolution cameras and better optics this can be further improved. The high degree of resolution and the ability to visually identify particles of different species or sizes with direct imaging make this a powerful new tool to characterize charging processes in granular media.}, author = {Waitukaitis, Scott R and Jaeger, Heinrich}, journal = {Review of Scientific Instruments}, number = {2}, publisher = {AIP}, title = {{In situ granular charge measurement by free-fall videography}}, doi = {10.1063/1.4789496}, volume = {84}, year = {2013}, } @article{11520, abstract = {We present the spatially resolved Hα dynamics of 16 star-forming galaxies at z ∼ 0.81 using the new KMOS multi-object integral field spectrograph on the ESO Very Large Telescope. These galaxies, selected using 1.18 μm narrowband imaging from the 10 deg2 CFHT-HiZELS survey of the SA 22 hr field, are found in a ∼4 Mpc overdensity of Hα emitters and likely reside in a group/intermediate environment, but not a cluster. We confirm and identify a rich group of star-forming galaxies at z = 0.813 ± 0.003, with 13 galaxies within 1000 km s−1 of each other, and seven within a diameter of 3 Mpc. All of our galaxies are “typical” star-forming galaxies at their redshift, 0.8 ± 0.4 SFR$^*_{z = 0.8}$, spanning a range of specific star formation rates (sSFRs) of 0.2–1.1 Gyr−1 and have a median metallicity very close to solar of 12 + log(O/H) = 8.62 ± 0.06. We measure the spatially resolved Hα dynamics of the galaxies in our sample and show that 13 out of 16 galaxies can be described by rotating disks and use the data to derive inclination corrected rotation speeds of 50–275 km s−1. The fraction of disks within our sample is 75% ± 8%, consistent with previous results based on Hubble Space Telescope morphologies of Hα-selected galaxies at z ∼ 1 and confirming that disks dominate the SFR density at z ∼ 1. Our Hα galaxies are well fitted by the z ∼ 1–2 Tully–Fisher (TF) relation, confirming the evolution seen in the zero point. Apart from having, on average, higher stellar masses and lower sSFRs, our group galaxies at z = 0.81 present the same mass–metallicity and TF relation as z ∼ 1 field galaxies and are all disk galaxies.}, author = {Sobral, D. and Swinbank, A. M. and Stott, J. P. and Matthee, Jorryt J and Bower, R. G. and Smail, Ian and Best, P. and Geach, J. E. and Sharples, R. M.}, issn = {1538-4357}, journal = {The Astrophysical Journal}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, galaxies: evolution – galaxies, high-redshift – galaxies, starburst}, number = {2}, publisher = {IOP Publishing}, title = {{The dynamics of z=0.8 H-alpha-selected star-forming galaxies from KMOS/CF-HiZELS}}, doi = {10.1088/0004-637x/779/2/139}, volume = {779}, year = {2013}, } @article{116, abstract = {We describe a model experiment for dynamic jamming: a two-dimensional collection of initially unjammed disks that are forced into the jammed state by uniaxial compression via a rake. This leads to a stable densification front that travels ahead of the rake, leaving regions behind it jammed. Using disk conservation in conjunction with an upper limit to the packing fraction at jamming onset, we predict the front speed as a function of packing fraction and rake speed. However, we find that the jamming front has a finite width, a feature that cannot be explained by disk conservation alone. This width appears to diverge on approach to jamming, which suggests that it may be related to growing lengthscales encountered in other jamming studies.}, author = {Waitukaitis, Scott R and Roth, Leah and Vitelli, Vincenzo and Jaeger, Heinrich}, journal = {EPL}, number = {4}, publisher = {Elsevier}, title = {{Dynamic jamming fronts}}, doi = {10.1209/0295-5075/102/44001}, volume = {102}, year = {2013}, } @article{11671, abstract = {Given only the URL of a Web page, can we identify its language? In this article we examine this question. URL-based language classification is useful when the content of the Web page is not available or downloading the content is a waste of bandwidth and time. We built URL-based language classifiers for English, German, French, Spanish, and Italian by applying a variety of algorithms and features. As algorithms we used machine learning algorithms which are widely applied for text classification and state-of-art algorithms for language identification of text. As features we used words, various sized n-grams, and custom-made features (our novel feature set). We compared our approaches with two baseline methods, namely classification by country code top-level domains and classification by IP addresses of the hosting Web servers. We trained and tested our classifiers in a 10-fold cross-validation setup on a dataset obtained from the Open Directory Project and from querying a commercial search engine. We obtained the lowest F1-measure for English (94) and the highest F1-measure for German (98) with the best performing classifiers. We also evaluated the performance of our methods: (i) on a set of Web pages written in Adobe Flash and (ii) as part of a language-focused crawler. In the first case, the content of the Web page is hard to extract and in the second page downloading pages of the “wrong” language constitutes a waste of bandwidth. In both settings the best classifiers have a high accuracy with an F1-measure between 95 (for English) and 98 (for Italian) for the Adobe Flash pages and a precision between 90 (for Italian) and 97 (for French) for the language-focused crawler.}, author = {Baykan, Eda and Weber, Ingmar and Henzinger, Monika H}, issn = {1559-114X}, journal = {ACM Transactions on the Web}, keywords = {Computer Networks and Communications}, number = {1}, publisher = {Association for Computing Machinery}, title = {{A comprehensive study of techniques for URL-based web page language classification}}, doi = {10.1145/2435215.2435218}, volume = {7}, year = {2013}, } @inproceedings{117, abstract = {The packing arrangement of individual particles inside a granular material and the resulting response to applied stresses depend critically on particle-particle interactions. One aspect that recently received attention are nanoscale surface features of particles, which play an important role in determining the strength of cohesive van der Waals and capillary interactions and also affect tribo-charging of grains. We describe experiments on freely falling granular streams that can detect the contributions from all three of these forces. We show that it is possible to measure the charge of individual grains and build up distributions that are detailed enough to provide stringent tests of tribo-charging models currently available. A second aspect concerns particle shape. In this case steric interactions become important and new types of aggregate behavior can be expected when non-convex particle shapes are considered that can interlock or entangle. However, a general connection between the mechanical response of a granular material and the constituents\' shape remains unknown. This has made it infeasible to tackle the "inverse packing problem", namely to start from a given, desired behavior for the aggregate as a whole and then find the particle shape the produces it. We discuss a new approach, using concepts rooted in artificial evolution that provides a way to solve this inverse problem. This approach facilitates exploring the role of arbitrary particle geometry in jammed systems and invites the discovery and design of granular matter with optimized properties.}, author = {Jaeger, Heinrich and Miskin, Marc and Waitukaitis, Scott R}, booktitle = { AIP Conference Proceedings}, location = {Sydney, Australia}, pages = {3 -- 6}, publisher = {AIP}, title = {{From nanoscale cohesion to macroscale entanglement: opportunities for designing granular aggregate behaviour by tailoring grain shape and interactions}}, doi = {10.1063/1.4811858}, volume = {1542}, year = {2013}, } @article{11759, abstract = {Matching markets play a prominent role in economic theory. A prime example of such a market is the sponsored search market. Here, as in other markets of that kind, market equilibria correspond to feasible, envy free, and bidder optimal outcomes. For settings without budgets such an outcome always exists and can be computed in polynomial-time by the so-called Hungarian Method. Moreover, every mechanism that computes such an outcome is incentive compatible. We show that the Hungarian Method can be modified so that it finds a feasible, envy free, and bidder optimal outcome for settings with budgets. We also show that in settings with budgets no mechanism that computes such an outcome can be incentive compatible for all inputs. For inputs in general position, however, the presented mechanism—as any other mechanism that computes such an outcome for settings with budgets—is incentive compatible.}, author = {Dütting, Paul and Henzinger, Monika H and Weber, Ingmar}, issn = {0020-0190}, journal = {Information Processing Letters}, number = {3}, pages = {67--73}, publisher = {Elsevier}, title = {{Sponsored search, market equilibria, and the Hungarian Method}}, doi = {10.1016/j.ipl.2012.11.006}, volume = {113}, year = {2013}, } @inproceedings{11793, abstract = {We study the problem of maintaining a breadth-first spanning tree (BFS tree) in partially dynamic distributed networks modeling a sequence of either failures or additions of communication links (but not both). We show (1 + ε)-approximation algorithms whose amortized time (over some number of link changes) is sublinear in D, the maximum diameter of the network. This breaks the Θ(D) time bound of recomputing “from scratch”. Our technique also leads to a (1 + ε)-approximate incremental algorithm for single-source shortest paths (SSSP) in the sequential (usual RAM) model. Prior to our work, the state of the art was the classic exact algorithm of [9] that is optimal under some assumptions [27]. Our result is the first to show that, in the incremental setting, this bound can be beaten in certain cases if a small approximation is allowed.}, author = {Henzinger, Monika H and Krinninger, Sebastian and Nanongkai, Danupon}, booktitle = {40th International Colloquium on Automata, Languages, and Programming}, isbn = {9783642392115}, issn = {1611-3349}, location = {Riga, Latvia}, pages = {607–619}, publisher = {Springer Nature}, title = {{Sublinear-time maintenance of breadth-first spanning tree in partially dynamic networks}}, doi = {10.1007/978-3-642-39212-2_53}, volume = {7966}, year = {2013}, } @inproceedings{11791, abstract = {The focus of classic mechanism design has been on truthful direct-revelation mechanisms. In the context of combinatorial auctions the truthful direct-revelation mechanism that maximizes social welfare is the VCG mechanism. For many valuation spaces computing the allocation and payments of the VCG mechanism, however, is a computationally hard problem. We thus study the performance of the VCG mechanism when bidders are forced to choose bids from a subspace of the valuation space for which the VCG outcome can be computed efficiently. We prove improved upper bounds on the welfare loss for restrictions to additive bids and upper and lower bounds for restrictions to non-additive bids. These bounds show that the welfare loss increases in expressiveness. All our bounds apply to equilibrium concepts that can be computed in polynomial time as well as to learning outcomes.}, author = {Dütting, Paul and Henzinger, Monika H and Starnberger, Martin}, booktitle = {9th International Conference on Web and Internet Economics}, isbn = {9783642450457}, issn = {1611-3349}, location = {Cambridge, MA, USA}, pages = {146–159}, publisher = {Springer Nature}, title = {{Valuation compressions in VCG-based combinatorial auctions}}, doi = {10.1007/978-3-642-45046-4_13}, volume = {8289}, year = {2013}, } @inproceedings{11792, abstract = {We study the problem of maximizing a monotone submodular function with viability constraints. This problem originates from computational biology, where we are given a phylogenetic tree over a set of species and a directed graph, the so-called food web, encoding viability constraints between these species. These food webs usually have constant depth. The goal is to select a subset of k species that satisfies the viability constraints and has maximal phylogenetic diversity. As this problem is known to be NP-hard, we investigate approximation algorithm. We present the first constant factor approximation algorithm if the depth is constant. Its approximation ratio is (1−1𝑒√). This algorithm not only applies to phylogenetic trees with viability constraints but for arbitrary monotone submodular set functions with viability constraints. Second, we show that there is no (1 − 1/e + ε)-approximation algorithm for our problem setting (even for additive functions) and that there is no approximation algorithm for a slight extension of this setting.}, author = {Dvořák, Wolfgang and Henzinger, Monika H and Williamson, David P.}, booktitle = {21st Annual European Symposium on Algorithms}, isbn = {9783642404498}, issn = {1611-3349}, location = {Sophia Antipolis, France}, pages = {409 -- 420}, publisher = {Springer Nature}, title = {{Maximizing a submodular function with viability constraints}}, doi = {10.1007/978-3-642-40450-4_35}, volume = {8125}, year = {2013}, } @inproceedings{11856, abstract = {We study dynamic (1 + ϵ)-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected n-node m-edge graphs under edge deletions. The fastest algorithm for this problem is a randomized algorithm with a total update time of Ȏ(mn) and constant query time by Roditty and Zwick (FOCS 2004). The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach (JACM 1981); it has a total update time of O(mn 2 ) and constant query time. We improve these results as follows: (1) We present an algorithm with a total update time of Ȏ(n 5/2 ) and constant query time that has an additive error of two in addition to the 1 + ϵ multiplicative error. This beats the previous Ȏ(mn) time when m = Ω(n 3/2 ). Note that the additive error is unavoidable since, even in the static case, an O(n 3-δ )-time (a so-called truly sub cubic) combinatorial algorithm with 1 + ϵ multiplicative error cannot have an additive error less than 2 - ϵ, unless we make a major breakthrough for Boolean matrix multiplication (Dor, Halperin and Zwick FOCS 1996) and many other long-standing problems (Vassilevska Williams and Williams FOCS 2010). The algorithm can also be turned into a (2 + ϵ)-approximation algorithm (without an additive error) with the same time guarantees, improving the recent (3 + ϵ)-approximation algorithm with Ȏ(n 5/2+O(1√(log n)) ) running time of Bernstein and Roditty (SODA 2011) in terms of both approximation and time guarantees. (2) We present a deterministic algorithm with a total update time of Ȏ(mn) and a query time of O(log log n). The algorithm has a multiplicative error of 1 + ϵ and gives the first improved deterministic algorithm since 1981. It also answers an open question raised by Bernstein in his STOC 2013 paper. In order to achieve our results, we introduce two new techniques: (1) A lazy Even-Shiloach tree algorithm which maintains a bounded-distance shortest-paths tree on a certain type of emulator called locally persevering emulator. (2) A derandomization technique based on moving Even-Shiloach trees as a way to derandomize the standard random set argument. These techniques might be of independent interest.}, author = {Henzinger, Monika H and Krinninger, Sebastian and Nanongkai, Danupon}, booktitle = {54th Annual Symposium on Foundations of Computer Science}, issn = {0272-5428}, location = {Berkeley, CA, United States}, pages = {538--547}, publisher = {Institute of Electrical and Electronics Engineers}, title = {{Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization}}, doi = {10.1109/focs.2013.64}, year = {2013}, } @article{11902, abstract = {We study the problem of matching bidders to items where each bidder i has general, strictly monotonic utility functions ui,j(pj) expressing his utility of being matched to item j at price pj. For this setting we prove that a bidder optimal outcome always exists, even when the utility functions are non-linear and non-continuous. We give sufficient conditions under which every mechanism that finds a bidder optimal outcome is incentive compatible. We also give a mechanism that finds a bidder optimal outcome if the conditions for incentive compatibility are satisfied. The running time of this mechanism is exponential in the number of items, but polynomial in the number of bidders.}, author = {Dütting, Paul and Henzinger, Monika H and Weber, Ingmar}, issn = {0304-3975}, journal = {Theoretical Computer Science}, number = {3}, pages = {22--32}, publisher = {Elsevier}, title = {{Bidder optimal assignments for general utilities}}, doi = {10.1016/j.tcs.2013.01.030}, volume = {478}, year = {2013}, }