@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}, } @article{11959, abstract = {No catalyst required! A highly efficient, catalyst-free process to generate diimide in situ from hydrazine monohydrate and molecular oxygen for the selective reduction of alkenes has been developed. The use of a gas–liquid segmented flow system allowed safe operating conditions and dramatically enhanced this atom-economical reaction, resulting in short processing times.}, author = {Pieber, Bartholomäus and Martinez, Sabrina Teixeira and Cantillo, David and Kappe, C. Oliver}, issn = {1521-3773}, journal = {Angewandte Chemie International Edition}, number = {39}, pages = {10241--10244}, publisher = {Wiley}, title = {{In situ generation of diimide from hydrazine and oxygen: Continuous-flow transfer hydrogenation of olefins}}, doi = {10.1002/anie.201303528}, volume = {52}, year = {2013}, } @article{11960, abstract = {It's not magic! The effects observed in microwave-irradiated chemical transformations can in most cases be rationalized by purely bulk thermal phenomena associated with rapid heating to elevated temperatures. As discussed in this Essay, the existence of so-called nonthermal or specific microwave effects is highly doubtful.}, author = {Kappe, C. Oliver and Pieber, Bartholomäus and Dallinger, Doris}, issn = {1521-3773}, journal = {Angewandte Chemie International Edition}, number = {4}, pages = {1088--1094}, publisher = {Wiley}, title = {{Microwave effects in organic synthesis: Myth or reality?}}, doi = {10.1002/anie.201204103}, volume = {52}, year = {2013}, } @article{11973, abstract = {The use of high-temperature/pressure gas–liquid continuous flow conditions dramatically enhances the iron-catalyzed aerobic oxidation of 2-benzylpyridines to their corresponding ketones. Pressurized air serves as a readily available oxygen source and propylene carbonate as a green solvent in this radically intensified preparation of synthetically valuable 2-aroylpyridines.}, author = {Pieber, Bartholomäus and Kappe, C. Oliver}, issn = {1463-9270}, journal = {Green Chemistry}, number = {2}, pages = {320--324}, publisher = {Royal Society of Chemistry}, title = {{Direct aerobic oxidation of 2-benzylpyridines in a gas-liquid continuous-flow regime using propylene carbonate as a solvent}}, doi = {10.1039/c2gc36896j}, volume = {15}, year = {2013}, } @article{12642, abstract = {Near-surface air temperature, typically measured at a height of 2 m, is the most important control on the energy exchange and the melt rate at a snow or ice surface. It is distributed in a simplistic manner in most glacier melt models by using constant linear lapse rates, which poorly represent the actual spatial and temporal variability of air temperature. In this paper, we test a simple thermodynamic model proposed by Greuell and Böhm in 1998 as an alternative, using a new dataset of air temperature measurements from along the flowline of Haut Glacier d’Arolla, Switzerland. The unmodified model performs little better than assuming a constant linear lapse rate. When modified to allow the ratio of the boundary layer height to the bulk heat transfer coefficient to vary along the flowline, the model matches measured air temperatures better, and a further reduction of the root-mean-square error is obtained, although there is still considerable scope for improvement. The modified model is shown to perform best under conditions favourable to the development of katabatic winds – few clouds, positive ambient air temperature, limited influence of synoptic or valley winds and a long fetch – but its performance is poor under cloudy conditions.}, author = {Petersen, Lene and Pellicciotti, Francesca and Juszak, Inge and Carenzo, Marco and Brock, Ben}, issn = {1727-5644}, journal = {Annals of Glaciology}, keywords = {Earth-Surface Processes}, number = {63}, pages = {120--130}, publisher = {International Glaciological Society}, title = {{Suitability of a constant air temperature lapse rate over an Alpine glacier: Testing the Greuell and Böhm model as an alternative}}, doi = {10.3189/2013aog63a477}, volume = {54}, year = {2013}, } @article{12643, abstract = {Parameterizations of incoming longwave radiation are increasingly receiving attention for both low and high elevation glacierized sites. In this paper, we test 13 clear-sky parameterizations combined with seven cloud corrections for all-sky atmospheric emissivity at one location on Haut Glacier d'Arolla. We also analyze the four seasons separately and conduct a cross-validation to test the parameters’ robustness. The best parameterization is the one by Dilley and O'Brien, B for clear-sky conditions combined with Unsworth and Monteith cloud correction. This model is also the most robust when tested in cross-validation. When validated at different sites in the southern Alps of Switzerland and north-western Italian Alps, all parameterizations show a substantial decrease in performance, except for one site, thus suggesting that it is important to recalibrate parameterizations of incoming longwave radiation for different locations. We argue that this is due to differences in the structure of the atmosphere at the sites. We also quantify the effect that the incoming longwave radiation parameterizations have on energy-balance melt modeling, and show that recalibration of model parameters is needed. Using parameters from other sites leads to a significant underestimation of melt and to an error that is larger than that associated with using different parameterizations. Once recalibrated, however, the parameters of most models seem to be stable over seasons and years at the location on Haut Glacier d'Arolla.}, author = {Juszak, I. and Pellicciotti, Francesca}, issn = {2169-897X}, journal = {Journal of Geophysical Research: Atmospheres}, keywords = {Space and Planetary Science, Earth and Planetary Sciences (miscellaneous), Atmospheric Science, Geophysics}, number = {8}, pages = {3066--3084}, publisher = {American Geophysical Union}, title = {{A comparison of parameterizations of incoming longwave radiation over melting glaciers: Model robustness and seasonal variability}}, doi = {10.1002/jgrd.50277}, volume = {118}, year = {2013}, } @article{12640, abstract = {Greater Himalayan glaciers are retreating and losing mass at rates comparable to glaciers in other regions of the world1,2,3,4,5. Assessments of future changes and their associated hydrological impacts are scarce, oversimplify glacier dynamics or include a limited number of climate models6,7,8,9. Here, we use results from the latest ensemble of climate models in combination with a high-resolution glacio-hydrological model to assess the hydrological impact of climate change on two climatically contrasting watersheds in the Greater Himalaya, the Baltoro and Langtang watersheds that drain into the Indus and Ganges rivers, respectively. We show that the largest uncertainty in future runoff is a result of variations in projected precipitation between climate models. In both watersheds, strong, but highly variable, increases in future runoff are projected and, despite the different characteristics of the watersheds, their responses are surprisingly similar. In both cases, glaciers will recede but net glacier melt runoff is on a rising limb at least until 2050. In combination with a positive change in precipitation, water availability during this century is not likely to decline. We conclude that river basins that depend on monsoon rains and glacier melt will continue to sustain the increasing water demands expected in these areas10.}, author = {Immerzeel, W. W. and Pellicciotti, Francesca and Bierkens, M. F. P.}, issn = {1752-0908}, journal = {Nature Geoscience}, keywords = {General Earth and Planetary Sciences}, number = {9}, pages = {742--745}, publisher = {Springer Nature}, title = {{Rising river flows throughout the twenty-first century in two Himalayan glacierized watersheds}}, doi = {10.1038/ngeo1896}, volume = {6}, year = {2013}, } @article{12641, abstract = {We investigate the sensitivity of a distributed enhanced temperature-index (ETI) melt model, in order to understand which parameters have the largest influence on model outputs and thus need to be accurately known. We use melt and meteorological data from two Alpine glaciers and one glacier in the Andes of Chile. Sensitivity analysis is conducted in a systematic way in terms of parameters and the different conditions (day, night, clear-sky, overcast), melt seasons and glaciers examined. The sensitivity of total melt to changes in individual parameters is calculated using a local method around the optimal value of the parameters. We verify that the parameters are optimal at the distributed scale and assess the model uncertainty induced by uncertainty in the parameters using a Monte Carlo technique. Model sensitivity to parameters is consistent across melt seasons, glaciers, different conditions and the daily statistics examined. The parameters to which the model is most sensitive are the shortwave-radiation factor, the temperature lapse rate for extrapolation of air temperature, the albedo parameters, the temperature threshold and the cloud transmittance factor parameters. A parameter uncertainty of 5% results in a model uncertainty of 5.6% of mean melt on Haut Glacier d’Arolla, Switzerland.}, author = {Heynen, Martin and Pellicciotti, Francesca and Carenzo, Marco}, issn = {1727-5644}, journal = {Annals of Glaciology}, number = {63}, pages = {311--321}, publisher = {International Glaciological Society}, title = {{Parameter sensitivity of a distributed enhanced temperature-index melt model}}, doi = {10.3189/2013aog63a537}, volume = {54}, year = {2013}, } @article{1304, abstract = {When confronted with a large-field stimulus rotating around the vertical body axis, flies display a following behavior called "optomotor response." As neural control elements, the large tangential horizontal system (HS) cells of the lobula plate have been prime candidates for long. Here, we applied optogenetic stimulation of HS cells to evaluate their behavioral role in Drosophila. To minimize interference of the optical activation of channelrhodopsin-2 with the visual perception of the flies, we used a bistable variant called ChR2-C128S. By applying pulses of blue and yellow light, we first demonstrate electrophysiologically that lobula plate tangential cells can be activated and deactivated repeatedly with no evident change in depolarization strength over trials. We next show that selective optogenetic activation of HS cells elicits robust yaw head movements and yaw turning responses in fixed and tethered flying flies, respectively.}, author = {Haikala, Väinö and Maximilian Jösch and Borst, Alexander and Mauss, Alex S}, journal = {Journal of Neuroscience}, number = {34}, pages = {13927 -- 13934}, publisher = {Society for Neuroscience}, title = {{Optogenetic control of fly optomotor responses}}, doi = {10.1523/JNEUROSCI.0340-13.2013}, volume = {33}, year = {2013}, } @article{1305, abstract = {In the fly Drosophila melanogaster, photoreceptor input to motion vision is split into two parallel pathways as represented by first-order interneurons L1 and L2 (Rister et al., 2007; Joesch et al., 2010). However, how these pathways are functionally specialized remains controversial. One study (Eichner et al., 2011) proposed that the L1-pathway evaluates only sequences of brightness increments (ON-ON), while the L2-pathway processes exclusively brightness decrements (OFF-OFF). Another study (Clark et al., 2011) proposed that each of the two pathways evaluates both ON-ON and OFF-OFF sequences. To decide between these alternatives, we recorded from motionsensitive neurons in flies in which the output from either L1 or L2 was genetically blocked. We found that blocking L1 abolishes ON-ON responses but leaves OFF-OFF responses intact. The opposite was true, when the output from L2 was blocked. We conclude that the L1 and L2 pathways are functionally specialized to detect ON-ON and OFF-OFF sequences, respectively.}, author = {Maximilian Jösch and Weber, Franz and Eichner, Hubert and Borst, Alexander}, journal = {Journal of Neuroscience}, number = {3}, pages = {902 -- 905}, publisher = {Society for Neuroscience}, title = {{Functional specialization of parallel motion detection circuits in the fly}}, doi = {10.1523/JNEUROSCI.3374-12.2013}, volume = {33}, year = {2013}, } @article{1308, abstract = {We derive sufficient conditions for advection-driven backward motion of the free boundary in a chemotaxis model with degenerate mobility. In this model, a porous-medium-type diffusive term and an advection term are in competition. The former induces forward motion, the latter may induce backward motion of the free boundary depending on the direction of advection. We deduce conditions on the growth of the initial data at the free boundary which ensure that at least initially the advection term is dominant. This implies local backward motion of the free boundary provided the advection is (locally) directed appropriately. Our result is based on a new class of moving test functions and Stampacchia's lemma. As a by-product of our estimates, we obtain quantitative bounds on the spreading of the support of solutions for the chemotaxis model and provide a proof for the finite speed of the support propagation property of solutions.}, author = {Julian Fischer}, journal = {SIAM Journal on Mathematical Analysis}, number = {3}, pages = {1585 -- 1615}, publisher = {Society for Industrial and Applied Mathematics }, title = {{Advection-driven support shrinking in a chemotaxis model with degenerate mobility}}, doi = {10.1137/120874291}, volume = {45}, year = {2013}, } @article{1307, abstract = {We prove uniqueness of solutions of the DLSS equation in a class of sufficiently regular functions. The global weak solutions of the DLSS equation constructed by Jüngel and Matthes belong to this class of uniqueness. We also show uniqueness of solutions for the quantum drift-diffusion equation, which contains additional drift and second-order diffusion terms. The results hold in case of periodic or Dirichlet-Neumann boundary conditions. Our proof is based on a monotonicity property of the DLSS operator and sophisticated approximation arguments; we derive a PDE satisfied by the pointwise square root of the solution, which enables us to exploit the monotonicity property of the operator.}, author = {Julian Fischer}, journal = {Communications in Partial Differential Equations}, number = {11}, pages = {2004 -- 2047}, publisher = {Taylor & Francis}, title = {{Uniqueness of solutions of the Derrida-Lebowitz-Speer-Spohn equation and quantum drift diffusion models}}, doi = {10.1080/03605302.2013.823548}, volume = {38}, year = {2013}, } @article{1310, abstract = {We derive lower bounds on asymptotic support propagation rates for strong solutions of the Cauchy problem for the thin-film equation. The bounds coincide up to a constant factor with the previously known upper bounds and thus are sharp. Our results hold in case of at most three spatial dimensions and n∈. (1, 2.92). The result is established using weighted backward entropy inequalities with singular weight functions to yield a differential inequality; combined with some entropy production estimates, the optimal rate of propagation is obtained. To the best of our knowledge, these are the first lower bounds on asymptotic support propagation rates for higher-order nonnegativity-preserving parabolic equations.}, author = {Julian Fischer}, journal = {Journal of Differential Equations}, number = {10}, pages = {3127 -- 3149}, publisher = {Academic Press}, title = {{Optimal lower bounds on asymptotic support propagation rates for the thin-film equation}}, doi = {10.1016/j.jde.2013.07.028}, volume = {255}, year = {2013}, } @inproceedings{1374, abstract = {We study two-player zero-sum games over infinite-state graphs equipped with ωB and finitary conditions. Our first contribution is about the strategy complexity, i.e the memory required for winning strategies: we prove that over general infinite-state graphs, memoryless strategies are sufficient for finitary Büchi, and finite-memory suffices for finitary parity games. We then study pushdown games with boundedness conditions, with two contributions. First we prove a collapse result for pushdown games with ωB-conditions, implying the decidability of solving these games. Second we consider pushdown games with finitary parity along with stack boundedness conditions, and show that solving these games is EXPTIME-complete.}, author = {Chatterjee, Krishnendu and Fijalkow, Nathanaël}, booktitle = {22nd EACSL Annual Conference on Computer Science Logic}, location = {Torino, Italy}, pages = {181 -- 196}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Infinite-state games with finitary conditions}}, doi = {10.4230/LIPIcs.CSL.2013.181}, volume = {23}, year = {2013}, } @inproceedings{1385, abstract = {It is often difficult to correctly implement a Boolean controller for a complex system, especially when concurrency is involved. Yet, it may be easy to formally specify a controller. For instance, for a pipelined processor it suffices to state that the visible behavior of the pipelined system should be identical to a non-pipelined reference system (Burch-Dill paradigm). We present a novel procedure to efficiently synthesize multiple Boolean control signals from a specification given as a quantified first-order formula (with a specific quantifier structure). Our approach uses uninterpreted functions to abstract details of the design. We construct an unsatisfiable SMT formula from the given specification. Then, from just one proof of unsatisfiability, we use a variant of Craig interpolation to compute multiple coordinated interpolants that implement the Boolean control signals. Our method avoids iterative learning and back-substitution of the control functions. We applied our approach to synthesize a controller for a simple two-stage pipelined processor, and present first experimental results.}, author = {Hofferek, Georg and Gupta, Ashutosh and Könighofer, Bettina and Jiang, Jie and Bloem, Roderick}, booktitle = {2013 Formal Methods in Computer-Aided Design}, location = {Portland, OR, United States}, pages = {77 -- 84}, publisher = {IEEE}, title = {{Synthesizing multiple boolean functions using interpolation on a single proof}}, doi = {10.1109/FMCAD.2013.6679394}, year = {2013}, } @inproceedings{1387, abstract = {Choices made by nondeterministic word automata depend on both the past (the prefix of the word read so far) and the future (the suffix yet to be read). In several applications, most notably synthesis, the future is diverse or unknown, leading to algorithms that are based on deterministic automata. Hoping to retain some of the advantages of nondeterministic automata, researchers have studied restricted classes of nondeterministic automata. Three such classes are nondeterministic automata that are good for trees (GFT; i.e., ones that can be expanded to tree automata accepting the derived tree languages, thus whose choices should satisfy diverse futures), good for games (GFG; i.e., ones whose choices depend only on the past), and determinizable by pruning (DBP; i.e., ones that embody equivalent deterministic automata). The theoretical properties and relative merits of the different classes are still open, having vagueness on whether they really differ from deterministic automata. In particular, while DBP ⊆ GFG ⊆ GFT, it is not known whether every GFT automaton is GFG and whether every GFG automaton is DBP. Also open is the possible succinctness of GFG and GFT automata compared to deterministic automata. We study these problems for ω-regular automata with all common acceptance conditions. We show that GFT=GFG⊃DBP, and describe a determinization construction for GFG automata.}, author = {Boker, Udi and Kuperberg, Denis and Kupferman, Orna and Skrzypczak, Michał}, location = {Riga, Latvia}, number = {PART 2}, pages = {89 -- 100}, publisher = {Springer}, title = {{Nondeterminism in the presence of a diverse or unknown future}}, doi = {10.1007/978-3-642-39212-2_11}, volume = {7966}, year = {2013}, } @article{1442, abstract = {We give a cohomological interpretation of both the Kac polynomial and the refined Donaldson-Thomas-invariants of quivers. This interpretation yields a proof of a conjecture of Kac from 1982 and gives a new perspective on recent work of Kontsevich-Soibelman. Thisis achieved by computing, via an arithmetic Fourier transform, the dimensions of the isotypical components of the cohomology of associated Nakajima quiver varieties under the action of a Weyl group. The generating function of the corresponding Poincare polynomials is an extension of Hua's formula for Kac polynomials of quivers involving Hall-Littlewood symmetric functions. The resulting formulae contain a wide range of information on the geometry of the quiver varieties.}, author = {Tamas Hausel and Letellier, Emmanuel and Rodríguez Villegas, Fernando}, journal = {Annals of Mathematics}, number = {3}, pages = {1147 -- 1168}, publisher = {Princeton University Press}, title = {{Positivity for Kac polynomials and DT-invariants of quivers}}, doi = {10.4007/annals.2013.177.3.8}, volume = {177}, year = {2013}, } @inbook{1443, abstract = {Here we survey several results and conjectures on the cohomology of the total space of the Hitchin system: the moduli space of semi-stable rank n and degree d Higgs bundles on a complex algebraic curve C. The picture emerging is a dynamic mixture of ideas originating in theoretical physics such as gauge theory and mirror symmetry, Weil conjectures in arithmetic algebraic geometry, representation theory of finite groups of Lie type and Langlands duality in number theory.}, author = {Tamas Hausel}, booktitle = {Handbook of Moduli: Volume II}, pages = {29 -- 70}, publisher = {International Press}, title = {{Global topology of the Hitchin system}}, volume = {25}, year = {2013}, } @article{1469, abstract = {We study connections between the topology of generic character varieties of fundamental groups of punctured Riemann surfaces, Macdonald polynomials, quiver representations, Hilbert schemes on Cx × Cx, modular forms and multiplicities in tensor products of irreducible characters of finite general linear groups.}, author = {Tamas Hausel and Letellier, Emmanuel and Rodríguez Villegas, Fernando}, journal = {Advances in Mathematics}, pages = {85 -- 128}, publisher = {Academic Press}, title = {{Arithmetic harmonic analysis on character and quiver varieties II}}, doi = {10.1016/j.aim.2012.10.009}, volume = {234}, year = {2013}, } @article{1470, abstract = {We show that a natural isomorphism between the rational cohomology groups of the two zero-dimensional Hilbert schemes of n-points of two surfaces, the affine plane minus the axes and the cotangent bundle of an elliptic curve, exchanges the weight filtration on the first set of cohomology groups with the perverse Leray filtration associated with a natural fibration on the second set of cohomology groups. We discuss some associated hard Lefschetz phenomena.}, author = {De Cataldo, Mark A and Tamas Hausel and Migliorini, Luca}, journal = {Journal of Singularities}, pages = {23 -- 38}, publisher = {Worldwide Center of Mathematics}, title = {{Exchange between perverse and weight filtration for the Hilbert schemes of points of two surfaces}}, doi = {10.5427/jsing.2013.7c}, volume = {7}, year = {2013}, } @article{11758, author = {Aceto, Luca and Henzinger, Monika H and Sgall, Jiří}, issn = {0890-5401}, journal = {Information and Computation}, number = {1}, pages = {1}, publisher = {Elsevier}, title = {{38th International Colloquium on Automata, Languages and Programming}}, doi = {10.1016/j.ic.2012.11.002}, volume = {222}, year = {2013}, } @article{1726, abstract = {The development of a functional tissue requires coordination of the amplification of progenitors and their differentiation into specific cell types. The molecular basis for this coordination during myotome ontogeny is not well understood. Dermomytome progenitors that colonize the myotome first acquire myocyte identity and subsequently proliferate as Pax7-expressing progenitors before undergoing terminal differentiation. We show that the dynamics of sonic hedgehog (Shh) signaling is crucial for this transition in both avian and mouse embryos. Initially, Shh ligand emanating from notochord/floor plate reaches the dermomyotome, where it both maintains the proliferation of dermomyotome cells and promotes myogenic differentiation of progenitors that colonized the myotome. Interfering with Shh signaling at this stage produces small myotomes and accumulation of Pax7-expressing progenitors. An in vivo reporter of Shh activity combined with mouse genetics revealed the existence of both activator and repressor Shh activities operating on distinct subsets of cells during the epaxial myotomal maturation. In contrast to observations in mice, in avians Shh promotes the differentiation of both epaxial and hypaxial myotome domains. Subsequently, myogenic progenitors become refractory to Shh; this is likely to occur at the level of, or upstream of, smoothened signaling. The end of responsiveness to Shh coincides with, and is thus likely to enable, the transition into the growth phase of the myotome.}, author = {Kahane, Nitza and Ribes, Vanessa and Anna Kicheva and Briscoe, James and Kalcheim, Chaya}, journal = {Development}, number = {8}, pages = {1740 -- 1750}, publisher = {Company of Biologists}, title = {{The transition from differentiation to growth during dermomyotome-derived myogenesis depends on temporally restricted hedgehog signaling}}, doi = {10.1242/dev.092726}, volume = {140}, year = {2013}, } @article{1727, abstract = {Cells at different positions in a developing tissue receive different concentrations of signaling molecules, called morphogens, and this influences their cell fate. Morphogen concentration gradients have been proposed to control patterning as well as growth in many developing tissues. Some outstanding questions about tissue patterning by morphogen gradients are the following: What are the mechanisms that regulate gradient formation and shape? Is the positional information encoded in the gradient sufficiently precise to determine the positions of target gene domain boundaries? What are the temporal dynamics of gradients and how do they relate to patterning and growth? These questions are inherently quantitative in nature and addressing them requires measuring morphogen concentrations in cells, levels of downstream signaling activity, and kinetics of morphogen transport. Here we first present methods for quantifying morphogen gradient shape in which the measurements can be calibrated to reflect actual morphogen concentrations. We then discuss using fluorescence recovery after photobleaching to study the kinetics of morphogen transport at the tissue level. Finally, we present particle tracking as a method to study morphogen intracellular trafficking.}, author = {Anna Kicheva and Holtzer, Laurent and Wartlick, Ortrud and Schmidt, Thomas S and González-Gaitán, Marcos A}, journal = {Cold Spring Harbor Protocols}, number = {5}, pages = {387 -- 403}, publisher = {Cold Spring Harbor Laboratory Press}, title = {{Quantitative imaging of morphogen gradients in drosophila imaginal discs}}, doi = {10.1101/pdb.top074237}, volume = {8}, year = {2013}, } @article{1760, abstract = {We report on hole g-factor measurements in three terminal SiGe self-assembled quantum dot devices with a top gate electrode positioned very close to the nanostructure. Measurements of both the perpendicular as well as the parallel g-factor reveal significant changes for a small modulation of the top gate voltage. From the observed modulations, we estimate that, for realistic experimental conditions, hole spins can be electrically manipulated with Rabi frequencies in the order of 100 MHz. This work emphasises the potential of hole-based nano-devices for efficient spin manipulation by means of the g-tensor modulation technique.}, author = {Ares, Natalia and Georgios Katsaros and Golovach, Vitaly N and Zhang, Jianjun and Prager, Aaron A and Glazman, Leonid I and Schmidt, Oliver G and De Franceschi, Silvano}, journal = {Applied Physics Letters}, number = {26}, publisher = {American Institute of Physics}, title = {{SiGe quantum dots for fast hole spin Rabi oscillations}}, doi = {10.1063/1.4858959}, volume = {103}, year = {2013}, } @article{1759, abstract = {We report an electric-field-induced giant modulation of the hole g factor in SiGe nanocrystals. The observed effect is ascribed to a so-far overlooked contribution to the g factor that stems from the mixing between heavy- and light-hole wave functions. We show that the relative displacement between the confined heavy- and light-hole states, occurring upon application of the electric field, alters their mixing strength leading to a strong nonmonotonic modulation of the g factor.}, author = {Ares, Natalia and Golovach, Vitaly N and Georgios Katsaros and Stoffel, Mathieu and Fournel, Frank and Glazman, Leonid I and Schmidt, Oliver G and De Franceschi, Silvano}, journal = {Physical Review Letters}, number = {4}, publisher = {American Physical Society}, title = {{Nature of tunable hole g factors in quantum dots}}, doi = {10.1103/PhysRevLett.110.046602}, volume = {110}, year = {2013}, } @article{1785, abstract = {The geometric aspects of quantum mechanics are emphasized most prominently by the concept of geometric phases, which are acquired whenever a quantum system evolves along a path in Hilbert space, that is, the space of quantum states of the system. The geometric phase is determined only by the shape of this path and is, in its simplest form, a real number. However, if the system has degenerate energy levels, then matrix-valued geometric state transformations, known as non-Abelian holonomies-the effect of which depends on the order of two consecutive paths-can be obtained. They are important, for example, for the creation of synthetic gauge fields in cold atomic gases or the description of non-Abelian anyon statistics. Moreover, there are proposals to exploit non-Abelian holonomic gates for the purposes of noise-resilient quantum computation. In contrast to Abelian geometric operations, non-Abelian ones have been observed only in nuclear quadrupole resonance experiments with a large number of spins, and without full characterization of the geometric process and its non-commutative nature. Here we realize non-Abelian non-adiabatic holonomic quantum operations on a single, superconducting, artificial three-level atom by applying a well-controlled, two-tone microwave drive. Using quantum process tomography, we determine fidelities of the resulting non-commuting gates that exceed 95 per cent. We show that two different quantum gates, originating from two distinct paths in Hilbert space, yield non-equivalent transformations when applied in different orders. This provides evidence for the non-Abelian character of the implemented holonomic quantum operations. In combination with a non-trivial two-quantum-bit gate, our method suggests a way to universal holonomic quantum computing.}, author = {Abdumalikov, Abdufarrukh A and Johannes Fink and Juliusson, K and Pechal, M and Berger, Stefan T and Wallraff, Andreas and Filipp, Stefan}, journal = {Nature}, number = {7446}, pages = {482 -- 485}, publisher = {Nature Publishing Group}, title = {{Experimental realization of non-Abelian non-adiabatic geometric gates}}, doi = {10.1038/nature12010}, volume = {496}, year = {2013}, } @article{1787, abstract = {When two indistinguishable single photons impinge at the two inputs of a beam splitter they coalesce into a pair of photons appearing in either one of its two outputs. This effect is due to the bosonic nature of photons and was first experimentally observed by Hong, Ou and Mandel. Here, we present the observation of the Hong-Ou-Mandel effect with two independent single-photon sources in the microwave frequency domain. We probe the indistinguishability of single photons, created with a controllable delay, in time-resolved second-order cross- and auto-correlation function measurements. Using quadrature amplitude detection we are able to resolve different photon numbers and detect coherence in and between the output arms. This scheme allows us to fully characterize the two-mode entanglement of the spatially separated beam-splitter output modes. Our experiments constitute a first step towards using two-photon interference at microwave frequencies for quantum communication and information processing.}, author = {Lang, C and Eichler, Christopher and Steffen, L. Kraig and Johannes Fink and Woolley, Matthew J and Blais, Alexandre and Wallraff, Andreas}, journal = {Nature Physics}, number = {6}, pages = {345 -- 348}, publisher = {Nature Publishing Group}, title = {{Correlations, indistinguishability and entanglement in Hong-Ou-Mandel experiments at microwave frequencies}}, doi = {10.1038/nphys2612}, volume = {9}, year = {2013}, } @article{1786, abstract = {We report the experimental observation and a theoretical explanation of collective suppression of linewidths for multiple superconducting qubits coupled to a good cavity. This demonstrates how strong qubit-cavity coupling can significantly modify the dephasing and dissipation processes that might be expected for individual qubits, and can potentially improve coherence times in many-body circuit QED.}, author = {Nissen, Felix and Johannes Fink and Mlynek, Jonas A and Wallraff, Andreas and Keeling, Jonathan M}, journal = {Physical Review Letters}, number = {20}, publisher = {American Physical Society}, title = {{Collective suppression of linewidths in circuit QED}}, doi = {10.1103/PhysRevLett.110.203602}, volume = {110}, year = {2013}, } @article{1790, abstract = {In the September 12, 2013 issue of Nature, the Epi4K Consortium (. Allen etal., 2013) reported sequencing 264patient trios with epileptic encephalopathies. The Consortium focused on genes exceptionally intolerant to sequence variations and found substantial interconnections with autism and intellectual disability gene networks.}, author = {Gaia Novarino and Baek, SeungTae and Gleeson, Joseph G}, journal = {Neuron}, number = {1}, pages = {9 -- 11}, publisher = {Elsevier}, title = {{The sacred disease: The puzzling genetics of epileptic disorders}}, doi = {10.1016/j.neuron.2013.09.019}, volume = {80}, year = {2013}, } @article{1977, abstract = {Complex I (NADH:ubiquinone oxidoreductase) is central to cellular energy production, being the first and largest enzyme of the respiratory chain in mitochondria. It couples electron transfer from NADH to ubiquinone with proton translocation across the inner mitochondrial membrane and is involved in a wide range of human neurodegenerative disorders. Mammalian complex I is composed of 44 different subunits, whereas the 'minimal' bacterial version contains 14 highly conserved 'core' subunits. The L-shaped assembly consists of hydrophilic and membrane domains. We have determined all known atomic structures of complex I, starting from the hydrophilic domain of Thermus thermophilus enzyme (eight subunits, nine Fe-S clusters), followed by the membrane domains of the Escherichia coli (six subunits, 55 transmembrane helices) and T. thermophilus (seven subunits, 64 transmembrane helices) enzymes, and finally culminating in a recent crystal structure of the entire intact complex I from T. thermophilus (536 kDa, 16 subunits, nine Fe-S clusters, 64 transmembrane helices). The structure suggests an unusual and unique coupling mechanism via longrange conformational changes. Determination of the structure of the entire complex was possible only through this step-by-step approach, building on from smaller subcomplexes towards the entire assembly. Large membrane proteins are notoriously difficult to crystallize, and so various non-standard and sometimes counterintuitive approaches were employed in order to achieve crystal diffraction to high resolution and solve the structures. These steps, as well as the implications from the final structure, are discussed in the present review.}, author = {Leonid Sazanov and Baradaran, Rozbeh and Efremov, Rouslan G and Berrisford, John M and Minhas, Gurdeep S}, journal = {Biochemical Society Transactions}, number = {5}, pages = {1265 -- 1271}, publisher = {Portland Press}, title = {{A long road towards the structure of respiratory complex I, a giant molecular proton pump}}, doi = {10.1042/BST20130193}, volume = {41}, year = {2013}, } @article{1978, abstract = {Complex I is the first and largest enzyme of the respiratory chain and has a central role in cellular energy production through the coupling of NADH:ubiquinone electron transfer to proton translocation. It is also implicated in many common human neurodegenerative diseases. Here, we report the first crystal structure of the entire, intact complex I (from Thermus thermophilus) at 3.3 Å resolution. The structure of the 536-kDa complex comprises 16 different subunits, with a total of 64 transmembrane helices and 9 iron-sulphur clusters. The core fold of subunit Nqo8 (ND1 in humans) is, unexpectedly, similar to a half-channel of the antiporter-like subunits. Small subunits nearby form a linked second half-channel, which completes the fourth proton-translocation pathway (present in addition to the channels in three antiporter-like subunits). The quinone-binding site is unusually long, narrow and enclosed. The quinone headgroup binds at the deep end of this chamber, near iron-sulphur cluster N2. Notably, the chamber is linked to the fourth channel by a 'funnel' of charged residues. The link continues over the entire membrane domain as a flexible central axis of charged and polar residues, and probably has a leading role in the propagation of conformational changes, aided by coupling elements. The structure suggests that a unique, out-of-the-membrane quinone-reaction chamber enables the redox energy to drive concerted long-range conformational changes in the four antiporter-like domains, resulting in translocation of four protons per cycle.}, author = {Baradaran, Rozbeh and Berrisford, John M and Minhas, Gurdeep S and Leonid Sazanov}, journal = {Nature}, number = {7438}, pages = {443 -- 448}, publisher = {Nature Publishing Group}, title = {{Crystal structure of the entire respiratory complex i}}, doi = {10.1038/nature11871}, volume = {494}, year = {2013}, } @article{1991, abstract = {Although transitions of sex-determination mechanisms are frequent in species with homomorphic sex chromosomes, heteromorphic sex chromosomes are thought to represent a terminal evolutionary stage owing to chromosome-specific adaptations such as dosage compensation or an accumulation of sex-specific mutations. Here we show that an autosome of Drosophila, the dot chromosome, was ancestrally a differentiated X chromosome. We analyse the whole genome of true fruitflies (Tephritidae), flesh flies (Sarcophagidae) and soldier flies (Stratiomyidae) to show that genes located on the dot chromosome of Drosophila are X-linked in outgroup species, whereas Drosophila X-linked genes are autosomal. We date this chromosomal transition to early drosophilid evolution by sequencing the genome of other Drosophilidae. Our results reveal several puzzling aspects of Drosophila dot chromosome biology to be possible remnants of its former life as a sex chromosome, such as its minor feminizing role in sex determination or its targeting by a chromosome-specific regulatory mechanism. We also show that patterns of biased gene expression of the dot chromosome during early embryogenesis, oogenesis and spermatogenesis resemble that of the current X chromosome. Thus, although sex chromosomes are not necessarily evolutionary end points and can revert back to an autosomal inheritance, the highly specialized genome architecture of this former X chromosome suggests that severe fitness costs must be overcome for such a turnover to occur.}, author = {Beatriz Vicoso and Bachtrog, Doris}, journal = {Nature}, number = {7458}, pages = {332 -- 335}, publisher = {Nature Publishing Group}, title = {{Reversal of an ancient sex chromosome to an autosome in Drosophila}}, doi = {10.1038/nature12235}, volume = {499}, year = {2013}, } @article{1988, abstract = {The rod-shaped bacterium Escherichia coli selects the cell center as site of division with the help of the proteins MinC, MinD, and MinE. This protein system collectively oscillates between the two cell poles by alternately binding to the membrane in one of the two cell halves. This dynamic behavior, which emerges from the interaction of the ATPase MinD and its activator MinE on the cell membrane, has become a paradigm for protein self-organization. Recently, it has been found that not only the binding of MinD to the membrane, but also interactions of MinE with the membrane contribute to Min-protein self-organization. Here, we show that by accounting for this finding in a computational model, we can comprehensively describe all observed Min-protein patterns in vivo and in vitro. Furthermore, by varying the system's geometry, our computations predict patterns that have not yet been reported. We confirm these predictions experimentally.}, author = {Bonny, Mike and Fischer-Friedrich, Elisabeth and Martin Loose and Schwille, Petra and Kruse, Karsten}, journal = {PLoS Computational Biology}, number = {12}, publisher = {Public Library of Science}, title = {{Membrane binding of MinE allows for a comprehensive description of Min-protein pattern formation}}, doi = {10.1371/journal.pcbi.1003347}, volume = {9}, year = {2013}, } @article{2010, abstract = {Many algorithms for inferring causality rely heavily on the faithfulness assumption. The main justification for imposing this assumption is that the set of unfaithful distributions has Lebesgue measure zero, since it can be seen as a collection of hypersurfaces in a hypercube. However, due to sampling error the faithfulness condition alone is not sufficient for statistical estimation, and strong-faithfulness has been proposed and assumed to achieve uniform or high-dimensional consistency. In contrast to the plain faithfulness assumption, the set of distributions that is not strong-faithful has nonzero Lebesgue measure and in fact, can be surprisingly large as we show in this paper. We study the strong-faithfulness condition from a geometric and combinatorial point of view and give upper and lower bounds on the Lebesgue measure of strong-faithful distributions for various classes of directed acyclic graphs. Our results imply fundamental limitations for the PC-algorithm and potentially also for other algorithms based on partial correlation testing in the Gaussian case.}, author = {Uhler, Caroline and Raskutti, Garvesh and Bühlmann, Peter and Yu, Bin}, journal = {The Annals of Statistics}, number = {2}, pages = {436 -- 463}, publisher = {Institute of Mathematical Statistics}, title = {{Geometry of the faithfulness assumption in causal inference}}, doi = {10.1214/12-AOS1080}, volume = {41}, year = {2013}, } @article{2009, abstract = {Traditional statistical methods for confidentiality protection of statistical databases do not scale well to deal with GWAS databases especially in terms of guarantees regarding protection from linkage to external information. The more recent concept of differential privacy, introduced by the cryptographic community, is an approach which provides a rigorous definition of privacy with meaningful privacy guarantees in the presence of arbitrary external information, although the guarantees may come at a serious price in terms of data utility. Building on such notions, we propose new methods to release aggregate GWAS data without compromising an individual’s privacy. We present methods for releasing differentially private minor allele frequencies, chi-square statistics and p-values. We compare these approaches on simulated data and on a GWAS study of canine hair length involving 685 dogs. We also propose a privacy-preserving method for finding genome-wide associations based on a differentially-private approach to penalized logistic regression.}, author = {Uhler, Caroline and Slavkovic, Aleksandra and Fienberg, Stephen}, journal = {Journal of Privacy and Confidentiality }, number = {1}, pages = {137 -- 166}, publisher = {Carnegie Mellon University}, title = {{Privacy-preserving data sharing for genome-wide association studies}}, doi = {10.29012/jpc.v5i1.629}, volume = {5}, year = {2013}, } @article{2074, abstract = {Sex chromosomes originate from autosomes. The accumulation of sexually antagonistic mutations on protosex chromosomes selects for a loss of recombination and sets in motion the evolutionary processes generating heteromorphic sex chromosomes. Recombination suppression and differentiation are generally viewed as the default path of sex chromosome evolution, and the occurrence of old, homomorphic sex chromosomes, such as those of ratite birds, has remained a mystery. Here, we analyze the genome and transcriptome of emu (Dromaius novaehollandiae) and confirm that most genes on the sex chromosome are shared between the Z and W. Surprisingly, however, levels of gene expression are generally sex-biased for all sex-linked genes relative to autosomes, including those in the pseudoautosomal region, and the male-bias increases after gonad formation. This expression bias suggests that the emu sex chromosomes have become masculinized, even in the absence of ZW differentiation. Thus, birds may have taken different evolutionary solutions to minimize the deleterious effects imposed by sexually antagonistic mutations: some lineages eliminate recombination along the protosex chromosomes to physically restrict sexually antagonistic alleles to one sex, whereas ratites evolved sex-biased expression to confine the product of a sexually antagonistic allele to the sex it benefits. This difference in conflict resolution may explain the preservation of recombining, homomorphic sex chromosomes in other lineages and illustrates the importance of sexually antagonistic mutations driving the evolution of sex chromosomes. }, author = {Beatriz Vicoso and Kaiser, Vera B and Bachtrog, Doris}, journal = {PNAS}, number = {16}, pages = {6453 -- 6458}, publisher = {National Academy of Sciences}, title = {{Sex biased gene expression at homomorphic sex chromosomes in emus and its implication for sex chromosome evolution}}, doi = {10.1073/pnas.1217027110}, volume = {110}, year = {2013}, } @article{2076, abstract = {Snakes exhibit genetic sex determination, with female heterogametic sex chromosomes (ZZ males, ZW females). Extensive cytogenetic work has suggested that the level of sex chromosome heteromorphism varies among species, with Boidae having entirely homomorphic sex chromosomes, Viperidae having completely heteromorphic sex chromosomes, and Colubridae showing partial differentiation. Here, we take a genomic approach to compare sex chromosome differentiation in these three snake families. We identify homomorphic sex chromosomes in boas (Boidae), but completely heteromorphic sex chromosomes in both garter snakes (Colubridae) and pygmy rattlesnake (Viperidae). Detection of W-linked gametologs enables us to establish the presence of evolutionary strata on garter and pygmy rattlesnake sex chromosomes where recombination was abolished at different time points. Sequence analysis shows that all strata are shared between pygmy rattlesnake and garter snake, i.e., recombination was abolished between the sex chromosomes before the two lineages diverged. The sex-biased transmission of the Z and its hemizygosity in females can impact patterns of molecular evolution, and we show that rates of evolution for Z-linked genes are increased relative to their pseudoautosomal homologs, both at synonymous and amino acid sites (even after controlling for mutational biases). This demonstrates that mutation rates are male-biased in snakes (male-driven evolution), but also supports faster-Z evolution due to differential selective effects on the Z. Finally, we perform a transcriptome analysis in boa and pygmy rattlesnake to establish baseline levels of sex-biased expression in homomorphic sex chromosomes, and show that heteromorphic ZW chromosomes in rattlesnakes lack chromosome-wide dosage compensation. Our study provides the first full scale overview of the evolution of snake sex chromosomes at the genomic level, thus greatly expanding our knowledge of reptilian and vertebrate sex chromosomes evolution. }, author = {Beatriz Vicoso and Emerson, Jr J. and Zektser, Yulia and Mahajan, Shivani and Bachtrog, Doris}, journal = {PLoS Biology}, number = {8}, publisher = {Public Library of Science}, title = {{Comparative sex chromosome genomics in snakes: Differentiation evolutionary strata and lack of global dosage compensation}}, doi = {10.1371/journal.pbio.1001643}, volume = {11}, year = {2013}, } @article{2108, abstract = {We present an interactive design system that allows non-expert users to create animated mechanical characters. Given an articulated character as input, the user iteratively creates an animation by sketching motion curves indicating how different parts of the character should move. For each motion curve, our framework creates an optimized mechanism that reproduces it as closely as possible. The resulting mechanisms are attached to the character and then connected to each other using gear trains, which are created in a semi-automated fashion. The mechanical assemblies generated with our system can be driven with a single input driver, such as a hand-operated crank or an electric motor, and they can be fabricated using rapid prototyping devices. We demonstrate the versatility of our approach by designing a wide range of mechanical characters, several of which we manufactured using 3D printing. While our pipeline is designed for characters driven by planar mechanisms, significant parts of it extend directly to non-planar mechanisms, allowing us to create characters with compelling 3D motions. }, author = {Coros, Stelian and Thomaszewski, Bernhard and Noris, Gioacchino and Sueda, Shinjiro and Forberg, Moira and Sumner, Robert W and Matusik, Wojciech and Bernd Bickel}, journal = {ACM Transactions on Graphics}, number = {4}, publisher = {ACM}, title = {{Computational design of mechanical characters}}, doi = {10.1145/2461912.2461953}, volume = {32}, year = {2013}, } @article{2110, abstract = {We present a method for practical physical reproduction and design of homogeneous materials with desired subsurface scattering. Our process uses a collection of different pigments that can be suspended in a clear base material. Our goal is to determine pigment concentrations that best reproduce the appearance and subsurface scattering of a given target material. In order to achieve this task we first fabricate a collection of material samples composed of known mixtures of the available pigments with the base material. We then acquire their reflectance profiles using a custom-built measurement device. We use the same device to measure the reflectance profile of a target material. Based on the database of mappings from pigment concentrations to reflectance profiles, we use an optimization process to compute the concentration of pigments to best replicate the target material appearance. We demonstrate the practicality of our method by reproducing a variety of different translucent materials. We also present a tool that allows the user to explore the range of achievable appearances for a given set of pigments. }, author = {Papas, Marios and Regg, Christian and Jarosz, Wojciech and Bernd Bickel and Jackson, Philip V and Matusik, Wojciech and Marschner, Steve and Groß, Markus S}, journal = {ACM Transactions on Graphics}, number = {4}, publisher = {ACM}, title = {{Fabricating translucent materials using continuous pigment mixtures}}, doi = {10.1145/2461912.2461974}, volume = {32}, year = {2013}, } @article{2111, abstract = {Animated animatronic figures are a unique way to give physical presence to a character. However, their movement and expressions are often limited due to mechanical constraints. In this paper, we propose a complete process for augmenting physical avatars using projector-based illumination, significantly increasing their expressiveness. Given an input animation, the system decomposes the motion into low-frequency motion that can be physically reproduced by the animatronic head and high-frequency details that are added using projected shading. At the core is a spatio-temporal optimization process that compresses the motion in gradient space, ensuring faithful motion replay while respecting the physical limitations of the system. We also propose a complete multi-camera and projection system, including a novel defocused projection and subsurface scattering compensation scheme. The result of our system is a highly expressive physical avatar that features facial details and motion otherwise unattainable due to physical constraints.}, author = {Bermano, Amit H and Bruschweiler, Philipp and Grundhöfer, Anselm and Iwai, Daisuke and Bernd Bickel and Groß, Markus S}, journal = {ACM Transactions on Graphics}, number = {6}, publisher = {ACM}, title = {{Augmenting physical avatars using projector-based illumination}}, doi = {10.1145/2508363.2508416}, volume = {32}, year = {2013}, } @article{2109, abstract = {Most additive manufacturing technologies work by layering, i.e. slicing the shape and then generating each slice independently. This introduces an anisotropy into the process, often as different accuracies in the tangential and normal directions, but also in terms of other parameters such as build speed or tensile strength and strain. We model this as an anisotropic cubic element. Our approach then finds a compromise between modeling each part of the shape individually in the best possible direction and using one direction for the whole shape part. In particular, we compute an orthogonal basis and consider only the three basis vectors as slice normals (i.e. fabrication directions). Then we optimize a decomposition of the shape along this basis so that each part can be consistently sliced along one of the basis vectors. In simulation, we show that this approach is superior to slicing the whole shape in one direction, only. It also has clear benefits if the shape is larger than the build volume of the available equipment.}, author = {Hildebrand, Kristian and Bernd Bickel and Alexa, Marc}, journal = {Computers and Graphics (Pergamon)}, number = {6}, pages = {669 -- 675}, publisher = {Elsevier}, title = {{Orthogonal slicing for additive manufacturing}}, doi = {10.1016/j.cag.2013.05.011}, volume = {37}, year = {2013}, } @article{2107, abstract = {We present a method for fabrication-oriented design of actuated deformable characters that allows a user to automatically create physical replicas of digitally designed characters using rapid manufacturing technologies. Given a deformable character and a set of target poses as input, our method computes a small set of actuators along with their locations on the surface and optimizes the internal material distribution such that the resulting character exhibits the desired deformation behavior. We approach this problem with a dedicated algorithm that combines finite-element analysis, sparse regularization, and constrained optimization. We validate our pipeline on a set of two- and three-dimensional example characters and present results in simulation and physically-fabricated prototypes.}, author = {Skouras, Mélina and Thomaszewski, Bernhard and Coros, Stelian and Bernd Bickel and Groß, Markus S}, journal = {ACM Transactions on Graphics}, number = {4}, publisher = {ACM}, title = {{Computational design of actuated deformable characters}}, doi = {10.1145/2461912.2461979}, volume = {32}, year = {2013}, } @article{2112, abstract = {Force-deformation measurements of cloth exhibit significant hysteresis, and many researchers have identified internal friction as the source of this effect. However, it has not been incorporated into computer animation models of cloth. In this paper, we propose a model of internal friction based on an augmented reparameterization of Dahl's model, and we show that this model provides a good match to several important features of cloth hysteresis even with a minimal set of parameters. We also propose novel parameter estimation procedures that are based on simple and inexpensive setups and need only sparse data, as opposed to the complex hardware and dense data acquisition of previous methods. Finally, we provide an algorithm for the efficient simulation of internal friction, and we demonstrate it on simulation examples that show disparate behavior with and without internal friction.}, author = {Miguel, Eder and Tamstorf, Rasmus and Bradley, Derek J and Schvartzman, Sara C and Thomaszewski, Bernhard and Bernd Bickel and Matusik, Wojciech and Marschner, Steve and Otaduy, Miguel A}, journal = {ACM Transactions on Graphics}, number = {6}, publisher = {ACM}, title = {{Modeling and estimation of internal friction in cloth}}, doi = {10.1145/2508363.2508389 }, volume = {32}, year = {2013}, } @article{2117, abstract = {We prove new upper and lower bounds for Banach space-valued stochastic integrals with respect to a compensated Poisson random measure. Our estimates apply to Banach spaces with non-trivial martingale (co)type and extend various results in the literature. We also develop a Malliavin framework to interpret Poisson stochastic integrals as vector-valued Skorohod integrals, and prove a Clark-Ocone representation formula.}, author = {Dirksen, Sjoerd and Jan Maas and van Neerven, Jan M}, journal = {Electronic Journal of Probability}, publisher = {Institute of Mathematical Statistics}, title = {{Poisson stochastic integration in Banach spaces}}, doi = {10.1214/EJP.v18-2945 }, volume = {18}, year = {2013}, } @article{2113, abstract = {A new method fabricates custom surface reflectance and spatially varying bidirectional reflectance distribution functions (svBRDFs). Researchers optimize a microgeometry for a range of normal distribution functions and simulate the resulting surface's effective reflectance. Using the simulation's results, they reproduce an input svBRDF's appearance by distributing the microgeometry on the printed material's surface. This method lets people print svBRDFs on planar samples with current 3D printing technology, even with a limited set of printing materials. It extends naturally to printing svBRDFs on arbitrary shapes.}, author = {Rouiller, Olivier and Bernd Bickel and Kautz, Jan and Matusik, Wojciech and Alexa, Marc}, journal = {IEEE Computer Graphics and Applications}, number = {6}, pages = {48 -- 57}, publisher = {IEEE}, title = {{3D printing spatially varying BRDFs}}, doi = {10.1109/MCG.2013.82 }, volume = {33}, year = {2013}, } @article{2114, abstract = {3D printing is considered a disruptive technology with a potentially tremendous socioeconomic impact. The three articles in this special issue illustrate how novel computer graphics approaches are advancing such digital fabrication.}, author = {Bernd Bickel and Alexa, Marc}, journal = {IEEE Computer Graphics and Applications}, number = {6}, pages = {24 -- 25}, publisher = {IEEE}, title = {{Computational aspects of fabrication: Modeling, design and 3d printing}}, doi = {10.1109/MCG.2013.89}, volume = {33}, year = {2013}, } @article{2129, abstract = {This paper continues the investigation of `Wasserstein-like' transportation distances for probability measures on discrete sets. We prove that the discrete transportation metrics on the d-dimensional discrete torus with mesh size 1/N converge, when N→∞, to the standard 2-Wasserstein distance W_2 on the continuous torus in the sense of Gromov-Hausdorff. This is the first convergence result for the recently developed discrete transportation metrics. The result shows the compatibility between these metrics and the well-established 2-Wasserstein metric. }, author = {Gigli, Nicola and Jan Maas}, journal = {SIAM Journal on Mathematical Analysis}, number = {2}, pages = {879 -- 899}, publisher = {Society for Industrial and Applied Mathematics }, title = {{Gromov-Hausdorff convergence of discrete transportation metrics}}, doi = {10.1137/120886315 }, volume = {45}, year = {2013}, } @article{2139, abstract = {Recently it has been shown that pairs of atoms can form metastable bonds due to non-conservative forces induced by dissipation [Lemeshko&Weimer, Nature Comm. 4, 2230 (2013)]. Here we study the dynamics of interaction-induced coherent population trapping - the process responsible for the formation of dissipatively bound molecules. We derive the effective dissipative potentials induced between ultracold atoms by laser light, and study the time evolution of the scattering states. We demonstrate that binding occurs on short timescales of ~10 microseconds, even if the initial kinetic energy of the atoms significantly exceeds the depth of the dissipative potential. Dissipatively-bound molecules with preordained bond lengths and vibrational wavefunctions can be created and detected in current experiments with ultracold atoms.}, author = {Mikhail Lemeshko}, journal = {Frontiers Physics}, number = {17}, publisher = {Frontiers Media}, title = {{Manipulating scattering of ultracold atoms with light-induced dissipation}}, doi = {10.3389/fphy.2013.00017}, volume = {1}, year = {2013}, } @inproceedings{2181, abstract = {There is a trade-off between performance and correctness in implementing concurrent data structures. Better performance may be achieved at the expense of relaxing correctness, by redefining the semantics of data structures. We address such a redefinition of data structure semantics and present a systematic and formal framework for obtaining new data structures by quantitatively relaxing existing ones. We view a data structure as a sequential specification S containing all "legal" sequences over an alphabet of method calls. Relaxing the data structure corresponds to defining a distance from any sequence over the alphabet to the sequential specification: the k-relaxed sequential specification contains all sequences over the alphabet within distance k from the original specification. In contrast to other existing work, our relaxations are semantic (distance in terms of data structure states). As an instantiation of our framework, we present two simple yet generic relaxation schemes, called out-of-order and stuttering relaxation, along with several ways of computing distances. We show that the out-of-order relaxation, when further instantiated to stacks, queues, and priority queues, amounts to tolerating bounded out-of-order behavior, which cannot be captured by a purely syntactic relaxation (distance in terms of sequence manipulation, e.g. edit distance). We give concurrent implementations of relaxed data structures and demonstrate that bounded relaxations provide the means for trading correctness for performance in a controlled way. The relaxations are monotonic which further highlights the trade-off: increasing k increases the number of permitted sequences, which as we demonstrate can lead to better performance. Finally, since a relaxed stack or queue also implements a pool, we actually have new concurrent pool implementations that outperform the state-of-the-art ones.}, author = {Henzinger, Thomas A and Kirsch, Christoph and Payer, Hannes and Sezgin, Ali and Sokolova, Ana}, booktitle = {Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming language}, isbn = {978-1-4503-1832-7}, location = {Rome, Italy}, pages = {317 -- 328}, publisher = {ACM}, title = {{Quantitative relaxation of concurrent data structures}}, doi = {10.1145/2429069.2429109}, year = {2013}, } @inproceedings{2182, abstract = {We propose a general framework for abstraction with respect to quantitative properties, such as worst-case execution time, or power consumption. Our framework provides a systematic way for counter-example guided abstraction refinement for quantitative properties. The salient aspect of the framework is that it allows anytime verification, that is, verification algorithms that can be stopped at any time (for example, due to exhaustion of memory), and report approximations that improve monotonically when the algorithms are given more time. We instantiate the framework with a number of quantitative abstractions and refinement schemes, which differ in terms of how much quantitative information they keep from the original system. We introduce both state-based and trace-based quantitative abstractions, and we describe conditions that define classes of quantitative properties for which the abstractions provide over-approximations. We give algorithms for evaluating the quantitative properties on the abstract systems. We present algorithms for counter-example based refinements for quantitative properties for both state-based and segment-based abstractions. We perform a case study on worst-case execution time of executables to evaluate the anytime verification aspect and the quantitative abstractions we proposed.}, author = {Cerny, Pavol and Henzinger, Thomas A and Radhakrishna, Arjun}, booktitle = {Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming language}, location = {Rome, Italy}, pages = {115 -- 128}, publisher = {ACM}, title = {{Quantitative abstraction refinement}}, doi = {10.1145/2429069.2429085}, year = {2013}, } @inproceedings{2209, abstract = {A straight skeleton is a well-known geometric structure, and several algorithms exist to construct the straight skeleton for a given polygon or planar straight-line graph. In this paper, we ask the reverse question: Given the straight skeleton (in form of a planar straight-line graph, with some rays to infinity), can we reconstruct a planar straight-line graph for which this was the straight skeleton? We show how to reduce this problem to the problem of finding a line that intersects a set of convex polygons. We can find these convex polygons and all such lines in $O(nlog n)$ time in the Real RAM computer model, where $n$ denotes the number of edges of the input graph. We also explain how our approach can be used for recognizing Voronoi diagrams of points, thereby completing a partial solution provided by Ash and Bolker in 1985. }, author = {Biedl, Therese and Held, Martin and Huber, Stefan}, location = {St. Petersburg, Russia}, pages = {37 -- 46}, publisher = {IEEE}, title = {{Recognizing straight skeletons and Voronoi diagrams and reconstructing their input}}, doi = {10.1109/ISVD.2013.11}, year = {2013}, } @article{2204, abstract = {We introduce a new platform for quantum simulation of many-body systems based on nonspherical atoms or molecules with zero dipole moments but possessing a significant value of electric quadrupole moments. We consider a quadrupolar Fermi gas trapped in a 2D square optical lattice, and show that the peculiar symmetry and broad tunability of the quadrupole-quadrupole interaction results in a rich phase diagram encompassing unconventional BCS and charge density wave phases, and opens up a perspective to create a topological superfluid. Quadrupolar species, such as metastable alkaline-earth atoms and homonuclear molecules, are stable against chemical reactions and collapse and are readily available in experiment at high densities.}, author = {Bhongale, Satyan and Mathey, Ludwig and Zhao, Erhai and Yelin, Susanne and Lemeshko, Mikhail}, journal = {Physical Review Letters}, number = {15}, publisher = {American Physical Society}, title = {{Quantum phases of quadrupolar fermi gases in optical lattices}}, doi = {10.1103/PhysRevLett.110.155301}, volume = {110}, year = {2013}, } @article{2206, abstract = {Magnetic impurities embedded in inert solids can exhibit long coherence times and interact with one another via their intrinsic anisotropic dipolar interaction. We argue that, as a consequence of these properties, disordered ensembles of magnetic impurities provide an effective platform for realizing a controllable, tunable version of the dipolar quantum spin glass seen in LiHoxY1-xF4. Specifically, we propose and analyze a system composed of dysprosium atoms embedded in solid helium. We describe the phase diagram of the system and discuss the realizability and detectability of the quantum spin glass and antiglass phases.}, author = {Mikhail Lemeshko and Yao, Norman Y and Gorshkov, Alexey V and Weimer, Hendrik and Bennett, Steven D and Momose, Takamasa and Gopalakrishnan, Sarang}, journal = {Physical Review B - Condensed Matter and Materials Physics}, number = {1}, publisher = {American Physical Society}, title = {{Controllable quantum spin glasses with magnetic impurities embedded in quantum solids}}, doi = {10.1103/PhysRevB.88.014426}, volume = {88}, year = {2013}, } @misc{2205, abstract = {The goal of the present article is to review the major developments that have led to the current understanding of molecule-field interactions and experimental methods for manipulating molecules with electromagnetic fields. Molecule-field interactions are at the core of several, seemingly distinct areas of molecular physics. This is reflected in the organisation of this article, which includes sections on field control of molecular beams, external field traps for cold molecules, control of molecular orientation and molecular alignment, manipulation of molecules by non-conservative forces, ultracold molecules and ultracold chemistry, controlled many-body phenomena, entanglement of molecules and dipole arrays, and stability of molecular systems in high-frequency super-intense laser fields. The article contains 852 references.}, author = {Mikhail Lemeshko and Krems, Roman V and Doyle, John M and Kais, Sabre}, booktitle = {Molecular Physics}, number = {12-13}, pages = {1648 -- 1682}, publisher = {Taylor & Francis}, title = {{Manipulation of molecules with electromagnetic fields}}, doi = {10.1080/00268976.2013.813595}, volume = {111}, year = {2013}, } @article{2207, abstract = {The formation of molecules and supramolecular structures results from bonding by conservative forces acting among electrons and nuclei and giving rise to equilibrium configurations defined by minima of the interaction potential. Here we show that bonding can also occur by the non-conservative forces responsible for interaction-induced coherent population trapping. The bound state arises in a dissipative process and manifests itself as a stationary state at a preordained interatomic distance. Remarkably, such a dissipative bonding is present even when the interactions among the atoms are purely repulsive. The dissipative bound states can be created and studied spectroscopically in present-day experiments with ultracold atoms or molecules and can potentially serve for cooling strongly interacting quantum gases.}, author = {Mikhail Lemeshko and Weimer, Hendrik}, journal = {Nature Communications}, publisher = {Nature Publishing Group}, title = {{Dissipative binding of atoms by non-conservative forces}}, doi = {10.1038/ncomms3230}, volume = {4}, year = {2013}, } @inproceedings{2210, abstract = {A straight skeleton is a well-known geometric structure, and several algorithms exist to construct the straight skeleton for a given polygon. In this paper, we ask the reverse question: Given the straight skeleton (in form of a tree with a drawing in the plane, but with the exact position of the leaves unspecified), can we reconstruct the polygon? We show that in most cases there exists at most one polygon; in the remaining case there is an infinite number of polygons determined by one angle that can range in an interval. We can find this (set of) polygon(s) in linear time in the Real RAM computer model.}, author = {Biedl, Therese and Held, Martin and Huber, Stefan}, booktitle = {29th European Workshop on Computational Geometry}, location = {Braunschweig, Germany}, pages = {95 -- 98}, publisher = {TU Braunschweig}, title = {{Reconstructing polygons from embedded straight skeletons}}, year = {2013}, } @inproceedings{2237, abstract = {We describe new extensions of the Vampire theorem prover for computing tree interpolants. These extensions generalize Craig interpolation in Vampire, and can also be used to derive sequence interpolants. We evaluated our implementation on a large number of examples over the theory of linear integer arithmetic and integer-indexed arrays, with and without quantifiers. When compared to other methods, our experiments show that some examples could only be solved by our implementation.}, author = {Blanc, Régis and Gupta, Ashutosh and Kovács, Laura and Kragl, Bernhard}, location = {Stellenbosch, South Africa}, pages = {173 -- 181}, publisher = {Springer}, title = {{Tree interpolation in Vampire}}, doi = {10.1007/978-3-642-45221-5_13}, volume = {8312}, year = {2013}, } @inproceedings{2238, abstract = {We study the problem of achieving a given value in Markov decision processes (MDPs) with several independent discounted reward objectives. We consider a generalised version of discounted reward objectives, in which the amount of discounting depends on the states visited and on the objective. This definition extends the usual definition of discounted reward, and allows to capture the systems in which the value of different commodities diminish at different and variable rates. We establish results for two prominent subclasses of the problem, namely state-discount models where the discount factors are only dependent on the state of the MDP (and independent of the objective), and reward-discount models where they are only dependent on the objective (but not on the state of the MDP). For the state-discount models we use a straightforward reduction to expected total reward and show that the problem whether a value is achievable can be solved in polynomial time. For the reward-discount model we show that memory and randomisation of the strategies are required, but nevertheless that the problem is decidable and it is sufficient to consider strategies which after a certain number of steps behave in a memoryless way. For the general case, we show that when restricted to graphs (i.e. MDPs with no randomisation), pure strategies and discount factors of the form 1/n where n is an integer, the problem is in PSPACE and finite memory suffices for achieving a given value. We also show that when the discount factors are not of the form 1/n, the memory required by a strategy can be infinite. }, author = {Chatterjee, Krishnendu and Forejt, Vojtěch and Wojtczak, Dominik}, location = {Stellenbosch, South Africa}, pages = {228 -- 242}, publisher = {Springer}, title = {{Multi-objective discounted reward verification in graphs and MDPs}}, doi = {10.1007/978-3-642-45221-5_17}, volume = {8312}, year = {2013}, } @inproceedings{2243, abstract = {We show that modal logic over universally first-order definable classes of transitive frames is decidable. More precisely, let K be an arbitrary class of transitive Kripke frames definable by a universal first-order sentence. We show that the global and finite global satisfiability problems of modal logic over K are decidable in NP, regardless of choice of K. We also show that the local satisfiability and the finite local satisfiability problems of modal logic over K are decidable in NEXPTIME.}, author = {Michaliszyn, Jakub and Otop, Jan}, location = {Torino, Italy}, pages = {563 -- 577}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Elementary modal logics over transitive structures}}, doi = {10.4230/LIPIcs.CSL.2013.563}, volume = {23}, year = {2013}, } @inproceedings{2244, abstract = {We consider two systems (α1,...,αm) and (β1,...,βn) of curves drawn on a compact two-dimensional surface ℳ with boundary. Each αi and each βj is either an arc meeting the boundary of ℳ at its two endpoints, or a closed curve. The αi are pairwise disjoint except for possibly sharing endpoints, and similarly for the βj. We want to "untangle" the βj from the αi by a self-homeomorphism of ℳ; more precisely, we seek an homeomorphism φ: ℳ → ℳ fixing the boundary of ℳ pointwise such that the total number of crossings of the αi with the φ(βj) is as small as possible. This problem is motivated by an application in the algorithmic theory of embeddings and 3-manifolds. We prove that if ℳ is planar, i.e., a sphere with h ≥ 0 boundary components ("holes"), then O(mn) crossings can be achieved (independently of h), which is asymptotically tight, as an easy lower bound shows. In general, for an arbitrary (orientable or nonorientable) surface ℳ with h holes and of (orientable or nonorientable) genus g ≥ 0, we obtain an O((m + n)4) upper bound, again independent of h and g. }, author = {Matoušek, Jiří and Sedgwick, Eric and Tancer, Martin and Wagner, Uli}, location = {Bordeaux, France}, pages = {472 -- 483}, publisher = {Springer}, title = {{Untangling two systems of noncrossing curves}}, doi = {10.1007/978-3-319-03841-4_41}, volume = {8242}, year = {2013}, } @inproceedings{2259, abstract = {The learning with rounding (LWR) problem, introduced by Banerjee, Peikert and Rosen at EUROCRYPT ’12, is a variant of learning with errors (LWE), where one replaces random errors with deterministic rounding. The LWR problem was shown to be as hard as LWE for a setting of parameters where the modulus and modulus-to-error ratio are super-polynomial. In this work we resolve the main open problem and give a new reduction that works for a larger range of parameters, allowing for a polynomial modulus and modulus-to-error ratio. In particular, a smaller modulus gives us greater efficiency, and a smaller modulus-to-error ratio gives us greater security, which now follows from the worst-case hardness of GapSVP with polynomial (rather than super-polynomial) approximation factors. As a tool in the reduction, we show that there is a “lossy mode” for the LWR problem, in which LWR samples only reveal partial information about the secret. This property gives us several interesting new applications, including a proof that LWR remains secure with weakly random secrets of sufficient min-entropy, and very simple constructions of deterministic encryption, lossy trapdoor functions and reusable extractors. Our approach is inspired by a technique of Goldwasser et al. from ICS ’10, which implicitly showed the existence of a “lossy mode” for LWE. By refining this technique, we also improve on the parameters of that work to only requiring a polynomial (instead of super-polynomial) modulus and modulus-to-error ratio. }, author = {Alwen, Joel F and Krenn, Stephan and Pietrzak, Krzysztof Z and Wichs, Daniel}, location = {Santa Barbara, CA, United States}, number = {1}, pages = {57 -- 74}, publisher = {Springer}, title = {{Learning with rounding, revisited: New reduction properties and applications}}, doi = {10.1007/978-3-642-40041-4_4}, volume = {8042}, year = {2013}, } @inproceedings{2258, abstract = {In a digital signature scheme with message recovery, rather than transmitting the message m and its signature σ, a single enhanced signature τ is transmitted. The verifier is able to recover m from τ and at the same time verify its authenticity. The two most important parameters of such a scheme are its security and overhead |τ| − |m|. A simple argument shows that for any scheme with “n bits security” |τ| − |m| ≥ n, i.e., the overhead is lower bounded by the security parameter n. Currently, the best known constructions in the random oracle model are far from this lower bound requiring an overhead of n + logq h , where q h is the number of queries to the random oracle. In this paper we give a construction which basically matches the n bit lower bound. We propose a simple digital signature scheme with n + o(logq h ) bits overhead, where q h denotes the number of random oracle queries. Our construction works in two steps. First, we propose a signature scheme with message recovery having optimal overhead in a new ideal model, the random invertible function model. Second, we show that a four-round Feistel network with random oracles as round functions is tightly “public-indifferentiable” from a random invertible function. At the core of our indifferentiability proof is an almost tight upper bound for the expected number of edges of the densest “small” subgraph of a random Cayley graph, which may be of independent interest. }, author = {Kiltz, Eike and Pietrzak, Krzysztof Z and Szegedy, Mario}, location = {Santa Barbara, CA, United States}, pages = {571 -- 588}, publisher = {Springer}, title = {{Digital signatures with minimal overhead from indifferentiable random invertible functions}}, doi = {10.1007/978-3-642-40041-4_31}, volume = {8042}, year = {2013}, } @article{2256, abstract = {Linked (Open) Data - bibliographic data on the Semantic Web. Report of the Working Group on Linked Data to the plenary assembly of the Austrian Library Network (translation of the title). Linked Data stands for a certain approach to publishing data on the Web. The underlying idea is to harmonise heterogeneous data sources of different origin in order to improve their accessibility and interoperability, effectively making them queryable as a big distributed database. This report summarises relevant developments in Europe as well as the Linked Data Working Group‘s strategic and technical considerations regarding the publishing of the Austrian Library Network’s (OBV’s) bibliographic datasets. It concludes with the mutual agreement that the implementation of Linked Data principles within the OBV can only be taken into consideration accompanied by a discussion about the provision of the datasets under a free license.}, author = {Danowski, Patrick and Goldfarb, Doron and Schaffner, Verena and Seidler, Wolfram}, journal = {VÖB Mitteilungen}, number = {3/4}, pages = {559 -- 587}, publisher = {Verein Österreichischer Bibliothekarinnen und Bibliothekare}, title = {{Linked (Open) Data - Bibliographische Daten im Semantic Web}}, volume = {66}, year = {2013}, } @inproceedings{2260, abstract = {Direct Anonymous Attestation (DAA) is one of the most complex cryptographic protocols deployed in practice. It allows an embedded secure processor known as a Trusted Platform Module (TPM) to attest to the configuration of its host computer without violating the owner’s privacy. DAA has been standardized by the Trusted Computing Group and ISO/IEC. The security of the DAA standard and all existing schemes is analyzed in the random-oracle model. We provide the first constructions of DAA in the standard model, that is, without relying on random oracles. Our constructions use new building blocks, including the first efficient signatures of knowledge in the standard model, which have many applications beyond DAA. }, author = {Bernhard, David and Fuchsbauer, Georg and Ghadafi, Essam}, location = {Banff, AB, Canada}, pages = {518 -- 533}, publisher = {Springer}, title = {{Efficient signatures of knowledge and DAA in the standard model}}, doi = {10.1007/978-3-642-38980-1_33}, volume = {7954}, year = {2013}, } @article{2264, abstract = {Faithful progression through the cell cycle is crucial to the maintenance and developmental potential of stem cells. Here, we demonstrate that neural stem cells (NSCs) and intermediate neural progenitor cells (NPCs) employ a zinc-finger transcription factor specificity protein 2 (Sp2) as a cell cycle regulator in two temporally and spatially distinct progenitor domains. Differential conditional deletion of Sp2 in early embryonic cerebral cortical progenitors, and perinatal olfactory bulb progenitors disrupted transitions through G1, G2 and M phases, whereas DNA synthesis appeared intact. Cell-autonomous function of Sp2 was identified by deletion of Sp2 using mosaic analysis with double markers, which clearly established that conditional Sp2-null NSCs and NPCs are M phase arrested in vivo. Importantly, conditional deletion of Sp2 led to a decline in the generation of NPCs and neurons in the developing and postnatal brains. Our findings implicate Sp2-dependent mechanisms as novel regulators of cell cycle progression, the absence of which disrupts neurogenesis in the embryonic and postnatal brain.}, author = {Liang, Huixuan and Xiao, Guanxi and Yin, Haifeng and Hippenmeyer, Simon and Horowitz, Jonathan and Ghashghaei, Troy}, journal = {Development}, number = {3}, pages = {552 -- 561}, publisher = {Company of Biologists}, title = {{Neural development is dependent on the function of specificity protein 2 in cell cycle progression}}, doi = {10.1242/dev.085621}, volume = {140}, year = {2013}, } @article{2269, abstract = {This paper presents a parallel, implementation-friendly analytic visibility method for triangular meshes. Together with an analytic filter convolution, it allows for a fully analytic solution to anti-aliased 3D mesh rendering on parallel hardware. Building on recent works in computational geometry, we present a new edge-triangle intersection algorithm and a novel method to complete the boundaries of all visible triangle regions after a hidden line elimination step. All stages of the method are embarrassingly parallel and easily implementable on parallel hardware. A GPU implementation is discussed and performance characteristics of the method are shown and compared to traditional sampling-based rendering methods.}, author = {Thomas Auzinger and Wimmer, Michael and Stefan Jeschke}, journal = {Computer Graphics Forum}, number = {124}, pages = {409 -- 418}, publisher = {Wiley-Blackwell}, title = {{Analytic Visibility on the GPU}}, doi = {DOI: 10.1111/cgf.12061}, volume = {32}, year = {2013}, } @inproceedings{2270, abstract = {Representation languages for coalitional games are a key research area in algorithmic game theory. There is an inher- ent tradeoff between how general a language is, allowing it to capture more elaborate games, and how hard it is computationally to optimize and solve such games. One prominent such language is the simple yet expressive Weighted Graph Games (WGGs) representation (Deng and Papadimitriou 1994), which maintains knowledge about synergies between agents in the form of an edge weighted graph. We consider the problem of finding the optimal coalition structure in WGGs. The agents in such games are vertices in a graph, and the value of a coalition is the sum of the weights of the edges present between coalition members. The optimal coalition structure is a partition of the agents to coalitions, that maximizes the sum of utilities obtained by the coalitions. We show that finding the optimal coalition structure is not only hard for general graphs, but is also intractable for restricted families such as planar graphs which are amenable for many other combinatorial problems. We then provide algorithms with constant factor approximations for planar, minorfree and bounded degree graphs.}, author = {Bachrach, Yoram and Kohli, Pushmeet and Kolmogorov, Vladimir and Zadimoghaddam, Morteza}, location = {Bellevue, WA, United States}, pages = {81--87}, publisher = {AAAI Press}, title = {{Optimal Coalition Structures in Cooperative Graph Games}}, year = {2013}, } @techreport{2273, abstract = {We propose a new family of message passing techniques for MAP estimation in graphical models which we call Sequential Reweighted Message Passing (SRMP). Special cases include well-known techniques such as Min-Sum Diusion (MSD) and a faster Sequential Tree-Reweighted Message Passing (TRW-S). Importantly, our derivation is simpler than the original derivation of TRW-S, and does not involve a decomposition into trees. This allows easy generalizations. We present such a generalization for the case of higher-order graphical models, and test it on several real-world problems with promising results.}, author = {Vladimir Kolmogorov}, publisher = {IST Austria}, title = {{Reweighted message passing revisited}}, year = {2013}, } @article{2278, abstract = {It is firmly established that interactions between neurons and glia are fundamental across species for the correct establishment of a functional brain. Here, we found that the glia of the Drosophila larval brain display an essential non-autonomous role during the development of the optic lobe. The optic lobe develops from neuroepithelial cells that proliferate by dividing symmetrically until they switch to asymmetric/differentiative divisions that generate neuroblasts. The proneural gene lethal of scute (l9sc) is transiently activated by the epidermal growth factor receptor (EGFR)-Ras signal transduction pathway at the leading edge of a proneural wave that sweeps from medial to lateral neuroepithelium, promoting this switch. This process is tightly regulated by the tissue-autonomous function within the neuroepithelium of multiple signaling pathways, including EGFR-Ras and Notch. This study shows that the Notch ligand Serrate (Ser) is expressed in the glia and it forms a complex in vivo with Notch and Canoe, which colocalize at the adherens junctions of neuroepithelial cells. This complex is crucial for interactions between glia and neuroepithelial cells during optic lobe development. Ser is tissue-autonomously required in the glia where it activates Notch to regulate its proliferation, and non-autonomously in the neuroepithelium where Ser induces Notch signaling to avoid the premature activation of the EGFR-Ras pathway and hence of L9sc. Interestingly, different Notch activity reporters showed very different expression patterns in the glia and in the neuroepithelium, suggesting the existence of tissue-specific factors that promote the expression of particular Notch target genes or/and a reporter response dependent on different thresholds of Notch signaling.}, author = {Pérez Gómez, Raquel and Slovakova, Jana and Rives Quinto, Noemí and Krejčí, Alena and Carmena, Ana}, journal = {Journal of Cell Science}, number = {21}, pages = {4873 -- 4884}, publisher = {Company of Biologists}, title = {{A serrate-notch-canoe complex mediates essential interactions between glia and neuroepithelial cells during Drosophila optic lobe development}}, doi = {10.1242/jcs.125617}, volume = {126}, year = {2013}, } @inproceedings{2276, abstract = {The problem of minimizing the Potts energy function frequently occurs in computer vision applications. One way to tackle this NP-hard problem was proposed by Kovtun [19, 20]. It identifies a part of an optimal solution by running k maxflow computations, where k is the number of labels. The number of “labeled” pixels can be significant in some applications, e.g. 50-93% in our tests for stereo. We show how to reduce the runtime to O (log k) maxflow computations (or one parametric maxflow computation). Furthermore, the output of our algorithm allows to speed-up the subsequent alpha expansion for the unlabeled part, or can be used as it is for time-critical applications. To derive our technique, we generalize the algorithm of Felzenszwalb et al. [7] for Tree Metrics . We also show a connection to k-submodular functions from combinatorial optimization, and discuss k-submodular relaxations for general energy functions.}, author = {Gridchyn, Igor and Kolmogorov, Vladimir}, location = {Sydney, Australia}, pages = {2320 -- 2327}, publisher = {IEEE}, title = {{Potts model, parametric maxflow and k-submodular functions}}, doi = {10.1109/ICCV.2013.288}, year = {2013}, } @article{2280, abstract = {The problem of packing ellipsoids of different sizes and shapes into an ellipsoidal container so as to minimize a measure of overlap between ellipsoids is considered. A bilevel optimization formulation is given, together with an algorithm for the general case and a simpler algorithm for the special case in which all ellipsoids are in fact spheres. Convergence results are proved and computational experience is described and illustrated. The motivating application-chromosome organization in the human cell nucleus-is discussed briefly, and some illustrative results are presented.}, author = {Uhler, Caroline and Wright, Stephen}, journal = {SIAM Review}, number = {4}, pages = {671 -- 706}, publisher = {Society for Industrial and Applied Mathematics }, title = {{Packing ellipsoids with overlap}}, doi = {10.1137/120872309}, volume = {55}, year = {2013}, } @article{2287, abstract = {Negative frequency-dependent selection should result in equal sex ratios in large populations of dioecious flowering plants, but deviations from equality are commonly reported. A variety of ecological and genetic factors can explain biased sex ratios, although the mechanisms involved are not well understood. Most dioecious species are long-lived and/or clonal complicating efforts to identify stages during the life cycle when biases develop. We investigated the demographic correlates of sex-ratio variation in two chromosome races of Rumex hastatulus, an annual, wind-pollinated colonizer of open habitats from the southern USA. We examined sex ratios in 46 populations and evaluated the hypothesis that the proximity of males in the local mating environment, through its influence on gametophytic selection, is the primary cause of female-biased sex ratios. Female-biased sex ratios characterized most populations of R. hastatulus (mean sex ratio = 0.62), with significant female bias in 89% of populations. Large, high-density populations had the highest proportion of females, whereas smaller, low-density populations had sex ratios closer to equality. Progeny sex ratios were more female biased when males were in closer proximity to females, a result consistent with the gametophytic selection hypothesis. Our results suggest that interactions between demographic and genetic factors are probably the main cause of female-biased sex ratios in R. hastatulus. The annual life cycle of this species may limit the scope for selection against males and may account for the weaker degree of bias in comparison with perennial Rumex species.}, author = {Pickup, Melinda and Barrett, Spencer}, journal = {Ecology and Evolution}, number = {3}, pages = {629 -- 639}, publisher = {Wiley-Blackwell}, title = {{The influence of demography and local mating environment on sex ratios in a wind-pollinated dioecious plant}}, doi = {10.1002/ece3.465}, volume = {3}, year = {2013}, } @article{2282, abstract = {Epithelial spreading is a common and fundamental aspect of various developmental and disease-related processes such as epithelial closure and wound healing. A key challenge for epithelial tissues undergoing spreading is to increase their surface area without disrupting epithelial integrity. Here we show that orienting cell divisions by tension constitutes an efficient mechanism by which the enveloping cell layer (EVL) releases anisotropic tension while undergoing spreading during zebrafish epiboly. The control of EVL cell-division orientation by tension involves cell elongation and requires myosin II activity to align the mitotic spindle with the main tension axis. We also found that in the absence of tension-oriented cell divisions and in the presence of increased tissue tension, EVL cells undergo ectopic fusions, suggesting that the reduction of tension anisotropy by oriented cell divisions is required to prevent EVL cells from fusing. We conclude that cell-division orientation by tension constitutes a key mechanism for limiting tension anisotropy and thus promoting tissue spreading during EVL epiboly.}, author = {Campinho, Pedro and Behrndt, Martin and Ranft, Jonas and Risler, Thomas and Minc, Nicolas and Heisenberg, Carl-Philipp J}, journal = {Nature Cell Biology}, pages = {1405 -- 1414}, publisher = {Nature Publishing Group}, title = {{Tension-oriented cell divisions limit anisotropic tissue tension in epithelial spreading during zebrafish epiboly}}, doi = {10.1038/ncb2869}, volume = {15}, year = {2013}, } @article{2283, abstract = {Pathogens exert a strong selection pressure on organisms to evolve effective immune defences. In addition to individual immunity, social organisms can act cooperatively to produce collective defences. In many ant species, queens have the option to found a colony alone or in groups with other, often unrelated, conspecifics. These associations are transient, usually lasting only as long as each queen benefits from the presence of others. In fact, once the first workers emerge, queens fight to the death for dominance. One potential advantage of co-founding may be that queens benefit from collective disease defences, such as mutual grooming, that act against common soil pathogens. We test this hypothesis by exposing single and co-founding queens to a fungal parasite, in order to assess whether queens in co-founding associations have improved survival. Surprisingly, co-foundresses exposed to the entomopathogenic fungus Metarhizium did not engage in cooperative disease defences, and consequently, we find no direct benefit of multiple queens on survival. However, an indirect benefit was observed, with parasite-exposed queens producing more brood when they co-founded, than when they were alone. We suggest this is due to a trade-off between reproduction and immunity. Additionally, we report an extraordinary ability of the queens to tolerate an infection for long periods after parasite exposure. Our study suggests that there are no social immunity benefits for co-founding ant queens, but that in parasite-rich environments, the presence of additional queens may nevertheless improve the chances of colony founding success.}, author = {Pull, Christopher and Hughes, William and Brown, Markus}, journal = {Naturwissenschaften}, number = {12}, pages = {1125 -- 1136}, publisher = {Springer}, title = {{Tolerating an infection: an indirect benefit of co-founding queen associations in the ant Lasius niger }}, doi = {10.1007/s00114-013-1115-5}, volume = {100}, year = {2013}, } @article{2286, abstract = {The spatiotemporal control of cell divisions is a key factor in epithelial morphogenesis and patterning. Mao et al (2013) now describe how differential rates of proliferation within the Drosophila wing disc epithelium give rise to anisotropic tissue tension in peripheral/proximal regions of the disc. Such global tissue tension anisotropy in turn determines the orientation of cell divisions by controlling epithelial cell elongation.}, author = {Campinho, Pedro and Heisenberg, Carl-Philipp J}, journal = {EMBO Journal}, number = {21}, pages = {2783 -- 2784}, publisher = {Wiley-Blackwell}, title = {{The force and effect of cell proliferation}}, doi = {10.1038/emboj.2013.225}, volume = {32}, year = {2013}, } @article{2289, abstract = {Formal verification aims to improve the quality of software by detecting errors before they do harm. At the basis of formal verification is the logical notion of correctness, which purports to capture whether or not a program behaves as desired. We suggest that the boolean partition of software into correct and incorrect programs falls short of the practical need to assess the behavior of software in a more nuanced fashion against multiple criteria. We therefore propose to introduce quantitative fitness measures for programs, specifically for measuring the function, performance, and robustness of reactive programs such as concurrent processes. This article describes the goals of the ERC Advanced Investigator Project QUAREM. The project aims to build and evaluate a theory of quantitative fitness measures for reactive models. Such a theory must strive to obtain quantitative generalizations of the paradigms that have been success stories in qualitative reactive modeling, such as compositionality, property-preserving abstraction and abstraction refinement, model checking, and synthesis. The theory will be evaluated not only in the context of software and hardware engineering, but also in the context of systems biology. In particular, we will use the quantitative reactive models and fitness measures developed in this project for testing hypotheses about the mechanisms behind data from biological experiments.}, author = {Henzinger, Thomas A}, journal = {Computer Science Research and Development}, number = {4}, pages = {331 -- 344}, publisher = {Springer}, title = {{Quantitative reactive modeling and verification}}, doi = {10.1007/s00450-013-0251-7}, volume = {28}, year = {2013}, } @article{2290, abstract = {The plant hormone indole-acetic acid (auxin) is essential for many aspects of plant development. Auxin-mediated growth regulation typically involves the establishment of an auxin concentration gradient mediated by polarly localized auxin transporters. The localization of auxin carriers and their amount at the plasma membrane are controlled by membrane trafficking processes such as secretion, endocytosis, and recycling. In contrast to endocytosis or recycling, how the secretory pathway mediates the localization of auxin carriers is not well understood. In this study we have used the differential cell elongation process during apical hook development to elucidate the mechanisms underlying the post-Golgi trafficking of auxin carriers in Arabidopsis. We show that differential cell elongation during apical hook development is defective in Arabidopsis mutant echidna (ech). ECH protein is required for the trans-Golgi network (TGN)-mediated trafficking of the auxin influx carrier AUX1 to the plasma membrane. In contrast, ech mutation only marginally perturbs the trafficking of the highly related auxin influx carrier LIKE-AUX1-3 or the auxin efflux carrier PIN-FORMED-3, both also involved in hook development. Electron tomography reveals that the trafficking defects in ech mutant are associated with the perturbation of secretory vesicle genesis from the TGN. Our results identify differential mechanisms for the post-Golgi trafficking of de novo-synthesized auxin carriers to plasma membrane from the TGN and reveal how trafficking of auxin influx carriers mediates the control of differential cell elongation in apical hook development.}, author = {Boutté, Yohann and Jonsson, Kristoffer and Mcfarlane, Heather and Johnson, Errin and Gendre, Delphine and Swarup, Ranjan and Friml, Jirí and Samuels, Lacey and Robert, Stéphanie and Bhalerao, Rishikesh}, journal = {PNAS}, number = {40}, pages = {16259 -- 16264}, publisher = {National Academy of Sciences}, title = {{ECHIDNA mediated post Golgi trafficking of auxin carriers for differential cell elongation}}, doi = {10.1073/pnas.1309057110}, volume = {110}, year = {2013}, } @inproceedings{2294, abstract = {In this work we propose a system for automatic classification of Drosophila embryos into developmental stages. While the system is designed to solve an actual problem in biological research, we believe that the principle underly- ing it is interesting not only for biologists, but also for researchers in computer vision. The main idea is to combine two orthogonal sources of information: one is a classifier trained on strongly invariant features, which makes it applicable to images of very different conditions, but also leads to rather noisy predictions. The other is a label propagation step based on a more powerful similarity measure that however is only consistent within specific subsets of the data at a time. In our biological setup, the information sources are the shape and the staining patterns of embryo images. We show experimentally that while neither of the methods can be used by itself to achieve satisfactory results, their combina- tion achieves prediction quality comparable to human performance.}, author = {Kazmar, Tomas and Kvon, Evgeny and Stark, Alexander and Lampert, Christoph}, location = {Sydney, Australia}, publisher = {IEEE}, title = {{Drosophila Embryo Stage Annotation using Label Propagation}}, doi = {10.1109/ICCV.2013.139}, year = {2013}, } @proceedings{2292, abstract = {This book constitutes the thoroughly refereed conference proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013, held in Klosterneuburg, Austria, in August 2013. The 67 revised full papers presented together with six invited talks were carefully selected from 191 submissions. Topics covered include algorithmic game theory, algorithmic learning theory, algorithms and data structures, automata, formal languages, bioinformatics, complexity, computational geometry, computer-assisted reasoning, concurrency theory, databases and knowledge-based systems, foundations of computing, logic in computer science, models of computation, semantics and verification of programs, and theoretical issues in artificial intelligence.}, editor = {Chatterjee, Krishnendu and Sgall, Jiri}, isbn = {978-3-642-40312-5}, location = {Klosterneuburg, Austria}, pages = {VI -- 854}, publisher = {Springer}, title = {{Mathematical Foundations of Computer Science 2013}}, doi = {10.1007/978-3-642-40313-2}, volume = {8087}, year = {2013}, } @inproceedings{2293, abstract = {Many computer vision problems have an asymmetric distribution of information between training and test time. In this work, we study the case where we are given additional information about the training data, which however will not be available at test time. This situation is called learning using privileged information (LUPI). We introduce two maximum-margin techniques that are able to make use of this additional source of information, and we show that the framework is applicable to several scenarios that have been studied in computer vision before. Experiments with attributes, bounding boxes, image tags and rationales as additional information in object classification show promising results.}, author = {Sharmanska, Viktoriia and Quadrianto, Novi and Lampert, Christoph}, location = {Sydney, Australia}, pages = {825 -- 832}, publisher = {IEEE}, title = {{Learning to rank using privileged information}}, doi = {10.1109/ICCV.2013.107}, year = {2013}, } @inproceedings{2291, abstract = {Cryptographic access control promises to offer easily distributed trust and broader applicability, while reducing reliance on low-level online monitors. Traditional implementations of cryptographic access control rely on simple cryptographic primitives whereas recent endeavors employ primitives with richer functionality and security guarantees. Worryingly, few of the existing cryptographic access-control schemes come with precise guarantees, the gap between the policy specification and the implementation being analyzed only informally, if at all. In this paper we begin addressing this shortcoming. Unlike prior work that targeted ad-hoc policy specification, we look at the well-established Role-Based Access Control (RBAC) model, as used in a typical file system. In short, we provide a precise syntax for a computational version of RBAC, offer rigorous definitions for cryptographic policy enforcement of a large class of RBAC security policies, and demonstrate that an implementation based on attribute-based encryption meets our security notions. We view our main contribution as being at the conceptual level. Although we work with RBAC for concreteness, our general methodology could guide future research for uses of cryptography in other access-control models. }, author = {Ferrara, Anna and Fuchsbauer, Georg and Warinschi, Bogdan}, location = {New Orleans, LA, United States}, pages = {115 -- 129}, publisher = {IEEE}, title = {{Cryptographically enforced RBAC}}, doi = {10.1109/CSF.2013.15}, year = {2013}, } @proceedings{2288, abstract = {This book constitutes the proceedings of the 11th International Conference on Computational Methods in Systems Biology, CMSB 2013, held in Klosterneuburg, Austria, in September 2013. The 15 regular papers included in this volume were carefully reviewed and selected from 27 submissions. They deal with computational models for all levels, from molecular and cellular, to organs and entire organisms.}, editor = {Gupta, Ashutosh and Henzinger, Thomas A}, isbn = {978-3-642-40707-9}, location = {Klosterneuburg, Austria}, publisher = {Springer}, title = {{Computational Methods in Systems Biology}}, doi = {10.1007/978-3-642-40708-6}, volume = {8130}, year = {2013}, } @inproceedings{2298, abstract = {We present a shape analysis for programs that manipulate overlaid data structures which share sets of objects. The abstract domain contains Separation Logic formulas that (1) combine a per-object separating conjunction with a per-field separating conjunction and (2) constrain a set of variables interpreted as sets of objects. The definition of the abstract domain operators is based on a notion of homomorphism between formulas, viewed as graphs, used recently to define optimal decision procedures for fragments of the Separation Logic. Based on a Frame Rule that supports the two versions of the separating conjunction, the analysis is able to reason in a modular manner about non-overlaid data structures and then, compose information only at a few program points, e.g., procedure returns. We have implemented this analysis in a prototype tool and applied it on several interesting case studies that manipulate overlaid and nested linked lists. }, author = {Dragoi, Cezara and Enea, Constantin and Sighireanu, Mihaela}, location = {Seattle, WA, United States}, pages = {150 -- 171}, publisher = {Springer}, title = {{Local shape analysis for overlaid data structures}}, doi = {10.1007/978-3-642-38856-9_10}, volume = {7935}, year = {2013}, } @article{2299, abstract = {The standard hardware design flow involves: (a) design of an integrated circuit using a hardware description language, (b) extensive functional and formal verification, and (c) logical synthesis. However, the above-mentioned processes consume significant effort and time. An alternative approach is to use a formal specification language as a high-level hardware description language and synthesize hardware from formal specifications. Our work is a case study of the synthesis of the widely and industrially used AMBA AHB protocol from formal specifications. Bloem et al. presented the first formal specifications for the AMBA AHB Arbiter and synthesized the AHB Arbiter circuit. However, in the first formal specification some important assumptions were missing. Our contributions are as follows: (a) We present detailed formal specifications for the AHB Arbiter incorporating the missing details, and obtain significant improvements in the synthesis results (both with respect to the number of gates in the synthesized circuit and with respect to the time taken to synthesize the circuit), and (b) we present formal specifications to generate compact circuits for the remaining two main components of AMBA AHB, namely, AHB Master and AHB Slave. Thus with systematic description we are able to automatically and completely synthesize an important and widely used industrial protocol.}, author = {Godhal, Yashdeep and Chatterjee, Krishnendu and Henzinger, Thomas A}, journal = {International Journal on Software Tools for Technology Transfer}, number = {5-6}, pages = {585 -- 601}, publisher = {Springer}, title = {{Synthesis of AMBA AHB from formal specification: A case study}}, doi = {10.1007/s10009-011-0207-9}, volume = {15}, year = {2013}, } @article{2297, abstract = {We present an overview of mathematical results on the low temperature properties of dilute quantum gases, which have been obtained in the past few years. The presentation includes a discussion of Bose-Einstein condensation, the excitation spectrum for trapped gases and its relation to superfluidity, as well as the appearance of quantized vortices in rotating systems. All these properties are intensely being studied in current experiments on cold atomic gases. We will give a description of the mathematics involved in understanding these phenomena, starting from the underlying many-body Schrödinger equation.}, author = {Seiringer, Robert}, journal = {Japanese Journal of Mathematics}, number = {2}, pages = {185 -- 232}, publisher = {Springer}, title = {{Hot topics in cold gases: A mathematical physics perspective}}, doi = {10.1007/s11537-013-1264-5}, volume = {8}, year = {2013}, } @book{2306, abstract = {Das Buch ist sowohl eine Einführung in die Themen Linked Data, Open Data und Open Linked Data als es auch den konkreten Bezug auf Bibliotheken behandelt. Hierzu werden konkrete Anwendungsprojekte beschrieben. Der Band wendet sich dabei sowohl an Personen aus der Bibliothekspraxis als auch an Personen aus dem Bibliotheksmanagement, die noch nicht mit dem Thema vertraut sind.}, author = {Danowski, Patrick and Pohl, Adrian}, isbn = { 978-3-11-027634-3}, issn = {2191-3587}, publisher = {De Gruyter}, title = {{(Open) Linked Data in Bibliotheken}}, doi = {10.1515/9783110278736}, volume = {50}, year = {2013}, } @inproceedings{2301, abstract = {We describe the design and implementation of P, a domain-specific language to write asynchronous event driven code. P allows the programmer to specify the system as a collection of interacting state machines, which communicate with each other using events. P unifies modeling and programming into one activity for the programmer. Not only can a P program be compiled into executable code, but it can also be tested using model checking techniques. P allows the programmer to specify the environment, used to "close" the system during testing, as nondeterministic ghost machines. Ghost machines are erased during compilation to executable code; a type system ensures that the erasure is semantics preserving. The P language is designed so that a P program can be checked for responsiveness-the ability to handle every event in a timely manner. By default, a machine needs to handle every event that arrives in every state. But handling every event in every state is impractical. The language provides a notion of deferred events where the programmer can annotate when she wants to delay processing an event. The default safety checker looks for presence of unhan-dled events. The language also provides default liveness checks that an event cannot be potentially deferred forever. P was used to implement and verify the core of the USB device driver stack that ships with Microsoft Windows 8. The resulting driver is more reliable and performs better than its prior incarnation (which did not use P); we have more confidence in the robustness of its design due to the language abstractions and verification provided by P.}, author = {Desai, Ankush and Gupta, Vivek and Jackson, Ethan and Qadeer, Shaz and Rajamani, Sriram and Zufferey, Damien}, booktitle = {Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation}, location = {Seattle, WA, United States}, pages = {321 -- 331}, publisher = {ACM}, title = {{P: Safe asynchronous event-driven programming}}, doi = {10.1145/2491956.2462184}, year = {2013}, } @article{2300, abstract = {We consider Ising models in two and three dimensions with nearest neighbor ferromagnetic interactions and long-range, power law decaying, antiferromagnetic interactions. If the strength of the ferromagnetic coupling J is larger than a critical value Jc, then the ground state is homogeneous and ferromagnetic. As the critical value is approached from smaller values of J, it is believed that the ground state consists of a periodic array of stripes (d=2) or slabs (d=3), all of the same size and alternating magnetization. Here we prove rigorously that the ground state energy per site converges to that of the optimal periodic striped or slabbed state, in the limit that J tends to the ferromagnetic transition point. While this theorem does not prove rigorously that the ground state is precisely striped or slabbed, it does prove that in any suitably large box the ground state is striped or slabbed with high probability.}, author = {Giuliani, Alessandro and Lieb, Élliott and Seiringer, Robert}, journal = {Physical Review B}, number = {6}, publisher = {American Physical Society}, title = {{Realization of stripes and slabs in two and three dimensions}}, doi = {10.1103/PhysRevB.88.064401}, volume = {88}, year = {2013}, } @article{2303, abstract = {MADM (Mosaic Analysis with Double Markers) technology offers a genetic approach in mice to visualize and concomitantly manipulate genetically defined cells at clonal level and single cell resolution. MADM employs Cre recombinase/loxP-dependent interchromosomal mitotic recombination to reconstitute two split marker genes—green GFP and red tdTomato—and can label sparse clones of homozygous mutant cells in one color and wild-type cells in the other color in an otherwise unlabeled background. At present, major MADM applications include lineage tracing, single cell labeling, conditional knockouts in small populations of cells and induction of uniparental chromosome disomy to assess effects of genomic imprinting. MADM can be applied universally in the mouse with the sole limitation being the specificity of the promoter controlling Cre recombinase expression. Here I review recent developments and extensions of the MADM technique and give an overview of the major discoveries and progresses enabled by the implementation of the novel genetic MADM tools.}, author = {Hippenmeyer, Simon}, journal = {Frontiers in Biology}, number = {6}, pages = {557 -- 568}, publisher = {Springer}, title = {{Dissection of gene function at clonal level using mosaic analysis with double markers}}, doi = {10.1007/s11515-013-1279-6}, volume = {8}, year = {2013}, } @article{2304, abstract = {This extended abstract is concerned with the irregularities of distribution of one-dimensional permuted van der Corput sequences that are generated from linear permutations. We show how to obtain upper bounds for the discrepancy and diaphony of these sequences, by relating them to Kronecker sequences and applying earlier results of Faure and Niederreiter.}, author = {Pausinger, Florian}, journal = {Electronic Notes in Discrete Mathematics}, pages = {43 -- 50}, publisher = {Elsevier}, title = {{Van der Corput sequences and linear permutations}}, doi = {10.1016/j.endm.2013.07.008}, volume = {43}, year = {2013}, } @inproceedings{2315, abstract = { We study the effects of random scatterers on the ground state of the one-dimensional Lieb-Liniger model of interacting bosons on the unit interval in the Gross-Pitaevskii regime. We prove that Bose Einstein condensation survives even a strong random potential with a high density of scatterers. The character of the wave function of the condensate, however, depends in an essential way on the interplay between randomness and the strength of the two-body interaction. For low density of scatterers or strong interactions the wave function extends over the whole interval. High density of scatterers and weak interaction, on the other hand, leads to localization of the wave function in a fragmented subset of the interval. }, author = {Seiringer, Robert and Yngvason, Jakob and Zagrebnov, Valentin}, pages = {610--619}, publisher = {World Scientific Publishing}, title = {{Disordered Bose-Einstein condensates with interaction}}, doi = {10.1142/9789814449243_0063}, year = {2013}, } @inproceedings{2319, abstract = {In a recent paper [7] we give the first rigorous derivation of the celebrated Ginzburg-Landau (GL)theory, starting from the microscopic Bardeen- Cooper-Schrieffer (BCS)model. Here we present our results in the simplified case of a one-dimensional system of particles interacting via a δ-potential.}, author = {Frank, Rupert L and Hainzl, Christian and Robert Seiringer and Solovej, Jan P}, pages = {57 -- 88}, publisher = {Springer}, title = {{ Derivation of Ginzburg-Landau theory for a one-dimensional system with contact interaction}}, doi = {10.1007/978-3-0348-0531-5_3}, year = {2013}, } @inproceedings{2328, abstract = {Linearizability of concurrent data structures is usually proved by monolithic simulation arguments relying on identifying the so-called linearization points. Regrettably, such proofs, whether manual or automatic, are often complicated and scale poorly to advanced non-blocking concurrency patterns, such as helping and optimistic updates. In response, we propose a more modular way of checking linearizability of concurrent queue algorithms that does not involve identifying linearization points. We reduce the task of proving linearizability with respect to the queue specification to establishing four basic properties, each of which can be proved independently by simpler arguments. As a demonstration of our approach, we verify the Herlihy and Wing queue, an algorithm that is challenging to verify by a simulation proof.}, author = {Henzinger, Thomas A and Sezgin, Ali and Vafeiadis, Viktor}, location = {Buenos Aires, Argentina}, pages = {242 -- 256}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Aspect-oriented linearizability proofs}}, doi = {10.1007/978-3-642-40184-8_18}, volume = {8052}, year = {2013}, } @article{2404, abstract = {The Lieb-Thirring inequalities give a bound on the negative eigenvalues of a Schrödinger operator in terms of an Lp-norm of the potential. These are dual to bounds on the H1-norms of a system of orthonormal functions. Here we extend these bounds to analogous inequalities for perturbations of the Fermi sea of noninteracting particles (i.e., for perturbations of the continuous spectrum of the Laplacian by local potentials).}, author = {Frank, Rupert L and Lewin, Mathieu and Lieb, Élliott H and Robert Seiringer}, journal = {Duke Mathematical Journal}, number = {3}, pages = {435 -- 495}, publisher = {Duke University Press}, title = {{A positive density analogue of the Lieb-Thirring inequality}}, doi = {10.1215/00127094-2019477}, volume = {162}, year = {2013}, } @article{2406, abstract = {We study the effects of random scatterers on the ground state of the one-dimensional Lieb-Liniger model of interacting bosons on the unit interval. We prove that, in the Gross-Pitaevskii limit, Bose Einstein condensation takes place in the whole parameter range considered. The character of the wave function of the condensate, however, depends in an essential way on the interplay between randomness and the strength of the two-body interaction. For low density of scatterers or strong interactions the wave function extends over the whole interval. High density of scatterers and weak interaction, on the other hand, leads to localization of the wave function in a fragmented subset of the unit interval.}, author = {Robert Seiringer and Yngvason, Jakob and Zagrebnov, Valentin A}, journal = {European Physical Journal: Special Topics}, number = {1}, pages = {103 -- 107}, publisher = {Springer}, title = {{Condensation of interacting bosons in a random potential}}, doi = {10.1140/epjst/e2013-01759-5}, volume = {217}, year = {2013}, } @article{2405, abstract = {We consider the bipolaron in the Pekar-Tomasevich approximation and address the question whether the ground state is spherically symmetric or not. Numerical analysis has, so far, not completely settled the question. Our contribution is to prove rigorously that the ground state remains spherical for small values of the electron-electron Coulomb repulsion.}, author = {Frank, Rupert L and Lieb, Élliott H and Robert Seiringer}, journal = {Communications in Mathematical Physics}, number = {2}, pages = {557 -- 573}, publisher = {Springer}, title = {{Symmetry of bipolaron bound states for small Coulomb repulsion}}, doi = {10.1007/s00220-012-1604-y}, volume = {319}, year = {2013}, }