TY - CONF AB - 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. AU - Henzinger, Monika H AU - Krinninger, Sebastian AU - Nanongkai, Danupon ID - 11793 SN - 1611-3349 T2 - 40th International Colloquium on Automata, Languages, and Programming TI - Sublinear-time maintenance of breadth-first spanning tree in partially dynamic networks VL - 7966 ER - TY - CONF AB - 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. AU - Dütting, Paul AU - Henzinger, Monika H AU - Starnberger, Martin ID - 11791 SN - 1611-3349 T2 - 9th International Conference on Web and Internet Economics TI - Valuation compressions in VCG-based combinatorial auctions VL - 8289 ER - TY - CONF AB - 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. AU - Dvořák, Wolfgang AU - Henzinger, Monika H AU - Williamson, David P. ID - 11792 SN - 1611-3349 T2 - 21st Annual European Symposium on Algorithms TI - Maximizing a submodular function with viability constraints VL - 8125 ER - TY - CONF AB - 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. AU - Henzinger, Monika H AU - Krinninger, Sebastian AU - Nanongkai, Danupon ID - 11856 SN - 0272-5428 T2 - 54th Annual Symposium on Foundations of Computer Science TI - Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization ER - TY - JOUR AB - 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. AU - Dütting, Paul AU - Henzinger, Monika H AU - Weber, Ingmar ID - 11902 IS - 3 JF - Theoretical Computer Science SN - 0304-3975 TI - Bidder optimal assignments for general utilities VL - 478 ER - TY - JOUR AB - 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. AU - Pieber, Bartholomäus AU - Martinez, Sabrina Teixeira AU - Cantillo, David AU - Kappe, C. Oliver ID - 11959 IS - 39 JF - Angewandte Chemie International Edition SN - 1433-7851 TI - In situ generation of diimide from hydrazine and oxygen: Continuous-flow transfer hydrogenation of olefins VL - 52 ER - TY - JOUR AB - 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. AU - Kappe, C. Oliver AU - Pieber, Bartholomäus AU - Dallinger, Doris ID - 11960 IS - 4 JF - Angewandte Chemie International Edition SN - 1433-7851 TI - Microwave effects in organic synthesis: Myth or reality? VL - 52 ER - TY - JOUR AB - 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. AU - Pieber, Bartholomäus AU - Kappe, C. Oliver ID - 11973 IS - 2 JF - Green Chemistry SN - 1463-9262 TI - Direct aerobic oxidation of 2-benzylpyridines in a gas-liquid continuous-flow regime using propylene carbonate as a solvent VL - 15 ER - TY - JOUR AB - 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. AU - Petersen, Lene AU - Pellicciotti, Francesca AU - Juszak, Inge AU - Carenzo, Marco AU - Brock, Ben ID - 12642 IS - 63 JF - Annals of Glaciology KW - Earth-Surface Processes SN - 0260-3055 TI - Suitability of a constant air temperature lapse rate over an Alpine glacier: Testing the Greuell and Böhm model as an alternative VL - 54 ER - TY - JOUR AB - 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. AU - Juszak, I. AU - Pellicciotti, Francesca ID - 12643 IS - 8 JF - Journal of Geophysical Research: Atmospheres KW - Space and Planetary Science KW - Earth and Planetary Sciences (miscellaneous) KW - Atmospheric Science KW - Geophysics SN - 2169-897X TI - A comparison of parameterizations of incoming longwave radiation over melting glaciers: Model robustness and seasonal variability VL - 118 ER - TY - JOUR AB - 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. AU - Immerzeel, W. W. AU - Pellicciotti, Francesca AU - Bierkens, M. F. P. ID - 12640 IS - 9 JF - Nature Geoscience KW - General Earth and Planetary Sciences SN - 1752-0894 TI - Rising river flows throughout the twenty-first century in two Himalayan glacierized watersheds VL - 6 ER - TY - JOUR AB - 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. AU - Heynen, Martin AU - Pellicciotti, Francesca AU - Carenzo, Marco ID - 12641 IS - 63 JF - Annals of Glaciology SN - 0260-3055 TI - Parameter sensitivity of a distributed enhanced temperature-index melt model VL - 54 ER - TY - JOUR AB - 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. AU - Haikala, Väinö AU - Maximilian Jösch AU - Borst, Alexander AU - Mauss, Alex S ID - 1304 IS - 34 JF - Journal of Neuroscience TI - Optogenetic control of fly optomotor responses VL - 33 ER - TY - JOUR AB - 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. AU - Maximilian Jösch AU - Weber, Franz AU - Eichner, Hubert AU - Borst, Alexander ID - 1305 IS - 3 JF - Journal of Neuroscience TI - Functional specialization of parallel motion detection circuits in the fly VL - 33 ER - TY - JOUR AB - 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. AU - Julian Fischer ID - 1308 IS - 3 JF - SIAM Journal on Mathematical Analysis TI - Advection-driven support shrinking in a chemotaxis model with degenerate mobility VL - 45 ER - TY - JOUR AB - 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. AU - Julian Fischer ID - 1307 IS - 11 JF - Communications in Partial Differential Equations TI - Uniqueness of solutions of the Derrida-Lebowitz-Speer-Spohn equation and quantum drift diffusion models VL - 38 ER - TY - JOUR AB - 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. AU - Julian Fischer ID - 1310 IS - 10 JF - Journal of Differential Equations TI - Optimal lower bounds on asymptotic support propagation rates for the thin-film equation VL - 255 ER - TY - CONF AB - 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. AU - Chatterjee, Krishnendu AU - Fijalkow, Nathanaël ID - 1374 T2 - 22nd EACSL Annual Conference on Computer Science Logic TI - Infinite-state games with finitary conditions VL - 23 ER - TY - CONF AB - 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. AU - Hofferek, Georg AU - Gupta, Ashutosh AU - Könighofer, Bettina AU - Jiang, Jie AU - Bloem, Roderick ID - 1385 T2 - 2013 Formal Methods in Computer-Aided Design TI - Synthesizing multiple boolean functions using interpolation on a single proof ER - TY - CONF AB - 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. AU - Boker, Udi AU - Kuperberg, Denis AU - Kupferman, Orna AU - Skrzypczak, Michał ID - 1387 IS - PART 2 TI - Nondeterminism in the presence of a diverse or unknown future VL - 7966 ER -