--- _id: '2955' abstract: - lang: eng text: 'We consider two-player stochastic games played on finite graphs with reachability objectives where the first player tries to ensure a target state to be visited almost-surely (i.e., with probability 1), or positively (i.e., with positive probability), no matter the strategy of the second player. We classify such games according to the information and the power of randomization available to the players. On the basis of information, the game can be one-sided with either (a) player 1, or (b) player 2 having partial observation (and the other player has perfect observation), or two-sided with (c) both players having partial observation. On the basis of randomization, the players (a) may not be allowed to use randomization (pure strategies), or (b) may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or (c) may use full randomization. Our main results for pure strategies are as follows. (1) For one-sided games with player 1 having partial observation we show that (in contrast to full randomized strategies) belief-based (subset-construction based) strategies are not sufficient, and we present an exponential upper bound on memory both for almostsure and positive winning strategies; we show that the problem of deciding the existence of almost-sure and positive winning strategies for player 1 is EXPTIME-complete. (2) For one-sided games with player 2 having partial observation we show that non-elementary memory is both necessary and sufficient for both almost-sure and positive winning strategies. (3) We show that for the general (two-sided) case finite-memory strategies are sufficient for both positive and almost-sure winning, and at least non-elementary memory is required. We establish the equivalence of the almost-sure winning problems for pure strategies and for randomized strategies with actions invisible. Our equivalence result exhibits serious flaws in previous results of the literature: we show a non-elementary memory lower bound for almost-sure winning whereas an exponential upper bound was previously claimed.' acknowledgement: 'This work was partially supported by FWF Grant No P 23499-N23, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.' article_number: '6280436' author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Laurent full_name: Doyen, Laurent last_name: Doyen citation: ama: 'Chatterjee K, Doyen L. Partial-observation stochastic games: How to win when belief fails. In: Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. IEEE; 2012. doi:10.1109/LICS.2012.28' apa: 'Chatterjee, K., & Doyen, L. (2012). Partial-observation stochastic games: How to win when belief fails. In Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. Dubrovnik, Croatia: IEEE. https://doi.org/10.1109/LICS.2012.28' chicago: 'Chatterjee, Krishnendu, and Laurent Doyen. “Partial-Observation Stochastic Games: How to Win When Belief Fails.” In Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. IEEE, 2012. https://doi.org/10.1109/LICS.2012.28.' ieee: 'K. Chatterjee and L. Doyen, “Partial-observation stochastic games: How to win when belief fails,” in Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, Dubrovnik, Croatia, 2012.' ista: 'Chatterjee K, Doyen L. 2012. Partial-observation stochastic games: How to win when belief fails. Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, 6280436.' mla: 'Chatterjee, Krishnendu, and Laurent Doyen. “Partial-Observation Stochastic Games: How to Win When Belief Fails.” Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, 6280436, IEEE, 2012, doi:10.1109/LICS.2012.28.' short: K. Chatterjee, L. Doyen, in:, Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2012. conference: end_date: 2012-06-28 location: Dubrovnik, Croatia name: 'LICS: Logic in Computer Science' start_date: 2012-06-25 date_created: 2018-12-11T12:00:32Z date_published: 2012-08-23T00:00:00Z date_updated: 2023-02-23T12:23:43Z day: '23' department: - _id: KrCh doi: 10.1109/LICS.2012.28 ec_funded: 1 external_id: arxiv: - '1107.2141' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1107.2141 month: '08' oa: 1 oa_version: Preprint project: - _id: 2584A770-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: P 23499-N23 name: Modern Graph Algorithmic Techniques in Formal Verification - _id: 25832EC2-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S 11407_N23 name: Rigorous Systems Engineering - _id: 2581B60A-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '279307' name: 'Quantitative Graph Games: Theory and Applications' - _id: 2587B514-B435-11E9-9278-68D0E5697425 name: Microsoft Research Faculty Fellowship publication: Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science publication_status: published publisher: IEEE publist_id: '3771' quality_controlled: '1' related_material: record: - id: '2211' relation: later_version status: public - id: '5381' relation: earlier_version status: public scopus_import: 1 status: public title: 'Partial-observation stochastic games: How to win when belief fails' type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2012' ... --- _id: '3341' abstract: - lang: eng text: 'We consider two-player stochastic games played on a finite state space for an infinite number of rounds. The games are concurrent: in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the two moves determine a probability distribution over the successor states. We also consider the important special case of turn-based stochastic games where players make moves in turns, rather than concurrently. We study concurrent games with \omega-regular winning conditions specified as parity objectives. The value for player 1 for a parity objective is the maximal probability with which the player can guarantee the satisfaction of the objective against all strategies of the opponent. We study the problem of continuity and robustness of the value function in concurrent and turn-based stochastic parity gameswith respect to imprecision in the transition probabilities. We present quantitative bounds on the difference of the value function (in terms of the imprecision of the transition probabilities) and show the value continuity for structurally equivalent concurrent games (two games are structurally equivalent if the support of the transition function is same and the probabilities differ). We also show robustness of optimal strategies for structurally equivalent turn-based stochastic parity games. Finally we show that the value continuity property breaks without the structurally equivalent assumption (even for Markov chains) and show that our quantitative bound is asymptotically optimal. Hence our results are tight (the assumption is both necessary and sufficient) and optimal (our quantitative bound is asymptotically optimal).' alternative_title: - LNCS author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X citation: ama: 'Chatterjee K. Robustness of structurally equivalent concurrent parity games. In: Vol 7213. Springer; 2012:270-285. doi:10.1007/978-3-642-28729-9_18' apa: 'Chatterjee, K. (2012). Robustness of structurally equivalent concurrent parity games (Vol. 7213, pp. 270–285). Presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Tallinn, Estonia: Springer. https://doi.org/10.1007/978-3-642-28729-9_18' chicago: Chatterjee, Krishnendu. “Robustness of Structurally Equivalent Concurrent Parity Games,” 7213:270–85. Springer, 2012. https://doi.org/10.1007/978-3-642-28729-9_18. ieee: 'K. Chatterjee, “Robustness of structurally equivalent concurrent parity games,” presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Tallinn, Estonia, 2012, vol. 7213, pp. 270–285.' ista: 'Chatterjee K. 2012. Robustness of structurally equivalent concurrent parity games. FoSSaCS: Foundations of Software Science and Computation Structures, LNCS, vol. 7213, 270–285.' mla: Chatterjee, Krishnendu. Robustness of Structurally Equivalent Concurrent Parity Games. Vol. 7213, Springer, 2012, pp. 270–85, doi:10.1007/978-3-642-28729-9_18. short: K. Chatterjee, in:, Springer, 2012, pp. 270–285. conference: end_date: 2012-04-01 location: Tallinn, Estonia name: 'FoSSaCS: Foundations of Software Science and Computation Structures' start_date: 2012-03-24 date_created: 2018-12-11T12:02:46Z date_published: 2012-03-22T00:00:00Z date_updated: 2023-02-23T12:23:46Z day: '22' department: - _id: KrCh doi: 10.1007/978-3-642-28729-9_18 ec_funded: 1 external_id: arxiv: - '1107.2009' intvolume: ' 7213' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1107.2009 month: '03' oa: 1 oa_version: Preprint page: 270 - 285 project: - _id: 2584A770-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: P 23499-N23 name: Modern Graph Algorithmic Techniques in Formal Verification - _id: 25832EC2-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S 11407_N23 name: Rigorous Systems Engineering - _id: 2581B60A-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '279307' name: 'Quantitative Graph Games: Theory and Applications' - _id: 2587B514-B435-11E9-9278-68D0E5697425 name: Microsoft Research Faculty Fellowship publication_status: published publisher: Springer publist_id: '3284' quality_controlled: '1' related_material: record: - id: '5382' relation: earlier_version status: public scopus_import: 1 status: public title: Robustness of structurally equivalent concurrent parity games type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 7213 year: '2012' ... --- _id: '2957' abstract: - lang: eng text: 'We consider probabilistic automata on infinite words with acceptance defined by parity conditions. We consider three qualitative decision problems: (i) the positive decision problem asks whether there is a word that is accepted with positive probability; (ii) the almost decision problem asks whether there is a word that is accepted with probability 1; and (iii) the limit decision problem asks whether words are accepted with probability arbitrarily close to 1. We unify and generalize several decidability results for probabilistic automata over infinite words, and identify a robust (closed under union and intersection) subclass of probabilistic automata for which all the qualitative decision problems are decidable for parity conditions. We also show that if the input words are restricted to lasso shape (regular) words, then the positive and almost problems are decidable for all probabilistic automata with parity conditions. For most decidable problems we show an optimal PSPACE-complete complexity bound.' article_number: '6280437' author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Mathieu full_name: Tracol, Mathieu id: 3F54FA38-F248-11E8-B48F-1D18A9856A87 last_name: Tracol citation: ama: 'Chatterjee K, Tracol M. Decidable problems for probabilistic automata on infinite words. In: Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. IEEE; 2012. doi:10.1109/LICS.2012.29' apa: 'Chatterjee, K., & Tracol, M. (2012). Decidable problems for probabilistic automata on infinite words. In Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. Dubrovnik, Croatia : IEEE. https://doi.org/10.1109/LICS.2012.29' chicago: Chatterjee, Krishnendu, and Mathieu Tracol. “Decidable Problems for Probabilistic Automata on Infinite Words.” In Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. IEEE, 2012. https://doi.org/10.1109/LICS.2012.29. ieee: K. Chatterjee and M. Tracol, “Decidable problems for probabilistic automata on infinite words,” in Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, Dubrovnik, Croatia , 2012. ista: 'Chatterjee K, Tracol M. 2012. Decidable problems for probabilistic automata on infinite words. Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, 6280437.' mla: Chatterjee, Krishnendu, and Mathieu Tracol. “Decidable Problems for Probabilistic Automata on Infinite Words.” Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, 6280437, IEEE, 2012, doi:10.1109/LICS.2012.29. short: K. Chatterjee, M. Tracol, in:, Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2012. conference: end_date: 2012-06-28 location: 'Dubrovnik, Croatia ' name: 'LICS: Logic in Computer Science' start_date: 2012-06-25 date_created: 2018-12-11T12:00:33Z date_published: 2012-08-23T00:00:00Z date_updated: 2023-02-23T12:23:51Z day: '23' department: - _id: KrCh doi: 10.1109/LICS.2012.29 ec_funded: 1 external_id: arxiv: - '1107.2091' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1107.2091 month: '08' oa: 1 oa_version: Preprint project: - _id: 2584A770-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: P 23499-N23 name: Modern Graph Algorithmic Techniques in Formal Verification - _id: 25832EC2-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S 11407_N23 name: Rigorous Systems Engineering - _id: 2581B60A-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '279307' name: 'Quantitative Graph Games: Theory and Applications' - _id: 2587B514-B435-11E9-9278-68D0E5697425 name: Microsoft Research Faculty Fellowship publication: Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science publication_status: published publisher: IEEE publist_id: '3769' quality_controlled: '1' related_material: record: - id: '5384' relation: earlier_version status: public scopus_import: 1 status: public title: Decidable problems for probabilistic automata on infinite words type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2012' ... --- _id: '3249' abstract: - lang: eng text: Boolean notions of correctness are formalized by preorders on systems. Quantitative measures of correctness can be formalized by real-valued distance functions between systems, where the distance between implementation and specification provides a measure of "fit" or "desirability". We extend the simulation preorder to the quantitative setting by making each player of a simulation game pay a certain price for her choices. We use the resulting games with quantitative objectives to define three different simulation distances. The correctness distance measures how much the specification must be changed in order to be satisfied by the implementation. The coverage distance measures how much the implementation restricts the degrees of freedom offered by the specification. The robustness distance measures how much a system can deviate from the implementation description without violating the specification. We consider these distances for safety as well as liveness specifications. The distances can be computed in polynomial time for safety specifications, and for liveness specifications given by weak fairness constraints. We show that the distance functions satisfy the triangle inequality, that the distance between two systems does not increase under parallel composition with a third system, and that the distance between two systems can be bounded from above and below by distances between abstractions of the two systems. These properties suggest that our simulation distances provide an appropriate basis for a quantitative theory of discrete systems. We also demonstrate how the robustness distance can be used to measure how many transmission errors are tolerated by error correcting codes. acknowledgement: This work was partially supported by the ERC Advanced Grant QUAREM, the FWF NFN Grant S11402-N23 (RiSE), the European Union project COMBEST and the European Network of Excellence Artist Design. author: - first_name: Pavol full_name: Cerny, Pavol id: 4DCBEFFE-F248-11E8-B48F-1D18A9856A87 last_name: Cerny - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 - first_name: Arjun full_name: Radhakrishna, Arjun id: 3B51CAC4-F248-11E8-B48F-1D18A9856A87 last_name: Radhakrishna citation: ama: Cerny P, Henzinger TA, Radhakrishna A. Simulation distances. Theoretical Computer Science. 2012;413(1):21-35. doi:10.1016/j.tcs.2011.08.002 apa: Cerny, P., Henzinger, T. A., & Radhakrishna, A. (2012). Simulation distances. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2011.08.002 chicago: Cerny, Pavol, Thomas A Henzinger, and Arjun Radhakrishna. “Simulation Distances.” Theoretical Computer Science. Elsevier, 2012. https://doi.org/10.1016/j.tcs.2011.08.002. ieee: P. Cerny, T. A. Henzinger, and A. Radhakrishna, “Simulation distances,” Theoretical Computer Science, vol. 413, no. 1. Elsevier, pp. 21–35, 2012. ista: Cerny P, Henzinger TA, Radhakrishna A. 2012. Simulation distances. Theoretical Computer Science. 413(1), 21–35. mla: Cerny, Pavol, et al. “Simulation Distances.” Theoretical Computer Science, vol. 413, no. 1, Elsevier, 2012, pp. 21–35, doi:10.1016/j.tcs.2011.08.002. short: P. Cerny, T.A. Henzinger, A. Radhakrishna, Theoretical Computer Science 413 (2012) 21–35. date_created: 2018-12-11T12:02:15Z date_published: 2012-01-06T00:00:00Z date_updated: 2023-02-23T12:24:04Z day: '06' department: - _id: ToHe doi: 10.1016/j.tcs.2011.08.002 ec_funded: 1 intvolume: ' 413' issue: '1' language: - iso: eng month: '01' oa_version: None page: 21 - 35 project: - _id: 25EE3708-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '267989' name: Quantitative Reactive Modeling - _id: 25832EC2-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S 11407_N23 name: Rigorous Systems Engineering - _id: 25EFB36C-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '215543' name: COMponent-Based Embedded Systems design Techniques - _id: 25F1337C-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '214373' name: Design for Embedded Systems publication: Theoretical Computer Science publication_status: published publisher: Elsevier publist_id: '3408' pubrep_id: '42' quality_controlled: '1' related_material: record: - id: '4393' relation: earlier_version status: public - id: '5389' relation: earlier_version status: public scopus_import: 1 status: public title: Simulation distances type: journal_article user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 413 year: '2012' ... --- _id: '3124' abstract: - lang: eng text: "We consider the problem of inference in a graphical model with binary variables. While in theory it is arguably preferable to compute marginal probabilities, in practice researchers often use MAP inference due to the availability of efficient discrete optimization algorithms. We bridge the gap between the two approaches by introducing the Discrete Marginals technique in which approximate marginals are obtained by minimizing an objective function with unary and pairwise terms over a discretized domain. This allows the use of techniques originally developed for MAP-MRF inference and learning. We explore two ways to set up the objective function - by discretizing the Bethe free energy and by learning it from training data. Experimental results show that for certain types of graphs a learned function can outperform the Bethe approximation. We also establish a link between the Bethe free energy and submodular functions.\r\n" alternative_title: - Inferning 2012 author: - first_name: Filip full_name: Korc, Filip id: 476A2FD6-F248-11E8-B48F-1D18A9856A87 last_name: Korc - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Christoph full_name: Lampert, Christoph id: 40C20FD2-F248-11E8-B48F-1D18A9856A87 last_name: Lampert orcid: 0000-0001-8622-7887 citation: ama: 'Korc F, Kolmogorov V, Lampert C. Approximating marginals using discrete energy minimization. In: ICML; 2012.' apa: 'Korc, F., Kolmogorov, V., & Lampert, C. (2012). Approximating marginals using discrete energy minimization. Presented at the ICML: International Conference on Machine Learning, Edinburgh, Scotland: ICML.' chicago: Korc, Filip, Vladimir Kolmogorov, and Christoph Lampert. “Approximating Marginals Using Discrete Energy Minimization.” ICML, 2012. ieee: 'F. Korc, V. Kolmogorov, and C. Lampert, “Approximating marginals using discrete energy minimization,” presented at the ICML: International Conference on Machine Learning, Edinburgh, Scotland, 2012.' ista: 'Korc F, Kolmogorov V, Lampert C. 2012. Approximating marginals using discrete energy minimization. ICML: International Conference on Machine Learning, Inferning 2012, .' mla: Korc, Filip, et al. Approximating Marginals Using Discrete Energy Minimization. ICML, 2012. short: F. Korc, V. Kolmogorov, C. Lampert, in:, ICML, 2012. conference: end_date: 2012-07-01 location: Edinburgh, Scotland name: 'ICML: International Conference on Machine Learning' start_date: 2012-06-26 date_created: 2018-12-11T12:01:31Z date_published: 2012-06-30T00:00:00Z date_updated: 2023-02-23T12:24:24Z day: '30' ddc: - '000' department: - _id: ChLa - _id: VlKo file: - access_level: open_access checksum: 3d0d4246548c736857302aadb2ff5d15 content_type: application/pdf creator: system date_created: 2018-12-12T10:11:34Z date_updated: 2020-07-14T12:46:00Z file_id: '4889' file_name: IST-2016-565-v1+1_DM-inferning2012.pdf file_size: 305836 relation: main_file file_date_updated: 2020-07-14T12:46:00Z has_accepted_license: '1' language: - iso: eng month: '06' oa: 1 oa_version: Submitted Version publication_status: published publisher: ICML publist_id: '3575' pubrep_id: '565' quality_controlled: '1' related_material: record: - id: '5396' relation: later_version status: public status: public title: Approximating marginals using discrete energy minimization type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 year: '2012' ... --- _id: '5396' abstract: - lang: eng text: We consider the problem of inference in agraphical model with binary variables. While in theory it is arguably preferable to compute marginal probabilities, in practice researchers often use MAP inference due to the availability of efficient discrete optimization algorithms. We bridge the gap between the two approaches by introducing the Discrete Marginals technique in which approximate marginals are obtained by minimizing an objective function with unary and pair-wise terms over a discretized domain. This allows the use of techniques originally devel-oped for MAP-MRF inference and learning. We explore two ways to set up the objective function - by discretizing the Bethe free energy and by learning it from training data. Experimental results show that for certain types of graphs a learned function can out-perform the Bethe approximation. We also establish a link between the Bethe free energy and submodular functions. alternative_title: - IST Austria Technical Report author: - first_name: Filip full_name: Korc, Filip id: 476A2FD6-F248-11E8-B48F-1D18A9856A87 last_name: Korc - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Christoph full_name: Lampert, Christoph id: 40C20FD2-F248-11E8-B48F-1D18A9856A87 last_name: Lampert orcid: 0000-0001-8622-7887 citation: ama: Korc F, Kolmogorov V, Lampert C. Approximating Marginals Using Discrete Energy Minimization. IST Austria; 2012. doi:10.15479/AT:IST-2012-0003 apa: Korc, F., Kolmogorov, V., & Lampert, C. (2012). Approximating marginals using discrete energy minimization. IST Austria. https://doi.org/10.15479/AT:IST-2012-0003 chicago: Korc, Filip, Vladimir Kolmogorov, and Christoph Lampert. Approximating Marginals Using Discrete Energy Minimization. IST Austria, 2012. https://doi.org/10.15479/AT:IST-2012-0003. ieee: F. Korc, V. Kolmogorov, and C. Lampert, Approximating marginals using discrete energy minimization. IST Austria, 2012. ista: Korc F, Kolmogorov V, Lampert C. 2012. Approximating marginals using discrete energy minimization, IST Austria, 13p. mla: Korc, Filip, et al. Approximating Marginals Using Discrete Energy Minimization. IST Austria, 2012, doi:10.15479/AT:IST-2012-0003. short: F. Korc, V. Kolmogorov, C. Lampert, Approximating Marginals Using Discrete Energy Minimization, IST Austria, 2012. date_created: 2018-12-12T11:39:06Z date_published: 2012-07-23T00:00:00Z date_updated: 2023-02-23T11:13:22Z day: '23' ddc: - '000' department: - _id: VlKo - _id: ChLa doi: 10.15479/AT:IST-2012-0003 file: - access_level: open_access checksum: 7e0ba85ad123b13223aaf6cdde2d288c content_type: application/pdf creator: system date_created: 2018-12-12T11:53:29Z date_updated: 2020-07-14T12:46:44Z file_id: '5490' file_name: IST-2012-0003_IST-2012-0003.pdf file_size: 618744 relation: main_file file_date_updated: 2020-07-14T12:46:44Z has_accepted_license: '1' language: - iso: eng month: '07' oa: 1 oa_version: Published Version page: '13' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '36' related_material: record: - id: '3124' relation: earlier_version status: public status: public title: Approximating marginals using discrete energy minimization type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2012' ... --- _id: '5398' abstract: - lang: eng text: This document is created as a part of the project “Repository for Research Data on IST Austria”. It summarises the actual state of research data at IST Austria, based on survey results. It supports the choice of appropriate software, which would best fit the requirements of their users, the researchers. author: - first_name: Jana full_name: Porsche, Jana id: 3252EDC2-F248-11E8-B48F-1D18A9856A87 last_name: Porsche citation: ama: Porsche J. Actual State of Research Data @ ISTAustria. IST Austria; 2012. apa: Porsche, J. (2012). Actual state of research data @ ISTAustria. IST Austria. chicago: Porsche, Jana. Actual State of Research Data @ ISTAustria. IST Austria, 2012. ieee: J. Porsche, Actual state of research data @ ISTAustria. IST Austria, 2012. ista: Porsche J. 2012. Actual state of research data @ ISTAustria, IST Austria,p. mla: Porsche, Jana. Actual State of Research Data @ ISTAustria. IST Austria, 2012. short: J. Porsche, Actual State of Research Data @ ISTAustria, IST Austria, 2012. date_created: 2018-12-12T11:39:06Z date_published: 2012-11-12T00:00:00Z date_updated: 2020-07-14T23:04:49Z day: '12' ddc: - '020' department: - _id: E-Lib file: - access_level: open_access checksum: e0a7c041eea1ca4b70ab6f9ec5177f4e content_type: application/pdf creator: system date_created: 2018-12-12T11:53:11Z date_updated: 2020-07-14T12:46:44Z file_id: '5472' file_name: IST-2012-103-v1+1_Actual_state_of_research_data_@_IST_Austria.pdf file_size: 238544 relation: main_file file_date_updated: 2020-07-14T12:46:44Z has_accepted_license: '1' language: - iso: eng month: '11' oa: 1 oa_version: Published Version publication_status: published publisher: IST Austria pubrep_id: '103' status: public title: Actual state of research data @ ISTAustria type: report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2012' ... --- _id: '5839' abstract: - lang: eng text: "Canny's edge detection algorithm is a classical and robust method for edge detection in gray-scale images. The two \r\nsignificant features of this method are introduction of NMS (Non-Maximum Suppression) and double thresholding of \r\nthe \ gradient image. Due to poor illumination, the region boundaries in \ an image may become vague, creating \r\nuncertainties in the gradient \ image. In this paper, we have proposed an algorithm based on the \ concept of type-2 fuzzy sets to handle uncertainties that automatically \ selects the threshold values needed to segment the gradient image using classical Canny’s edge detection algorithm. The results show that our algorithm works significantly well on different benchmark images as well as medical images (hand radiography images). " author: - first_name: Ranita full_name: Biswas, Ranita id: 3C2B033E-F248-11E8-B48F-1D18A9856A87 last_name: Biswas orcid: 0000-0002-5372-7890 - first_name: Jaya full_name: Sil, Jaya last_name: Sil citation: ama: Biswas R, Sil J. An Improved Canny Edge Detection Algorithm Based on Type-2 Fuzzy Sets. Procedia Technology. 2012;4:820-824. doi:10.1016/j.protcy.2012.05.134 apa: Biswas, R., & Sil, J. (2012). An Improved Canny Edge Detection Algorithm Based on Type-2 Fuzzy Sets. Procedia Technology. Elsevier. https://doi.org/10.1016/j.protcy.2012.05.134 chicago: Biswas, Ranita, and Jaya Sil. “An Improved Canny Edge Detection Algorithm Based on Type-2 Fuzzy Sets.” Procedia Technology. Elsevier, 2012. https://doi.org/10.1016/j.protcy.2012.05.134. ieee: R. Biswas and J. Sil, “An Improved Canny Edge Detection Algorithm Based on Type-2 Fuzzy Sets,” Procedia Technology, vol. 4. Elsevier, pp. 820–824, 2012. ista: Biswas R, Sil J. 2012. An Improved Canny Edge Detection Algorithm Based on Type-2 Fuzzy Sets. Procedia Technology. 4, 820–824. mla: Biswas, Ranita, and Jaya Sil. “An Improved Canny Edge Detection Algorithm Based on Type-2 Fuzzy Sets.” Procedia Technology, vol. 4, Elsevier, 2012, pp. 820–24, doi:10.1016/j.protcy.2012.05.134. short: R. Biswas, J. Sil, Procedia Technology 4 (2012) 820–824. date_created: 2019-01-17T11:54:21Z date_published: 2012-05-01T00:00:00Z date_updated: 2021-01-12T08:03:43Z day: '01' ddc: - '000' doi: 10.1016/j.protcy.2012.05.134 extern: '1' file: - access_level: open_access checksum: ba0185986b151d8c11201f48cd505ceb content_type: application/pdf creator: dernst date_created: 2019-01-21T07:28:06Z date_updated: 2020-07-14T12:47:12Z file_id: '5863' file_name: 2012_Procedia_Biswas.pdf file_size: 305426 relation: main_file file_date_updated: 2020-07-14T12:47:12Z has_accepted_license: '1' intvolume: ' 4' language: - iso: eng license: https://creativecommons.org/licenses/by-nc-nd/4.0/ month: '05' oa: 1 oa_version: Published Version page: 820-824 publication: Procedia Technology publication_identifier: issn: - 2212-0173 publication_status: published publisher: Elsevier quality_controlled: '1' status: public title: An Improved Canny Edge Detection Algorithm Based on Type-2 Fuzzy Sets tmp: image: /images/cc_by_nc_nd.png legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) short: CC BY-NC-ND (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 4 year: '2012' ... --- _id: '596' abstract: - lang: eng text: The human Mediator complex controls RNA polymerase II (pol II) function in ways that remain incompletely understood. Activator-Mediator binding alters Mediator structure, and these activator-induced structural shifts appear to play key roles in regulating transcription. A recent cryo-electron microscopy (EM) analysis revealed that pol II adopted a stable orientation within a Mediator-pol II-TFIIF assembly in which Mediator was bound to the activation domain of viral protein 16 (VP16). Whereas TFIIF was shown to be important for orienting pol II within this assembly, the potential role of the activator was not assessed. To determine how activator binding might affect pol II orientation, we isolated human Mediator-pol II-TFIIF complexes in which Mediator was not bound to an activator. Cryo-EM analysis of this assembly, coupled with pol II crystal structure docking, revealed that pol II binds Mediator at the same general location; however, in contrast to VP16-bound Mediator, pol II does not appear to stably orient in the absence of an activator. Variability in pol II orientation might be important mechanistically, perhaps to enable sense and antisense transcription at human promoters. Because Mediator interacts extensively with pol II, these results suggest that Mediator structural shifts induced by activator binding help stably orient pol II prior to transcription initiation. article_processing_charge: No author: - first_name: Carrie A full_name: Bernecky, Carrie A id: 2CB9DFE2-F248-11E8-B48F-1D18A9856A87 last_name: Bernecky orcid: 0000-0003-0893-7036 - first_name: Dylan full_name: Taatjes, Dylan last_name: Taatjes citation: ama: Bernecky C, Taatjes D. Activator-mediator binding stabilizes RNA polymerase II orientation within the human mediator-RNA polymerase II-TFIIF assembly. Journal of Molecular Biology. 2012;417(5):387-394. doi:10.1016/j.jmb.2012.02.014 apa: Bernecky, C., & Taatjes, D. (2012). Activator-mediator binding stabilizes RNA polymerase II orientation within the human mediator-RNA polymerase II-TFIIF assembly. Journal of Molecular Biology. Elsevier. https://doi.org/10.1016/j.jmb.2012.02.014 chicago: Bernecky, Carrie, and Dylan Taatjes. “Activator-Mediator Binding Stabilizes RNA Polymerase II Orientation within the Human Mediator-RNA Polymerase II-TFIIF Assembly.” Journal of Molecular Biology. Elsevier, 2012. https://doi.org/10.1016/j.jmb.2012.02.014. ieee: C. Bernecky and D. Taatjes, “Activator-mediator binding stabilizes RNA polymerase II orientation within the human mediator-RNA polymerase II-TFIIF assembly,” Journal of Molecular Biology, vol. 417, no. 5. Elsevier, pp. 387–394, 2012. ista: Bernecky C, Taatjes D. 2012. Activator-mediator binding stabilizes RNA polymerase II orientation within the human mediator-RNA polymerase II-TFIIF assembly. Journal of Molecular Biology. 417(5), 387–394. mla: Bernecky, Carrie, and Dylan Taatjes. “Activator-Mediator Binding Stabilizes RNA Polymerase II Orientation within the Human Mediator-RNA Polymerase II-TFIIF Assembly.” Journal of Molecular Biology, vol. 417, no. 5, Elsevier, 2012, pp. 387–94, doi:10.1016/j.jmb.2012.02.014. short: C. Bernecky, D. Taatjes, Journal of Molecular Biology 417 (2012) 387–394. date_created: 2018-12-11T11:47:24Z date_published: 2012-04-13T00:00:00Z date_updated: 2021-01-12T08:05:21Z day: '13' doi: 10.1016/j.jmb.2012.02.014 extern: '1' intvolume: ' 417' issue: '5' language: - iso: eng main_file_link: - open_access: '1' url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4582759/ month: '04' oa: 1 oa_version: None page: 387 - 394 publication: Journal of Molecular Biology publication_status: published publisher: Elsevier publist_id: '7208' status: public title: Activator-mediator binding stabilizes RNA polymerase II orientation within the human mediator-RNA polymerase II-TFIIF assembly type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 417 year: '2012' ... --- _id: '6136' abstract: - lang: eng text: Tonic receptors convey stimulus duration and intensity and are implicated in homeostatic control. However, how tonic homeostatic signals are generated and how they reconfigure neural circuits and modify animal behavior is poorly understood. Here we show that Caenorhabditis elegans O2-sensing neurons are tonic receptors that continuously signal ambient [O2] to set the animal's behavioral state. Sustained signaling relied on a Ca2+ relay involving L-type voltage-gated Ca2+ channels, the ryanodine and the inositol-1,4,5-trisphosphate receptors. Tonic activity evoked continuous neuropeptide release, which helps elicit the enduring behavioral state associated with high [O2]. Sustained O2 receptor signaling was propagated to downstream neural circuits, including the hub interneuron RMG. O2 receptors evoked similar locomotory states at particular O2 concentrations, regardless of previous d[O2]/dt. However, a phasic component of the URX receptors' response to high d[O2]/dt, as well as tonic-to-phasic transformations in downstream interneurons, enabled transient reorientation movements shaped by d[O2]/dt. Our results highlight how tonic homeostatic signals can generate both transient and enduring behavioral change. author: - first_name: Karl Emanuel full_name: Busch, Karl Emanuel last_name: Busch - first_name: Patrick full_name: Laurent, Patrick last_name: Laurent - first_name: Zoltan full_name: Soltesz, Zoltan last_name: Soltesz - first_name: Robin Joseph full_name: Murphy, Robin Joseph last_name: Murphy - first_name: Olivier full_name: Faivre, Olivier last_name: Faivre - first_name: Berthold full_name: Hedwig, Berthold last_name: Hedwig - first_name: Martin full_name: Thomas, Martin last_name: Thomas - first_name: Heather L full_name: Smith, Heather L last_name: Smith - first_name: Mario full_name: de Bono, Mario id: 4E3FF80E-F248-11E8-B48F-1D18A9856A87 last_name: de Bono orcid: 0000-0001-8347-0443 citation: ama: Busch KE, Laurent P, Soltesz Z, et al. Tonic signaling from O2 sensors sets neural circuit activity and behavioral state. Nature Neuroscience. 2012;15(4):581-591. doi:10.1038/nn.3061 apa: Busch, K. E., Laurent, P., Soltesz, Z., Murphy, R. J., Faivre, O., Hedwig, B., … de Bono, M. (2012). Tonic signaling from O2 sensors sets neural circuit activity and behavioral state. Nature Neuroscience. Springer Nature. https://doi.org/10.1038/nn.3061 chicago: Busch, Karl Emanuel, Patrick Laurent, Zoltan Soltesz, Robin Joseph Murphy, Olivier Faivre, Berthold Hedwig, Martin Thomas, Heather L Smith, and Mario de Bono. “Tonic Signaling from O2 Sensors Sets Neural Circuit Activity and Behavioral State.” Nature Neuroscience. Springer Nature, 2012. https://doi.org/10.1038/nn.3061. ieee: K. E. Busch et al., “Tonic signaling from O2 sensors sets neural circuit activity and behavioral state,” Nature Neuroscience, vol. 15, no. 4. Springer Nature, pp. 581–591, 2012. ista: Busch KE, Laurent P, Soltesz Z, Murphy RJ, Faivre O, Hedwig B, Thomas M, Smith HL, de Bono M. 2012. Tonic signaling from O2 sensors sets neural circuit activity and behavioral state. Nature Neuroscience. 15(4), 581–591. mla: Busch, Karl Emanuel, et al. “Tonic Signaling from O2 Sensors Sets Neural Circuit Activity and Behavioral State.” Nature Neuroscience, vol. 15, no. 4, Springer Nature, 2012, pp. 581–91, doi:10.1038/nn.3061. short: K.E. Busch, P. Laurent, Z. Soltesz, R.J. Murphy, O. Faivre, B. Hedwig, M. Thomas, H.L. Smith, M. de Bono, Nature Neuroscience 15 (2012) 581–591. date_created: 2019-03-20T14:23:30Z date_published: 2012-03-04T00:00:00Z date_updated: 2021-01-12T08:06:17Z day: '04' doi: 10.1038/nn.3061 extern: '1' external_id: pmid: - '22388961' intvolume: ' 15' issue: '4' language: - iso: eng main_file_link: - open_access: '1' url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3564487/ month: '03' oa: 1 oa_version: Submitted Version page: 581-591 pmid: 1 publication: Nature Neuroscience publication_identifier: issn: - 1097-6256 - 1546-1726 publication_status: published publisher: Springer Nature quality_controlled: '1' status: public title: Tonic signaling from O2 sensors sets neural circuit activity and behavioral state type: journal_article user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 15 year: '2012' ... --- _id: '6746' abstract: - lang: eng text: This paper proposes a novel cooperative approach for two-hop amplify-and-forward (A&F) relaying that exploits both the signal forwarded by the relay and the one directly transmitted by the source in impulse-radio ultra-wideband (IR-UWB) systems. Specifically, we focus on a non-coherent setup employing a double-differential encoding scheme at the source node and a single differential demodulation at the relay and destination. The log-likelihood ratio based decision rule is derived at the destination node. A semi-analytical power allocation strategy is presented by evaluating a closed-form expression for the effective signal to noise ratio (SNR) at the destination, which is maximized by exhaustive search. Numerical simulations show that the proposed system outperforms both the direct transmission with single differential encoding and the non-cooperative multi-hop approach in different scenarios. author: - first_name: Marco full_name: Mondelli, Marco id: 27EB676C-8706-11E9-9510-7717E6697425 last_name: Mondelli orcid: 0000-0002-3242-7020 - first_name: Qi full_name: Zhou, Qi last_name: Zhou - first_name: Xiaoli full_name: Ma, Xiaoli last_name: Ma - first_name: Vincenzo full_name: Lottici, Vincenzo last_name: Lottici citation: ama: 'Mondelli M, Zhou Q, Ma X, Lottici V. A cooperative approach for amplify-and-forward differential transmitted reference IR-UWB relay systems. In: 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE; 2012:2905-2908. doi:10.1109/icassp.2012.6288524' apa: 'Mondelli, M., Zhou, Q., Ma, X., & Lottici, V. (2012). A cooperative approach for amplify-and-forward differential transmitted reference IR-UWB relay systems. In 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (pp. 2905–2908). Kyoto, Japan: IEEE. https://doi.org/10.1109/icassp.2012.6288524' chicago: Mondelli, Marco, Qi Zhou, Xiaoli Ma, and Vincenzo Lottici. “A Cooperative Approach for Amplify-and-Forward Differential Transmitted Reference IR-UWB Relay Systems.” In 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2905–8. IEEE, 2012. https://doi.org/10.1109/icassp.2012.6288524. ieee: M. Mondelli, Q. Zhou, X. Ma, and V. Lottici, “A cooperative approach for amplify-and-forward differential transmitted reference IR-UWB relay systems,” in 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Kyoto, Japan, 2012, pp. 2905–2908. ista: 'Mondelli M, Zhou Q, Ma X, Lottici V. 2012. A cooperative approach for amplify-and-forward differential transmitted reference IR-UWB relay systems. 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). ICASSP: International Conference on Acoustics, Speech and Signal Processing, 2905–2908.' mla: Mondelli, Marco, et al. “A Cooperative Approach for Amplify-and-Forward Differential Transmitted Reference IR-UWB Relay Systems.” 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), IEEE, 2012, pp. 2905–08, doi:10.1109/icassp.2012.6288524. short: M. Mondelli, Q. Zhou, X. Ma, V. Lottici, in:, 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), IEEE, 2012, pp. 2905–2908. conference: end_date: 2012-03-30 location: Kyoto, Japan name: 'ICASSP: International Conference on Acoustics, Speech and Signal Processing' start_date: 2012-03-25 date_created: 2019-07-31T09:14:48Z date_published: 2012-07-31T00:00:00Z date_updated: 2021-01-12T08:08:49Z day: '31' doi: 10.1109/icassp.2012.6288524 extern: '1' language: - iso: eng month: '07' oa_version: None page: 2905-2908 publication: 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) publication_identifier: issn: - 1520-6149 publication_status: published publisher: IEEE quality_controlled: '1' status: public title: A cooperative approach for amplify-and-forward differential transmitted reference IR-UWB relay systems type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2012' ... --- _id: '7074' abstract: - lang: eng text: The Seebeck coefficients, electrical resistivities, total thermal conductivities, and magnetization are reported for temperatures between 5 and 350 K for n-type Bi0.88Sb0.12 nano-composite alloys made by Ho-doping at the 0, 1, and 3 % atomic levels. The alloys were prepared using a dc hot-pressing method, and are shown to be single phase for both Ho contents with grain sizes on the average of 900 nm. We find the parent compound has a maximum of ZT = 0.28 at 231 K, while doping 1 % Ho increases the maximum ZT to 0.31 at 221 K and the 3 % doped sample suppresses the maximum ZT = 0.24 at a temperature of 260 K. article_processing_charge: No article_type: original author: - first_name: K. C. full_name: Lukas, K. C. last_name: Lukas - first_name: G. full_name: Joshi, G. last_name: Joshi - first_name: Kimberly A full_name: Modic, Kimberly A id: 13C26AC0-EB69-11E9-87C6-5F3BE6697425 last_name: Modic orcid: 0000-0001-9760-3147 - first_name: Z. F. full_name: Ren, Z. F. last_name: Ren - first_name: C. P. full_name: Opeil, C. P. last_name: Opeil citation: ama: Lukas KC, Joshi G, Modic KA, Ren ZF, Opeil CP. Thermoelectric properties of Ho-doped Bi0.88Sb0.12. Journal of Materials Science. 2012;47(15):5729-5734. doi:10.1007/s10853-012-6463-6 apa: Lukas, K. C., Joshi, G., Modic, K. A., Ren, Z. F., & Opeil, C. P. (2012). Thermoelectric properties of Ho-doped Bi0.88Sb0.12. Journal of Materials Science. Springer Nature. https://doi.org/10.1007/s10853-012-6463-6 chicago: Lukas, K. C., G. Joshi, Kimberly A Modic, Z. F. Ren, and C. P. Opeil. “Thermoelectric Properties of Ho-Doped Bi0.88Sb0.12.” Journal of Materials Science. Springer Nature, 2012. https://doi.org/10.1007/s10853-012-6463-6. ieee: K. C. Lukas, G. Joshi, K. A. Modic, Z. F. Ren, and C. P. Opeil, “Thermoelectric properties of Ho-doped Bi0.88Sb0.12,” Journal of Materials Science, vol. 47, no. 15. Springer Nature, pp. 5729–5734, 2012. ista: Lukas KC, Joshi G, Modic KA, Ren ZF, Opeil CP. 2012. Thermoelectric properties of Ho-doped Bi0.88Sb0.12. Journal of Materials Science. 47(15), 5729–5734. mla: Lukas, K. C., et al. “Thermoelectric Properties of Ho-Doped Bi0.88Sb0.12.” Journal of Materials Science, vol. 47, no. 15, Springer Nature, 2012, pp. 5729–34, doi:10.1007/s10853-012-6463-6. short: K.C. Lukas, G. Joshi, K.A. Modic, Z.F. Ren, C.P. Opeil, Journal of Materials Science 47 (2012) 5729–5734. date_created: 2019-11-19T13:36:54Z date_published: 2012-08-01T00:00:00Z date_updated: 2021-01-12T08:11:43Z day: '01' doi: 10.1007/s10853-012-6463-6 extern: '1' intvolume: ' 47' issue: '15' language: - iso: eng month: '08' oa_version: None page: 5729-5734 publication: Journal of Materials Science publication_identifier: eissn: - 1573-4803 issn: - 0022-2461 publication_status: published publisher: Springer Nature quality_controlled: '1' status: public title: Thermoelectric properties of Ho-doped Bi0.88Sb0.12 type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 47 year: '2012' ... --- _id: '7308' abstract: - lang: eng text: 'Carbon has been used widely as the basis of porous cathodes for nonaqueous Li–O2 cells. However, the stability of carbon and the effect of carbon on electrolyte decomposition in such cells are complex and depend on the hydrophobicity/hydrophilicity of the carbon surface. Analyzing carbon cathodes, cycled in Li–O2 cells between 2 and 4 V, using acid treatment and Fenton’s reagent, and combined with differential electrochemical mass spectrometry and FTIR, demonstrates the following: Carbon is relatively stable below 3.5 V (vs Li/Li+) on discharge or charge, especially so for hydrophobic carbon, but is unstable on charging above 3.5 V (in the presence of Li2O2), oxidatively decomposing to form Li2CO3. Direct chemical reaction with Li2O2 accounts for only a small proportion of the total carbon decomposition on cycling. Carbon promotes electrolyte decomposition during discharge and charge in a Li–O2 cell, giving rise to Li2CO3 and Li carboxylates (DMSO and tetraglyme electrolytes). The Li2CO3 and Li carboxylates present at the end of discharge and those that form on charge result in polarization on the subsequent charge. Li2CO3 (derived from carbon and from the electrolyte) as well as the Li carboxylates (derived from the electrolyte) decompose and form on charging. Oxidation of Li2CO3 on charging to ∼4 V is incomplete; Li2CO3 accumulates on cycling resulting in electrode passivation and capacity fading. Hydrophilic carbon is less stable and more catalytically active toward electrolyte decomposition than carbon with a hydrophobic surface. If the Li–O2 cell could be charged at or below 3.5 V, then carbon may be relatively stable, however, its ability to promote electrolyte decomposition, presenting problems for its use in a practical Li–O2 battery. The results emphasize that stable cycling of Li2O2 at the cathode in a Li–O2 cell depends on the synergy between electrolyte and electrode; the stability of the electrode and the electrolyte cannot be considered in isolation.' article_processing_charge: No article_type: original author: - first_name: Muhammed M. full_name: Ottakam Thotiyl, Muhammed M. last_name: Ottakam Thotiyl - first_name: Stefan Alexander full_name: Freunberger, Stefan Alexander id: A8CA28E6-CE23-11E9-AD2D-EC27E6697425 last_name: Freunberger orcid: 0000-0003-2902-5319 - first_name: Zhangquan full_name: Peng, Zhangquan last_name: Peng - first_name: Peter G. full_name: Bruce, Peter G. last_name: Bruce citation: ama: Ottakam Thotiyl MM, Freunberger SA, Peng Z, Bruce PG. The carbon electrode in nonaqueous Li–O2 cells. Journal of the American Chemical Society. 2012;135(1):494-500. doi:10.1021/ja310258x apa: Ottakam Thotiyl, M. M., Freunberger, S. A., Peng, Z., & Bruce, P. G. (2012). The carbon electrode in nonaqueous Li–O2 cells. Journal of the American Chemical Society. ACS. https://doi.org/10.1021/ja310258x chicago: Ottakam Thotiyl, Muhammed M., Stefan Alexander Freunberger, Zhangquan Peng, and Peter G. Bruce. “The Carbon Electrode in Nonaqueous Li–O2 Cells.” Journal of the American Chemical Society. ACS, 2012. https://doi.org/10.1021/ja310258x. ieee: M. M. Ottakam Thotiyl, S. A. Freunberger, Z. Peng, and P. G. Bruce, “The carbon electrode in nonaqueous Li–O2 cells,” Journal of the American Chemical Society, vol. 135, no. 1. ACS, pp. 494–500, 2012. ista: Ottakam Thotiyl MM, Freunberger SA, Peng Z, Bruce PG. 2012. The carbon electrode in nonaqueous Li–O2 cells. Journal of the American Chemical Society. 135(1), 494–500. mla: Ottakam Thotiyl, Muhammed M., et al. “The Carbon Electrode in Nonaqueous Li–O2 Cells.” Journal of the American Chemical Society, vol. 135, no. 1, ACS, 2012, pp. 494–500, doi:10.1021/ja310258x. short: M.M. Ottakam Thotiyl, S.A. Freunberger, Z. Peng, P.G. Bruce, Journal of the American Chemical Society 135 (2012) 494–500. date_created: 2020-01-15T12:18:57Z date_published: 2012-11-28T00:00:00Z date_updated: 2021-01-12T08:12:56Z day: '28' doi: 10.1021/ja310258x extern: '1' intvolume: ' 135' issue: '1' language: - iso: eng month: '11' oa_version: None page: 494-500 publication: Journal of the American Chemical Society publication_identifier: issn: - 0002-7863 - 1520-5126 publication_status: published publisher: ACS quality_controlled: '1' status: public title: The carbon electrode in nonaqueous Li–O2 cells type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 135 year: '2012' ... --- _id: '7309' abstract: - lang: eng text: Energy‐storage technologies, including electrical double‐layer capacitors and rechargeable batteries, have attracted significant attention for applications in portable electronic devices, electric vehicles, bulk electricity storage at power stations, and “load leveling” of renewable sources, such as solar energy and wind power. Transforming lithium batteries and electric double‐layer capacitors requires a step change in the science underpinning these devices, including the discovery of new materials, new electrochemistry, and an increased understanding of the processes on which the devices depend. The Review will consider some of the current scientific issues underpinning lithium batteries and electric double‐layer capacitors. article_processing_charge: No article_type: original author: - first_name: Nam-Soon full_name: Choi, Nam-Soon last_name: Choi - first_name: Zonghai full_name: Chen, Zonghai last_name: Chen - first_name: Stefan Alexander full_name: Freunberger, Stefan Alexander id: A8CA28E6-CE23-11E9-AD2D-EC27E6697425 last_name: Freunberger orcid: 0000-0003-2902-5319 - first_name: Xiulei full_name: Ji, Xiulei last_name: Ji - first_name: Yang-Kook full_name: Sun, Yang-Kook last_name: Sun - first_name: Khalil full_name: Amine, Khalil last_name: Amine - first_name: Gleb full_name: Yushin, Gleb last_name: Yushin - first_name: Linda F. full_name: Nazar, Linda F. last_name: Nazar - first_name: Jaephil full_name: Cho, Jaephil last_name: Cho - first_name: Peter G. full_name: Bruce, Peter G. last_name: Bruce citation: ama: Choi N-S, Chen Z, Freunberger SA, et al. Challenges facing Lithium batteries and electrical double-layer capacitors. Angewandte Chemie International Edition. 2012;51(40):9994-10024. doi:10.1002/anie.201201429 apa: Choi, N.-S., Chen, Z., Freunberger, S. A., Ji, X., Sun, Y.-K., Amine, K., … Bruce, P. G. (2012). Challenges facing Lithium batteries and electrical double-layer capacitors. Angewandte Chemie International Edition. Wiley. https://doi.org/10.1002/anie.201201429 chicago: Choi, Nam-Soon, Zonghai Chen, Stefan Alexander Freunberger, Xiulei Ji, Yang-Kook Sun, Khalil Amine, Gleb Yushin, Linda F. Nazar, Jaephil Cho, and Peter G. Bruce. “Challenges Facing Lithium Batteries and Electrical Double-Layer Capacitors.” Angewandte Chemie International Edition. Wiley, 2012. https://doi.org/10.1002/anie.201201429. ieee: N.-S. Choi et al., “Challenges facing Lithium batteries and electrical double-layer capacitors,” Angewandte Chemie International Edition, vol. 51, no. 40. Wiley, pp. 9994–10024, 2012. ista: Choi N-S, Chen Z, Freunberger SA, Ji X, Sun Y-K, Amine K, Yushin G, Nazar LF, Cho J, Bruce PG. 2012. Challenges facing Lithium batteries and electrical double-layer capacitors. Angewandte Chemie International Edition. 51(40), 9994–10024. mla: Choi, Nam-Soon, et al. “Challenges Facing Lithium Batteries and Electrical Double-Layer Capacitors.” Angewandte Chemie International Edition, vol. 51, no. 40, Wiley, 2012, pp. 9994–10024, doi:10.1002/anie.201201429. short: N.-S. Choi, Z. Chen, S.A. Freunberger, X. Ji, Y.-K. Sun, K. Amine, G. Yushin, L.F. Nazar, J. Cho, P.G. Bruce, Angewandte Chemie International Edition 51 (2012) 9994–10024. date_created: 2020-01-15T12:19:11Z date_published: 2012-10-01T00:00:00Z date_updated: 2021-01-12T08:12:56Z day: '01' doi: 10.1002/anie.201201429 extern: '1' intvolume: ' 51' issue: '40' language: - iso: eng month: '10' oa_version: None page: 9994-10024 publication: Angewandte Chemie International Edition publication_identifier: issn: - 1433-7851 publication_status: published publisher: Wiley quality_controlled: '1' status: public title: Challenges facing Lithium batteries and electrical double-layer capacitors type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 51 year: '2012' ... --- _id: '7310' abstract: - lang: eng text: The rechargeable nonaqueous lithium-air (Li-O2) battery is receiving a great deal of interest because, theoretically, its specific energy far exceeds the best that can be achieved with lithium-ion cells. Operation of the rechargeable Li-O2 battery depends critically on repeated and highly reversible formation/decomposition of lithium peroxide (Li2O2) at the cathode upon cycling. Here, we show that this process is possible with the use of a dimethyl sulfoxide electrolyte and a porous gold electrode (95% capacity retention from cycles 1 to 100), whereas previously only partial Li2O2 formation/decomposition and limited cycling could occur. Furthermore, we present data indicating that the kinetics of Li2O2 oxidation on charge is approximately 10 times faster than on carbon electrodes. article_processing_charge: No article_type: original author: - first_name: Z. full_name: Peng, Z. last_name: Peng - first_name: Stefan Alexander full_name: Freunberger, Stefan Alexander id: A8CA28E6-CE23-11E9-AD2D-EC27E6697425 last_name: Freunberger orcid: 0000-0003-2902-5319 - first_name: Y. full_name: Chen, Y. last_name: Chen - first_name: P. G. full_name: Bruce, P. G. last_name: Bruce citation: ama: Peng Z, Freunberger SA, Chen Y, Bruce PG. A reversible and higher-rate Li-O2 battery. Science. 2012;337(6094):563-566. doi:10.1126/science.1223985 apa: Peng, Z., Freunberger, S. A., Chen, Y., & Bruce, P. G. (2012). A reversible and higher-rate Li-O2 battery. Science. AAAS. https://doi.org/10.1126/science.1223985 chicago: Peng, Z., Stefan Alexander Freunberger, Y. Chen, and P. G. Bruce. “A Reversible and Higher-Rate Li-O2 Battery.” Science. AAAS, 2012. https://doi.org/10.1126/science.1223985. ieee: Z. Peng, S. A. Freunberger, Y. Chen, and P. G. Bruce, “A reversible and higher-rate Li-O2 battery,” Science, vol. 337, no. 6094. AAAS, pp. 563–566, 2012. ista: Peng Z, Freunberger SA, Chen Y, Bruce PG. 2012. A reversible and higher-rate Li-O2 battery. Science. 337(6094), 563–566. mla: Peng, Z., et al. “A Reversible and Higher-Rate Li-O2 Battery.” Science, vol. 337, no. 6094, AAAS, 2012, pp. 563–66, doi:10.1126/science.1223985. short: Z. Peng, S.A. Freunberger, Y. Chen, P.G. Bruce, Science 337 (2012) 563–566. date_created: 2020-01-15T12:19:23Z date_published: 2012-08-03T00:00:00Z date_updated: 2021-01-12T08:12:57Z day: '03' doi: 10.1126/science.1223985 extern: '1' intvolume: ' 337' issue: '6094' language: - iso: eng month: '08' oa_version: None page: 563-566 publication: Science publication_identifier: issn: - 0036-8075 - 1095-9203 publication_status: published publisher: AAAS quality_controlled: '1' status: public title: A reversible and higher-rate Li-O2 battery type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 337 year: '2012' ... --- _id: '7311' abstract: - lang: eng text: Stability of the electrolyte toward reduced oxygen species generated at the cathode is a crucial challenge for the rechargeable nonaqueous Li–O2 battery. Here, we investigate dimethylformamide as the basis of an electrolyte. Although reactions at the O2 cathode on the first discharge–charge cycle are dominated by reversible Li2O2 formation/decomposition, there is also electrolyte decomposition, which increases on cycling. The products of decomposition at the cathode on discharge are Li2O2, Li2CO3, HCO2Li, CH3CO2Li, NO, H2O, and CO2. Li2CO3 accumulates in the electrode with cycling. The stability of dimethylformamide toward reduced oxygen species is insufficient for its use in the rechargeable nonaqueous Li–O2 battery. article_processing_charge: No article_type: original author: - first_name: Yuhui full_name: Chen, Yuhui last_name: Chen - first_name: Stefan Alexander full_name: Freunberger, Stefan Alexander id: A8CA28E6-CE23-11E9-AD2D-EC27E6697425 last_name: Freunberger orcid: 0000-0003-2902-5319 - first_name: Zhangquan full_name: Peng, Zhangquan last_name: Peng - first_name: Fanny full_name: Bardé, Fanny last_name: Bardé - first_name: Peter G. full_name: Bruce, Peter G. last_name: Bruce citation: ama: Chen Y, Freunberger SA, Peng Z, Bardé F, Bruce PG. Li–O2 battery with a dimethylformamide electrolyte. Journal of the American Chemical Society. 2012;134(18):7952-7957. doi:10.1021/ja302178w apa: Chen, Y., Freunberger, S. A., Peng, Z., Bardé, F., & Bruce, P. G. (2012). Li–O2 battery with a dimethylformamide electrolyte. Journal of the American Chemical Society. ACS. https://doi.org/10.1021/ja302178w chicago: Chen, Yuhui, Stefan Alexander Freunberger, Zhangquan Peng, Fanny Bardé, and Peter G. Bruce. “Li–O2 Battery with a Dimethylformamide Electrolyte.” Journal of the American Chemical Society. ACS, 2012. https://doi.org/10.1021/ja302178w. ieee: Y. Chen, S. A. Freunberger, Z. Peng, F. Bardé, and P. G. Bruce, “Li–O2 battery with a dimethylformamide electrolyte,” Journal of the American Chemical Society, vol. 134, no. 18. ACS, pp. 7952–7957, 2012. ista: Chen Y, Freunberger SA, Peng Z, Bardé F, Bruce PG. 2012. Li–O2 battery with a dimethylformamide electrolyte. Journal of the American Chemical Society. 134(18), 7952–7957. mla: Chen, Yuhui, et al. “Li–O2 Battery with a Dimethylformamide Electrolyte.” Journal of the American Chemical Society, vol. 134, no. 18, ACS, 2012, pp. 7952–57, doi:10.1021/ja302178w. short: Y. Chen, S.A. Freunberger, Z. Peng, F. Bardé, P.G. Bruce, Journal of the American Chemical Society 134 (2012) 7952–7957. date_created: 2020-01-15T12:19:36Z date_published: 2012-04-19T00:00:00Z date_updated: 2021-01-12T08:12:58Z day: '19' doi: 10.1021/ja302178w extern: '1' intvolume: ' 134' issue: '18' language: - iso: eng month: '04' oa_version: None page: 7952-7957 publication: Journal of the American Chemical Society publication_identifier: issn: - 0002-7863 - 1520-5126 publication_status: published publisher: ACS quality_controlled: '1' status: public title: Li–O2 battery with a dimethylformamide electrolyte type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 134 year: '2012' ... --- _id: '762' abstract: - lang: eng text: 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. article_processing_charge: No author: - first_name: Dan-Adrian full_name: Alistarh, Dan-Adrian id: 4A899BFC-F248-11E8-B48F-1D18A9856A87 last_name: Alistarh orcid: 0000-0003-3650-940X - first_name: Rachid full_name: Guerraoui, Rachid last_name: Guerraoui - first_name: Petr full_name: Kuznetsov, Petr last_name: Kuznetsov - first_name: Giuliano full_name: Losa, Giuliano last_name: Losa citation: ama: 'Alistarh D-A, Guerraoui R, Kuznetsov P, Losa G. On the cost of composing shared-memory algorithms. In: ACM; 2012:298-307. doi:10.1145/2312005.2312057' apa: 'Alistarh, D.-A., Guerraoui, R., Kuznetsov, P., & Losa, G. (2012). On the cost of composing shared-memory algorithms (pp. 298–307). Presented at the SPAA: Symposium on Parallelism in Algorithms and Architectures, ACM. https://doi.org/10.1145/2312005.2312057' chicago: Alistarh, Dan-Adrian, Rachid Guerraoui, Petr Kuznetsov, and Giuliano Losa. “On the Cost of Composing Shared-Memory Algorithms,” 298–307. ACM, 2012. https://doi.org/10.1145/2312005.2312057. ieee: 'D.-A. Alistarh, R. Guerraoui, P. Kuznetsov, and G. Losa, “On the cost of composing shared-memory algorithms,” presented at the SPAA: Symposium on Parallelism in Algorithms and Architectures, 2012, pp. 298–307.' ista: 'Alistarh D-A, Guerraoui R, Kuznetsov P, Losa G. 2012. On the cost of composing shared-memory algorithms. SPAA: Symposium on Parallelism in Algorithms and Architectures, 298–307.' mla: Alistarh, Dan-Adrian, et al. On the Cost of Composing Shared-Memory Algorithms. ACM, 2012, pp. 298–307, doi:10.1145/2312005.2312057. short: D.-A. Alistarh, R. Guerraoui, P. Kuznetsov, G. Losa, in:, ACM, 2012, pp. 298–307. conference: name: 'SPAA: Symposium on Parallelism in Algorithms and Architectures' date_created: 2018-12-11T11:48:22Z date_published: 2012-01-01T00:00:00Z date_updated: 2023-02-23T13:12:27Z day: '01' doi: 10.1145/2312005.2312057 extern: '1' language: - iso: eng month: '01' oa_version: None page: 298 - 307 publication_status: published publisher: ACM publist_id: '6892' status: public title: On the cost of composing shared-memory algorithms type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2012' ... --- _id: '763' abstract: - lang: eng text: 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]. acknowledgement: "Hagit Attiya - Supported in party by Israel Science Foundation (grant number 1227/10).\r\nCorentin Travers - Additional supports from the ANR projects ALADDIN and DISPLEXITY\r\n" alternative_title: - LNCS article_processing_charge: No author: - first_name: Dan-Adrian full_name: Alistarh, Dan-Adrian id: 4A899BFC-F248-11E8-B48F-1D18A9856A87 last_name: Alistarh orcid: 0000-0003-3650-940X - first_name: Hagit full_name: Attiya, Hagit last_name: Attiya - first_name: Rachid full_name: Guerraoui, Rachid last_name: Guerraoui - first_name: Corentin full_name: Travers, Corentin last_name: Travers citation: ama: 'Alistarh D-A, Attiya H, Guerraoui R, Travers C. Early deciding synchronous renaming in O(log f) rounds or less. In: Vol 7355 LNCS. Springer; 2012:195-206. doi:10.1007/978-3-642-31104-8_17' apa: 'Alistarh, D.-A., Attiya, H., Guerraoui, R., & Travers, C. (2012). Early deciding synchronous renaming in O(log f) rounds or less (Vol. 7355 LNCS, pp. 195–206). Presented at the SIROCCO: Structural Information and Communication Complexity, Springer. https://doi.org/10.1007/978-3-642-31104-8_17' chicago: Alistarh, Dan-Adrian, Hagit Attiya, Rachid Guerraoui, and Corentin Travers. “Early Deciding Synchronous Renaming in O(Log f) Rounds or Less,” 7355 LNCS:195–206. Springer, 2012. https://doi.org/10.1007/978-3-642-31104-8_17. ieee: 'D.-A. Alistarh, H. Attiya, R. Guerraoui, and C. Travers, “Early deciding synchronous renaming in O(log f) rounds or less,” presented at the SIROCCO: Structural Information and Communication Complexity, 2012, vol. 7355 LNCS, pp. 195–206.' ista: 'Alistarh D-A, Attiya H, Guerraoui R, Travers C. 2012. Early deciding synchronous renaming in O(log f) rounds or less. SIROCCO: Structural Information and Communication Complexity, LNCS, vol. 7355 LNCS, 195–206.' mla: Alistarh, Dan-Adrian, et al. Early Deciding Synchronous Renaming in O(Log f) Rounds or Less. Vol. 7355 LNCS, Springer, 2012, pp. 195–206, doi:10.1007/978-3-642-31104-8_17. short: D.-A. Alistarh, H. Attiya, R. Guerraoui, C. Travers, in:, Springer, 2012, pp. 195–206. conference: name: 'SIROCCO: Structural Information and Communication Complexity' date_created: 2018-12-11T11:48:22Z date_published: 2012-01-01T00:00:00Z date_updated: 2023-02-23T13:12:41Z day: '01' doi: 10.1007/978-3-642-31104-8_17 extern: '1' language: - iso: eng month: '01' oa_version: None page: 195 - 206 publication_status: published publisher: Springer publist_id: '6893' status: public title: Early deciding synchronous renaming in O(log f) rounds or less type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 7355 LNCS year: '2012' ... --- _id: '764' abstract: - lang: eng text: 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. acknowledgement: "We would like to thank Hagit Attiya, Keren Censor-Hillel, and the anonymous\r\nreviewers for their feedback on drafts of this paper.\r\nPart of the work was performed as C. Travers was a Post-Doctoral Fellow at the Technion, Haifa,\r\nsupported by the “Sam & Cecilia Neaman” Fellowship. Part of the work was performed as S. Gilbert was\r\na Post-Doctoral Fellow at the Swiss Federal Institute of Technology, Lausanne, Switzerland." article_processing_charge: No author: - first_name: Dan-Adrian full_name: Alistarh, Dan-Adrian id: 4A899BFC-F248-11E8-B48F-1D18A9856A87 last_name: Alistarh orcid: 0000-0003-3650-940X - first_name: Seth full_name: Gilbert, Seth last_name: Gilbert - first_name: Rachid full_name: Guerraoui, Rachid last_name: Guerraoui - first_name: Corentin full_name: Travers, Corentin last_name: Travers citation: ama: 'Alistarh D-A, Gilbert S, Guerraoui R, Travers C. Of choices, failures and asynchrony: the many faces of set agreement. Algorithmica (New York). 2012;62(1-2):595-629. doi:10.1007/s00453-011-9581-7' apa: 'Alistarh, D.-A., Gilbert, S., Guerraoui, R., & Travers, C. (2012). Of choices, failures and asynchrony: the many faces of set agreement. Algorithmica (New York). Springer. https://doi.org/10.1007/s00453-011-9581-7' chicago: 'Alistarh, Dan-Adrian, Seth Gilbert, Rachid Guerraoui, and Corentin Travers. “Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement.” Algorithmica (New York). Springer, 2012. https://doi.org/10.1007/s00453-011-9581-7.' ieee: 'D.-A. Alistarh, S. Gilbert, R. Guerraoui, and C. Travers, “Of choices, failures and asynchrony: the many faces of set agreement,” Algorithmica (New York), vol. 62, no. 1–2. Springer, pp. 595–629, 2012.' ista: 'Alistarh D-A, Gilbert S, Guerraoui R, Travers C. 2012. Of choices, failures and asynchrony: the many faces of set agreement. Algorithmica (New York). 62(1–2), 595–629.' mla: 'Alistarh, Dan-Adrian, et al. “Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement.” Algorithmica (New York), vol. 62, no. 1–2, Springer, 2012, pp. 595–629, doi:10.1007/s00453-011-9581-7.' short: D.-A. Alistarh, S. Gilbert, R. Guerraoui, C. Travers, Algorithmica (New York) 62 (2012) 595–629. date_created: 2018-12-11T11:48:23Z date_published: 2012-02-01T00:00:00Z date_updated: 2023-02-23T13:13:02Z day: '01' doi: 10.1007/s00453-011-9581-7 extern: '1' intvolume: ' 62' issue: 1-2 language: - iso: eng month: '02' oa_version: None page: 595 - 629 publication: Algorithmica (New York) publication_status: published publisher: Springer publist_id: '6894' status: public title: 'Of choices, failures and asynchrony: the many faces of set agreement' type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 62 year: '2012' ... --- _id: '766' abstract: - lang: eng text: '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.' article_processing_charge: No author: - first_name: Dan-Adrian full_name: Alistarh, Dan-Adrian id: 4A899BFC-F248-11E8-B48F-1D18A9856A87 last_name: Alistarh orcid: 0000-0003-3650-940X - first_name: Michael full_name: Bender, Michael last_name: Bender - first_name: Seth full_name: Gilbert, Seth last_name: Gilbert - first_name: Rachid full_name: Guerraoui, Rachid last_name: Guerraoui citation: ama: 'Alistarh D-A, Bender M, Gilbert S, Guerraoui R. How to allocate tasks asynchronously. In: IEEE; 2012:331-340. doi:10.1109/FOCS.2012.41' apa: 'Alistarh, D.-A., Bender, M., Gilbert, S., & Guerraoui, R. (2012). How to allocate tasks asynchronously (pp. 331–340). Presented at the FOCS: Foundations of Computer Science, IEEE. https://doi.org/10.1109/FOCS.2012.41' chicago: Alistarh, Dan-Adrian, Michael Bender, Seth Gilbert, and Rachid Guerraoui. “How to Allocate Tasks Asynchronously,” 331–40. IEEE, 2012. https://doi.org/10.1109/FOCS.2012.41. ieee: 'D.-A. Alistarh, M. Bender, S. Gilbert, and R. Guerraoui, “How to allocate tasks asynchronously,” presented at the FOCS: Foundations of Computer Science, 2012, pp. 331–340.' ista: 'Alistarh D-A, Bender M, Gilbert S, Guerraoui R. 2012. How to allocate tasks asynchronously. FOCS: Foundations of Computer Science, 331–340.' mla: Alistarh, Dan-Adrian, et al. How to Allocate Tasks Asynchronously. IEEE, 2012, pp. 331–40, doi:10.1109/FOCS.2012.41. short: D.-A. Alistarh, M. Bender, S. Gilbert, R. Guerraoui, in:, IEEE, 2012, pp. 331–340. conference: name: 'FOCS: Foundations of Computer Science' date_created: 2018-12-11T11:48:23Z date_published: 2012-01-01T00:00:00Z date_updated: 2023-02-23T13:13:27Z day: '01' doi: 10.1109/FOCS.2012.41 extern: '1' language: - iso: eng month: '01' oa_version: None page: 331 - 340 publication_status: published publisher: IEEE publist_id: '6890' status: public title: How to allocate tasks asynchronously type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2012' ...