@inproceedings{762,
  abstract     = {Decades of research in distributed computing have led to a variety of perspectives on what it means for a concurrent algorithm to be efficient, depending on model assumptions, progress guarantees, and complexity metrics. It is therefore natural to ask whether one could compose algorithms that perform efficiently under different conditions, so that the composition preserves the performance of the original components when their conditions are met. In this paper, we evaluate the cost of composing shared-memory algorithms. First, we formally define the notion of safely composable algorithms and we show that every sequential type has a safely composable implementation, as long as enough state is transferred between modules. Since such generic implementations are inherently expensive, we present a more general light-weight specification that allows the designer to transfer very little state between modules, by taking advantage of the semantics of the implemented object. Using this framework, we implement a composed longlived test-and-set object, with the property that each of its modules is asymptotically optimal with respect to the progress condition it ensures, while the entire implementation only uses objects with consensus number at most two. Thus, we show that the overhead of composition can be negligible in the case of some important shared-memory abstractions.},
  author       = {Alistarh, Dan-Adrian and Guerraoui, Rachid and Kuznetsov, Petr and Losa, Giuliano},
  pages        = {298 -- 307},
  publisher    = {ACM},
  title        = {{On the cost of composing shared-memory algorithms}},
  doi          = {10.1145/2312005.2312057},
  year         = {2012},
}

@inproceedings{763,
  abstract     = {Renaming is a fundamental problem in distributed computing, in which a set of n processes need to pick unique names from a namespace of limited size. In this paper, we present the first early-deciding upper bounds for synchronous renaming, in which the running time adapts to the actual number of failures f in the execution. We show that, surprisingly, renaming can be solved in constant time if the number of failures f is limited to O(√n), while for general f ≤ n - 1 renaming can always be solved in O(log f) communication rounds. In the wait-free case, i.e. for f = n - 1, our upper bounds match the Ω(log n) lower bound of Chaudhuri et al. [13].},
  author       = {Alistarh, Dan-Adrian and Attiya, Hagit and Guerraoui, Rachid and Travers, Corentin},
  pages        = {195 -- 206},
  publisher    = {Springer},
  title        = {{Early deciding synchronous renaming in O(log f) rounds or less}},
  doi          = {10.1007/978-3-642-31104-8_17},
  volume       = {7355 LNCS},
  year         = {2012},
}

@article{764,
  abstract     = {Set agreement is a fundamental problem in distributed computing in which processes collectively choose a small subset of values from a larger set of proposals. The impossibility of fault-tolerant set agreement in asynchronous networks is one of the seminal results in distributed computing. In synchronous networks, too, the complexity of set agreement has been a significant research challenge that has now been resolved. Real systems, however, are neither purely synchronous nor purely asynchronous. Rather, they tend to alternate between periods of synchrony and periods of asynchrony. Nothing specific is known about the complexity of set agreement in such a "partially synchronous" setting. In this paper, we address this challenge, presenting the first (asymptotically) tight bound on the complexity of set agreement in such systems. We introduce a novel technique for simulating, in a fault-prone asynchronous shared memory, executions of an asynchronous and failure-prone message-passing system in which some fragments appear synchronous to some processes. We use this simulation technique to derive a lower bound on the round complexity of set agreement in a partially synchronous system by a reduction from asynchronous wait-free set agreement. Specifically, we show that every set agreement protocol requires at least $\lfloor\frac t k \rfloor + 2$ synchronous rounds to decide. We present an (asymptotically) matching algorithm that relies on a distributed asynchrony detection mechanism to decide as soon as possible during periods of synchrony. From these two results, we derive the size of the minimal window of synchrony needed to solve set agreement. By relating synchronous, asynchronous and partially synchronous environments, our simulation technique is of independent interest. In particular, it allows us to obtain a new lower bound on the complexity of early deciding k-set agreement complementary to that of Gafni et al. (in SIAM J. Comput. 40(1):63-78, 2011), and to re-derive the combinatorial topology lower bound of Guerraoui et al. (in Theor. Comput. Sci. 410(6-7):570-580, 2009) in an algorithmic way.},
  author       = {Alistarh, Dan-Adrian and Gilbert, Seth and Guerraoui, Rachid and Travers, Corentin},
  journal      = {Algorithmica (New York)},
  number       = {1-2},
  pages        = {595 -- 629},
  publisher    = {Springer},
  title        = {{Of choices, failures and asynchrony: the many faces of set agreement}},
  doi          = {10.1007/s00453-011-9581-7},
  volume       = {62},
  year         = {2012},
}

@inproceedings{766,
  abstract     = {Asynchronous task allocation is a fundamental problem in distributed computing in which p asynchronous processes must execute a set of m tasks. Also known as write-all or do-all, this problem been studied extensively, both independently and as a key building block for various distributed algorithms. In this paper, we break new ground on this classic problem: we introduce the To-Do Tree concurrent data structure, which improves on the best known randomized and deterministic upper bounds. In the presence of an adaptive adversary, the randomized To-Do Tree algorithm has O(m + p log p log2 m) work complexity. We then show that there exists a deterministic variant of the To-Do Tree algorithm with work complexity O(m + p log5 m log2 max(m, p)). For all values of m and p, our algorithms are within log factors of the Ω(m + p log p) lower bound for this problem. The key technical ingredient in our results is a new approach for analyzing concurrent executions against a strong adaptive scheduler. This technique allows us to handle the complex dependencies between the processes' coin flips and their scheduling, and to tightly bound the work needed to perform subsets of the tasks.},
  author       = {Alistarh, Dan-Adrian and Bender, Michael and Gilbert, Seth and Guerraoui, Rachid},
  pages        = {331 -- 340},
  publisher    = {IEEE},
  title        = {{How to allocate tasks asynchronously}},
  doi          = {10.1109/FOCS.2012.41},
  year         = {2012},
}

@article{345,
  abstract     = {Nanocomposites are highly promising materials to enhance the efficiency of current thermoelectric devices. A straightforward and at the same time highly versatile and controllable approach to produce nanocomposites is the assembly of solution-processed nanocrystal building blocks. The convenience of this bottom-up approach to produce nanocomposites with homogeneous phase distributions and adjustable composition is demonstrated here by blending Ag2Te and PbTe colloidal nanocrystals to form Ag2Te–PbTe bulk nanocomposites. The thermoelectric properties of these nanocomposites are analyzed in the temperature range from 300 to 700 K. The evolution of their electrical conductivity and Seebeck coefficient is discussed in terms of the blend composition and the characteristics of the constituent materials. },
  author       = {Cadavid, Doris and Ibáñez, Maria and Gorsse, Stéphane and López, Antonio and Cirera, Albert and Morante, Joan and Cabot, Andreu},
  journal      = {Journal of Nanoparticle Research},
  number       = {12},
  publisher    = {Kluwer},
  title        = {{Bottom-up processing of thermoelectric nanocomposites from colloidal nanocrystal building blocks: The case of Ag2Te–PbTe}},
  doi          = {10.1007/s11051-012-1328-0},
  volume       = {14},
  year         = {2012},
}

@article{346,
  abstract     = {Arrays of vertically aligned ZnO : Cl/TiO2 and ZnO : Cl/ZnxTiOy/TiO2 core–shell nanowires (NWs) were prepared by means of the combination of two solution-growth processes. First, single-crystal ZnO NWs with controlled n-type doping were grown on conducting substrates by a low-cost, high-yield and seed-free electrochemical route. These NWs were covered by a titanium oxide shell of tunable thickness mediating successive adsorption-hydrolysis-condensation steps. Using this atomic-layer growth procedure, titania shells with controlled thickness and the anatase TiO2 phase were obtained after sintering at 450 °C. Higher sintering temperatures resulted in the formation of ZnO : Cl/ZnxTiOy/TiO2 core–shell NWs by the interdiffusion of Zn and Ti ions at the ZnO–TiO2 interface. The performance of ZnO : Cl/TiO2 and ZnO : Cl/ZnxTiOy/TiO2 core–shell NWs towards photoelectrochemical (PEC) water splitting was investigated as a function of the titania shell thickness. Furthermore, the performance of such core–shell NWs as photoelectrodes in dye-sensitized solar cells was also characterized. The TiO2 presence at the ZnO : Cl surface promoted a two-fold increase on the produced photocurrent densities, probing their potential for PEC and optoelectronic applications. Electrochemical impedance spectroscopy was used to corroborate the lower resistance for charge transfer between the NWs and the electrolyte in the presence of the TiO2 shell.},
  author       = {Fan, Jiandong and Zamani, Reza and Fábrega, Cristina and Shavel, Alexey and Flox, Cristina and Ibáñez, Maria and Andreu, Teresa and López, Amtonio and Arbiol, Jordi and Morante, Joan and Cabot, Andreu},
  journal      = {Journal of Physics D: Applied Physics},
  number       = {41},
  publisher    = {IOP Publishing Ltd.},
  title        = {{Solution-growth and optoelectronic performance of ZnO : Cl/TiO2 and ZnO : Cl/ZnxTiOy/TiO2 core–shell nanowires with tunable shell thickness}},
  doi          = {10.1088/0022-3727/45/41/415301},
  volume       = {45},
  year         = {2012},
}

@article{347,
  abstract     = {A synthetic route for producing Cu 2ZnGeSe 4 nanocrystals with narrow size distributions and controlled composition is presented. These nanocrystals were used to produce densely packed nanomaterials by hot-pressing. From the characterization of the thermoelectric properties of these nanomaterials, Cu 2ZnGeSe 4 is demonstrated to show excellent thermoelectric properties. A very preliminary adjustment of the nanocrystal composition has already resulted in a figure of merit of up to 0.55 at 450°C. },
  author       = {Ibáñez, Maria and Zamani, Reza and Lalonde, Aaron and Cadavid, Doris and Li, Wenhua and Shavel, Alexey and Arbiol, Jordi and Morante, Joan and Gorsse, Stéphane and Snyder, G Jeffrey and Cabot, Andreu},
  journal      = {Journal of the American Chemical Society},
  number       = {9},
  pages        = {4060 -- 4063},
  publisher    = {ACS},
  title        = {{Cu 2ZnGeSe 4 nanocrystals: Synthesis and thermoelectric properties}},
  doi          = {10.1021/ja211952z},
  volume       = {134},
  year         = {2012},
}

@article{377,
  abstract     = {The potential to control the composition and crystal phase at the nanometer scale enable the production of nanocrystalline materials with enhanced functionalities and new applications. In the present work, we detail a novel colloidal synthesis route to prepare nanoparticles of the ternary semiconductor Cu2GeSe3 (CGSe) with nanometer-scale control over their crystal phases. We also demonstrate the structural effect on the thermoelectric properties of bottom-up-prepared CGSe nanomaterials. By careful adjustment of the nucleation and growth temperatures, pure orthorhombic CGSe nanoparticles with cationic order or polytypic CGSe nanoparticles with disordered cation positions can be produced. In this second type of nanoparticle, a high density of twins can be created to periodically change the atomic plane stacking, forming a hexagonal wurtzite CGSe phase. The high yield of the synthetic routes reported here allows the production of single-phase and multiphase CGSe nanoparticles in the gram scale, which permits characterization of the thermoelectric properties of these materials. Reduced thermal conductivities and a related 2.5-fold increase of the thermoelectric figure of merit for multiphase nanomaterials compared to pure-phase CGSe are systematically obtained. These results are discussed in terms of the density and efficiency of phonon scattering centers in both types of materials.},
  author       = {Ibáñez, Maria and Zamani, Reza and Li, Wenhua and Cadavid, Doris and Gorse, Stéphane and Katchoi, Nebll and Shavel, Alexey and López, Antonioo and Morante, Joan and Arbiol, Jordi and Cabot, Andreu},
  journal      = {Chemistry of Materials},
  number       = {23},
  pages        = {4615 -- 4622},
  publisher    = {American Chemical Society},
  title        = {{Crystallographic control at the nanoscale to enhance functionality: Polytypic Cu2GeSe3 nanoparticles as thermoelectric materials}},
  doi          = {10.1021/cm303252q},
  volume       = {24},
  year         = {2012},
}

@article{3836,
  abstract     = {Hierarchical Timing Language (HTL) is a coordination language for distributed, hard real-time applications. HTL is a hierarchical extension of Giotto and, like its predecessor, based on the logical execution time (LET) paradigm of real-time programming. Giotto is compiled into code for a virtual machine, called the EmbeddedMachine (or E machine). If HTL is targeted to the E machine, then the hierarchicalprogram structure needs to be flattened; the flattening makes separatecompilation difficult, and may result in E machinecode of exponential size. In this paper, we propose a generalization of the E machine, which supports a hierarchicalprogram structure at runtime through real-time trigger mechanisms that are arranged in a tree. We present the generalized E machine, and a modular compiler for HTL that generates code of linear size. The compiler may generate code for any part of a given HTL program separately in any order.},
  author       = {Ghosal, Arkadeb and Iercan, Daniel and Kirsch, Christoph and Henzinger, Thomas A and Sangiovanni Vincentelli, Alberto},
  journal      = {Science of Computer Programming},
  number       = {2},
  pages        = {96 -- 112},
  publisher    = {Elsevier},
  title        = {{Separate compilation of hierarchical real-time programs into linear-bounded embedded machine code}},
  doi          = {10.1016/j.scico.2010.06.004},
  volume       = {77},
  year         = {2012},
}

@article{3846,
  abstract     = {We summarize classical and recent results about two-player games played on graphs with ω-regular objectives. These games have applications in the verification and synthesis of reactive systems. Important distinctions are whether a graph game is turn-based or concurrent; deterministic or stochastic; zero-sum or not. We cluster known results and open problems according to these classifications.},
  author       = {Chatterjee, Krishnendu and Henzinger, Thomas A},
  journal      = {Journal of Computer and System Sciences},
  number       = {2},
  pages        = {394 -- 413},
  publisher    = {Elsevier},
  title        = {{A survey of stochastic ω regular games}},
  doi          = {10.1016/j.jcss.2011.05.002},
  volume       = {78},
  year         = {2012},
}

@article{387,
  abstract     = {In this Letter we present detailed study of the density of states near defects in Bi 2Se 3. In particular, we present data on the commonly found triangular defects in this system. While we do not find any measurable quasiparticle scattering interference effects, we do find localized resonances, which can be well fitted by theory once the potential is taken to be extended to properly account for the observed defects. The data together with the fits confirm that while the local density of states around the Dirac point of the electronic spectrum at the surface is significantly disrupted near the impurity by the creation of low-energy resonance state, the Dirac point is not locally destroyed. We discuss our results in terms of the expected protected surface state of topological insulators. © 2012 American Physical Society.},
  author       = {Alpichshev, Zhanybek and Biswas, Rudro and Balatsky, Alexander and Analytis, James and Chu, Jiunhaw and Fisher, Ian and Kapitulnik, Aharon},
  journal      = {Physical Review Letters},
  number       = {20},
  publisher    = {American Physical Society},
  title        = {{STM imaging of impurity resonances on Bi 2Se 3}},
  doi          = {10.1103/PhysRevLett.108.206402},
  volume       = {108},
  year         = {2012},
}

@article{3246,
  abstract     = {Visualizing and analyzing shape changes at various scales, ranging from single molecules to whole organisms, are essential for understanding complex morphogenetic processes, such as early embryonic development. Embryo morphogenesis relies on the interplay between different tissues, the properties of which are again determined by the interaction between their constituent cells. Cell interactions, on the other hand, are controlled by various molecules, such as signaling and adhesion molecules, which in order to exert their functions need to be spatiotemporally organized within and between the interacting cells. In this review, we will focus on the role of cell adhesion functioning at different scales to organize cell, tissue and embryo morphogenesis. We will specifically ask how the subcellular distribution of adhesion molecules controls the formation of cell-cell contacts, how cell-cell contacts determine tissue shape, and how tissue interactions regulate embryo morphogenesis.},
  author       = {Barone, Vanessa and Heisenberg, Carl-Philipp J},
  journal      = {Current Opinion in Cell Biology},
  number       = {1},
  pages        = {148 -- 153},
  publisher    = {Elsevier},
  title        = {{Cell adhesion in embryo morphogenesis}},
  doi          = {10.1016/j.ceb.2011.11.006},
  volume       = {24},
  year         = {2012},
}

@article{3157,
  abstract     = {Colorectal tumours that are wild type for KRAS are often sensitive to EGFR blockade, but almost always develop resistance within several months of initiating therapy. The mechanisms underlying this acquired resistance to anti-EGFR antibodies are largely unknown. This situation is in marked contrast to that of small-molecule targeted agents, such as inhibitors of ABL, EGFR, BRAF and MEK, in which mutations in the genes encoding the protein targets render the tumours resistant to the effects of the drugs. The simplest hypothesis to account for the development of resistance to EGFR blockade is that rare cells with KRAS mutations pre-exist at low levels in tumours with ostensibly wild-type KRAS genes. Although this hypothesis would seem readily testable, there is no evidence in pre-clinical models to support it, nor is there data from patients. To test this hypothesis, we determined whether mutant KRAS DNA could be detected in the circulation of 28 patients receiving monotherapy with panitumumab, a therapeutic anti-EGFR antibody. We found that 9 out of 24 (38%) patients whose tumours were initially KRAS wild type developed detectable mutations in KRAS in their sera, three of which developed multiple different KRAS mutations. The appearance of these mutations was very consistent, generally occurring between 5 and 6months following treatment. Mathematical modelling indicated that the mutations were present in expanded subclones before the initiation of panitumumab treatment. These results suggest that the emergence of KRAS mutations is a mediator of acquired resistance to EGFR blockade and that these mutations can be detected in a non-invasive manner. They explain why solid tumours develop resistance to targeted therapies in a highly reproducible fashion.},
  author       = {Diaz Jr, Luis and Williams, Richard and Wu, Jian and Kinde, Isaac and Hecht, Joel and Berlin, Jordan and Allen, Benjamin and Božić, Ivana and Reiter, Johannes and Nowak, Martin and Kinzler, Kenneth and Oliner, Kelly and Vogelstein, Bert},
  journal      = {Nature},
  number       = {7404},
  pages        = {537 -- 540},
  publisher    = {Nature Publishing Group},
  title        = {{The molecular evolution of acquired resistance to targeted EGFR blockade in colorectal cancers}},
  doi          = {10.1038/nature11219},
  volume       = {486},
  year         = {2012},
}

@article{3260,
  abstract     = {Many scenarios in the living world, where individual organisms compete for winning positions (or resources), have properties of auctions. Here we study the evolution of bids in biological auctions. For each auction, n individuals are drawn at random from a population of size N. Each individual makes a bid which entails a cost. The winner obtains a benefit of a certain value. Costs and benefits are translated into reproductive success (fitness). Therefore, successful bidding strategies spread in the population. We compare two types of auctions. In “biological all-pay auctions”, the costs are the bid for every participating individual. In “biological second price all-pay auctions”, the cost for everyone other than the winner is the bid, but the cost for the winner is the second highest bid. Second price all-pay auctions are generalizations of the “war of attrition” introduced by Maynard Smith. We study evolutionary dynamics in both types of auctions. We calculate pairwise invasion plots and evolutionarily stable distributions over the continuous strategy space. We find that the average bid in second price all-pay auctions is higher than in all-pay auctions, but the average cost for the winner is similar in both auctions. In both cases, the average bid is a declining function of the number of participants, n. The more individuals participate in an auction the smaller is the chance of winning, and thus expensive bids must be avoided.
},
  author       = {Chatterjee, Krishnendu and Reiter, Johannes and Nowak, Martin},
  journal      = {Theoretical Population Biology},
  number       = {1},
  pages        = {69 -- 80},
  publisher    = {Academic Press},
  title        = {{Evolutionary dynamics of biological auctions}},
  doi          = {10.1016/j.tpb.2011.11.003},
  volume       = {81},
  year         = {2012},
}

@inproceedings{3251,
  abstract     = {Many infinite state systems can be seen as well-structured transition systems (WSTS), i.e., systems equipped with a well-quasi-ordering on states that is also a simulation relation. WSTS are an attractive target for formal analysis because there exist generic algorithms that decide interesting verification problems for this class. Among the most popular algorithms are acceleration-based forward analyses for computing the covering set. Termination of these algorithms can only be guaranteed for flattable WSTS. Yet, many WSTS of practical interest are not flattable and the question whether any given WSTS is flattable is itself undecidable. We therefore propose an analysis that computes the covering set and captures the essence of acceleration-based algorithms, but sacrifices precision for guaranteed termination. Our analysis is an abstract interpretation whose abstract domain builds on the ideal completion of the well-quasi-ordered state space, and a widening operator that mimics acceleration and controls the loss of precision of the analysis. We present instances of our framework for various classes of WSTS. Our experience with a prototype implementation indicates that, despite the inherent precision loss, our analysis often computes the precise covering set of the analyzed system.},
  author       = {Zufferey, Damien and Wies, Thomas and Henzinger, Thomas A},
  location     = {Philadelphia, PA, USA},
  pages        = {445 -- 460},
  publisher    = {Springer},
  title        = {{Ideal abstractions for well structured transition systems}},
  doi          = {10.1007/978-3-642-27940-9_29},
  volume       = {7148},
  year         = {2012},
}

@article{3258,
  abstract     = {CA3 pyramidal neurons are important for memory formation and pattern completion in the hippocampal network. It is generally thought that proximal synapses from the mossy fibers activate these neurons most efficiently, whereas distal inputs from the perforant path have a weaker modulatory influence. We used confocally targeted patch-clamp recording from dendrites and axons to map the activation of rat CA3 pyramidal neurons at the subcellular level. Our results reveal two distinct dendritic domains. In the proximal domain, action potentials initiated in the axon backpropagate actively with large amplitude and fast time course. In the distal domain, Na+ channel–mediated dendritic spikes are efficiently initiated by waveforms mimicking synaptic events. CA3 pyramidal neuron dendrites showed a high Na+-to-K+ conductance density ratio, providing ideal conditions for active backpropagation and dendritic spike initiation. Dendritic spikes may enhance the computational power of CA3 pyramidal neurons in the hippocampal network.},
  author       = {Kim, Sooyun and Guzmán, José and Hu, Hua and Jonas, Peter M},
  issn         = {1546-1726},
  journal      = {Nature Neuroscience},
  number       = {4},
  pages        = {600 -- 606},
  publisher    = {Nature Publishing Group},
  title        = {{Active dendrites support efficient initiation of dendritic spikes in hippocampal CA3 pyramidal neurons}},
  doi          = {10.1038/nn.3060},
  volume       = {15},
  year         = {2012},
}

@phdthesis{2964,
  abstract     = {CA3 pyramidal neurons are important for memory formation and pattern completion in the hippocampal network. These neurons receive multiple excitatory inputs from numerous sources. Therefore, the rules of spatiotemporal integration of multiple synaptic inputs and propagation of action potentials are important to understand how CA3 neurons contribute to higher brain functions at cellular level. By using confocally targeted patch-clamp recording techniques, we investigated the biophysical properties of rat CA3 pyramidal neuron dendrites. We found two distinct dendritic domains critical for action potential initiation and propagation: In the proximal domain, action potentials initiated in the axon backpropagate actively with large amplitude and fast time course. In the distal domain, Na+-channel mediated dendritic spikes are efficiently evoked by local dendritic depolarization or waveforms mimicking synaptic events. These findings can be explained by a high Na+-to-K+ conductance density ratio of CA3 pyramidal neuron dendrites. The results challenge the prevailing view that proximal mossy fiber inputs activate CA3 pyramidal neurons more efficiently than distal perforant inputs by showing that the distal synapses trigger a different form of activity represented by dendritic spikes. The high probability of dendritic spike initiation in the distal area may enhance the computational power of CA3 pyramidal neurons in the hippocampal network.  },
  author       = {Kim, Sooyun},
  issn         = {2663-337X},
  pages        = {65},
  publisher    = {Institute of Science and Technology Austria},
  title        = {{Active properties of hippocampal CA3 pyramidal neuron dendrites}},
  year         = {2012},
}