@article{232, abstract = {We study the average order of the divisor function, as it ranges over the values of binary quartic forms that are reducible over ℚ.}, author = {De La Bretèche, Régis and Browning, Timothy D}, journal = {Journal fur die Reine und Angewandte Mathematik}, number = {646}, pages = {1 -- 44}, publisher = {Walter de Gruyter}, title = {{Le problème des diviseurs pour des formes binaires de degré 4}}, doi = {10.1515/CRELLE.2010.064}, year = {2010}, } @inproceedings{2322, author = {Frank, Rupert L and Lieb, Élliott H and Robert Seiringer}, pages = {523 -- 535}, publisher = {World Scientific Publishing}, title = {{ Equivalence of Sobolev inequalities and Lieb-Thirring inequalities}}, doi = {10.1142/9789814304634_0045 }, year = {2010}, } @inproceedings{2323, abstract = {Since the first experimental realization of Bose-Einstein condensation in cold atomic gases in 1995 there has been a surge of activity in this field. Ingenious experiments have allowed us to probe matter close to zero temperature and reveal some of the fascinating effects quantum mechanics has bestowed on nature. It is a challenge for mathematical physicists to understand these various phenomena from first principles, that is, starting from the underlying many-body Schrödinger equation. Recent progress in this direction concerns mainly equilibrium properties of dilute, cold quantum gases. We shall explain some of the results in this article, and describe the mathematics involved in understanding these phenomena. Topics include the ground state energy and the free energy at positive temperature, the effect of interparticle interaction on the critical temperature for Bose-Einstein condensation, as well as the occurrence of superfluidity and quantized vortices in rapidly rotating gases.}, author = {Robert Seiringer}, pages = {231 -- 245}, publisher = {World Scientific Publishing}, title = {{Hot topics on cold gases}}, doi = {10.1142/9789814304634_0013}, year = {2010}, } @inbook{2324, abstract = {We determine the sharp constant in the Hardy inequality for fractional Sobolev spaces on half-spaces. Our proof relies on a nonlinear and nonlocal version of the ground state representation.}, author = {Frank, Rupert L and Robert Seiringer}, booktitle = {Around the Research of Vladimir Maz'ya I}, pages = {161 -- 167}, publisher = {Springer}, title = {{Sharp fractional Hardy inequalities in half-spaces}}, doi = {10.1007/978-1-4419-1341-8_6}, volume = {11}, year = {2010}, } @article{2389, abstract = {We study the eigenvalues of Schrödinger type operators T + λV and their asymptotic behavior in the small coupling limit λ → 0, in the case where the symbol of the kinetic energy, T (p), strongly degenerates on a non-trivial manifold of codimension one.}, author = {Hainzl, Christian and Robert Seiringer}, journal = {Mathematische Nachrichten}, number = {3}, pages = {489 -- 499}, publisher = {Wiley-Blackwell}, title = {{Asymptotic behavior of eigenvalues of Schrödinger type operators with degenerate kinetic energy}}, doi = {10.1002/mana.200810195}, volume = {283}, year = {2010}, } @article{2392, abstract = {The binding of polarons, or its absence, is an old and subtle topic. Here we prove two things rigorously. First, the transition from many-body collapse to the existence of a thermodynamic limit for N polarons occurs precisely at U=2α, where U is the electronic Coulomb repulsion and α is the polaron coupling constant. Second, if U is large enough, there is no multipolaron binding of any kind. Considering the known fact that there is binding for some U>2α, these conclusions are not obvious and their proof has been an open problem for some time.}, author = {Frank, Rupert L and Lieb, Élliott H and Robert Seiringer and Thomas, Lawrence E}, journal = {Physical Review Letters}, number = {21}, publisher = {American Physical Society}, title = {{Bipolaron and N-polaron binding energies}}, doi = {10.1103/PhysRevLett.104.210402}, volume = {104}, year = {2010}, } @article{2409, abstract = {Background: The availability of many gene alignments with overlapping taxon sets raises the question of which strategy is the best to infer species phylogenies from multiple gene information. Methods and programs abound that use the gene alignment in different ways to reconstruct the species tree. In particular, different methods combine the original data at different points along the way from the underlying sequences to the final tree. Accordingly, they are classified into superalignment, supertree and medium-level approaches. Here, we present a simulation study to compare different methods from each of these three approaches. Results: We observe that superalignment methods usually outperform the other approaches over a wide range of parameters including sparse data and gene-specific evolutionary parameters. In the presence of high incongruency among gene trees, however, other combination methods show better performance than the superalignment approach. Surprisingly, some supertree and medium-level methods exhibit, on average, worse results than a single gene phylogeny with complete taxon information. Conclusions: For some methods, using the reconstructed gene tree as an estimation of the species tree is superior to the combination of incomplete information. Superalignment usually performs best since it is less susceptible to stochastic error. Supertree methods can outperform superalignment in the presence of gene-tree conflict.}, author = {Kupczok, Anne and Schmidt, Heiko and Von Haeseler, Arndt}, journal = {Algorithms for Molecular Biology}, number = {1}, publisher = {BioMed Central}, title = {{Accuracy of phylogeny reconstruction methods combining overlapping gene data sets }}, doi = {10.1186/1748-7188-5-37}, volume = {5}, year = {2010}, } @article{2435, abstract = {We consider a generalization of the van Kampen-Flores Theorem and relate it to the long-standing g-conjecture for simplicial spheres. }, author = {Nevo, Eran and Uli Wagner}, journal = {Israel Journal of Mathematics}, number = {1}, pages = {381 -- 402}, publisher = {Springer}, title = {{On the embeddability of skeleta of spheres}}, doi = {10.1007/s11856-009-0119-5}, volume = {174}, year = {2010}, } @article{7078, abstract = {We report resonant ultrasound spectroscopy (RUS), dilatometry/magnetostriction, magnetotransport, magnetization, specific-heat, and 119Sn Mössbauer spectroscopy measurements on SnTe and Sn0.995Cr0.005Te. Hall measurements at T=77 K indicate that our Bridgman-grown single crystals have a p-type carrier concentration of 3.4×1019 cm−3 and that our Cr-doped crystals have an n-type concentration of 5.8×1022 cm−3. Although our SnTe crystals are diamagnetic over the temperature range 2≤T≤1100 K, the Cr-doped crystals are room-temperature ferromagnets with a Curie temperature of 294 K. For each sample type, three-terminal capacitive dilatometry measurements detect a subtle 0.5 μm distortion at Tc≈85 K. Whereas our RUS measurements on SnTe show elastic hardening near the structural transition, pointing to co-elastic behavior, similar measurements on Sn0.995Cr0.005Te show a pronounced softening, pointing to ferroelastic behavior. Effective Debye temperature, θD, values of SnTe obtained from 119Sn Mössbauer studies show a hardening of phonons in the range 60–115 K (θD=162 K) as compared with the 100–300 K range (θD=150 K). In addition, a precursor softening extending over approximately 100 K anticipates this collapse at the critical temperature and quantitative analysis over three decades of its reduced modulus finds ΔC44/C44=A|(T−T0)/T0|−κ with κ=0.50±0.02, a value indicating a three-dimensional softening of phonon branches at a temperature T0∼75 K, considerably below Tc. We suggest that the differences in these two types of elastic behaviors lie in the absence of elastic domain-wall motion in the one case and their nucleation in the other.}, author = {Salje, E. K. H. and Safarik, D. J. and Modic, Kimberly A and Gubernatis, J. E. and Cooley, J. C. and Taylor, R. D. and Mihaila, B. and Saxena, A. and Lookman, T. and Smith, J. L. and Fisher, R. A. and Pasternak, M. and Opeil, C. P. and Siegrist, T. and Littlewood, P. B. and Lashley, J. C.}, issn = {1098-0121}, journal = {Physical Review B}, number = {18}, publisher = {APS}, title = {{Tin telluride: A weakly co-elastic metal}}, doi = {10.1103/physrevb.82.184112}, volume = {82}, year = {2010}, } @article{7079, abstract = {We have observed that reacting Pb:Te:Ag:Se in a 1:1:1.9:1 molar ratio gives rise to what appears to be a predominantly single-phase alloy, which crystallizes in the PbSe cF8 fcc structure. However, further investigation of the structure using energy dispersive x-ray analysis reveals the presence of two phases, PbSe and β-Ag2Te, with identical lattice parameters. The total thermal conductivity of the formed alloy is remarkably low for a crystalline material, κT<0.6W∕mK at 675K, it is reproducible, and in addition, the compound has good mechanical properties.}, author = {Drymiotis, Fivos R. and Drye, Tyler B. and Wang, Yisha and He, Jian and Rhodes, Daniel and Modic, Kimberly A and Cawthorne, Samantha and Zhang, Qiu Run}, issn = {0021-8979}, journal = {Journal of Applied Physics}, number = {3}, publisher = {AIP}, title = {{Structure formation and very low thermal conductivity in Pb:Te:Ag:Se mixtures}}, doi = {10.1063/1.3284946}, volume = {107}, year = {2010}, } @article{7318, abstract = {The decomposition reaction of H2O2 aqueous solutions (H2O2 - H2O + 1/2O2) catalyzed by transition metal oxide powders has been compared with the charging voltage of nonaqueous Li-O2 cells containing the same catalyst. An inverse linear relationship between Ln k (rate constant for the H2O2 decomposition) and the charging voltage has been found, despite differences in media and possible mechanistic differences. The results suggest that the decomposition may be a reliable, useful, and fast screening tool for materials that promote the charging process of the Li-O2 battery and may ultimately give insight into the charging mechanism.}, author = {Giordani, V. and Freunberger, Stefan Alexander and Bruce, P. G. and Tarascon, J.-M. and Larcher, D.}, issn = {1099-0062}, journal = {Electrochemical and Solid-State Letters}, number = {12}, publisher = {The Electrochemical Society}, title = {{H2O2 decomposition reaction as selecting tool for catalysts in Li–O2 cells}}, doi = {10.1149/1.3494045}, volume = {13}, year = {2010}, } @inproceedings{754, abstract = {Most people believe that renaming is easy: simply choose a name at random; if more than one process selects the same name, then try again. We highlight the issues that occur when trying to implement such a scheme and shed new light on the read-write complexity of randomized renaming in an asynchronous environment. At the heart of our new perspective stands an adaptive implementation of a randomized test-and-set object, that has poly-logarithmic step complexity per operation, with high probability. Interestingly, our implementation is anonymous, as it does not require process identifiers. Based on this implementation, we present two new randomized renaming algorithms. The first ensures a tight namespace of n names using O( n log4 n) total steps, with high probability. This significantly improves on the complexity of the best previously known namespace-optimal algorithms. The second algorithm achieves a namespace of size k (1 + ε) using O( k log4 k / log2 (1 + ε) ) total steps, both with high probability, where k is the total contention in the execution. It is the first adaptive randomized renaming algorithm, and it improves on existing deterministic solutions by providing a smaller namespace, and by lowering step complexity.}, author = {Alistarh, Dan-Adrian and Attiya, Hagit and Gilbert, Seth and Giurgiu, Andrei and Guerraoui, Rachid}, pages = {94 -- 108}, publisher = {Springer}, title = {{Fast randomized test-and-set and renaming}}, doi = {10.1007/978-3-642-15763-9_9}, volume = {6343 LNCS}, year = {2010}, } @inproceedings{755, abstract = {Gossip, also known as epidemic dissemination, is becoming an increasingly popular technique in distributed systems. Yet, it has remained a partially open question: how robust are such protocols? We consider a natural extension of the random phone-call model (introduced by Karp et al. [1]), and we analyze two different notions of robustness: the ability to tolerate adaptive failures, and the ability to tolerate oblivious failures. For adaptive failures, we present a new gossip protocol, TrickleGossip, which achieves near-optimal O(n log 3 n) message complexity. To the best of our knowledge, this is the first epidemic-style protocol that can tolerate adaptive failures. We also show a direct relation between resilience and message complexity, demonstrating that gossip protocols which tolerate a large number of adaptive failures need to use a super-linear number of messages with high probability. For oblivious failures, we present a new gossip protocol, CoordinatedGossip, that achieves optimal O(n) message complexity. This protocol makes novel use of the universe reduction technique to limit the message complexity.}, author = {Alistarh, Dan-Adrian and Gilbert, Seth and Guerraoui, Rachid and Zadimoghaddam, Morteza}, number = {PART 2}, pages = {115 -- 126}, publisher = {Springer}, title = {{How efficient can gossip be? (On the cost of resilient information exchange)}}, doi = {10.1007/978-3-642-14162-1_10}, volume = {6199 LNCS}, year = {2010}, } @inproceedings{756, abstract = {This paper studies non-cryptographic authenticated broadcast in radio networks subject to malicious failures. We introduce two protocols that address this problem. The first, NeighborWatchRB, makes use of a novel strategy in which honest devices monitor their neighbors for malicious behavior. Second, we present a more robust variant, MultiPathRB, that tolerates the maximum possible density of malicious devices per region, using an elaborate voting strategy. We also introduce a new proof technique to show that both protocols ensure asymptotically optimal running time. We demonstrate the fault tolerance of our protocols through extensive simulation. Simulations show the practical superiority of the NeighborWatchRB protocol (an advantage hidden in the constants of the asymptotic complexity). The NeighborWatchRB protocol even performs relatively well when compared to the simple, fast epidemic protocols commonly used in the radio setting, protocols that tolerate no malicious faults. We therefore believe that the overhead for ensuring authenticated broadcast is reasonable, especially in applications that use authenticated broadcast only when necessary, such as distributing an authenticated digest.}, author = {Alistarh, Dan-Adrian and Gilbert, Seth and Guerraoui, Rachid and Milošević, Žarko and Newport, Calvin}, pages = {50 -- 59}, publisher = {ACM}, title = {{Securing every bit: Authenticated broadcast in radio networks}}, doi = {10.1145/1810479.1810489}, year = {2010}, } @inproceedings{758, abstract = {Set agreement [4] is a fundamental problem in distributed computing, in which processes collectively choose a small subset of values from a larger set of proposals. Set agreement has been extensively studied in both synchronous and asynchronous systems [10,11,3,5,8,9]. Real world distributed systems, however, are neither purely synchronous nor purely asynchronous. To describe such a system, Dwork et al. [6] introduced the idea of partial synchrony. They assume for every execution some (unknown) time GST (global stabilization time), after which the system is synchronous. In a recent paper [1,2], we study the complexity of set agreement in the context of partially synchronous systems, determining the minimum-sized window of synchrony in which set agreement can be solved. We show that at least ⌊t/k⌋ + 2 synchronous rounds are required for k-set agreement, where t < n is the number of crashes, and k is the agreement parameter of the set agreement task. We then introduce an algorithm that terminates in any window of synchrony of size at least ⌊t/k⌋ + 4 rounds. Together, these results tightly bound the inherent price of tolerating some asynchrony.}, author = {Alistarh, Dan-Adrian and Gilbert, Seth and Guerraoui, Rachid and Travers, Corentin}, pages = {404 -- 405}, publisher = {Springer}, title = {{Brief announcement: New bounds for partially synchronous set agreement}}, doi = {10.1007/978-3-642-15763-9_40}, volume = {6343 LNCS}, year = {2010}, } @article{7703, abstract = {By combining gene expression profiling with image registration, Tomer et al. (2010) find that the mushroom body of the segmented worm Platynereis dumerilii shares many features with the mammalian cerebral cortex. The authors propose that the mushroom body and cortex evolved from the same structure in the common ancestor of vertebrates and invertebrates.}, author = {Sweeney, Lora Beatrice Jaeger and Luo, Liqun}, issn = {0092-8674}, journal = {Cell}, number = {5}, pages = {679--681}, publisher = {Elsevier}, title = {{‘Fore brain: A hint of the ancestral cortex}}, doi = {10.1016/j.cell.2010.08.024}, volume = {142}, year = {2010}, } @article{474, abstract = {Classical models of gene flow fail in three ways: they cannot explain large-scale patterns; they predict much more genetic diversity than is observed; and they assume that loosely linked genetic loci evolve independently. We propose a new model that deals with these problems. Extinction events kill some fraction of individuals in a region. These are replaced by offspring from a small number of parents, drawn from the preexisting population. This model of evolution forwards in time corresponds to a backwards model, in which ancestral lineages jump to a new location if they are hit by an event, and may coalesce with other lineages that are hit by the same event. We derive an expression for the identity in allelic state, and show that, over scales much larger than the largest event, this converges to the classical value derived by Wright and Malécot. However, rare events that cover large areas cause low genetic diversity, large-scale patterns, and correlations in ancestry between unlinked loci.}, author = {Barton, Nicholas H and Kelleher, Jerome and Etheridge, Alison}, journal = {Evolution}, number = {9}, pages = {2701 -- 2715}, publisher = {Wiley-Blackwell}, title = {{A new model for extinction and recolonization in two dimensions: Quantifying phylogeography}}, doi = {10.1111/j.1558-5646.2010.01019.x}, volume = {64}, year = {2010}, } @inproceedings{488, abstract = {Streaming string transducers [1] define (partial) functions from input strings to output strings. A streaming string transducer makes a single pass through the input string and uses a finite set of variables that range over strings from the output alphabet. At every step, the transducer processes an input symbol, and updates all the variables in parallel using assignments whose right-hand-sides are concatenations of output symbols and variables with the restriction that a variable can be used at most once in a right-hand-side expression. It has been shown that streaming string transducers operating on strings over infinite data domains are of interest in algorithmic verification of list-processing programs, as they lead to PSPACE decision procedures for checking pre/post conditions and for checking semantic equivalence, for a well-defined class of heap-manipulating programs. In order to understand the theoretical expressiveness of streaming transducers, we focus on streaming transducers processing strings over finite alphabets, given the existence of a robust and well-studied class of "regular" transductions for this case. Such regular transductions can be defined either by two-way deterministic finite-state transducers, or using a logical MSO-based characterization. Our main result is that the expressiveness of streaming string transducers coincides exactly with this class of regular transductions. }, author = {Alur, Rajeev and Cerny, Pavol}, location = {Chennai, India}, pages = {1 -- 12}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Expressiveness of streaming string transducers}}, doi = {10.4230/LIPIcs.FSTTCS.2010.1}, volume = {8}, year = {2010}, } @inproceedings{489, abstract = {Graph games of infinite length are a natural model for open reactive processes: one player represents the controller, trying to ensure a given specification, and the other represents a hostile environment. The evolution of the system depends on the decisions of both players, supplemented by chance. In this work, we focus on the notion of randomised strategy. More specifically, we show that three natural definitions may lead to very different results: in the most general cases, an almost-surely winning situation may become almost-surely losing if the player is only allowed to use a weaker notion of strategy. In more reasonable settings, translations exist, but they require infinite memory, even in simple cases. Finally, some traditional problems becomes undecidable for the strongest type of strategies.}, author = {Cristau, Julien and David, Claire and Horn, Florian}, booktitle = {Proceedings of GandALF 2010}, location = {Minori, Amalfi Coast, Italy}, pages = {30 -- 39}, publisher = {Open Publishing Association}, title = {{How do we remember the past in randomised strategies? }}, doi = {10.4204/EPTCS.25.7}, volume = {25}, year = {2010}, } @article{533, abstract = {Any programming error that can be revealed before compiling a program saves precious time for the programmer. While integrated development environments already do a good job by detecting, e.g., data-flow abnormalities, current static analysis tools suffer from false positives ("noise") or require strong user interaction. We propose to avoid this deficiency by defining a new class of errors. A program fragment is doomed if its execution will inevitably fail, regardless of which state it is started in. We use a formal verification method to identify such errors fully automatically and, most significantly, without producing noise. We report on experiments with a prototype tool.}, author = {Hoenicke, Jochen and Leino, Kari and Podelski, Andreas and Schäf, Martin and Wies, Thomas}, journal = {Formal Methods in System Design}, number = {2-3}, pages = {171 -- 199}, publisher = {Springer}, title = {{Doomed program points}}, doi = {10.1007/s10703-010-0102-0}, volume = {37}, year = {2010}, }