@article{6133, abstract = {cGMP signaling is widespread in the nervous system. However, it has proved difficult to visualize and genetically probe endogenously evoked cGMP dynamics in neurons in vivo. Here, we combine cGMP and Ca2+ biosensors to image and dissect a cGMP signaling network in a Caenorhabditis elegans oxygen-sensing neuron. We show that a rise in O2 can evoke a tonic increase in cGMP that requires an atypical O2-binding soluble guanylate cyclase and that is sustained until oxygen levels fall. Increased cGMP leads to a sustained Ca2+ response in the neuron that depends on cGMP-gated ion channels. Elevated levels of cGMP and Ca2+ stimulate competing negative feedback loops that shape cGMP dynamics. Ca2+-dependent negative feedback loops, including activation of phosphodiesterase-1 (PDE-1), dampen the rise of cGMP. A different negative feedback loop, mediated by phosphodiesterase-2 (PDE-2) and stimulated by cGMP-dependent kinase (PKG), unexpectedly promotes cGMP accumulation following a rise in O2, apparently by keeping in check gating of cGMP channels and limiting activation of Ca2+-dependent negative feedback loops. Simultaneous imaging of Ca2+ and cGMP suggests that cGMP levels can rise close to cGMP channels while falling elsewhere. O2-evoked cGMP and Ca2+ responses are highly reproducible when the same neuron in an individual animal is stimulated repeatedly, suggesting that cGMP transduction has high intrinsic reliability. However, responses vary substantially across individuals, despite animals being genetically identical and similarly reared. This variability may reflect stochastic differences in expression of cGMP signaling components. Our work provides in vivo insights into the architecture of neuronal cGMP signaling.}, author = {Couto, A. and Oda, S. and Nikolaev, V. O. and Soltesz, Z. and de Bono, Mario}, issn = {0027-8424}, journal = {Proceedings of the National Academy of Sciences}, number = {35}, pages = {E3301--E3310}, publisher = {Proceedings of the National Academy of Sciences}, title = {{In vivo genetic dissection of O2-evoked cGMP dynamics in a Caenorhabditis elegans gas sensor}}, doi = {10.1073/pnas.1217428110}, volume = {110}, year = {2013}, } @misc{6440, abstract = {In order to guarantee that each method of a data structure updates the logical state exactly once, al-most all non-blocking implementations employ Compare-And-Swap (CAS) based synchronization. For FIFO queue implementations this translates into concurrent enqueue or dequeue methods competing among themselves to update the same variable, the tail or the head, respectively, leading to high contention and poor scalability. Recent non-blocking queue implementations try to alleviate high contentionby increasing the number of contention points, all the while using CAS-based synchronization. Furthermore, obtaining a wait-free implementation with competition is achieved by additional synchronization which leads to further degradation of performance.In this paper we formalize the notion of competitiveness of a synchronizing statement which can beused as a measure for the scalability of concurrent implementations. We present a new queue implementation, the Speculative Pairing (SP) queue, which, as we show, decreases competitiveness by using Fetch-And-Increment (FAI) instead of CAS. We prove that the SP queue is linearizable and lock-free.We also show that replacing CAS with FAI leads to wait-freedom for dequeue methods without an adverse effect on performance. In fact, our experiments suggest that the SP queue can perform and scale better than the state-of-the-art queue implementations.}, author = {Henzinger, Thomas A and Payer, Hannes and Sezgin, Ali}, issn = {2664-1690}, pages = {23}, publisher = {IST Austria}, title = {{Replacing competition with cooperation to achieve scalable lock-free FIFO queues }}, doi = {10.15479/AT:IST-2013-124-v1-1}, 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{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}, } @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}, } @phdthesis{1405, abstract = {Motivated by the analysis of highly dynamic message-passing systems, i.e. unbounded thread creation, mobility, etc. we present a framework for the analysis of depth-bounded systems. Depth-bounded systems are one of the most expressive known fragment of the π-calculus for which interesting verification problems are still decidable. Even though they are infinite state systems depth-bounded systems are well-structured, thus can be analyzed algorithmically. We give an interpretation of depth-bounded systems as graph-rewriting systems. This gives more flexibility and ease of use to apply depth-bounded systems to other type of systems like shared memory concurrency. First, we develop an adequate domain of limits for depth-bounded systems, a prerequisite for the effective representation of downward-closed sets. Downward-closed sets are needed by forward saturation-based algorithms to represent potentially infinite sets of states. Then, we present an abstract interpretation framework to compute the covering set of well-structured transition systems. Because, in general, the covering set is not computable, our abstraction over-approximates the actual covering set. Our abstraction captures the essence of acceleration based-algorithms while giving up enough precision to ensure convergence. We have implemented the analysis in the PICASSO tool and show that it is accurate in practice. Finally, we build some further analyses like termination using the covering set as starting point.}, author = {Zufferey, Damien}, issn = {2663-337X}, pages = {134}, publisher = {Institute of Science and Technology Austria}, title = {{Analysis of dynamic message passing programs}}, doi = {10.15479/at:ista:1405}, year = {2013}, } @article{905, abstract = {A survey of avifauna was carried out in the Mys Shmidta area, north Chukotka, Russia from 8 June to 12 July 2011. A total of 90 species was recorded in the area, which together with literature data made a final list of 104 species. For several species this area is beyond the northern, north-eastern or north-western limits of their known distribution. We collected new data for 19 globally or locally threatened species. Tundra Swan Cygnus columbianus, Emperor Goose Anser canagica, American Golden Plover Pluvialis dominica, Western Sandpiper Calidris mauri, Semipalmated Sandpiper C. pusilla, Northern House Martin Delichon urbica and Barn Swallow Hirundo rustica were all confirmed to be breeding. Breeding of Brent Goose Branta bernicla nigricans, Spectacled Eider Somateria fischeri and Steller's Eider Polysticta stelleri was judged to be 'very likely'. There was no evidence for breeding of Ross's Gull Rhodostethia rosea despite several records. Two Eurasian Dotterels Eudromias morinellus were recorded displaying for the first time in the area, but the status of the species is unclear. The area is important for Snowy Owl Nyctea scandiaca, and as moulting grounds for Emperor Goose. Canada Goose Branta canadensis, Baikal Teal Anas formosa, Bar-tailed Godwit Limosa lapponica, Slaty-backed Gull Larus schistisagus, Thayer's Gull L. thayeri, Black-headed Gull L. ridibundus, White-tailed Eagle Haliaeetus albicilla, Steller's Sea Eagle H. pelagicus, Osprey Pandion haliaetus, Arctic Warbler Phylloscopus borealis and House Sparrow Passer domesticus are more likely to be rare vagrants or migrants. An observation of a Pine Siskin Carduelis pinus is the first record for Eurasia.}, author = {Arkhipov, Vladimir Y and Noah T and Koschkar, Steffen and Fyodor Kondrashov}, journal = {Forktail}, number = {29}, pages = {25 -- 30}, publisher = {Oriental Bird Club}, title = {{Birds of Mys Shmidta, north Chukotka, Russia}}, year = {2013}, } @article{9153, abstract = {Internal tide driven mixing plays a key role in sustaining the deep ocean stratification and meridional overturning circulation. Internal tides can be generated by topographic horizontal scales ranging from hundreds of meters to tens of kilometers. State of the art topographic products barely resolve scales smaller than ∼10 km in the deep ocean. On these scales abyssal hills dominate ocean floor roughness. The impact of abyssal hill roughness on internal‐tide generation is evaluated in this study. The conversion of M2 barotropic to baroclinic tidal energy is calculated based on linear wave theory both in real and spectral space using the Shuttle Radar Topography Mission SRTM30_PLUS bathymetric product at 1/120° resolution with and without the addition of synthetic abyssal hill roughness. Internal tide generation by abyssal hills integrates to 0.1 TW globally or 0.03 TW when the energy flux is empirically corrected for supercritical slope (i.e., ∼10% of the energy flux due to larger topographic scales resolved in standard products in both cases). The abyssal hill driven energy conversion is dominated by mid‐ocean ridges, where abyssal hill roughness is large. Focusing on two regions located over the Mid‐Atlantic Ridge and the East Pacific Rise, it is shown that regionally linear theory predicts an increase of the energy flux due to abyssal hills of up to 100% or 60% when an empirical correction for supercritical slopes is attempted. Therefore, abyssal hills, unresolved in state of the art topographic products, can have a strong impact on internal tide generation, especially over mid‐ocean ridges.}, author = {Melet, Angélique and Nikurashin, Maxim and Muller, Caroline J and Falahat, S. and Nycander, Jonas and Timko, Patrick G. and Arbic, Brian K. and Goff, John A.}, issn = {2169-9275}, journal = {Journal of Geophysical Research: Oceans}, number = {11}, pages = {6303--6318}, publisher = {American Geophysical Union}, title = {{Internal tide generation by abyssal hills using analytical theory}}, doi = {10.1002/2013jc009212}, volume = {118}, year = {2013}, } @article{9154, abstract = {In this study the response of tropical precipitation extremes to warming in organized convection is examined using a cloud-resolving model. Vertical shear is imposed to organize the convection into squall lines. Earlier studies show that in disorganized convection, the fractional increase of precipitation extremes is similar to that of surface water vapor, which is substantially smaller than the increase in column water vapor. It has been suggested that organized convection could lead to stronger amplifications. Regardless of the strength of the shear, amplifications of precipitation extremes in the cloud-resolving simulations are comparable to those of surface water vapor and are substantially less than increases in column water vapor. The results without shear and with critical shear, for which the squall lines are perpendicular to the shear, are surprisingly similar with a fractional rate of increase of precipitation extremes slightly smaller than that of surface water vapor. Interestingly, the dependence on shear is nonmonotonic, and stronger supercritical shear yields larger rates, close to or slightly larger than surface humidity. A scaling is used to evaluate the thermodynamic and dynamic contributions to precipitation extreme changes. To first order, they are dominated by the thermodynamic component, which has the same magnitude for all shears, close to the change in surface water vapor. The dynamic contribution plays a secondary role and tends to weaken extremes without shear and with critical shear, while it strengthens extremes with supercritical shear. These different dynamic contributions for different shears are due to different responses of convective mass fluxes in individual updrafts to warming.}, author = {Muller, Caroline J}, issn = {0894-8755}, journal = {Journal of Climate}, keywords = {Atmospheric Science}, number = {14}, pages = {5028--5043}, publisher = {American Meteorological Society}, title = {{Impact of convective organization on the response of tropical precipitation extremes to warming}}, doi = {10.1175/jcli-d-12-00655.1}, volume = {26}, year = {2013}, } @article{9167, abstract = {We introduce a self-propelled colloidal hematite docker that can be steered to a small particle cargo many times its size, dock, transport the cargo to a remote location, and then release it. The self-propulsion and docking are reversible and activated by visible light. The docker can be steered either by a weak uniform magnetic field or by nanoscale tracks in a textured substrate. The light-activated motion and docking originate from osmotic/phoretic particle transport in a concentration gradient of fuel, hydrogen peroxide, induced by the photocatalytic activity of the hematite. The docking mechanism is versatile and can be applied to various materials and shapes. The hematite dockers are simple single-component particles and are synthesized in bulk quantities. This system opens up new possibilities for designing complex micrometer-size factories as well as new biomimetic systems.}, author = {Palacci, Jérémie A and Sacanna, Stefano and Vatchinsky, Adrian and Chaikin, Paul M. and Pine, David J.}, issn = {15205126}, journal = {Journal of the American Chemical Society}, keywords = {Colloid and Surface Chemistry, Biochemistry, General Chemistry, Catalysis}, number = {43}, pages = {15978--15981}, publisher = {American Chemical Society}, title = {{Photoactivated colloidal dockers for cargo transportation}}, doi = {10.1021/ja406090s}, volume = {135}, year = {2013}, } @article{9459, abstract = {Nucleosome remodelers of the DDM1/Lsh family are required for DNA methylation of transposable elements, but the reason for this is unknown. How DDM1 interacts with other methylation pathways, such as small-RNA-directed DNA methylation (RdDM), which is thought to mediate plant asymmetric methylation through DRM enzymes, is also unclear. Here, we show that most asymmetric methylation is facilitated by DDM1 and mediated by the methyltransferase CMT2 separately from RdDM. We find that heterochromatic sequences preferentially require DDM1 for DNA methylation and that this preference depends on linker histone H1. RdDM is instead inhibited by heterochromatin and absolutely requires the nucleosome remodeler DRD1. Together, DDM1 and RdDM mediate nearly all transposon methylation and collaborate to repress transposition and regulate the methylation and expression of genes. Our results indicate that DDM1 provides DNA methyltransferases access to H1-containing heterochromatin to allow stable silencing of transposable elements in cooperation with the RdDM pathway.}, author = {Zemach, Assaf and Kim, M. Yvonne and Hsieh, Ping-Hung and Coleman-Derr, Devin and Eshed-Williams, Leor and Thao, Ka and Harmer, Stacey L. and Zilberman, Daniel}, issn = {1097-4172}, journal = {Cell}, number = {1}, pages = {193--205}, publisher = {Elsevier}, title = {{The Arabidopsis nucleosome remodeler DDM1 allows DNA methyltransferases to access H1-containing heterochromatin}}, doi = {10.1016/j.cell.2013.02.033}, volume = {153}, year = {2013}, } @article{9481, abstract = {Arabidopsis thaliana endosperm, a transient tissue that nourishes the embryo, exhibits extensive localized DNA demethylation on maternally inherited chromosomes. Demethylation mediates parent-of-origin–specific (imprinted) gene expression but is apparently unnecessary for the extensive accumulation of maternally biased small RNA (sRNA) molecules detected in seeds. Endosperm DNA in the distantly related monocots rice and maize is likewise locally hypomethylated, but whether this hypomethylation is generally parent-of-origin specific is unknown. Imprinted expression of sRNA also remains uninvestigated in monocot seeds. Here, we report high-coverage sequencing of the Kitaake rice cultivar that enabled us to show that localized hypomethylation in rice endosperm occurs solely on the maternal genome, preferring regions of high DNA accessibility. Maternally expressed imprinted genes are enriched for hypomethylation at putative promoter regions and transcriptional termini and paternally expressed genes at promoters and gene bodies, mirroring our recent results in A. thaliana. However, unlike in A. thaliana, rice endosperm sRNA populations are dominated by specific strong sRNA-producing loci, and imprinted 24-nt sRNAs are expressed from both parental genomes and correlate with hypomethylation. Overlaps between imprinted sRNA loci and imprinted genes expressed from opposite alleles suggest that sRNAs may regulate genomic imprinting. Whereas sRNAs in seedling tissues primarily originate from small class II (cut-and-paste) transposable elements, those in endosperm are more uniformly derived, including sequences from other transposon classes, as well as genic and intergenic regions. Our data indicate that the endosperm exhibits a unique pattern of sRNA expression and suggest that localized hypomethylation of maternal endosperm DNA is conserved in flowering plants.}, author = {Rodrigues, Jessica A. and Ruan, Randy and Nishimura, Toshiro and Sharma, Manoj K. and Sharma, Rita and Ronald, Pamela C and Fischer, Robert L. and Zilberman, Daniel}, issn = {1091-6490}, journal = {Proceedings of the National Academy of Sciences}, keywords = {Multidisciplinary}, number = {19}, pages = {7934--7939}, publisher = {National Academy of Sciences}, title = {{Imprinted expression of genes and small RNA is associated with localized hypomethylation of the maternal genome in rice endosperm}}, doi = {10.1073/pnas.1306164110}, volume = {110}, year = {2013}, } @article{9520, abstract = {Plants undergo alternation of generation in which reproductive cells develop in the plant body ("sporophytic generation") and then differentiate into a multicellular gamete-forming "gametophytic generation." Different populations of helper cells assist in this transgenerational journey, with somatic tissues supporting early development and single nurse cells supporting gametogenesis. New data reveal a two-way relationship between early reproductive cells and their helpers involving complex epigenetic and signaling networks determining cell number and fate. Later, the egg cell plays a central role in specifying accessory cells, whereas in both gametophytes, companion cells contribute non-cell-autonomously to the epigenetic landscape of the gamete genomes.}, author = {Feng, Xiaoqi and Zilberman, Daniel and Dickinson, Hugh}, issn = {1878-1551}, journal = {Developmental Cell}, number = {3}, pages = {215--225}, publisher = {Elsevier}, title = {{A conversation across generations: Soma-germ cell crosstalk in plants}}, doi = {10.1016/j.devcel.2013.01.014}, volume = {24}, year = {2013}, } @article{9663, abstract = {Molecular dynamics simulations of small Cu nanoparticles using three different interatomic potentials at rising temperature indicate that small nanoparticles can undergo solid-solid structural transitions through a direct geometrical conversion route. The direct geometrical conversion can happen for cuboctahedral nanoparticles, which turn into an icosahedra shape: one diagonal of the square faces contracts, and the faces are folded along the diagonal to give rise to two equilateral triangles. The transition is a kinetic process that cannot be fully explained through an energetic point of view. It has low activation energy and fast reaction time in the simulations. The transition mechanism is via the transmission of shear waves initiated from the particle surface and does not involve dislocation activity.}, author = {Cheng, Bingqing and Ngan, Alfonso H. W.}, issn = {1089-7690}, journal = {The Journal of Chemical Physics}, number = {16}, publisher = {AIP Publishing}, title = {{Thermally induced solid-solid structural transition of copper nanoparticles through direct geometrical conversion}}, doi = {10.1063/1.4802025}, volume = {138}, year = {2013}, } @article{10384, abstract = {Recent studies aimed at investigating artificial analogs of bacterial colonies have shown that low-density suspensions of self-propelled particles confined in two dimensions can assemble into finite aggregates that merge and split, but have a typical size that remains constant (living clusters). In this Letter, we address the problem of the formation of living clusters and crystals of active particles in three dimensions. We study two systems: self-propelled particles interacting via a generic attractive potential and colloids that can move toward each other as a result of active agents (e.g., by molecular motors). In both cases, fluidlike “living” clusters form. We explain this general feature in terms of the balance between active forces and regression to thermodynamic equilibrium. This balance can be quantified in terms of a dimensionless number that allows us to collapse the observed clustering behavior onto a universal curve. We also discuss how active motion affects the kinetics of crystal formation.}, author = {Mognetti, B. M. and Šarić, Anđela and Angioletti-Uberti, S. and Cacciuto, A. and Valeriani, C. and Frenkel, D.}, issn = {1079-7114}, journal = {Physical Review Letters}, keywords = {general physics and astronomy}, number = {24}, publisher = {American Physical Society}, title = {{Living clusters and crystals from low-density suspensions of active colloids}}, doi = {10.1103/physrevlett.111.245702}, volume = {111}, year = {2013}, } @article{10396, abstract = {Stimfit is a free cross-platform software package for viewing and analyzing electrophysiological data. It supports most standard file types for cellular neurophysiology and other biomedical formats. Its analysis algorithms have been used and validated in several experimental laboratories. Its embedded Python scripting interface makes Stimfit highly extensible and customizable.}, author = {Schlögl, Alois and Jonas, Peter M and Schmidt-Hieber, C. and Guzman, S. J.}, issn = {1862-278X}, journal = {Biomedical Engineering / Biomedizinische Technik}, keywords = {biomedical engineering, data analysis, free software}, location = {Graz, Austria}, number = {SI-1-Track-G}, publisher = {De Gruyter}, title = {{Stimfit: A fast visualization and analysis environment for cellular neurophysiology}}, doi = {10.1515/bmt-2013-4181}, volume = {58}, year = {2013}, } @inproceedings{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}, }