[{"language":[{"iso":"eng"}],"publication_status":"published","related_material":{"record":[{"id":"2211","status":"public","relation":"later_version"},{"status":"public","id":"5381","relation":"earlier_version"}]},"ec_funded":1,"oa_version":"Preprint","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."}],"month":"08","scopus_import":1,"main_file_link":[{"url":"http://arxiv.org/abs/1107.2141","open_access":"1"}],"date_updated":"2023-02-23T12:23:43Z","department":[{"_id":"KrCh"}],"_id":"2955","status":"public","type":"conference","conference":{"name":"LICS: Logic in Computer Science","location":"Dubrovnik, Croatia","end_date":"2012-06-28","start_date":"2012-06-25"},"day":"23","publication":"Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science","year":"2012","doi":"10.1109/LICS.2012.28","date_published":"2012-08-23T00:00:00Z","date_created":"2018-12-11T12:00:32Z","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.","publisher":"IEEE","quality_controlled":"1","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","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","short":"K. Chatterjee, L. Doyen, in:, Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2012.","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.","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.","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.","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."},"title":"Partial-observation stochastic games: How to win when belief fails","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"full_name":"Doyen, Laurent","last_name":"Doyen","first_name":"Laurent"}],"publist_id":"3771","external_id":{"arxiv":["1107.2141"]},"article_number":"6280436","project":[{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}]},{"date_updated":"2023-02-23T12:23:46Z","department":[{"_id":"KrCh"}],"_id":"3341","status":"public","conference":{"name":"FoSSaCS: Foundations of Software Science and Computation Structures","start_date":"2012-03-24","location":"Tallinn, Estonia","end_date":"2012-04-01"},"type":"conference","language":[{"iso":"eng"}],"publication_status":"published","ec_funded":1,"volume":7213,"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"5382"}]},"oa_version":"Preprint","abstract":[{"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).","lang":"eng"}],"intvolume":" 7213","month":"03","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1107.2009"}],"alternative_title":["LNCS"],"scopus_import":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"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.","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","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","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.","short":"K. Chatterjee, in:, Springer, 2012, pp. 270–285.","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.","ista":"Chatterjee K. 2012. Robustness of structurally equivalent concurrent parity games. FoSSaCS: Foundations of Software Science and Computation Structures, LNCS, vol. 7213, 270–285."},"title":"Robustness of structurally equivalent concurrent parity games","external_id":{"arxiv":["1107.2009"]},"publist_id":"3284","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"}],"project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"day":"22","year":"2012","date_created":"2018-12-11T12:02:46Z","date_published":"2012-03-22T00:00:00Z","doi":"10.1007/978-3-642-28729-9_18","page":"270 - 285","oa":1,"publisher":"Springer","quality_controlled":"1"},{"department":[{"_id":"KrCh"}],"date_updated":"2023-02-23T12:23:51Z","status":"public","type":"conference","conference":{"name":"LICS: Logic in Computer Science","start_date":"2012-06-25","end_date":"2012-06-28","location":"Dubrovnik, Croatia "},"_id":"2957","related_material":{"record":[{"status":"public","id":"5384","relation":"earlier_version"}]},"ec_funded":1,"language":[{"iso":"eng"}],"publication_status":"published","month":"08","scopus_import":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1107.2091"}],"oa_version":"Preprint","abstract":[{"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.","lang":"eng"}],"title":"Decidable problems for probabilistic automata on infinite words","publist_id":"3769","author":[{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"last_name":"Tracol","full_name":"Tracol, Mathieu","first_name":"Mathieu","id":"3F54FA38-F248-11E8-B48F-1D18A9856A87"}],"external_id":{"arxiv":["1107.2091"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"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.","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.","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","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","short":"K. Chatterjee, M. Tracol, in:, Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2012.","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.","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."},"project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"article_number":"6280437","date_published":"2012-08-23T00:00:00Z","doi":"10.1109/LICS.2012.29","date_created":"2018-12-11T12:00:33Z","day":"23","publication":"Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science","year":"2012","quality_controlled":"1","publisher":"IEEE","oa":1},{"oa_version":"None","abstract":[{"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.","lang":"eng"}],"intvolume":" 413","month":"01","scopus_import":1,"language":[{"iso":"eng"}],"publication_status":"published","ec_funded":1,"volume":413,"issue":"1","related_material":{"record":[{"status":"public","id":"4393","relation":"earlier_version"},{"id":"5389","status":"public","relation":"earlier_version"}]},"_id":"3249","pubrep_id":"42","status":"public","type":"journal_article","date_updated":"2023-02-23T12:24:04Z","department":[{"_id":"ToHe"}],"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.","quality_controlled":"1","publisher":"Elsevier","publication":"Theoretical Computer Science","day":"06","year":"2012","date_created":"2018-12-11T12:02:15Z","date_published":"2012-01-06T00:00:00Z","doi":"10.1016/j.tcs.2011.08.002","page":"21 - 35","project":[{"call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425","name":"Quantitative Reactive Modeling","grant_number":"267989"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FP7","_id":"25EFB36C-B435-11E9-9278-68D0E5697425","name":"COMponent-Based Embedded Systems design Techniques","grant_number":"215543"},{"_id":"25F1337C-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Design for Embedded Systems","grant_number":"214373"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"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.","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","ieee":"P. Cerny, T. A. Henzinger, and A. Radhakrishna, “Simulation distances,” Theoretical Computer Science, vol. 413, no. 1. Elsevier, pp. 21–35, 2012.","short":"P. Cerny, T.A. Henzinger, A. Radhakrishna, Theoretical Computer Science 413 (2012) 21–35.","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.","ista":"Cerny P, Henzinger TA, Radhakrishna A. 2012. Simulation distances. Theoretical Computer Science. 413(1), 21–35."},"title":"Simulation distances","publist_id":"3408","author":[{"first_name":"Pavol","id":"4DCBEFFE-F248-11E8-B48F-1D18A9856A87","last_name":"Cerny","full_name":"Cerny, Pavol"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","last_name":"Henzinger"},{"full_name":"Radhakrishna, Arjun","last_name":"Radhakrishna","first_name":"Arjun","id":"3B51CAC4-F248-11E8-B48F-1D18A9856A87"}]},{"department":[{"_id":"ChLa"},{"_id":"VlKo"}],"title":"Approximating marginals using discrete energy minimization","file_date_updated":"2020-07-14T12:46:00Z","publist_id":"3575","author":[{"full_name":"Korc, Filip","last_name":"Korc","id":"476A2FD6-F248-11E8-B48F-1D18A9856A87","first_name":"Filip"},{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"},{"id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","first_name":"Christoph","orcid":"0000-0001-8622-7887","full_name":"Lampert, Christoph","last_name":"Lampert"}],"ddc":["000"],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-02-23T12:24:24Z","citation":{"chicago":"Korc, Filip, Vladimir Kolmogorov, and Christoph Lampert. “Approximating Marginals Using Discrete Energy Minimization.” ICML, 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.","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.","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.","short":"F. Korc, V. Kolmogorov, C. Lampert, in:, ICML, 2012."},"status":"public","pubrep_id":"565","type":"conference","conference":{"name":"ICML: International Conference on Machine Learning","start_date":"2012-06-26","end_date":"2012-07-01","location":"Edinburgh, Scotland"},"_id":"3124","date_published":"2012-06-30T00:00:00Z","related_material":{"record":[{"id":"5396","status":"public","relation":"later_version"}]},"date_created":"2018-12-11T12:01:31Z","day":"30","file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_id":"4889","checksum":"3d0d4246548c736857302aadb2ff5d15","creator":"system","date_updated":"2020-07-14T12:46:00Z","file_size":305836,"date_created":"2018-12-12T10:11:34Z","file_name":"IST-2016-565-v1+1_DM-inferning2012.pdf"}],"language":[{"iso":"eng"}],"has_accepted_license":"1","year":"2012","publication_status":"published","month":"06","publisher":"ICML","alternative_title":["Inferning 2012"],"quality_controlled":"1","oa":1,"oa_version":"Submitted Version","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"}]},{"page":"13","doi":"10.15479/AT:IST-2012-0003","date_published":"2012-07-23T00:00:00Z","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"3124"}]},"date_created":"2018-12-12T11:39:06Z","publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","publication_status":"published","year":"2012","day":"23","file":[{"date_created":"2018-12-12T11:53:29Z","file_name":"IST-2012-0003_IST-2012-0003.pdf","creator":"system","date_updated":"2020-07-14T12:46:44Z","file_size":618744,"file_id":"5490","checksum":"7e0ba85ad123b13223aaf6cdde2d288c","access_level":"open_access","relation":"main_file","content_type":"application/pdf"}],"language":[{"iso":"eng"}],"publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"oa":1,"month":"07","abstract":[{"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.","lang":"eng"}],"oa_version":"Published Version","author":[{"first_name":"Filip","id":"476A2FD6-F248-11E8-B48F-1D18A9856A87","last_name":"Korc","full_name":"Korc, Filip"},{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov"},{"last_name":"Lampert","full_name":"Lampert, Christoph","orcid":"0000-0001-8622-7887","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","first_name":"Christoph"}],"file_date_updated":"2020-07-14T12:46:44Z","title":"Approximating marginals using discrete energy minimization","department":[{"_id":"VlKo"},{"_id":"ChLa"}],"date_updated":"2023-02-23T11:13:22Z","citation":{"ieee":"F. Korc, V. Kolmogorov, and C. Lampert, Approximating marginals using discrete energy minimization. IST Austria, 2012.","short":"F. Korc, V. Kolmogorov, C. Lampert, Approximating Marginals Using Discrete Energy Minimization, IST Austria, 2012.","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","mla":"Korc, Filip, et al. Approximating Marginals Using Discrete Energy Minimization. IST Austria, 2012, doi:10.15479/AT:IST-2012-0003.","ista":"Korc F, Kolmogorov V, Lampert C. 2012. Approximating marginals using discrete energy minimization, IST Austria, 13p.","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."},"ddc":["000"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"technical_report","status":"public","pubrep_id":"36","_id":"5396"},{"date_created":"2018-12-12T11:39:06Z","date_published":"2012-11-12T00:00:00Z","publication_status":"published","year":"2012","has_accepted_license":"1","language":[{"iso":"eng"}],"file":[{"file_size":238544,"date_updated":"2020-07-14T12:46:44Z","creator":"system","file_name":"IST-2012-103-v1+1_Actual_state_of_research_data_@_IST_Austria.pdf","date_created":"2018-12-12T11:53:11Z","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_id":"5472","checksum":"e0a7c041eea1ca4b70ab6f9ec5177f4e"}],"day":"12","oa":1,"publisher":"IST Austria","month":"11","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."}],"oa_version":"Published Version","author":[{"full_name":"Porsche, Jana","last_name":"Porsche","id":"3252EDC2-F248-11E8-B48F-1D18A9856A87","first_name":"Jana"}],"file_date_updated":"2020-07-14T12:46:44Z","department":[{"_id":"E-Lib"}],"title":"Actual state of research data @ ISTAustria","citation":{"chicago":"Porsche, Jana. 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.","ieee":"J. Porsche, Actual state of research data @ ISTAustria. IST Austria, 2012.","short":"J. Porsche, Actual State of Research Data @ ISTAustria, IST Austria, 2012.","apa":"Porsche, J. (2012). Actual state of research data @ ISTAustria. IST Austria.","ama":"Porsche J. Actual State of Research Data @ ISTAustria. IST Austria; 2012."},"date_updated":"2020-07-14T23:04:49Z","ddc":["020"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"report","pubrep_id":"103","status":"public","_id":"5398"},{"citation":{"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.","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.","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.","short":"R. Biswas, J. Sil, Procedia Technology 4 (2012) 820–824.","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"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"3C2B033E-F248-11E8-B48F-1D18A9856A87","first_name":"Ranita","last_name":"Biswas","orcid":"0000-0002-5372-7890","full_name":"Biswas, Ranita"},{"last_name":"Sil","full_name":"Sil, Jaya","first_name":"Jaya"}],"title":"An Improved Canny Edge Detection Algorithm Based on Type-2 Fuzzy Sets","quality_controlled":"1","publisher":"Elsevier","oa":1,"has_accepted_license":"1","year":"2012","day":"01","publication":"Procedia Technology","page":"820-824","date_published":"2012-05-01T00:00:00Z","doi":"10.1016/j.protcy.2012.05.134","date_created":"2019-01-17T11:54:21Z","_id":"5839","type":"journal_article","tmp":{"short":"CC BY-NC-ND (4.0)","name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","image":"/images/cc_by_nc_nd.png"},"status":"public","date_updated":"2021-01-12T08:03:43Z","extern":"1","ddc":["000"],"file_date_updated":"2020-07-14T12:47:12Z","abstract":[{"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). ","lang":"eng"}],"oa_version":"Published Version","month":"05","intvolume":" 4","publication_identifier":{"issn":["2212-0173"]},"publication_status":"published","file":[{"creator":"dernst","date_updated":"2020-07-14T12:47:12Z","file_size":305426,"date_created":"2019-01-21T07:28:06Z","file_name":"2012_Procedia_Biswas.pdf","access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_id":"5863","checksum":"ba0185986b151d8c11201f48cd505ceb"}],"language":[{"iso":"eng"}],"volume":4},{"year":"2012","publication_status":"published","day":"13","publication":"Journal of Molecular Biology","language":[{"iso":"eng"}],"page":"387 - 394","date_published":"2012-04-13T00:00:00Z","issue":"5","doi":"10.1016/j.jmb.2012.02.014","volume":417,"date_created":"2018-12-11T11:47:24Z","abstract":[{"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.","lang":"eng"}],"oa_version":"None","publisher":"Elsevier","main_file_link":[{"url":"https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4582759/","open_access":"1"}],"oa":1,"month":"04","intvolume":" 417","date_updated":"2021-01-12T08:05:21Z","citation":{"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.","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.","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.","short":"C. Bernecky, D. Taatjes, Journal of Molecular Biology 417 (2012) 387–394.","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","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"},"extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Bernecky","orcid":"0000-0003-0893-7036","full_name":"Bernecky, Carrie A","id":"2CB9DFE2-F248-11E8-B48F-1D18A9856A87","first_name":"Carrie A"},{"first_name":"Dylan","last_name":"Taatjes","full_name":"Taatjes, Dylan"}],"publist_id":"7208","article_processing_charge":"No","title":"Activator-mediator binding stabilizes RNA polymerase II orientation within the human mediator-RNA polymerase II-TFIIF assembly","_id":"596","type":"journal_article","status":"public"},{"author":[{"first_name":"Karl Emanuel","last_name":"Busch","full_name":"Busch, Karl Emanuel"},{"first_name":"Patrick","full_name":"Laurent, Patrick","last_name":"Laurent"},{"first_name":"Zoltan","last_name":"Soltesz","full_name":"Soltesz, Zoltan"},{"full_name":"Murphy, Robin Joseph","last_name":"Murphy","first_name":"Robin Joseph"},{"last_name":"Faivre","full_name":"Faivre, Olivier","first_name":"Olivier"},{"first_name":"Berthold","last_name":"Hedwig","full_name":"Hedwig, Berthold"},{"first_name":"Martin","last_name":"Thomas","full_name":"Thomas, Martin"},{"first_name":"Heather L","last_name":"Smith","full_name":"Smith, Heather L"},{"first_name":"Mario","id":"4E3FF80E-F248-11E8-B48F-1D18A9856A87","last_name":"de Bono","full_name":"de Bono, Mario","orcid":"0000-0001-8347-0443"}],"external_id":{"pmid":["22388961"]},"title":"Tonic signaling from O2 sensors sets neural circuit activity and behavioral state","citation":{"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.","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.","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","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.","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.","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."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","page":"581-591","date_published":"2012-03-04T00:00:00Z","doi":"10.1038/nn.3061","date_created":"2019-03-20T14:23:30Z","year":"2012","day":"04","publication":"Nature Neuroscience","publisher":"Springer Nature","quality_controlled":"1","oa":1,"date_updated":"2021-01-12T08:06:17Z","extern":"1","type":"journal_article","status":"public","_id":"6136","volume":15,"issue":"4","publication_identifier":{"issn":["1097-6256","1546-1726"]},"publication_status":"published","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3564487/","open_access":"1"}],"month":"03","intvolume":" 15","abstract":[{"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.","lang":"eng"}],"oa_version":"Submitted Version","pmid":1},{"type":"conference","conference":{"name":"ICASSP: International Conference on Acoustics, Speech and Signal Processing","start_date":"2012-03-25","end_date":"2012-03-30","location":"Kyoto, Japan"},"status":"public","_id":"6746","author":[{"first_name":"Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco","orcid":"0000-0002-3242-7020","last_name":"Mondelli"},{"first_name":"Qi","full_name":"Zhou, Qi","last_name":"Zhou"},{"first_name":"Xiaoli","last_name":"Ma","full_name":"Ma, Xiaoli"},{"first_name":"Vincenzo","full_name":"Lottici, Vincenzo","last_name":"Lottici"}],"title":"A cooperative approach for amplify-and-forward differential transmitted reference IR-UWB relay systems","date_updated":"2021-01-12T08:08:49Z","citation":{"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.","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","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.","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.","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.","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."},"extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","publisher":"IEEE","month":"07","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."}],"oa_version":"None","page":"2905-2908","doi":"10.1109/icassp.2012.6288524","date_published":"2012-07-31T00:00:00Z","date_created":"2019-07-31T09:14:48Z","publication_identifier":{"issn":["1520-6149"]},"year":"2012","publication_status":"published","day":"31","publication":"2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)","language":[{"iso":"eng"}]},{"title":"Thermoelectric properties of Ho-doped Bi0.88Sb0.12","article_processing_charge":"No","author":[{"first_name":"K. C.","last_name":"Lukas","full_name":"Lukas, K. C."},{"first_name":"G.","last_name":"Joshi","full_name":"Joshi, G."},{"id":"13C26AC0-EB69-11E9-87C6-5F3BE6697425","first_name":"Kimberly A","full_name":"Modic, Kimberly A","orcid":"0000-0001-9760-3147","last_name":"Modic"},{"last_name":"Ren","full_name":"Ren, Z. F.","first_name":"Z. F."},{"last_name":"Opeil","full_name":"Opeil, C. P.","first_name":"C. P."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","citation":{"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.","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.","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","short":"K.C. Lukas, G. Joshi, K.A. Modic, Z.F. Ren, C.P. Opeil, Journal of Materials Science 47 (2012) 5729–5734.","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."},"date_updated":"2021-01-12T08:11:43Z","status":"public","type":"journal_article","article_type":"original","_id":"7074","date_created":"2019-11-19T13:36:54Z","date_published":"2012-08-01T00:00:00Z","volume":47,"issue":"15","doi":"10.1007/s10853-012-6463-6","page":"5729-5734","language":[{"iso":"eng"}],"publication":"Journal of Materials Science","day":"01","year":"2012","publication_status":"published","publication_identifier":{"issn":["0022-2461"],"eissn":["1573-4803"]},"intvolume":" 47","month":"08","publisher":"Springer Nature","quality_controlled":"1","oa_version":"None","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."}]},{"abstract":[{"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.","lang":"eng"}],"oa_version":"None","quality_controlled":"1","publisher":"ACS","intvolume":" 135","month":"11","publication_status":"published","year":"2012","publication_identifier":{"issn":["0002-7863","1520-5126"]},"language":[{"iso":"eng"}],"publication":"Journal of the American Chemical Society","day":"28","page":"494-500","date_created":"2020-01-15T12:18:57Z","volume":135,"date_published":"2012-11-28T00:00:00Z","issue":"1","doi":"10.1021/ja310258x","_id":"7308","article_type":"original","type":"journal_article","status":"public","citation":{"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.","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.","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","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.","short":"M.M. Ottakam Thotiyl, S.A. Freunberger, Z. Peng, P.G. Bruce, Journal of the American Chemical Society 135 (2012) 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."},"date_updated":"2021-01-12T08:12:56Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","article_processing_charge":"No","author":[{"full_name":"Ottakam Thotiyl, Muhammed M.","last_name":"Ottakam Thotiyl","first_name":"Muhammed M."},{"id":"A8CA28E6-CE23-11E9-AD2D-EC27E6697425","first_name":"Stefan Alexander","last_name":"Freunberger","orcid":"0000-0003-2902-5319","full_name":"Freunberger, Stefan Alexander"},{"last_name":"Peng","full_name":"Peng, Zhangquan","first_name":"Zhangquan"},{"first_name":"Peter G.","last_name":"Bruce","full_name":"Bruce, Peter G."}],"title":"The carbon electrode in nonaqueous Li–O2 cells"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","date_updated":"2021-01-12T08:12:56Z","citation":{"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.","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.","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.","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.","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."},"title":"Challenges facing Lithium batteries and electrical double-layer capacitors","article_processing_charge":"No","author":[{"first_name":"Nam-Soon","last_name":"Choi","full_name":"Choi, Nam-Soon"},{"last_name":"Chen","full_name":"Chen, Zonghai","first_name":"Zonghai"},{"last_name":"Freunberger","orcid":"0000-0003-2902-5319","full_name":"Freunberger, Stefan Alexander","id":"A8CA28E6-CE23-11E9-AD2D-EC27E6697425","first_name":"Stefan Alexander"},{"last_name":"Ji","full_name":"Ji, Xiulei","first_name":"Xiulei"},{"last_name":"Sun","full_name":"Sun, Yang-Kook","first_name":"Yang-Kook"},{"first_name":"Khalil","last_name":"Amine","full_name":"Amine, Khalil"},{"first_name":"Gleb","full_name":"Yushin, Gleb","last_name":"Yushin"},{"last_name":"Nazar","full_name":"Nazar, Linda F.","first_name":"Linda F."},{"last_name":"Cho","full_name":"Cho, Jaephil","first_name":"Jaephil"},{"first_name":"Peter G.","full_name":"Bruce, Peter G.","last_name":"Bruce"}],"_id":"7309","status":"public","type":"journal_article","article_type":"original","publication":"Angewandte Chemie International Edition","language":[{"iso":"eng"}],"day":"01","year":"2012","publication_status":"published","publication_identifier":{"issn":["1433-7851"]},"date_created":"2020-01-15T12:19:11Z","date_published":"2012-10-01T00:00:00Z","volume":51,"doi":"10.1002/anie.201201429","issue":"40","page":"9994-10024","oa_version":"None","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."}],"intvolume":" 51","month":"10","quality_controlled":"1","publisher":"Wiley"},{"day":"03","language":[{"iso":"eng"}],"publication":"Science","publication_identifier":{"issn":["0036-8075","1095-9203"]},"year":"2012","publication_status":"published","date_published":"2012-08-03T00:00:00Z","issue":"6094","doi":"10.1126/science.1223985","volume":337,"date_created":"2020-01-15T12:19:23Z","page":"563-566","oa_version":"None","abstract":[{"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.","lang":"eng"}],"month":"08","intvolume":" 337","publisher":"AAAS","quality_controlled":"1","extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T08:12:57Z","citation":{"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.","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.","short":"Z. Peng, S.A. Freunberger, Y. Chen, P.G. Bruce, Science 337 (2012) 563–566.","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","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","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.","ista":"Peng Z, Freunberger SA, Chen Y, Bruce PG. 2012. A reversible and higher-rate Li-O2 battery. Science. 337(6094), 563–566."},"title":"A reversible and higher-rate Li-O2 battery","author":[{"first_name":"Z.","last_name":"Peng","full_name":"Peng, Z."},{"id":"A8CA28E6-CE23-11E9-AD2D-EC27E6697425","first_name":"Stefan Alexander","orcid":"0000-0003-2902-5319","full_name":"Freunberger, Stefan Alexander","last_name":"Freunberger"},{"full_name":"Chen, Y.","last_name":"Chen","first_name":"Y."},{"first_name":"P. G.","full_name":"Bruce, P. G.","last_name":"Bruce"}],"article_processing_charge":"No","_id":"7310","status":"public","type":"journal_article","article_type":"original"},{"language":[{"iso":"eng"}],"publication":"Journal of the American Chemical Society","day":"19","publication_status":"published","year":"2012","publication_identifier":{"issn":["0002-7863","1520-5126"]},"date_created":"2020-01-15T12:19:36Z","doi":"10.1021/ja302178w","volume":134,"issue":"18","date_published":"2012-04-19T00:00:00Z","page":"7952-7957","oa_version":"None","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."}],"intvolume":" 134","month":"04","quality_controlled":"1","publisher":"ACS","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","date_updated":"2021-01-12T08:12:58Z","citation":{"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.","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","short":"Y. Chen, S.A. Freunberger, Z. Peng, F. Bardé, P.G. Bruce, Journal of the American Chemical Society 134 (2012) 7952–7957.","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.","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.","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."},"title":"Li–O2 battery with a dimethylformamide electrolyte","article_processing_charge":"No","author":[{"first_name":"Yuhui","last_name":"Chen","full_name":"Chen, Yuhui"},{"first_name":"Stefan Alexander","id":"A8CA28E6-CE23-11E9-AD2D-EC27E6697425","orcid":"0000-0003-2902-5319","full_name":"Freunberger, Stefan Alexander","last_name":"Freunberger"},{"last_name":"Peng","full_name":"Peng, Zhangquan","first_name":"Zhangquan"},{"first_name":"Fanny","last_name":"Bardé","full_name":"Bardé, Fanny"},{"full_name":"Bruce, Peter G.","last_name":"Bruce","first_name":"Peter G."}],"_id":"7311","status":"public","article_type":"original","type":"journal_article"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","date_updated":"2023-02-23T13:12:27Z","citation":{"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.","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.","short":"D.-A. Alistarh, R. Guerraoui, P. Kuznetsov, G. Losa, in:, ACM, 2012, pp. 298–307.","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.","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","mla":"Alistarh, Dan-Adrian, et al. On the Cost of Composing Shared-Memory Algorithms. ACM, 2012, pp. 298–307, doi:10.1145/2312005.2312057."},"title":"On the cost of composing shared-memory algorithms","article_processing_charge":"No","publist_id":"6892","author":[{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","last_name":"Alistarh","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian"},{"last_name":"Guerraoui","full_name":"Guerraoui, Rachid","first_name":"Rachid"},{"first_name":"Petr","last_name":"Kuznetsov","full_name":"Kuznetsov, Petr"},{"full_name":"Losa, Giuliano","last_name":"Losa","first_name":"Giuliano"}],"_id":"762","status":"public","conference":{"name":"SPAA: Symposium on Parallelism in Algorithms and Architectures"},"type":"conference","language":[{"iso":"eng"}],"day":"01","year":"2012","publication_status":"published","date_created":"2018-12-11T11:48:22Z","doi":"10.1145/2312005.2312057","date_published":"2012-01-01T00:00:00Z","page":"298 - 307","oa_version":"None","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."}],"month":"01","publisher":"ACM"},{"language":[{"iso":"eng"}],"day":"01","year":"2012","publication_status":"published","date_created":"2018-12-11T11:48:22Z","volume":"7355 LNCS","doi":"10.1007/978-3-642-31104-8_17","date_published":"2012-01-01T00:00:00Z","page":"195 - 206","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","oa_version":"None","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]."}],"month":"01","publisher":"Springer","alternative_title":["LNCS"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","date_updated":"2023-02-23T13:12:41Z","citation":{"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.","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.","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","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.","short":"D.-A. Alistarh, H. Attiya, R. Guerraoui, C. Travers, in:, Springer, 2012, pp. 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."},"title":"Early deciding synchronous renaming in O(log f) rounds or less","article_processing_charge":"No","publist_id":"6893","author":[{"last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Hagit","last_name":"Attiya","full_name":"Attiya, Hagit"},{"first_name":"Rachid","full_name":"Guerraoui, Rachid","last_name":"Guerraoui"},{"last_name":"Travers","full_name":"Travers, Corentin","first_name":"Corentin"}],"_id":"763","status":"public","conference":{"name":"SIROCCO: Structural Information and Communication Complexity"},"type":"conference"},{"publisher":"Springer","month":"02","intvolume":" 62","abstract":[{"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.","lang":"eng"}],"oa_version":"None","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.","page":"595 - 629","issue":"1-2","date_published":"2012-02-01T00:00:00Z","volume":62,"doi":"10.1007/s00453-011-9581-7","date_created":"2018-12-11T11:48:23Z","publication_status":"published","year":"2012","day":"01","publication":"Algorithmica (New York)","language":[{"iso":"eng"}],"type":"journal_article","status":"public","_id":"764","author":[{"first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X"},{"first_name":"Seth","last_name":"Gilbert","full_name":"Gilbert, Seth"},{"last_name":"Guerraoui","full_name":"Guerraoui, Rachid","first_name":"Rachid"},{"first_name":"Corentin","full_name":"Travers, Corentin","last_name":"Travers"}],"publist_id":"6894","article_processing_charge":"No","title":"Of choices, failures and asynchrony: the many faces of set agreement","citation":{"short":"D.-A. Alistarh, S. Gilbert, R. Guerraoui, C. Travers, Algorithmica (New York) 62 (2012) 595–629.","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.","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","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.","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.","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."},"date_updated":"2023-02-23T13:13:02Z","extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"date_updated":"2023-02-23T13:13:27Z","citation":{"mla":"Alistarh, Dan-Adrian, et al. How to Allocate Tasks Asynchronously. IEEE, 2012, pp. 331–40, doi: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.","short":"D.-A. Alistarh, M. Bender, S. Gilbert, R. Guerraoui, in:, IEEE, 2012, pp. 331–340.","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.","ista":"Alistarh D-A, Bender M, Gilbert S, Guerraoui R. 2012. How to allocate tasks asynchronously. FOCS: Foundations of Computer Science, 331–340."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","article_processing_charge":"No","publist_id":"6890","author":[{"full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","last_name":"Alistarh","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Michael","last_name":"Bender","full_name":"Bender, Michael"},{"first_name":"Seth","full_name":"Gilbert, Seth","last_name":"Gilbert"},{"full_name":"Guerraoui, Rachid","last_name":"Guerraoui","first_name":"Rachid"}],"title":"How to allocate tasks asynchronously","_id":"766","conference":{"name":"FOCS: Foundations of Computer Science"},"type":"conference","status":"public","year":"2012","publication_status":"published","language":[{"iso":"eng"}],"day":"01","page":"331 - 340","date_created":"2018-12-11T11:48:23Z","doi":"10.1109/FOCS.2012.41","date_published":"2012-01-01T00:00:00Z","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."}],"oa_version":"None","publisher":"IEEE","month":"01"}]