@article{217, abstract = {We show that the number of nontrivial rational points of height at most B, which lie on the cubic surface x1 x2 x3 = x4 (x1 + x2 + x3)2, has order of magnitude B (log B)6. This agrees with Manin's conjecture.}, author = {Timothy Browning}, journal = {Journal of Number Theory}, number = {2}, pages = {242 -- 283}, publisher = {Elsevier}, title = {{The density of rational points on a certain singular cubic surface}}, doi = {10.1016/j.jnt.2005.11.007}, volume = {119}, year = {2005}, } @article{2307, abstract = {The human norepinephrine (NE) transporter (hNET) attenuates neuronal signaling by rapid NE clearance from the synaptic cleft, and NET is a target for cocaine and amphetamines as well as therapeutics for depression, obsessive-compulsive disorder, and post-traumatic stress disorder. In spite of its central importance in the nervous system, little is known about how NET substrates, such as NE, 1-methyl-4-tetrahydropyridinium (MPP+), or amphetamine, interact with NET at the molecular level. Nor do we understand the mechanisms behind the transport rate. Previously we introduced a fluorescent substrate similar to MPP+, which allowed separate and simultaneous binding and transport measurement (Schwartz, J. W., Blakely, R. D., and DeFelice, L. J. (2003) J. Biol. Chem. 278, 9768-9777). Here we use this substrate, 4-(4-(dimethylamino)styrl)-N-methyl-pyridinium (ASP+), in combination with green fluorescent protein-tagged hNETs to measure substrate-transporter stoichiometry and substrate binding kinetics. Calibrated confocal microscopy and fluorescence correlation spectroscopy reveal that hNETs, which are homo-multimers, bind one substrate molecule per transporter subunit. Substrate residence at the transporter, obtained from rapid on-off kinetics revealed in fluorescence correlation spectroscopy, is 526 μs. Substrate residence obtained by infinite dilution is 1000 times slower. This novel examination of substrate-transporter kinetics indicates that a single ASP + molecule binds and unbinds thousands of times before being transported or ultimately dissociated from hNET. Calibrated fluorescent images combined with mass spectroscopy give a transport rate of 0.06 ASP +/hNET-protein/s, thus 36,000 on-off binding events (and 36 actual departures) occur for one transport event. Therefore binding has a low probability of resulting in transport. We interpret these data to mean that inefficient binding could contribute to slow transport rates.}, author = {Schwartz, Joel W and Gaia Novarino and Piston, David W and DeFelice, Louis J}, journal = {Journal of Biological Chemistry}, number = {19}, pages = {19177 -- 19184}, publisher = {American Society for Biochemistry and Molecular Biology}, title = {{Substrate binding stoichiometry and kinetics of the norepinephrine transporter}}, doi = {10.1074/jbc.M412923200}, volume = {280}, year = {2005}, } @book{2335, abstract = {This book contains a unique survey of the mathematically rigorous results about the quantum-mechanical many-body problem that have been obtained by the authors in the past seven years. It addresses a topic that is not only rich mathematically, using a large variety of techniques in mathematical analysis, but is also one with strong ties to current experiments on ultra-cold Bose gases and Bose-Einstein condensation. The book provides a pedagogical entry into an active area of ongoing research for both graduate students and researchers. It is an outgrowth of a course given by the authors for graduate students and post-doctoral researchers at the Oberwolfach Research Institute in 2004. The book also provides a coherent summary of the field and a reference for mathematicians and physicists active in research on quantum mechanics.}, author = {Lieb, Élliott and Seiringer, Robert and Solovej, Jan and Yngvason, Jakob}, isbn = {978-3-7643-7336-8}, pages = {VIII, 203}, publisher = {Birkhäuser Verlag}, title = {{The Mathematics of the Bose gas and its Condensation}}, doi = {10.1007/b137508}, volume = {34}, year = {2005}, } @inbook{2336, abstract = { Now that the low temperature properties of quantum-mechanical many-body systems (bosons) at low density, ρ, can be examined experimentally it is appropriate to revisit some of the formulas deduced by many authors 4–5 decades ago, and to explore new regimes not treated before. For systems with repulsive (i.e. positive) interaction potentials the experimental low temperature state and the ground state are effectively synonymous — and this fact is used in all modeling. In such cases, the leading term in the energy/particle is 2πħ2 aρ/m where a is the scattering length of the two-body potential. Owing to the delicate and peculiar nature of bosonic correlations (such as the strange N 7/5 law for charged bosons), four decades of research failed to establish this plausible formula rigorously. The only previous lower bound for the energy was found by Dyson in 1957, but it was 14 times too small. The correct asymptotic formula has been obtained by us and this work will be presented. The reason behind the mathematical difficulties will be emphasized. A different formula, postulated as late as 1971 by Schick, holds in two dimensions and this, too, will be shown to be correct. With the aid of the methodology developed to prove the lower bound for the homogeneous gas, several other problems have been successfully addressed. One is the proof by us that the Gross-Pitaevskii equation correctly describes the ground state in the ‘traps’ actually used in the experiments. For this system it is also possible to prove complete Bose condensation and superfluidity as we have shown. On the frontier of experimental developments is the possibility that a dilute gas in an elongated trap will behave like a one-dimensional system; we have proved this mathematically. Another topic is a proof that Foldy’s 1961 theory of a high density Bose gas of charged particles correctly describes its ground state energy; using this we can also prove the N 7/5 formula for the ground state energy of the two-component charged Bose gas proposed by Dyson in 1967. All of this is quite recent work and it is hoped that the mathematical methodology might be useful, ultimately, to solve more complex problems connected with these interesting systems.}, author = {Lieb, Élliott H and Robert Seiringer and Solovej, Jan P and Yngvason, Jakob}, booktitle = {Perspectives in Analysis}, editor = {Benedicks, Michael and Jones, Peter W and Smirnov, Stanislav and Winckler, Björn}, pages = {97 -- 183}, publisher = {Springer}, title = {{The quantum-mechanical many-body problem: The Bose gas}}, doi = {10.1007/3-540-30434-7_9}, volume = {27}, year = {2005}, } @article{2359, abstract = {The validity of substituting a c-number z for the k = 0 mode operator a0 is established rigorously in full generality, thereby verifying one aspect of Bogoliubov's 1947 theory. This substitution not only yields the correct value of thermodynamic quantities such as the pressure or ground state energy, but also the value of |z|2 that maximizes the partition function equals the true amount of condensation in the presence of a gauge-symmetry-breaking term. This point had previously been elusive.}, author = {Lieb, Élliott H and Robert Seiringer and Yngvason, Jakob}, journal = {Physical Review Letters}, number = {8}, publisher = {American Physical Society}, title = {{Justification of c-number substitutions in bosonic hamiltonians}}, doi = {10.1103/PhysRevLett.94.080401}, volume = {94}, year = {2005}, } @article{2361, abstract = {The strong subadditivity of entropy plays a key role in several areas of physics and mathematics. It states that the entropy S[±]=- Tr(ϱlnϱ) of a density matrix ϱ123 on the product of three Hilbert spaces satisfies S[ϱ123]- S[ϱ12]≤S[ϱ23]-S[ϱ2]. We strengthen this to S[ϱ123]-S[ϱ12] ≤αnα(S[ϱ23α]-S[ϱ2α]), where the nα are weights and the ϱ23α are partitions of ϱ23. Correspondingly, there is a strengthening of the theorem that the map A|Trexp[L+lnA] is concave. As applications we prove some monotonicity and convexity properties of the Wehrl coherent state entropy and entropy inequalities for quantum gases.}, author = {Lieb, Élliott H and Robert Seiringer}, journal = {Physical Review A - Atomic, Molecular, and Optical Physics}, number = {6}, publisher = {American Physical Society}, title = {{Stronger subadditivity of entropy}}, doi = {10.1103/PhysRevA.71.062329}, volume = {71}, year = {2005}, } @article{2362, abstract = {Recent developments in the physics of low-density trapped gases make it worthwhile to verify old, well-known results that, while plausible, were based on perturbation theory and assumptions about pseudopotentials. We use and extend recently developed techniques to give a rigorous derivation of the asymptotic formula for the ground-state energy of a dilute gas of N fermions interacting with a short-range, positive potential of scattering length a. For spin-12 fermions, this is E∼E0+(22m)2πNa, where E0 is the energy of the noninteracting system and is the density. A similar formula holds in two dimensions (2D), with a replaced by ln(a2). Obviously this 2D energy is not the expectation value of a density-independent pseudopotential.}, author = {Lieb, Élliott H and Robert Seiringer and Solovej, Jan P}, journal = {Physical Review A - Atomic, Molecular, and Optical Physics}, number = {5}, publisher = {American Physical Society}, title = {{Ground state energy of the low density Fermi gas}}, doi = {10.1103/PhysRevA.71.053605}, volume = {71}, year = {2005}, } @article{2427, abstract = {Intersection graphs of disks and of line segments, respectively, have been well studied, because of both practical applications and theoretically interesting properties of these graphs. Despite partial results, the complexity status of the Clique problem for these two graph classes is still open. Here, we consider the Clique problem for intersection graphs of ellipses, which, in a sense, interpolate between disks and line segments, and show that the problem is APX-hard in that case. Moreover, this holds even if for all ellipses, the ratio of the larger over the smaller radius is some prescribed number. Furthermore, the reduction immediately carries over to intersection graphs of triangles. To our knowledge, this is the first hardness result for the Clique problem in intersection graphs of convex objects with finite description complexity. We also describe a simple approximation algorithm for the case of ellipses for which the ratio of radii is bounded.}, author = {Ambühl, Christoph and Uli Wagner}, journal = {Theory of Computing Systems}, number = {3}, pages = {279 -- 292}, publisher = {Springer}, title = {{The Clique problem in intersection graphs of ellipses and triangles}}, doi = {10.1007/s00224-005-1141-6}, volume = {38}, year = {2005}, } @inproceedings{2428, abstract = {We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict-free, in the sense that in every interval I there is a color that appears exactly once in I. We present several deterministic and randomized algorithms for achieving this goal, and analyze their performance, that is, the maximum number of colors that they need to use, as a function of the number n of inserted points. We first show that a natural and simple (deterministic) approach may perform rather poorly, requiring Ω(√n) colors in the worst case. We then modify this approach, to obtain an efficient deterministic algorithm that uses a maximum of Θ(log 2 n) colors. Next, we present two randomized solutions. The first algorithm requires an expected number of at most O(log 2 n) colors, and produces a coloring which is valid with high probability, and the second one, which is a variant of our efficient deterministic algorithm, requires an expected number of at most O(log n log log n) colors but always produces a valid coloring. We also analyze the performance of the simplest proposed algorithm when the points are inserted in a random order, and present an incomplete analysis that indicates that, with high probability, it uses only O(log n) colors. Finally, we show that in the extension of this problem to two dimensions, where the relevant ranges are disks, n colors may be required in the worst case. The average-case behavior for disks, and cases involving other planar ranges, are still open.}, author = {Fiat, Amos and Levy, Meital B and Matoušek, Jiří and Pach, Elchanan M and Sharir, Micha and Smorodinsky, Shakhar and Uli Wagner and Welzl, Emo}, pages = {545 -- 554}, publisher = {SIAM}, title = {{Online conflict-free coloring for intervals}}, doi = {10.1137/S0097539704446682}, year = {2005}, } @inproceedings{4560, abstract = {We define and study a quantitative generalization of the traditional boolean framework of model-based specification and verification. In our setting, propositions have integer values at states, and properties have integer values on traces. For example, the value of a quantitative proposition at a state may represent power consumed at the state, and the value of a quantitative property on a trace may represent energy used along the trace. The value of a quantitative property at a state, then, is the maximum (or minimum) value achievable over all possible traces from the state. In this framework, model checking can be used to compute, for example, the minimum battery capacity necessary for achieving a given objective, or the maximal achievable lifetime of a system with a given initial battery capacity. In the case of open systems, these problems require the solution of games with integer values. Quantitative model checking and game solving is undecidable, except if bounds on the computation can be found. Indeed, many interesting quantitative properties, like minimal necessary battery capacity and maximal achievable lifetime, can be naturally specified by quantitative-bound automata, which are finite automata with integer registers whose analysis is constrained by a bound function f that maps each system K to an integer f(K). Along with the linear-time, automaton-based view of quantitative verification, we present a corresponding branching-time view based on a quantitative-bound μ-calculus, and we study the relationship, expressive power, and complexity of both views. }, author = {Chakrabarti, Arindam and Krishnendu Chatterjee and Thomas Henzinger and Kupferman, Orna and Majumdar, Ritankar S}, pages = {50 -- 64}, publisher = {Springer}, title = {{Verifying quantitative properties using bound functions}}, doi = {10.1007/11560548_7}, volume = {3725}, year = {2005}, } @inproceedings{4576, abstract = {We present a language for specifying web service interfaces. A web service interface puts three kinds of constraints on the users of the service. First, the interface specifies the methods that can be called by a client, together with types of input and output parameters; these are called signature constraints. Second, the interface may specify propositional constraints on method calls and output values that may oc- cur in a web service conversation; these are called consis- tency constraints. Third, the interface may specify temporal constraints on the ordering of method calls; these are called protocol constraints. The interfaces can be used to check, first, if two or more web services are compatible, and second, if a web service A can be safely substituted for a web ser- vice B. The algorithm for compatibility checking verifies that two or more interfaces fulfill each others’ constraints. The algorithm for substitutivity checking verifies that service A demands fewer and fulfills more constraints than service B.}, author = {Beyer, Dirk and Chakrabarti, Arindam and Thomas Henzinger}, pages = {148 -- 159}, publisher = {ACM}, title = {{Web service interfaces}}, doi = {10.1145/1060745.1060770}, year = {2005}, } @inproceedings{4579, abstract = {BLAST is an automatic verification tool for checking temporal safety properties of C programs. Given a C program and a temporal safety property, BLAST statically proves that either the program satisfies the safety property or the program has an execution trace that exhibits a violation of the property. BLAST constructs, explores, and refines abstractions of the program state space based on lazy predicate abstraction and interpolation-based predicate discovery. We show how BLAST can be used to statically prove memory safety for C programs. We take a two-step approach. First, we use Ccured, a type-based memory safety analyzer, to annotate with run-time checks all program points that cannot be proved memory safe by the type system. Second, we use BLAST to remove as many of the run-time checks as possible (by proving that these checks never fail), and to generate for the remaining run-time checks execution traces that witness them fail. Our experience shows that BLAST can remove many of the run-time checks added by Ccured and provide useful information to the programmer about many of the remaining checks.}, author = {Beyer, Dirk and Thomas Henzinger and Jhala, Ranjit and Majumdar, Ritankar S}, pages = {2 -- 18}, publisher = {Springer}, title = {{Checking memory safety with BLAST}}, doi = {10.1007/978-3-540-31984-9_2}, volume = {3442}, year = {2005}, } @inproceedings{4624, abstract = {Surveying results from [5] and [6], we motivate and introduce the theory behind formalizing rich interfaces for software and hardware components. Rich interfaces specify the protocol aspects of component interaction. Their formalization, called interface automata, permits a compiler to check the compatibility of component interaction protocols. Interface automata support incremental design and independent implementability. Incremental design means that the compatibility checking of interfaces can proceed for partial system descriptions, without knowing the interfaces of all components. Independent implementability means that compatible interfaces can be refined separately, while still maintaining compatibility.}, author = {de Alfaro, Luca and Thomas Henzinger}, pages = {83 -- 104}, publisher = {Springer}, title = {{Interface-based design}}, doi = {10.1007/1-4020-3532-2_3}, volume = {195}, year = {2005}, } @article{4625, abstract = {Temporal logic is two-valued: formulas are interpreted as either true or false. When applied to the analysis of stochastic systems, or systems with imprecise formal models, temporal logic is therefore fragile: even small changes in the model can lead to opposite truth values for a specification. We present a generalization of the branching-time logic CTL which achieves robustness with respect to model perturbations by giving a quantitative interpretation to predicates and logical operators, and by discounting the importance of events according to how late they occur. In every state, the value of a formula is a real number in the interval [0,1], where 1 corresponds to truth and 0 to falsehood. The boolean operators and and or are replaced by min and max, the path quantifiers ∃ and ∀ determine sup and inf over all paths from a given state, and the temporal operators ⋄ and □ specify sup and inf over a given path; a new operator averages all values along a path. Furthermore, all path operators are discounted by a parameter that can be chosen to give more weight to states that are closer to the beginning of the path. We interpret the resulting logic DCTL over transition systems, Markov chains, and Markov decision processes. We present two semantics for DCTL: a path semantics, inspired by the standard interpretation of state and path formulas in CTL, and a fixpoint semantics, inspired by the μ-calculus evaluation of CTL formulas. We show that, while these semantics coincide for CTL, they differ for DCTL, and we provide model-checking algorithms for both semantics.}, author = {de Alfaro, Luca and Faella, Marco and Thomas Henzinger and Majumdar, Ritankar S and Stoelinga, Mariëlle}, journal = {Theoretical Computer Science}, number = {1}, pages = {139 -- 170}, publisher = {Elsevier}, title = {{Model checking discounted temporal properties}}, doi = {10.1016/j.tcs.2005.07.033}, volume = {345}, year = {2005}, } @inproceedings{575, abstract = {We present the first demonstration of Jozsa's "counterfactual computation", using an optical Grover's search algorithm. We put the algorithm in a superposition of 'running' and 'not-running', obtaining information even though the algorithm does not run.}, author = {Onur Hosten and Rakher, Matthew T and Barreiro, Julio T and Peters, Nicholas A and Kwiat, Paul G}, pages = {365 -- 367}, publisher = {IEEE}, title = {{Counterfactual quantum computation}}, doi = { 10.1109/QELS.2005.1548783}, volume = {1}, year = {2005}, } @article{6153, abstract = {A current challenge in neuroscience is to bridge the gaps between genes, proteins, neurons, neural circuits, and behavior in a single animal model. The nematode Caenorhabditis elegans has unique features that facilitate this synthesis. Its nervous system includes exactly 302 neurons, and their pattern of synaptic connectivity is known. With only five olfactory neurons, C. elegans can dynamically respond to dozens of attractive and repellant odors. Thermosensory neurons enable the nematode to remember its cultivation temperature and to track narrow isotherms. Polymodal sensory neurons detect a wide range of nociceptive cues and signal robust escape responses. Pairing of sensory stimuli leads to long-lived changes in behavior consistent with associative learning. Worms exhibit social behaviors and complex ultradian rhythms driven by Ca2+ oscillators with clock-like properties. Genetic analysis has identified gene products required for nervous system function and elucidated the molecular and neural bases of behaviors.}, author = {de Bono, Mario and Villu Maricq, Andres}, issn = {0147-006X}, journal = {Annual Review of Neuroscience}, pages = {451--501}, publisher = {Annual Reviews}, title = {{Neuronal substrates of complex behaviors in C. elegans}}, doi = {10.1146/annurev.neuro.27.070203.144259}, volume = {28}, year = {2005}, } @article{6154, author = {Cheung, Benny H.H. and Cohen, Merav and Rogers, Candida and Albayram, Onder and de Bono, Mario}, issn = {0960-9822}, journal = {Current Biology}, number = {10}, pages = {905--917}, publisher = {Elsevier}, title = {{Experience-dependent modulation of C. elegans behavior by ambient oxygen}}, doi = {10.1016/j.cub.2005.04.017}, volume = {15}, year = {2005}, } @inbook{1444, abstract = {The paper surveys the mirror symmetry conjectures of Hausel-Thaddeus and Hausel-Rodriguez-Villegas concerning the equality of certain Hodge numbers of SL(n, ℂ) vs. PGL(n, ℂ) flat connections and character varieties for curves, respectively. Several new results and conjectures and their relations to works of Hitchin, Gothen, Garsia-Haiman and Earl-Kirwan are explained. These use the representation theory of finite groups of Lie-type via the arithmetic of character varieties and lead to an unexpected conjecture for a Hard Lefschetz theorem for their cohomology.}, author = {Tamas Hausel}, booktitle = {Geometric Methods in Algebra and Number Theory}, pages = {193 -- 217}, publisher = {Springer}, title = {{Mirror symmetry and Langlands duality in the non-Abelian Hodge theory of a curve}}, doi = {10.1007/0-8176-4417-2_9}, volume = {235}, year = {2005}, } @article{1447, abstract = {Building on a recent paper [8], here we argue that the combinatorics of matroids are intimately related to the geometry and topology of toric hyperkähler varieties. We show that just like toric varieties occupy a central role in Stanley’s proof for the necessity of McMullen’s conjecture (or g-inequalities) about the classification of face vectors of simplicial polytopes, the topology of toric hyperkähler varieties leads to new restrictions on face vectors of matroid complexes. Namely in this paper we will give two proofs that the injectivity part of the Hard Lefschetz theorem survives for toric hyperkähler varieties. We explain how this implies the g-inequalities for rationally representable matroids. We show how the geometrical intuition in the first proof, coupled with results of Chari [3], leads to a proof of the g-inequalities for general matroid complexes, which is a recent result of Swartz [20]. The geometrical idea in the second proof will show that a pure O-sequence should satisfy the g-inequalities, thus showing that our result is in fact a consequence of a long-standing conjecture of Stanley.}, author = {Tamas Hausel}, journal = {Open Mathematics}, number = {1}, pages = {26 -- 38}, publisher = {Central European Science Journals}, title = {{Quaternionic geometry of matroids}}, doi = {10.2478/BF02475653}, volume = {3}, year = {2005}, } @article{1463, abstract = {We study an integration theory in circle equivariant cohomology in order to prove a theorem relating the cohomology ring of a hyperkähler quotient to the cohomology ring of the quotient by a maximal abelian subgroup, analogous to a theorem of Martin for symplectic quotients. We discuss applications of this theorem to quiver varieties, and compute as an example the ordinary and equivariant cohomology rings of a hyperpolygon space.}, author = {Tamas Hausel and Proudfoot, Nicholas J}, journal = {Topology}, number = {1}, pages = {231 -- 248}, publisher = {Elsevier}, title = {{Abelianization for hyperkähler quotients}}, doi = {10.1016/j.top.2004.04.002}, volume = {44}, year = {2005}, }