[{"publisher":"ML Research Press","abstract":[{"lang":"eng","text":"When searching for characteristic subpatterns in potentially noisy graph data, it appears self-evident that having multiple observations would be better than having just one. However, it turns out that the inconsistencies introduced when different graph instances have different edge sets pose a serious challenge. In this work we address this challenge for the problem of finding maximum weighted cliques.\r\n    We introduce the concept of most persistent soft-clique. This is subset of vertices, that 1) is almost fully or at least densely connected, 2) occurs in all or almost all graph instances, and 3) has the maximum weight. We present a measure of clique-ness, that essentially counts the number of edge missing to make a subset of vertices into a clique. With this measure, we show that the problem of finding the most persistent soft-clique problem can be cast either as: a) a max-min two person game optimization problem, or b) a min-min soft margin optimization problem. Both formulations lead to the same solution when using a partial Lagrangian method to solve the optimization problems. By experiments on synthetic data and on real social network data, we show that the proposed method is able to reliably find soft cliques in graph data, even if that is distorted by random noise or unreliable observations."}],"publication":"Proceedings of the 29th International Conference on Machine Learning","month":"06","external_id":{"arxiv":["1206.4652"]},"date_published":"2012-06-01T00:00:00Z","page":"211-218","author":[{"first_name":"Novi","last_name":"Quadrianto","full_name":"Quadrianto, Novi"},{"orcid":"0000-0001-8622-7887","full_name":"Lampert, Christoph","last_name":"Lampert","first_name":"Christoph","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87"},{"id":"3E92416E-F248-11E8-B48F-1D18A9856A87","first_name":"Chao","last_name":"Chen","full_name":"Chen, Chao"}],"day":"01","article_processing_charge":"No","oa_version":"Preprint","quality_controlled":"1","citation":{"mla":"Quadrianto, Novi, et al. “The Most Persistent Soft-Clique in a Set of Sampled Graphs.” <i>Proceedings of the 29th International Conference on Machine Learning</i>, ML Research Press, 2012, pp. 211–18.","apa":"Quadrianto, N., Lampert, C., &#38; Chen, C. (2012). The most persistent soft-clique in a set of sampled graphs. In <i>Proceedings of the 29th International Conference on Machine Learning</i> (pp. 211–218). Edinburgh, United Kingdom: ML Research Press.","short":"N. Quadrianto, C. Lampert, C. Chen, in:, Proceedings of the 29th International Conference on Machine Learning, ML Research Press, 2012, pp. 211–218.","ista":"Quadrianto N, Lampert C, Chen C. 2012. The most persistent soft-clique in a set of sampled graphs. Proceedings of the 29th International Conference on Machine Learning. ICML: International Conference on Machine Learning, 211–218.","ama":"Quadrianto N, Lampert C, Chen C. The most persistent soft-clique in a set of sampled graphs. In: <i>Proceedings of the 29th International Conference on Machine Learning</i>. ML Research Press; 2012:211-218.","chicago":"Quadrianto, Novi, Christoph Lampert, and Chao Chen. “The Most Persistent Soft-Clique in a Set of Sampled Graphs.” In <i>Proceedings of the 29th International Conference on Machine Learning</i>, 211–18. ML Research Press, 2012.","ieee":"N. Quadrianto, C. Lampert, and C. Chen, “The most persistent soft-clique in a set of sampled graphs,” in <i>Proceedings of the 29th International Conference on Machine Learning</i>, Edinburgh, United Kingdom, 2012, pp. 211–218."},"main_file_link":[{"url":"http://arxiv.org/abs/1206.4652","open_access":"1"}],"scopus_import":"1","title":"The most persistent soft-clique in a set of sampled graphs","type":"conference","arxiv":1,"department":[{"_id":"ChLa"},{"_id":"HeEd"}],"language":[{"iso":"eng"}],"publication_status":"published","status":"public","_id":"3127","date_updated":"2025-06-11T08:09:42Z","year":"2012","conference":{"location":"Edinburgh, United Kingdom","start_date":"2012-06-26","name":"ICML: International Conference on Machine Learning","end_date":"2012-07-01"},"publist_id":"3572","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2018-12-11T12:01:33Z","oa":1},{"date_updated":"2025-06-26T08:59:21Z","oa":1,"publist_id":"3569","department":[{"_id":"HeEd"}],"arxiv":1,"scopus_import":"1","_id":"3129","status":"public","article_processing_charge":"No","page":"189 - 200","citation":{"mla":"Busaryev, Oleksiy, et al. <i>Annotating Simplices with a Homology Basis and Its Applications</i>. Vol. 7357, Springer, 2012, pp. 189–200, doi:<a href=\"https://doi.org/10.1007/978-3-642-31155-0_17\">10.1007/978-3-642-31155-0_17</a>.","apa":"Busaryev, O., Cabello, S., Chen, C., Dey, T., &#38; Wang, Y. (2012). Annotating simplices with a homology basis and its applications (Vol. 7357, pp. 189–200). Presented at the SWAT: Symposium and Workshops on Algorithm Theory, Helsinki, Finland: Springer. <a href=\"https://doi.org/10.1007/978-3-642-31155-0_17\">https://doi.org/10.1007/978-3-642-31155-0_17</a>","short":"O. Busaryev, S. Cabello, C. Chen, T. Dey, Y. Wang, in:, Springer, 2012, pp. 189–200.","ista":"Busaryev O, Cabello S, Chen C, Dey T, Wang Y. 2012. Annotating simplices with a homology basis and its applications. SWAT: Symposium and Workshops on Algorithm Theory, LNCS, vol. 7357, 189–200.","chicago":"Busaryev, Oleksiy, Sergio Cabello, Chao Chen, Tamal Dey, and Yusu Wang. “Annotating Simplices with a Homology Basis and Its Applications,” 7357:189–200. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-31155-0_17\">https://doi.org/10.1007/978-3-642-31155-0_17</a>.","ama":"Busaryev O, Cabello S, Chen C, Dey T, Wang Y. Annotating simplices with a homology basis and its applications. In: Vol 7357. Springer; 2012:189-200. doi:<a href=\"https://doi.org/10.1007/978-3-642-31155-0_17\">10.1007/978-3-642-31155-0_17</a>","ieee":"O. Busaryev, S. Cabello, C. Chen, T. Dey, and Y. Wang, “Annotating simplices with a homology basis and its applications,” presented at the SWAT: Symposium and Workshops on Algorithm Theory, Helsinki, Finland, 2012, vol. 7357, pp. 189–200."},"volume":7357,"quality_controlled":"1","publisher":"Springer","intvolume":"      7357","month":"06","year":"2012","doi":"10.1007/978-3-642-31155-0_17","acknowledgement":"Research was partially supported by the Slovenian Research Agency, program P1-0297 and NSF grant CCF 1064416.","alternative_title":["LNCS"],"date_created":"2018-12-11T12:01:33Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"start_date":"2012-07-04","name":"SWAT: Symposium and Workshops on Algorithm Theory","location":"Helsinki, Finland","end_date":"2012-07-06"},"language":[{"iso":"eng"}],"title":"Annotating simplices with a homology basis and its applications","type":"conference","publication_status":"published","day":"19","author":[{"first_name":"Oleksiy","last_name":"Busaryev","full_name":"Busaryev, Oleksiy"},{"last_name":"Cabello","full_name":"Cabello, Sergio","first_name":"Sergio"},{"last_name":"Chen","full_name":"Chen, Chao","id":"3E92416E-F248-11E8-B48F-1D18A9856A87","first_name":"Chao"},{"last_name":"Dey","full_name":"Dey, Tamal","first_name":"Tamal"},{"full_name":"Wang, Yusu","last_name":"Wang","first_name":"Yusu"}],"main_file_link":[{"url":"http://arxiv.org/abs/1107.3793","open_access":"1"}],"oa_version":"Preprint","abstract":[{"lang":"eng","text":"Let K be a simplicial complex and g the rank of its p-th homology group Hp(K) defined with ℤ2 coefficients. We show that we can compute a basis H of Hp(K) and annotate each p-simplex of K with a binary vector of length g with the following property: the annotations, summed over all p-simplices in any p-cycle z, provide the coordinate vector of the homology class [z] in the basis H. The basis and the annotations for all simplices can be computed in O(n ω ) time, where n is the size of K and ω &lt; 2.376 is a quantity so that two n×n matrices can be multiplied in O(n ω ) time. The precomputed annotations permit answering queries about the independence or the triviality of p-cycles efficiently.\r\n\r\nUsing annotations of edges in 2-complexes, we derive better algorithms for computing optimal basis and optimal homologous cycles in 1 - dimensional homology. Specifically, for computing an optimal basis of H1(K) , we improve the previously known time complexity from O(n 4) to O(n ω  + n 2 g ω − 1). Here n denotes the size of the 2-skeleton of K and g the rank of H1(K) . Computing an optimal cycle homologous to a given 1-cycle is NP-hard even for surfaces and an algorithm taking 2 O(g) nlogn time is known for surfaces. We extend this algorithm to work with arbitrary 2-complexes in O(n ω ) + 2 O(g) n 2logn time using annotations.\r\n"}],"date_published":"2012-06-19T00:00:00Z","external_id":{"arxiv":["1107.3793"]}},{"doi":"10.1007/978-3-642-31424-7_8","acknowledgement":"Tomas Brazdil, Antonin Kucera, and Petr Novotny are supported by the Czech Science Foundation, grant No. P202/10/1469. Krishnendu Chatterjee is supported by the FWF (Austrian Science Fund) NFN Grant No S11407-N23 (RiSE) and ERC Start grant (279307: Graph Games).","year":"2012","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"end_date":"2012-07-13","start_date":"2012-07-07","name":"CAV: Computer Aided Verification","location":"Berkeley, CA, USA"},"date_created":"2018-12-11T12:01:35Z","alternative_title":["LNCS"],"project":[{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF"}],"title":"Efficient controller synthesis for consumption games with multiple resource types","type":"conference","language":[{"iso":"eng"}],"publication_status":"published","author":[{"last_name":"Brázdil","full_name":"Brázdil, Brázdil","first_name":"Brázdil"},{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"full_name":"Kučera, Antonín","last_name":"Kučera","first_name":"Antonín"},{"full_name":"Novotny, Petr","last_name":"Novotny","first_name":"Petr","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87"}],"day":"01","oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1202.0796"}],"abstract":[{"lang":"eng","text":"We introduce consumption games, a model for discrete interactive system with multiple resources that are consumed or reloaded independently. More precisely, a consumption game is a finite-state graph where each transition is labeled by a vector of resource updates, where every update is a non-positive number or ω. The ω updates model the reloading of a given resource. Each vertex belongs either to player □ or player ◇, where the aim of player □ is to play so that the resources are never exhausted. We consider several natural algorithmic problems about consumption games, and show that although these problems are computationally hard in general, they are solvable in polynomial time for every fixed number of resource types (i.e., the dimension of the update vectors) and bounded resource updates. "}],"external_id":{"arxiv":["1202.0796"]},"date_published":"2012-07-01T00:00:00Z","date_updated":"2025-06-11T08:10:20Z","publist_id":"3562","oa":1,"scopus_import":"1","arxiv":1,"department":[{"_id":"KrCh"}],"status":"public","_id":"3135","page":"23 - 38","ec_funded":1,"article_processing_charge":"No","quality_controlled":"1","volume":7358,"citation":{"ieee":"B. Brázdil, K. Chatterjee, A. Kučera, and P. Novotný, “Efficient controller synthesis for consumption games with multiple resource types,” presented at the CAV: Computer Aided Verification, Berkeley, CA, USA, 2012, vol. 7358, pp. 23–38.","chicago":"Brázdil, Brázdil, Krishnendu Chatterjee, Antonín Kučera, and Petr Novotný. “Efficient Controller Synthesis for Consumption Games with Multiple Resource Types,” 7358:23–38. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-31424-7_8\">https://doi.org/10.1007/978-3-642-31424-7_8</a>.","ama":"Brázdil B, Chatterjee K, Kučera A, Novotný P. Efficient controller synthesis for consumption games with multiple resource types. In: Vol 7358. Springer; 2012:23-38. doi:<a href=\"https://doi.org/10.1007/978-3-642-31424-7_8\">10.1007/978-3-642-31424-7_8</a>","ista":"Brázdil B, Chatterjee K, Kučera A, Novotný P. 2012. Efficient controller synthesis for consumption games with multiple resource types. CAV: Computer Aided Verification, LNCS, vol. 7358, 23–38.","short":"B. Brázdil, K. Chatterjee, A. Kučera, P. Novotný, in:, Springer, 2012, pp. 23–38.","mla":"Brázdil, Brázdil, et al. <i>Efficient Controller Synthesis for Consumption Games with Multiple Resource Types</i>. Vol. 7358, Springer, 2012, pp. 23–38, doi:<a href=\"https://doi.org/10.1007/978-3-642-31424-7_8\">10.1007/978-3-642-31424-7_8</a>.","apa":"Brázdil, B., Chatterjee, K., Kučera, A., &#38; Novotný, P. (2012). Efficient controller synthesis for consumption games with multiple resource types (Vol. 7358, pp. 23–38). Presented at the CAV: Computer Aided Verification, Berkeley, CA, USA: Springer. <a href=\"https://doi.org/10.1007/978-3-642-31424-7_8\">https://doi.org/10.1007/978-3-642-31424-7_8</a>"},"intvolume":"      7358","publisher":"Springer","month":"07"},{"date_published":"2012-07-01T00:00:00Z","abstract":[{"lang":"eng","text":"Continuous-time Markov chains (CTMC) with their rich theory and efficient simulation algorithms have been successfully used in modeling stochastic processes in diverse areas such as computer science, physics, and biology. However, systems that comprise non-instantaneous events cannot be accurately and efficiently modeled with CTMCs. In this paper we define delayed CTMCs, an extension of CTMCs that allows for the specification of a lower bound on the time interval between an event's initiation and its completion, and we propose an algorithm for the computation of their behavior. Our algorithm effectively decomposes the computation into two stages: a pure CTMC governs event initiations while a deterministic process guarantees lower bounds on event completion times. Furthermore, from the nature of delayed CTMCs, we obtain a parallelized version of our algorithm. We use our formalism to model genetic regulatory circuits (biological systems where delayed events are common) and report on the results of our numerical algorithm as run on a cluster. We compare performance and accuracy of our results with results obtained by using pure CTMCs. © 2012 Springer-Verlag."}],"oa_version":"None","day":"01","author":[{"orcid":"0000-0001-6220-2052","first_name":"Calin C","id":"47F8433E-F248-11E8-B48F-1D18A9856A87","full_name":"Guet, Calin C","last_name":"Guet"},{"full_name":"Gupta, Ashutosh","last_name":"Gupta","first_name":"Ashutosh","id":"335E5684-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","last_name":"Henzinger","full_name":"Henzinger, Thomas A"},{"full_name":"Mateescu, Maria","last_name":"Mateescu","first_name":"Maria","id":"3B43276C-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Sezgin","full_name":"Sezgin, Ali","id":"4C7638DA-F248-11E8-B48F-1D18A9856A87","first_name":"Ali"}],"publication_status":"published","language":[{"iso":"eng"}],"project":[{"call_identifier":"FP7","name":"Quantitative Reactive Modeling","grant_number":"267989","_id":"25EE3708-B435-11E9-9278-68D0E5697425"}],"type":"conference","title":"Delayed continuous time Markov chains for genetic regulatory circuits","alternative_title":["LNCS"],"date_created":"2018-12-11T12:01:36Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","conference":{"end_date":"2012-07-13","name":"CAV: Computer Aided Verification","start_date":"2012-07-07","location":"Berkeley, CA, USA"},"year":"2012","doi":"10.1007/978-3-642-31424-7_24","acknowledgement":"This work was supported by the ERC Advanced Investigator grant on Quantitative Reactive Modeling (QUAREM) and by the Swiss National Science Foundation.","month":"07","publisher":"Springer","citation":{"apa":"Guet, C. C., Gupta, A., Henzinger, T. A., Mateescu, M., &#38; Sezgin, A. (2012). Delayed continuous time Markov chains for genetic regulatory circuits (Vol. 7358, pp. 294–309). Presented at the CAV: Computer Aided Verification, Berkeley, CA, USA: Springer. <a href=\"https://doi.org/10.1007/978-3-642-31424-7_24\">https://doi.org/10.1007/978-3-642-31424-7_24</a>","mla":"Guet, Calin C., et al. <i>Delayed Continuous Time Markov Chains for Genetic Regulatory Circuits</i>. Vol. 7358, Springer, 2012, pp. 294–309, doi:<a href=\"https://doi.org/10.1007/978-3-642-31424-7_24\">10.1007/978-3-642-31424-7_24</a>.","ista":"Guet CC, Gupta A, Henzinger TA, Mateescu M, Sezgin A. 2012. Delayed continuous time Markov chains for genetic regulatory circuits. CAV: Computer Aided Verification, LNCS, vol. 7358, 294–309.","short":"C.C. Guet, A. Gupta, T.A. Henzinger, M. Mateescu, A. Sezgin, in:, Springer, 2012, pp. 294–309.","ama":"Guet CC, Gupta A, Henzinger TA, Mateescu M, Sezgin A. Delayed continuous time Markov chains for genetic regulatory circuits. In: Vol 7358. Springer; 2012:294-309. doi:<a href=\"https://doi.org/10.1007/978-3-642-31424-7_24\">10.1007/978-3-642-31424-7_24</a>","chicago":"Guet, Calin C, Ashutosh Gupta, Thomas A Henzinger, Maria Mateescu, and Ali Sezgin. “Delayed Continuous Time Markov Chains for Genetic Regulatory Circuits,” 7358:294–309. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-31424-7_24\">https://doi.org/10.1007/978-3-642-31424-7_24</a>.","ieee":"C. C. Guet, A. Gupta, T. A. Henzinger, M. Mateescu, and A. Sezgin, “Delayed continuous time Markov chains for genetic regulatory circuits,” presented at the CAV: Computer Aided Verification, Berkeley, CA, USA, 2012, vol. 7358, pp. 294–309."},"volume":"7358 ","quality_controlled":"1","ec_funded":1,"page":"294 - 309","corr_author":"1","_id":"3136","status":"public","department":[{"_id":"CaGu"},{"_id":"ToHe"}],"scopus_import":1,"publist_id":"3561","date_updated":"2024-10-09T20:54:47Z"},{"author":[{"first_name":"Benoît","full_name":"Delahaye, Benoît","last_name":"Delahaye"},{"full_name":"Fahrenberg, Uli","last_name":"Fahrenberg","first_name":"Uli"},{"full_name":"Henzinger, Thomas A","last_name":"Henzinger","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724"},{"full_name":"Legay, Axel","last_name":"Legay","first_name":"Axel"},{"last_name":"Nickovic","full_name":"Nickovic, Dejan","id":"41BCEE5C-F248-11E8-B48F-1D18A9856A87","first_name":"Dejan"}],"day":"01","oa_version":"Submitted Version","abstract":[{"lang":"eng","text":"We propose synchronous interfaces, a new interface theory for discrete-time systems. We use an application to time-triggered scheduling to drive the design choices for our formalism; in particular, additionally to deriving useful mathematical properties, we focus on providing a syntax which is adapted to natural high-level system modeling. As a result, we develop an interface model that relies on a guarded-command based language and is equipped with shared variables and explicit discrete-time clocks. We define all standard interface operations: compatibility checking, composition, refinement, and shared refinement. Apart from the synchronous interface model, the contribution of this paper is the establishment of a formal relation between interface theories and real-time scheduling, where we demonstrate a fully automatic framework for the incremental computation of time-triggered schedules."}],"date_published":"2012-06-01T00:00:00Z","file":[{"date_updated":"2020-07-14T12:46:01Z","creator":"system","file_size":493198,"date_created":"2018-12-12T10:11:25Z","content_type":"application/pdf","checksum":"feae2e07f2d9a59843f8ddabf25d179f","relation":"main_file","access_level":"open_access","file_name":"IST-2012-88-v1+1_Synchronous_interface_theories_and_time_triggered_scheduling.pdf","file_id":"4879"}],"acknowledgement":"Research partially supported by the Danish-Chinese Center for Cyber Physical Systems (Grant No.61061130541) and VKR Center of Excellence MT-LAB.","doi":"10.1007/978-3-642-30793-5_13","year":"2012","conference":{"end_date":"2012-06-16","start_date":"2012-06-13","name":"FORTE: Formal Techniques for Networked and Distributed Systems & FMOODS: Formal Methods for Open Object-Based Distributed Systems ","location":"Stockholm, Sweden"},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","alternative_title":["LNCS"],"date_created":"2018-12-11T12:01:43Z","title":"Synchronous interface theories and time triggered scheduling","type":"conference","language":[{"iso":"eng"}],"publication_status":"published","page":"203 - 218","quality_controlled":"1","pubrep_id":"88","volume":7273,"citation":{"ama":"Delahaye B, Fahrenberg U, Henzinger TA, Legay A, Nickovic D. Synchronous interface theories and time triggered scheduling. In: Vol 7273. Springer; 2012:203-218. doi:<a href=\"https://doi.org/10.1007/978-3-642-30793-5_13\">10.1007/978-3-642-30793-5_13</a>","chicago":"Delahaye, Benoît, Uli Fahrenberg, Thomas A Henzinger, Axel Legay, and Dejan Nickovic. “Synchronous Interface Theories and Time Triggered Scheduling,” 7273:203–18. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-30793-5_13\">https://doi.org/10.1007/978-3-642-30793-5_13</a>.","ieee":"B. Delahaye, U. Fahrenberg, T. A. Henzinger, A. Legay, and D. Nickovic, “Synchronous interface theories and time triggered scheduling,” presented at the FORTE: Formal Techniques for Networked and Distributed Systems &#38; FMOODS: Formal Methods for Open Object-Based Distributed Systems , Stockholm, Sweden, 2012, vol. 7273, pp. 203–218.","apa":"Delahaye, B., Fahrenberg, U., Henzinger, T. A., Legay, A., &#38; Nickovic, D. (2012). Synchronous interface theories and time triggered scheduling (Vol. 7273, pp. 203–218). Presented at the FORTE: Formal Techniques for Networked and Distributed Systems &#38; FMOODS: Formal Methods for Open Object-Based Distributed Systems , Stockholm, Sweden: Springer. <a href=\"https://doi.org/10.1007/978-3-642-30793-5_13\">https://doi.org/10.1007/978-3-642-30793-5_13</a>","mla":"Delahaye, Benoît, et al. <i>Synchronous Interface Theories and Time Triggered Scheduling</i>. Vol. 7273, Springer, 2012, pp. 203–18, doi:<a href=\"https://doi.org/10.1007/978-3-642-30793-5_13\">10.1007/978-3-642-30793-5_13</a>.","short":"B. Delahaye, U. Fahrenberg, T.A. Henzinger, A. Legay, D. Nickovic, in:, Springer, 2012, pp. 203–218.","ista":"Delahaye B, Fahrenberg U, Henzinger TA, Legay A, Nickovic D. 2012. Synchronous interface theories and time triggered scheduling. FORTE: Formal Techniques for Networked and Distributed Systems &#38; FMOODS: Formal Methods for Open Object-Based Distributed Systems , LNCS, vol. 7273, 203–218."},"has_accepted_license":"1","intvolume":"      7273","publisher":"Springer","month":"06","date_updated":"2021-01-12T07:41:26Z","publist_id":"3539","oa":1,"scopus_import":1,"department":[{"_id":"ToHe"}],"file_date_updated":"2020-07-14T12:46:01Z","ddc":["004"],"status":"public","_id":"3155"},{"intvolume":"        11","publisher":"Taylor and Francis","month":"06","page":"2055 - 2058","article_processing_charge":"No","volume":11,"quality_controlled":"1","citation":{"apa":"Pantazis, P., &#38; Bollenbach, M. T. (2012). Transcription factor kinetics and the emerging asymmetry in the early mammalian embryo. <i>Cell Cycle</i>. Taylor and Francis. <a href=\"https://doi.org/10.4161/cc.20118\">https://doi.org/10.4161/cc.20118</a>","mla":"Pantazis, Periklis, and Mark Tobias Bollenbach. “Transcription Factor Kinetics and the Emerging Asymmetry in the Early Mammalian Embryo.” <i>Cell Cycle</i>, vol. 11, no. 11, Taylor and Francis, 2012, pp. 2055–58, doi:<a href=\"https://doi.org/10.4161/cc.20118\">10.4161/cc.20118</a>.","short":"P. Pantazis, M.T. Bollenbach, Cell Cycle 11 (2012) 2055–2058.","ista":"Pantazis P, Bollenbach MT. 2012. Transcription factor kinetics and the emerging asymmetry in the early mammalian embryo. Cell Cycle. 11(11), 2055–2058.","ama":"Pantazis P, Bollenbach MT. Transcription factor kinetics and the emerging asymmetry in the early mammalian embryo. <i>Cell Cycle</i>. 2012;11(11):2055-2058. doi:<a href=\"https://doi.org/10.4161/cc.20118\">10.4161/cc.20118</a>","chicago":"Pantazis, Periklis, and Mark Tobias Bollenbach. “Transcription Factor Kinetics and the Emerging Asymmetry in the Early Mammalian Embryo.” <i>Cell Cycle</i>. Taylor and Francis, 2012. <a href=\"https://doi.org/10.4161/cc.20118\">https://doi.org/10.4161/cc.20118</a>.","ieee":"P. Pantazis and M. T. Bollenbach, “Transcription factor kinetics and the emerging asymmetry in the early mammalian embryo,” <i>Cell Cycle</i>, vol. 11, no. 11. Taylor and Francis, pp. 2055–2058, 2012."},"scopus_import":"1","department":[{"_id":"ToBo"}],"status":"public","_id":"3160","corr_author":"1","date_updated":"2025-09-30T07:53:56Z","publist_id":"3531","abstract":[{"text":"There is a long-running controversy about how early cell fate decisions are made in the developing mammalian embryo. 1,2 In particular, it is controversial when the first events that can predict the establishment of the pluripotent and extra-embryonic lineages in the blastocyst of the pre-implantation embryo occur. It has long been proposed that the position and polarity of cells at the 16- to 32-cell stage embryo influence their decision to either give rise to the pluripotent cell lineage that eventually contributes to the inner cell mass (ICM), comprising the primitive endoderm (PE) and the epiblast (EPI), or the extra-embryonic trophectoderm (TE) surrounding the blastocoel. The positioning of cells in the embryo at this developmental stage could largely be the result of random events, making this a stochastic model of cell lineage allocation. Contrary to such a stochastic model, some studies have detected putative differences in the lineage potential of individual blastomeres before compaction, indicating that the first cell fate decisions may occur as early as at the 4-cell stage. Using a non-invasive, quantitative in vivo imaging assay to study the kinetic behavior of Oct4 (also known as POU5F1), a key transcription factor (TF) controlling pre-implantation development in the mouse embryo, 3-5 a recent study identifies Oct4 kinetics as a predictive measure of cell lineage patterning in the early mouse embryo. 6 Here, we discuss the implications of such molecular heterogeneities in early development and offer potential avenues toward a mechanistic understanding of these observations, contributing to the resolution of the controversy of developmental cell lineage allocation.","lang":"eng"}],"publication":"Cell Cycle","date_published":"2012-06-01T00:00:00Z","external_id":{"isi":["000304770100011"]},"author":[{"first_name":"Periklis","last_name":"Pantazis","full_name":"Pantazis, Periklis"},{"orcid":"0000-0003-4398-476X","id":"3E6DB97A-F248-11E8-B48F-1D18A9856A87","first_name":"Tobias","last_name":"Bollenbach","full_name":"Bollenbach, Tobias"}],"day":"01","oa_version":"None","issue":"11","title":"Transcription factor kinetics and the emerging asymmetry in the early mammalian embryo","type":"journal_article","isi":1,"language":[{"iso":"eng"}],"publication_status":"published","doi":"10.4161/cc.20118","year":"2012","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_created":"2018-12-11T12:01:44Z"},{"language":[{"iso":"eng"}],"title":"Parametric identification of temporal properties","type":"conference","publication_status":"published","year":"2012","doi":"10.1007/978-3-642-29860-8_12","alternative_title":["LNCS"],"date_created":"2018-12-11T12:01:45Z","conference":{"end_date":"2011-09-30","name":"RV: Runtime Verification","start_date":"2011-09-27","location":"San Francisco, CA, United States"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"Given a dense-time real-valued signal and a parameterized temporal logic formula with both magnitude and timing parameters, we compute the subset of the parameter space that renders the formula satisfied by the trace. We provide two preliminary implementations, one which follows the exact semantics and attempts to compute the validity domain by quantifier elimination in linear arithmetics and one which conducts adaptive search in the parameter space."}],"date_published":"2012-01-01T00:00:00Z","file":[{"content_type":"application/pdf","date_created":"2020-05-15T12:50:15Z","file_size":374726,"creator":"dernst","date_updated":"2020-07-14T12:46:01Z","file_name":"2012_RV_Asarin.pdf","file_id":"7862","relation":"main_file","access_level":"open_access","checksum":"ba4a75287008fc64b8fbf78a7476ec32"}],"day":"01","author":[{"first_name":"Eugene","full_name":"Asarin, Eugene","last_name":"Asarin"},{"full_name":"Donzé, Alexandre","last_name":"Donzé","first_name":"Alexandre"},{"last_name":"Maler","full_name":"Maler, Oded","first_name":"Oded"},{"last_name":"Nickovic","full_name":"Nickovic, Dejan","id":"41BCEE5C-F248-11E8-B48F-1D18A9856A87","first_name":"Dejan"}],"oa_version":"Submitted Version","department":[{"_id":"ToHe"}],"file_date_updated":"2020-07-14T12:46:01Z","ddc":["000"],"scopus_import":1,"_id":"3162","status":"public","date_updated":"2021-01-12T07:41:29Z","oa":1,"publist_id":"3525","publisher":"Springer","intvolume":"      7186","month":"01","article_processing_charge":"No","page":"147 - 160","citation":{"mla":"Asarin, Eugene, et al. <i>Parametric Identification of Temporal Properties</i>. Vol. 7186, Springer, 2012, pp. 147–60, doi:<a href=\"https://doi.org/10.1007/978-3-642-29860-8_12\">10.1007/978-3-642-29860-8_12</a>.","apa":"Asarin, E., Donzé, A., Maler, O., &#38; Nickovic, D. (2012). Parametric identification of temporal properties (Vol. 7186, pp. 147–160). Presented at the RV: Runtime Verification, San Francisco, CA, United States: Springer. <a href=\"https://doi.org/10.1007/978-3-642-29860-8_12\">https://doi.org/10.1007/978-3-642-29860-8_12</a>","ista":"Asarin E, Donzé A, Maler O, Nickovic D. 2012. Parametric identification of temporal properties. RV: Runtime Verification, LNCS, vol. 7186, 147–160.","short":"E. Asarin, A. Donzé, O. Maler, D. Nickovic, in:, Springer, 2012, pp. 147–160.","chicago":"Asarin, Eugene, Alexandre Donzé, Oded Maler, and Dejan Nickovic. “Parametric Identification of Temporal Properties,” 7186:147–60. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-29860-8_12\">https://doi.org/10.1007/978-3-642-29860-8_12</a>.","ama":"Asarin E, Donzé A, Maler O, Nickovic D. Parametric identification of temporal properties. In: Vol 7186. Springer; 2012:147-160. doi:<a href=\"https://doi.org/10.1007/978-3-642-29860-8_12\">10.1007/978-3-642-29860-8_12</a>","ieee":"E. Asarin, A. Donzé, O. Maler, and D. Nickovic, “Parametric identification of temporal properties,” presented at the RV: Runtime Verification, San Francisco, CA, United States, 2012, vol. 7186, pp. 147–160."},"has_accepted_license":"1","quality_controlled":"1","volume":7186},{"day":"01","author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"last_name":"Henzinger","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","orcid":"0000-0002-5008-6530"}],"main_file_link":[{"url":"https://arxiv.org/abs/1109.5018","open_access":"1"}],"oa_version":"Preprint","abstract":[{"lang":"eng","text":"Computing the winning set for Büchi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solving the problem is Õ(n·m), where n is the number of vertices and m is the number of edges in the graph. We are the first to break the Õ(n·m) boundary by presenting a new technique that reduces the running time to O(n 2). This bound also leads to O(n 2) time algorithms for computing the set of almost-sure winning vertices for Büchi objectives (1) in alternating games with probabilistic transitions (improving an earlier bound of Õ(n·m)), (2) in concurrent graph games with constant actions (improving an earlier bound of O(n 3)), and (3) in Markov decision processes (improving for m &gt; n 4/3 an earlier bound of O(min(m 1.5, m·n 2/3)). We also show that the same technique can be used to compute the maximal end-component decomposition of a graph in time O(n 2), which is an improvement over earlier bounds for m &gt; n 4/3. Finally, we show how to maintain the winning set for Büchi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. This is the first dynamic algorithm for this problem."}],"date_published":"2012-01-01T00:00:00Z","external_id":{"arxiv":["1109.5018"]},"publication":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","year":"2012","acknowledgement":"The research was supported by Austrian Science Fund (FWF) Grant No P 23499-N23 on Modern Graph Algorithmic Techniques in Formal Verification, Vienna Science and Technology Fund (WWTF) Grant ICT10-002, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.","doi":"10.1137/1.9781611973099.109","date_created":"2018-12-11T12:01:46Z","conference":{"end_date":"2012-01-19","start_date":"2012-01-17","name":"SODA: Symposium on Discrete Algorithms","location":"Kyoto, Japan"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"title":"An O(n2) time algorithm for alternating Büchi games","type":"conference","project":[{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7"},{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"publication_status":"published","article_processing_charge":"No","ec_funded":1,"page":"1386 - 1399","citation":{"ieee":"K. Chatterjee and M. Henzinger, “An O(n2) time algorithm for alternating Büchi games,” in <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Kyoto, Japan, 2012, pp. 1386–1399.","chicago":"Chatterjee, Krishnendu, and Monika Henzinger. “An O(N2) Time Algorithm for Alternating Büchi Games.” In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 1386–99. SIAM, 2012. <a href=\"https://doi.org/10.1137/1.9781611973099.109\">https://doi.org/10.1137/1.9781611973099.109</a>.","ama":"Chatterjee K, Henzinger M. An O(n2) time algorithm for alternating Büchi games. In: <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>. SIAM; 2012:1386-1399. doi:<a href=\"https://doi.org/10.1137/1.9781611973099.109\">10.1137/1.9781611973099.109</a>","ista":"Chatterjee K, Henzinger M. 2012. An O(n2) time algorithm for alternating Büchi games. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1386–1399.","short":"K. Chatterjee, M. Henzinger, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2012, pp. 1386–1399.","mla":"Chatterjee, Krishnendu, and Monika Henzinger. “An O(N2) Time Algorithm for Alternating Büchi Games.” <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, SIAM, 2012, pp. 1386–99, doi:<a href=\"https://doi.org/10.1137/1.9781611973099.109\">10.1137/1.9781611973099.109</a>.","apa":"Chatterjee, K., &#38; Henzinger, M. (2012). An O(n2) time algorithm for alternating Büchi games. In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 1386–1399). Kyoto, Japan: SIAM. <a href=\"https://doi.org/10.1137/1.9781611973099.109\">https://doi.org/10.1137/1.9781611973099.109</a>"},"quality_controlled":"1","pubrep_id":"15","OA_type":"green","publisher":"SIAM","month":"01","OA_place":"repository","date_updated":"2025-09-29T11:45:12Z","related_material":{"record":[{"id":"5379","status":"public","relation":"earlier_version"},{"id":"2141","relation":"later_version","status":"public"}]},"oa":1,"publist_id":"3519","department":[{"_id":"KrCh"}],"arxiv":1,"_id":"3165","corr_author":"1","status":"public"},{"page":"31 - 41","article_processing_charge":"No","quality_controlled":"1","volume":7,"has_accepted_license":"1","citation":{"ieee":"C. Lampert and J. Peters, “Real-time detection of colored objects in multiple camera streams with off-the-shelf hardware components,” <i>Journal of Real-Time Image Processing</i>, vol. 7, no. 1. Springer, pp. 31–41, 2012.","ama":"Lampert C, Peters J. Real-time detection of colored objects in multiple camera streams with off-the-shelf hardware components. <i>Journal of Real-Time Image Processing</i>. 2012;7(1):31-41. doi:<a href=\"https://doi.org/10.1007/s11554-010-0168-3\">10.1007/s11554-010-0168-3</a>","chicago":"Lampert, Christoph, and Jan Peters. “Real-Time Detection of Colored Objects in Multiple Camera Streams with off-the-Shelf Hardware Components.” <i>Journal of Real-Time Image Processing</i>. Springer, 2012. <a href=\"https://doi.org/10.1007/s11554-010-0168-3\">https://doi.org/10.1007/s11554-010-0168-3</a>.","short":"C. Lampert, J. Peters, Journal of Real-Time Image Processing 7 (2012) 31–41.","ista":"Lampert C, Peters J. 2012. Real-time detection of colored objects in multiple camera streams with off-the-shelf hardware components. Journal of Real-Time Image Processing. 7(1), 31–41.","mla":"Lampert, Christoph, and Jan Peters. “Real-Time Detection of Colored Objects in Multiple Camera Streams with off-the-Shelf Hardware Components.” <i>Journal of Real-Time Image Processing</i>, vol. 7, no. 1, Springer, 2012, pp. 31–41, doi:<a href=\"https://doi.org/10.1007/s11554-010-0168-3\">10.1007/s11554-010-0168-3</a>.","apa":"Lampert, C., &#38; Peters, J. (2012). Real-time detection of colored objects in multiple camera streams with off-the-shelf hardware components. <i>Journal of Real-Time Image Processing</i>. Springer. <a href=\"https://doi.org/10.1007/s11554-010-0168-3\">https://doi.org/10.1007/s11554-010-0168-3</a>"},"intvolume":"         7","publisher":"Springer","month":"03","date_updated":"2025-09-30T07:46:36Z","publist_id":"3417","oa":1,"scopus_import":"1","ddc":["000"],"file_date_updated":"2020-07-14T12:46:04Z","department":[{"_id":"ChLa"}],"status":"public","_id":"3248","corr_author":"1","author":[{"id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","first_name":"Christoph","last_name":"Lampert","full_name":"Lampert, Christoph","orcid":"0000-0001-8622-7887"},{"full_name":"Peters, Jan","last_name":"Peters","first_name":"Jan"}],"day":"01","oa_version":"Submitted Version","issue":"1","abstract":[{"text":"We describe RTblob, a high speed vision system that detects objects in cluttered scenes based on their color and shape at a speed of over 800 frames/s. Because the system is available as open-source software and relies only on off-the-shelf PC hardware components, it can provide the basis for multiple application scenarios. As an illustrative example, we show how RTblob can be used in a robotic table tennis scenario to estimate ball trajectories through 3D space simultaneously from four cameras images at a speed of 200 Hz.","lang":"eng"}],"publication":"Journal of Real-Time Image Processing","date_published":"2012-03-01T00:00:00Z","external_id":{"isi":["000303242600004"]},"file":[{"file_name":"2012_Springer_Lampert.pdf","file_id":"5958","access_level":"open_access","relation":"main_file","checksum":"241be47ea50e81a283bcf4c45b07e8cc","date_created":"2019-02-12T10:52:25Z","content_type":"application/pdf","file_size":2933187,"creator":"kschuh","date_updated":"2020-07-14T12:46:04Z"}],"doi":"10.1007/s11554-010-0168-3","year":"2012","publication_identifier":{"issn":["1861-8200"],"eissn":["1861-8219"]},"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_created":"2018-12-11T12:02:15Z","type":"journal_article","title":"Real-time detection of colored objects in multiple camera streams with off-the-shelf hardware components","language":[{"iso":"eng"}],"isi":1,"publication_status":"published","article_type":"original"},{"day":"19","page":"99 - 114","author":[{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654"}],"citation":{"short":"K.Z. Pietrzak, in:, Springer, 2012, pp. 99–114.","ista":"Pietrzak KZ. 2012. Cryptography from learning parity with noise. SOFSEM: Current Trends in Theory and Practice of Computer Science, LNCS, vol. 7147, 99–114.","apa":"Pietrzak, K. Z. (2012). Cryptography from learning parity with noise (Vol. 7147, pp. 99–114). Presented at the SOFSEM: Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic: Springer. <a href=\"https://doi.org/10.1007/978-3-642-27660-6_9\">https://doi.org/10.1007/978-3-642-27660-6_9</a>","mla":"Pietrzak, Krzysztof Z. <i>Cryptography from Learning Parity with Noise</i>. Vol. 7147, Springer, 2012, pp. 99–114, doi:<a href=\"https://doi.org/10.1007/978-3-642-27660-6_9\">10.1007/978-3-642-27660-6_9</a>.","ieee":"K. Z. Pietrzak, “Cryptography from learning parity with noise,” presented at the SOFSEM: Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, 2012, vol. 7147, pp. 99–114.","chicago":"Pietrzak, Krzysztof Z. “Cryptography from Learning Parity with Noise,” 7147:99–114. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-27660-6_9\">https://doi.org/10.1007/978-3-642-27660-6_9</a>.","ama":"Pietrzak KZ. Cryptography from learning parity with noise. In: Vol 7147. Springer; 2012:99-114. doi:<a href=\"https://doi.org/10.1007/978-3-642-27660-6_9\">10.1007/978-3-642-27660-6_9</a>"},"volume":7147,"oa_version":"None","quality_controlled":"1","publisher":"Springer","abstract":[{"text":"The Learning Parity with Noise (LPN) problem has recently found many applications in cryptography as the hardness assumption underlying the constructions of &quot;provably secure&quot; cryptographic schemes like encryption or authentication protocols. Being provably secure means that the scheme comes with a proof showing that the existence of an efficient adversary against the scheme implies that the underlying hardness assumption is wrong. LPN based schemes are appealing for theoretical and practical reasons. On the theoretical side, LPN based schemes offer a very strong security guarantee. The LPN problem is equivalent to the problem of decoding random linear codes, a problem that has been extensively studied in the last half century. The fastest known algorithms run in exponential time and unlike most number-theoretic problems used in cryptography, the LPN problem does not succumb to known quantum algorithms. On the practical side, LPN based schemes are often extremely simple and efficient in terms of code-size as well as time and space requirements. This makes them prime candidates for light-weight devices like RFID tags, which are too weak to implement standard cryptographic primitives like the AES block-cipher. This talk will be a gentle introduction to provable security using simple LPN based schemes as examples. Starting from pseudorandom generators and symmetric key encryption, over secret-key authentication protocols, and, if time admits, touching on recent constructions of public-key identification, commitments and zero-knowledge proofs.","lang":"eng"}],"intvolume":"      7147","date_published":"2012-02-19T00:00:00Z","month":"02","year":"2012","doi":"10.1007/978-3-642-27660-6_9","date_updated":"2024-10-09T20:54:42Z","date_created":"2018-12-11T12:02:15Z","alternative_title":["LNCS"],"conference":{"end_date":"2012-01-27","start_date":"2012-01-21","name":"SOFSEM: Current Trends in Theory and Practice of Computer Science","location":"Špindlerův Mlýn, Czech Republic"},"publist_id":"3407","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"KrPi"}],"language":[{"iso":"eng"}],"type":"conference","scopus_import":1,"title":"Cryptography from learning parity with noise","corr_author":"1","_id":"3250","publication_status":"published","status":"public"},{"status":"public","_id":"3251","scopus_import":"1","ddc":["000","005"],"department":[{"_id":"ToHe"}],"file_date_updated":"2020-07-14T12:46:05Z","publist_id":"3406","oa":1,"related_material":{"record":[{"id":"1405","status":"public","relation":"dissertation_contains"}]},"date_updated":"2026-04-09T14:35:23Z","month":"01","intvolume":"      7148","publisher":"Springer","pubrep_id":"100","quality_controlled":"1","volume":7148,"has_accepted_license":"1","citation":{"apa":"Zufferey, D., Wies, T., &#38; Henzinger, T. A. (2012). Ideal abstractions for well structured transition systems (Vol. 7148, pp. 445–460). Presented at the VMCAI: Verification, Model Checking and Abstract Interpretation, Philadelphia, PA, USA: Springer. <a href=\"https://doi.org/10.1007/978-3-642-27940-9_29\">https://doi.org/10.1007/978-3-642-27940-9_29</a>","mla":"Zufferey, Damien, et al. <i>Ideal Abstractions for Well Structured Transition Systems</i>. Vol. 7148, Springer, 2012, pp. 445–60, doi:<a href=\"https://doi.org/10.1007/978-3-642-27940-9_29\">10.1007/978-3-642-27940-9_29</a>.","short":"D. Zufferey, T. Wies, T.A. Henzinger, in:, Springer, 2012, pp. 445–460.","ista":"Zufferey D, Wies T, Henzinger TA. 2012. Ideal abstractions for well structured transition systems. VMCAI: Verification, Model Checking and Abstract Interpretation, LNCS, vol. 7148, 445–460.","ama":"Zufferey D, Wies T, Henzinger TA. Ideal abstractions for well structured transition systems. In: Vol 7148. Springer; 2012:445-460. doi:<a href=\"https://doi.org/10.1007/978-3-642-27940-9_29\">10.1007/978-3-642-27940-9_29</a>","chicago":"Zufferey, Damien, Thomas Wies, and Thomas A Henzinger. “Ideal Abstractions for Well Structured Transition Systems,” 7148:445–60. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-27940-9_29\">https://doi.org/10.1007/978-3-642-27940-9_29</a>.","ieee":"D. Zufferey, T. Wies, and T. A. Henzinger, “Ideal abstractions for well structured transition systems,” presented at the VMCAI: Verification, Model Checking and Abstract Interpretation, Philadelphia, PA, USA, 2012, vol. 7148, pp. 445–460."},"page":"445 - 460","ec_funded":1,"publication_status":"published","project":[{"_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989","name":"Quantitative Reactive Modeling","call_identifier":"FP7"},{"call_identifier":"FWF","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425"}],"type":"conference","title":"Ideal abstractions for well structured transition systems","language":[{"iso":"eng"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","conference":{"location":"Philadelphia, PA, USA","start_date":"2012-01-22","name":"VMCAI: Verification, Model Checking and Abstract Interpretation","end_date":"2012-01-24"},"date_created":"2018-12-11T12:02:16Z","alternative_title":["LNCS"],"acknowledgement":"This research was supported in part by the European Research Council (ERC) Advanced Investigator Grant QUAREM and by the Austrian Science Fund (FWF) project S11402-N23.","doi":"10.1007/978-3-642-27940-9_29","year":"2012","date_published":"2012-01-01T00:00:00Z","file":[{"file_id":"4759","file_name":"IST-2012-100-v1+1_Ideal_abstractions_for_well-structured_transition_systems.pdf","access_level":"open_access","relation":"main_file","checksum":"f2f0d55efa32309ad1fe65a5fcaad90c","content_type":"application/pdf","date_created":"2018-12-12T10:09:35Z","file_size":217104,"creator":"system","date_updated":"2020-07-14T12:46:05Z"}],"abstract":[{"text":"Many infinite state systems can be seen as well-structured transition systems (WSTS), i.e., systems equipped with a well-quasi-ordering on states that is also a simulation relation. WSTS are an attractive target for formal analysis because there exist generic algorithms that decide interesting verification problems for this class. Among the most popular algorithms are acceleration-based forward analyses for computing the covering set. Termination of these algorithms can only be guaranteed for flattable WSTS. Yet, many WSTS of practical interest are not flattable and the question whether any given WSTS is flattable is itself undecidable. We therefore propose an analysis that computes the covering set and captures the essence of acceleration-based algorithms, but sacrifices precision for guaranteed termination. Our analysis is an abstract interpretation whose abstract domain builds on the ideal completion of the well-quasi-ordered state space, and a widening operator that mimics acceleration and controls the loss of precision of the analysis. We present instances of our framework for various classes of WSTS. Our experience with a prototype implementation indicates that, despite the inherent precision loss, our analysis often computes the precise covering set of the analyzed system.","lang":"eng"}],"oa_version":"Submitted Version","author":[{"id":"4397AC76-F248-11E8-B48F-1D18A9856A87","first_name":"Damien","last_name":"Zufferey","full_name":"Zufferey, Damien","orcid":"0000-0002-3197-8736"},{"id":"447BFB88-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas","last_name":"Wies","full_name":"Wies, Thomas"},{"first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724"}],"day":"01"},{"department":[{"_id":"KrCh"}],"scopus_import":"1","arxiv":1,"_id":"3252","status":"public","date_updated":"2025-06-11T08:06:25Z","oa":1,"publist_id":"3405","publisher":"Springer","intvolume":"      7148","month":"01","article_processing_charge":"No","ec_funded":1,"page":"152 - 168","citation":{"short":"K. Chatterjee, V. Raman, in:, Springer, 2012, pp. 152–168.","ista":"Chatterjee K, Raman V. 2012. Synthesizing protocols for digital contract signing. VMCAI: Verification, Model Checking and Abstract Interpretation, LNCS, vol. 7148, 152–168.","apa":"Chatterjee, K., &#38; Raman, V. (2012). Synthesizing protocols for digital contract signing (Vol. 7148, pp. 152–168). Presented at the VMCAI: Verification, Model Checking and Abstract Interpretation, Philadelphia, PA, USA: Springer. <a href=\"https://doi.org/10.1007/978-3-642-27940-9_11\">https://doi.org/10.1007/978-3-642-27940-9_11</a>","mla":"Chatterjee, Krishnendu, and Vishwanath Raman. <i>Synthesizing Protocols for Digital Contract Signing</i>. Vol. 7148, Springer, 2012, pp. 152–68, doi:<a href=\"https://doi.org/10.1007/978-3-642-27940-9_11\">10.1007/978-3-642-27940-9_11</a>.","ieee":"K. Chatterjee and V. Raman, “Synthesizing protocols for digital contract signing,” presented at the VMCAI: Verification, Model Checking and Abstract Interpretation, Philadelphia, PA, USA, 2012, vol. 7148, pp. 152–168.","ama":"Chatterjee K, Raman V. Synthesizing protocols for digital contract signing. In: Vol 7148. Springer; 2012:152-168. doi:<a href=\"https://doi.org/10.1007/978-3-642-27940-9_11\">10.1007/978-3-642-27940-9_11</a>","chicago":"Chatterjee, Krishnendu, and Vishwanath Raman. “Synthesizing Protocols for Digital Contract Signing,” 7148:152–68. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-27940-9_11\">https://doi.org/10.1007/978-3-642-27940-9_11</a>."},"quality_controlled":"1","volume":7148,"language":[{"iso":"eng"}],"project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","call_identifier":"FWF"},{"call_identifier":"FWF","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"title":"Synthesizing protocols for digital contract signing","type":"conference","publication_status":"published","year":"2012","doi":"10.1007/978-3-642-27940-9_11","acknowledgement":"The research was supported by Austrian Science Fund (FWF) Grant No P 23499-N23 (Modern Graph Algorithmic Techniques in Formal Verification), FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.\r\nThe authors would like to thank Avik Chaudhuri for his invaluable help and feedback.","alternative_title":["LNCS"],"date_created":"2018-12-11T12:02:16Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"end_date":"2012-01-24","location":"Philadelphia, PA, USA","name":"VMCAI: Verification, Model Checking and Abstract Interpretation","start_date":"2012-01-22"},"abstract":[{"lang":"eng","text":"We study the automatic synthesis of fair non-repudiation protocols, a class of fair exchange protocols, used for digital contract signing. First, we show how to specify the objectives of the participating agents, the trusted third party (TTP) and the protocols as path formulas in Linear Temporal Logic (LTL) and prove that the satisfaction of the objectives of the agents and the TTP imply satisfaction of the protocol objectives. We then show that weak (co-operative) co-synthesis and classical (strictly competitive) co-synthesis fail in synthesizing these protocols, whereas assume-guarantee synthesis (AGS) succeeds. We demonstrate the success of assume-guarantee synthesis as follows: (a) any solution of assume-guarantee synthesis is attack-free; no subset of participants can violate the objectives of the other participants without violating their own objectives; (b) the Asokan-Shoup-Waidner (ASW) certified mail protocol that has known vulnerabilities is not a solution of AGS; and (c) the Kremer-Markowitch (KM) non-repudiation protocol is a solution of AGS. To our knowledge this is the first application of synthesis to fair non-repudiation protocols, and our results show how synthesis can generate correct protocols and automatically discover vulnerabilities. The solution to assume-guarantee synthesis can be computed efficiently as the secure equilibrium solution of three-player graph games. © 2012 Springer-Verlag."}],"external_id":{"arxiv":["1004.2697"]},"date_published":"2012-01-20T00:00:00Z","day":"20","author":[{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"last_name":"Raman","full_name":"Raman, Vishwanath","first_name":"Vishwanath"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1004.2697"}],"oa_version":"Preprint"},{"intvolume":"      7148","abstract":[{"text":"We describe a framework for reasoning about programs with lists carrying integer numerical data. We use abstract domains to describe and manipulate complex constraints on configurations of these programs mixing constraints on the shape of the heap, sizes of the lists, on the multisets of data stored in these lists, and on the data at their different positions. Moreover, we provide powerful techniques for automatic validation of Hoare-triples and invariant checking, as well as for automatic synthesis of invariants and procedure summaries using modular inter-procedural analysis. The approach has been implemented in a tool called Celia and experimented successfully on a large benchmark of programs.","lang":"eng"}],"publisher":"Springer","month":"02","date_published":"2012-02-26T00:00:00Z","author":[{"full_name":"Bouajjani, Ahmed","last_name":"Bouajjani","first_name":"Ahmed"},{"last_name":"Dragoi","full_name":"Dragoi, Cezara","id":"2B2B5ED0-F248-11E8-B48F-1D18A9856A87","first_name":"Cezara"},{"last_name":"Enea","full_name":"Enea, Constantin","first_name":"Constantin"},{"first_name":"Mihaela","last_name":"Sighireanu","full_name":"Sighireanu, Mihaela"}],"page":"1 - 22","day":"26","quality_controlled":"1","oa_version":"None","volume":7148,"citation":{"ieee":"A. Bouajjani, C. Dragoi, C. Enea, and M. Sighireanu, “Abstract domains for automated reasoning about list manipulating programs with infinite data,” presented at the VMCAI: Verification, Model Checking and Abstract Interpretation, Philadelphia, PA, USA, 2012, vol. 7148, pp. 1–22.","chicago":"Bouajjani, Ahmed, Cezara Dragoi, Constantin Enea, and Mihaela Sighireanu. “Abstract Domains for Automated Reasoning about List Manipulating Programs with Infinite Data,” 7148:1–22. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-27940-9_1\">https://doi.org/10.1007/978-3-642-27940-9_1</a>.","ama":"Bouajjani A, Dragoi C, Enea C, Sighireanu M. Abstract domains for automated reasoning about list manipulating programs with infinite data. In: Vol 7148. Springer; 2012:1-22. doi:<a href=\"https://doi.org/10.1007/978-3-642-27940-9_1\">10.1007/978-3-642-27940-9_1</a>","ista":"Bouajjani A, Dragoi C, Enea C, Sighireanu M. 2012. Abstract domains for automated reasoning about list manipulating programs with infinite data. VMCAI: Verification, Model Checking and Abstract Interpretation, LNCS, vol. 7148, 1–22.","short":"A. Bouajjani, C. Dragoi, C. Enea, M. Sighireanu, in:, Springer, 2012, pp. 1–22.","mla":"Bouajjani, Ahmed, et al. <i>Abstract Domains for Automated Reasoning about List Manipulating Programs with Infinite Data</i>. Vol. 7148, Springer, 2012, pp. 1–22, doi:<a href=\"https://doi.org/10.1007/978-3-642-27940-9_1\">10.1007/978-3-642-27940-9_1</a>.","apa":"Bouajjani, A., Dragoi, C., Enea, C., &#38; Sighireanu, M. (2012). Abstract domains for automated reasoning about list manipulating programs with infinite data (Vol. 7148, pp. 1–22). Presented at the VMCAI: Verification, Model Checking and Abstract Interpretation, Philadelphia, PA, USA: Springer. <a href=\"https://doi.org/10.1007/978-3-642-27940-9_1\">https://doi.org/10.1007/978-3-642-27940-9_1</a>"},"title":"Abstract domains for automated reasoning about list manipulating programs with infinite data","type":"conference","scopus_import":"1","language":[{"iso":"eng"}],"department":[{"_id":"ToHe"}],"status":"public","publication_status":"published","_id":"3253","date_updated":"2024-10-21T06:02:58Z","acknowledgement":"This work was partly supported by the French National Research Agency (ANR) project Veridyc (ANR-09-SEGI-016).","doi":"10.1007/978-3-642-27940-9_1","year":"2012","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publist_id":"3404","conference":{"end_date":"2012-01-24","start_date":"2012-01-22","name":"VMCAI: Verification, Model Checking and Abstract Interpretation","location":"Philadelphia, PA, USA"},"date_created":"2018-12-11T12:02:17Z","alternative_title":["LNCS"]},{"publist_id":"3400","oa":1,"date_updated":"2021-01-12T07:42:10Z","status":"public","_id":"3255","scopus_import":1,"file_date_updated":"2020-07-14T12:46:05Z","department":[{"_id":"KrCh"}],"ddc":["000"],"quality_controlled":"1","volume":7119,"citation":{"chicago":"Chatterjee, Krishnendu, and Laurent Doyen. “Games and Markov Decision Processes with Mean Payoff Parity and Energy Parity Objectives,” 7119:37–46. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-25929-6_3\">https://doi.org/10.1007/978-3-642-25929-6_3</a>.","ama":"Chatterjee K, Doyen L. Games and Markov decision processes with mean payoff parity and energy parity objectives. In: Vol 7119. Springer; 2012:37-46. doi:<a href=\"https://doi.org/10.1007/978-3-642-25929-6_3\">10.1007/978-3-642-25929-6_3</a>","ieee":"K. Chatterjee and L. Doyen, “Games and Markov decision processes with mean payoff parity and energy parity objectives,” presented at the MEMICS: Mathematical and Engineering Methods in Computer Science, Lednice, Czech Republic, 2012, vol. 7119, pp. 37–46.","apa":"Chatterjee, K., &#38; Doyen, L. (2012). Games and Markov decision processes with mean payoff parity and energy parity objectives (Vol. 7119, pp. 37–46). Presented at the MEMICS: Mathematical and Engineering Methods in Computer Science, Lednice, Czech Republic: Springer. <a href=\"https://doi.org/10.1007/978-3-642-25929-6_3\">https://doi.org/10.1007/978-3-642-25929-6_3</a>","mla":"Chatterjee, Krishnendu, and Laurent Doyen. <i>Games and Markov Decision Processes with Mean Payoff Parity and Energy Parity Objectives</i>. Vol. 7119, Springer, 2012, pp. 37–46, doi:<a href=\"https://doi.org/10.1007/978-3-642-25929-6_3\">10.1007/978-3-642-25929-6_3</a>.","short":"K. Chatterjee, L. Doyen, in:, Springer, 2012, pp. 37–46.","ista":"Chatterjee K, Doyen L. 2012. Games and Markov decision processes with mean payoff parity and energy parity objectives. MEMICS: Mathematical and Engineering Methods in Computer Science, LNCS, vol. 7119, 37–46."},"has_accepted_license":"1","page":"37 - 46","article_processing_charge":"No","month":"01","intvolume":"      7119","publisher":"Springer","conference":{"location":"Lednice, Czech Republic","start_date":"2011-10-14","name":"MEMICS: Mathematical and Engineering Methods in Computer Science","end_date":"2011-10-16"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2018-12-11T12:02:17Z","alternative_title":["LNCS"],"acknowledgement":"This work was partially supported by FWF NFN Grant S11407-N23 (RiSE) and a Microsoft faculty fellowship.","doi":"10.1007/978-3-642-25929-6_3","year":"2012","publication_status":"published","type":"conference","title":"Games and Markov decision processes with mean payoff parity and energy parity objectives","project":[{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"}],"language":[{"iso":"eng"}],"oa_version":"Submitted Version","author":[{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Laurent","last_name":"Doyen","full_name":"Doyen, Laurent"}],"day":"01","date_published":"2012-01-01T00:00:00Z","file":[{"date_updated":"2020-07-14T12:46:05Z","creator":"dernst","file_size":114060,"date_created":"2020-05-15T12:53:12Z","content_type":"application/pdf","checksum":"eed2cc1e76b160418c977e76e8899a60","relation":"main_file","access_level":"open_access","file_name":"2012_MEMICS_Chatterjee.pdf","file_id":"7863"}],"abstract":[{"text":"In this paper we survey results of two-player games on graphs and Markov decision processes with parity, mean-payoff and energy objectives, and the combination of mean-payoff and energy objectives with parity objectives. These problems have applications in verification and synthesis of reactive systems in resource-constrained environments.","lang":"eng"}]},{"date_created":"2018-12-11T12:02:25Z","alternative_title":["LNCS"],"conference":{"start_date":"2012-03-19","name":"TCC: Theory of Cryptography Conference","location":"Taormina, Sicily, Italy","end_date":"2012-03-21"},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","year":"2012","acknowledgement":"Supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013) / ERC Starting Grant (259668-PSPC)","doi":"10.1007/978-3-642-28914-9_21","publication_status":"published","language":[{"iso":"eng"}],"type":"conference","title":"Hardness preserving constructions of pseudorandom functions","project":[{"_id":"258C570E-B435-11E9-9278-68D0E5697425","grant_number":"259668","name":"Provable Security for Physical Cryptography","call_identifier":"FP7"}],"main_file_link":[{"url":"http://www.iacr.org/archive/tcc2012/tcc2012-index.html"}],"oa_version":"None","day":"04","author":[{"full_name":"Jain, Abhishek","last_name":"Jain","first_name":"Abhishek"},{"full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"},{"full_name":"Tentes, Aris","last_name":"Tentes","first_name":"Aris"}],"date_published":"2012-05-04T00:00:00Z","abstract":[{"text":"We show a hardness-preserving construction of a PRF from any length doubling PRG which improves upon known constructions whenever we can put a non-trivial upper bound q on the number of queries to the PRF. Our construction requires only O(logq) invocations to the underlying PRG with each query. In comparison, the number of invocations by the best previous hardness-preserving construction (GGM using Levin's trick) is logarithmic in the hardness of the PRG. For example, starting from an exponentially secure PRG {0,1} n → {0,1} 2n, we get a PRF which is exponentially secure if queried at most q = exp(√n)times and where each invocation of the PRF requires Θ(√n) queries to the underlying PRG. This is much less than the Θ(n) required by known constructions. \r\n","lang":"eng"}],"publist_id":"3367","date_updated":"2021-01-12T07:42:21Z","_id":"3279","status":"public","department":[{"_id":"KrPi"}],"scopus_import":1,"citation":{"ama":"Jain A, Pietrzak KZ, Tentes A. Hardness preserving constructions of pseudorandom functions. In: Vol 7194. Springer; 2012:369-382. doi:<a href=\"https://doi.org/10.1007/978-3-642-28914-9_21\">10.1007/978-3-642-28914-9_21</a>","chicago":"Jain, Abhishek, Krzysztof Z Pietrzak, and Aris Tentes. “Hardness Preserving Constructions of Pseudorandom Functions,” 7194:369–82. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-28914-9_21\">https://doi.org/10.1007/978-3-642-28914-9_21</a>.","ieee":"A. Jain, K. Z. Pietrzak, and A. Tentes, “Hardness preserving constructions of pseudorandom functions,” presented at the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy, 2012, vol. 7194, pp. 369–382.","apa":"Jain, A., Pietrzak, K. Z., &#38; Tentes, A. (2012). Hardness preserving constructions of pseudorandom functions (Vol. 7194, pp. 369–382). Presented at the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy: Springer. <a href=\"https://doi.org/10.1007/978-3-642-28914-9_21\">https://doi.org/10.1007/978-3-642-28914-9_21</a>","mla":"Jain, Abhishek, et al. <i>Hardness Preserving Constructions of Pseudorandom Functions</i>. Vol. 7194, Springer, 2012, pp. 369–82, doi:<a href=\"https://doi.org/10.1007/978-3-642-28914-9_21\">10.1007/978-3-642-28914-9_21</a>.","short":"A. Jain, K.Z. Pietrzak, A. Tentes, in:, Springer, 2012, pp. 369–382.","ista":"Jain A, Pietrzak KZ, Tentes A. 2012. Hardness preserving constructions of pseudorandom functions. TCC: Theory of Cryptography Conference, LNCS, vol. 7194, 369–382."},"quality_controlled":"1","volume":7194,"ec_funded":1,"page":"369 - 382","month":"05","publisher":"Springer","intvolume":"      7194"},{"date_published":"2012-05-04T00:00:00Z","abstract":[{"lang":"eng","text":"The (decisional) learning with errors problem (LWE) asks to distinguish &quot;noisy&quot; inner products of a secret vector with random vectors from uniform. The learning parities with noise problem (LPN) is the special case where the elements of the vectors are bits. In recent years, the LWE and LPN problems have found many applications in cryptography. In this paper we introduce a (seemingly) much stronger adaptive assumption, called &quot;subspace LWE&quot; (SLWE), where the adversary can learn the inner product of the secret and random vectors after they were projected into an adaptively and adversarially chosen subspace. We prove that, surprisingly, the SLWE problem mapping into subspaces of dimension d is almost as hard as LWE using secrets of length d (the other direction is trivial.) This result immediately implies that several existing cryptosystems whose security is based on the hardness of the LWE/LPN problems are provably secure in a much stronger sense than anticipated. As an illustrative example we show that the standard way of using LPN for symmetric CPA secure encryption is even secure against a very powerful class of related key attacks. "}],"main_file_link":[{"url":"http://www.iacr.org/archive/tcc2012/71940166/71940166.pdf","open_access":"1"}],"oa_version":"Submitted Version","day":"04","author":[{"orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak"}],"publication_status":"published","language":[{"iso":"eng"}],"type":"conference","title":"Subspace LWE","project":[{"call_identifier":"FP7","name":"Provable Security for Physical Cryptography","grant_number":"259668","_id":"258C570E-B435-11E9-9278-68D0E5697425"}],"alternative_title":["LNCS"],"date_created":"2018-12-11T12:02:26Z","conference":{"end_date":"2012-03-21","location":"Taormina, Sicily, Italy","start_date":"2012-03-19","name":"TCC: Theory of Cryptography Conference"},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","year":"2012","doi":"10.1007/978-3-642-28914-9_31","acknowledgement":"Supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013) / ERC Starting Grant (259668-PSPC).","month":"05","publisher":"Springer","intvolume":"      7194","citation":{"mla":"Pietrzak, Krzysztof Z. <i>Subspace LWE</i>. Vol. 7194, Springer, 2012, pp. 548–63, doi:<a href=\"https://doi.org/10.1007/978-3-642-28914-9_31\">10.1007/978-3-642-28914-9_31</a>.","apa":"Pietrzak, K. Z. (2012). Subspace LWE (Vol. 7194, pp. 548–563). Presented at the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy: Springer. <a href=\"https://doi.org/10.1007/978-3-642-28914-9_31\">https://doi.org/10.1007/978-3-642-28914-9_31</a>","ista":"Pietrzak KZ. 2012. Subspace LWE. TCC: Theory of Cryptography Conference, LNCS, vol. 7194, 548–563.","short":"K.Z. Pietrzak, in:, Springer, 2012, pp. 548–563.","chicago":"Pietrzak, Krzysztof Z. “Subspace LWE,” 7194:548–63. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-28914-9_31\">https://doi.org/10.1007/978-3-642-28914-9_31</a>.","ama":"Pietrzak KZ. Subspace LWE. In: Vol 7194. Springer; 2012:548-563. doi:<a href=\"https://doi.org/10.1007/978-3-642-28914-9_31\">10.1007/978-3-642-28914-9_31</a>","ieee":"K. Z. Pietrzak, “Subspace LWE,” presented at the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy, 2012, vol. 7194, pp. 548–563."},"quality_controlled":"1","volume":7194,"ec_funded":1,"page":"548 - 563","_id":"3280","corr_author":"1","status":"public","department":[{"_id":"KrPi"}],"scopus_import":"1","oa":1,"publist_id":"3366","date_updated":"2024-10-21T06:02:59Z"},{"volume":7194,"oa_version":"None","quality_controlled":"1","main_file_link":[{"url":"http://www.iacr.org/archive/tcc2012/tcc2012-index.html"}],"citation":{"ieee":"K. Z. Pietrzak, A. Rosen, and G. Segev, “Lossy functions do not amplify well,” presented at the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy, 2012, vol. 7194, pp. 458–475.","ama":"Pietrzak KZ, Rosen A, Segev G. Lossy functions do not amplify well. In: Vol 7194. Springer; 2012:458-475. doi:<a href=\"https://doi.org/10.1007/978-3-642-28914-9_26\">10.1007/978-3-642-28914-9_26</a>","chicago":"Pietrzak, Krzysztof Z, Alon Rosen, and Gil Segev. “Lossy Functions Do Not Amplify Well,” 7194:458–75. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-28914-9_26\">https://doi.org/10.1007/978-3-642-28914-9_26</a>.","ista":"Pietrzak KZ, Rosen A, Segev G. 2012. Lossy functions do not amplify well. TCC: Theory of Cryptography Conference, LNCS, vol. 7194, 458–475.","short":"K.Z. Pietrzak, A. Rosen, G. Segev, in:, Springer, 2012, pp. 458–475.","mla":"Pietrzak, Krzysztof Z., et al. <i>Lossy Functions Do Not Amplify Well</i>. Vol. 7194, Springer, 2012, pp. 458–75, doi:<a href=\"https://doi.org/10.1007/978-3-642-28914-9_26\">10.1007/978-3-642-28914-9_26</a>.","apa":"Pietrzak, K. Z., Rosen, A., &#38; Segev, G. (2012). Lossy functions do not amplify well (Vol. 7194, pp. 458–475). Presented at the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy: Springer. <a href=\"https://doi.org/10.1007/978-3-642-28914-9_26\">https://doi.org/10.1007/978-3-642-28914-9_26</a>"},"author":[{"orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak"},{"full_name":"Rosen, Alon","last_name":"Rosen","first_name":"Alon"},{"last_name":"Segev","full_name":"Segev, Gil","first_name":"Gil"}],"page":"458 - 475","day":"04","month":"05","date_published":"2012-05-04T00:00:00Z","intvolume":"      7194","abstract":[{"text":"We consider the problem of amplifying the &quot;lossiness&quot; of functions. We say that an oracle circuit C*: {0,1} m → {0,1}* amplifies relative lossiness from ℓ/n to L/m if for every function f:{0,1} n → {0,1} n it holds that 1 If f is injective then so is C f. 2 If f has image size of at most 2 n-ℓ, then C f has image size at most 2 m-L. The question is whether such C* exists for L/m ≫ ℓ/n. This problem arises naturally in the context of cryptographic &quot;lossy functions,&quot; where the relative lossiness is the key parameter. We show that for every circuit C* that makes at most t queries to f, the relative lossiness of C f is at most L/m ≤ ℓ/n + O(log t)/n. In particular, no black-box method making a polynomial t = poly(n) number of queries can amplify relative lossiness by more than an O(logn)/n additive term. We show that this is tight by giving a simple construction (cascading with some randomization) that achieves such amplification.","lang":"eng"}],"publisher":"Springer","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publist_id":"3365","conference":{"location":"Taormina, Sicily, Italy","name":"TCC: Theory of Cryptography Conference","start_date":"2012-03-19","end_date":"2012-03-21"},"alternative_title":["LNCS"],"date_created":"2018-12-11T12:02:26Z","date_updated":"2024-10-21T06:03:00Z","acknowledgement":"We would like to thank Oded Goldreich and Omer Rein- gold for discussions at an early stage of this project, and Scott Aaronson for clarifications regarding the collision problem.\r\n","doi":"10.1007/978-3-642-28914-9_26","year":"2012","status":"public","publication_status":"published","_id":"3281","scopus_import":"1","title":"Lossy functions do not amplify well","type":"conference","language":[{"iso":"eng"}],"department":[{"_id":"KrPi"}]},{"language":[{"iso":"eng"}],"title":"Message authentication, revisited","type":"conference","project":[{"_id":"258C570E-B435-11E9-9278-68D0E5697425","name":"Provable Security for Physical Cryptography","grant_number":"259668","call_identifier":"FP7"}],"publication_status":"published","year":"2012","doi":"10.1007/978-3-642-29011-4_22","acknowledgement":"Supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013) / ERC Starting Grant (259668-PSPC)","date_created":"2018-12-11T12:02:27Z","alternative_title":["LNCS"],"license":"https://creativecommons.org/licenses/by/4.0/","conference":{"location":"Cambridge, UK","name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques","start_date":"2012-04-15","end_date":"2012-04-19"},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"Traditionally, symmetric-key message authentication codes (MACs) are easily built from pseudorandom functions (PRFs). In this work we propose a wide variety of other approaches to building efficient MACs, without going through a PRF first. In particular, unlike deterministic PRF-based MACs, where each message has a unique valid tag, we give a number of probabilistic MAC constructions from various other primitives/assumptions. Our main results are summarized as follows: We show several new probabilistic MAC constructions from a variety of general assumptions, including CCA-secure encryption, Hash Proof Systems and key-homomorphic weak PRFs. By instantiating these frameworks under concrete number theoretic assumptions, we get several schemes which are more efficient than just using a state-of-the-art PRF instantiation under the corresponding assumption. For probabilistic MACs, unlike deterministic ones, unforgeability against a chosen message attack (uf-cma ) alone does not imply security if the adversary can additionally make verification queries (uf-cmva ). We give an efficient generic transformation from any uf-cma secure MAC which is &quot;message-hiding&quot; into a uf-cmva secure MAC. This resolves the main open problem of Kiltz et al. from Eurocrypt'11; By using our transformation on their constructions, we get the first efficient MACs from the LPN assumption. While all our new MAC constructions immediately give efficient actively secure, two-round symmetric-key identification schemes, we also show a very simple, three-round actively secure identification protocol from any weak PRF. In particular, the resulting protocol is much more efficient than the trivial approach of building a regular PRF from a weak PRF. © 2012 International Association for Cryptologic Research.","lang":"eng"}],"date_published":"2012-03-10T00:00:00Z","file":[{"checksum":"8557c17a8c2586d06ebfe62d934f5c5f","access_level":"open_access","relation":"main_file","file_id":"5074","file_name":"IST-2016-686-v1+1_059.pdf","date_updated":"2020-07-14T12:46:06Z","creator":"system","file_size":372292,"content_type":"application/pdf","date_created":"2018-12-12T10:14:23Z"}],"day":"10","author":[{"first_name":"Yevgeniy","last_name":"Dodis","full_name":"Dodis, Yevgeniy"},{"first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654"},{"first_name":"Eike","last_name":"Kiltz","full_name":"Kiltz, Eike"},{"last_name":"Wichs","full_name":"Wichs, Daniel","first_name":"Daniel"}],"oa_version":"Submitted Version","file_date_updated":"2020-07-14T12:46:06Z","department":[{"_id":"KrPi"}],"ddc":["000","004"],"scopus_import":"1","_id":"3282","status":"public","date_updated":"2024-10-21T06:02:59Z","oa":1,"publist_id":"3364","publisher":"Springer","intvolume":"      7237","month":"03","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"ec_funded":1,"page":"355 - 374","citation":{"ista":"Dodis Y, Pietrzak KZ, Kiltz E, Wichs D. 2012. Message authentication, revisited. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 7237, 355–374.","short":"Y. Dodis, K.Z. Pietrzak, E. Kiltz, D. Wichs, in:, Springer, 2012, pp. 355–374.","mla":"Dodis, Yevgeniy, et al. <i>Message Authentication, Revisited</i>. Vol. 7237, Springer, 2012, pp. 355–74, doi:<a href=\"https://doi.org/10.1007/978-3-642-29011-4_22\">10.1007/978-3-642-29011-4_22</a>.","apa":"Dodis, Y., Pietrzak, K. Z., Kiltz, E., &#38; Wichs, D. (2012). Message authentication, revisited (Vol. 7237, pp. 355–374). Presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Cambridge, UK: Springer. <a href=\"https://doi.org/10.1007/978-3-642-29011-4_22\">https://doi.org/10.1007/978-3-642-29011-4_22</a>","ieee":"Y. Dodis, K. Z. Pietrzak, E. Kiltz, and D. Wichs, “Message authentication, revisited,” presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Cambridge, UK, 2012, vol. 7237, pp. 355–374.","ama":"Dodis Y, Pietrzak KZ, Kiltz E, Wichs D. Message authentication, revisited. In: Vol 7237. Springer; 2012:355-374. doi:<a href=\"https://doi.org/10.1007/978-3-642-29011-4_22\">10.1007/978-3-642-29011-4_22</a>","chicago":"Dodis, Yevgeniy, Krzysztof Z Pietrzak, Eike Kiltz, and Daniel Wichs. “Message Authentication, Revisited,” 7237:355–74. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-29011-4_22\">https://doi.org/10.1007/978-3-642-29011-4_22</a>."},"has_accepted_license":"1","quality_controlled":"1","volume":7237,"pubrep_id":"686"},{"conference":{"location":"Tallinn, Estonia","name":"FoSSaCS: Foundations of Software Science and Computation Structures","start_date":"2012-03-24","end_date":"2012-04-01"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["LNCS"],"date_created":"2018-12-11T12:02:46Z","doi":"10.1007/978-3-642-28729-9_18","year":"2012","publication_status":"published","type":"conference","title":"Robustness of structurally equivalent concurrent parity games","project":[{"call_identifier":"FWF","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"language":[{"iso":"eng"}],"oa_version":"Preprint","main_file_link":[{"url":"http://arxiv.org/abs/1107.2009","open_access":"1"}],"author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"}],"day":"22","external_id":{"arxiv":["1107.2009"]},"date_published":"2012-03-22T00:00:00Z","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"}],"publist_id":"3284","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"5382"}]},"oa":1,"date_updated":"2024-10-09T20:54:38Z","status":"public","corr_author":"1","_id":"3341","scopus_import":1,"arxiv":1,"department":[{"_id":"KrCh"}],"quality_controlled":"1","volume":7213,"citation":{"ista":"Chatterjee K. 2012. Robustness of structurally equivalent concurrent parity games. FoSSaCS: Foundations of Software Science and Computation Structures, LNCS, vol. 7213, 270–285.","short":"K. Chatterjee, in:, Springer, 2012, pp. 270–285.","mla":"Chatterjee, Krishnendu. <i>Robustness of Structurally Equivalent Concurrent Parity Games</i>. Vol. 7213, Springer, 2012, pp. 270–85, doi:<a href=\"https://doi.org/10.1007/978-3-642-28729-9_18\">10.1007/978-3-642-28729-9_18</a>.","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. <a href=\"https://doi.org/10.1007/978-3-642-28729-9_18\">https://doi.org/10.1007/978-3-642-28729-9_18</a>","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.","ama":"Chatterjee K. Robustness of structurally equivalent concurrent parity games. In: Vol 7213. Springer; 2012:270-285. doi:<a href=\"https://doi.org/10.1007/978-3-642-28729-9_18\">10.1007/978-3-642-28729-9_18</a>","chicago":"Chatterjee, Krishnendu. “Robustness of Structurally Equivalent Concurrent Parity Games,” 7213:270–85. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-28729-9_18\">https://doi.org/10.1007/978-3-642-28729-9_18</a>."},"page":"270 - 285","ec_funded":1,"month":"03","intvolume":"      7213","publisher":"Springer"},{"issue":"3","citation":{"ama":"Tasic B, Miyamichi K, Hippenmeyer S, et al. Extensions of MADM (Mosaic Analysis with Double Markers) in Mice . <i>PLoS One</i>. 2012;7(3). doi:<a href=\"https://doi.org/10.1371/journal.pone.0033332\">10.1371/journal.pone.0033332</a>","chicago":"Tasic, Bosiljka, Kazunari Miyamichi, Simon Hippenmeyer, Vardhan Dani, H. Zeng, William Joo, Hui Zong, Yanru Chen Tsai, and Liqun Luo. “Extensions of MADM (Mosaic Analysis with Double Markers) in Mice .” <i>PLoS One</i>. Public Library of Science, 2012. <a href=\"https://doi.org/10.1371/journal.pone.0033332\">https://doi.org/10.1371/journal.pone.0033332</a>.","ieee":"B. Tasic <i>et al.</i>, “Extensions of MADM (Mosaic Analysis with Double Markers) in Mice ,” <i>PLoS One</i>, vol. 7, no. 3. Public Library of Science, 2012.","apa":"Tasic, B., Miyamichi, K., Hippenmeyer, S., Dani, V., Zeng, H., Joo, W., … Luo, L. (2012). Extensions of MADM (Mosaic Analysis with Double Markers) in Mice . <i>PLoS One</i>. Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pone.0033332\">https://doi.org/10.1371/journal.pone.0033332</a>","mla":"Tasic, Bosiljka, et al. “Extensions of MADM (Mosaic Analysis with Double Markers) in Mice .” <i>PLoS One</i>, vol. 7, no. 3, Public Library of Science, 2012, doi:<a href=\"https://doi.org/10.1371/journal.pone.0033332\">10.1371/journal.pone.0033332</a>.","short":"B. Tasic, K. Miyamichi, S. Hippenmeyer, V. Dani, H. Zeng, W. Joo, H. Zong, Y. Chen Tsai, L. Luo, PLoS One 7 (2012).","ista":"Tasic B, Miyamichi K, Hippenmeyer S, Dani V, Zeng H, Joo W, Zong H, Chen Tsai Y, Luo L. 2012. Extensions of MADM (Mosaic Analysis with Double Markers) in Mice . PLoS One. 7(3)."},"volume":7,"quality_controlled":0,"day":"27","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"author":[{"first_name":"Bosiljka","last_name":"Tasic","full_name":"Tasic, Bosiljka"},{"full_name":"Miyamichi, Kazunari","last_name":"Miyamichi","first_name":"Kazunari"},{"full_name":"Simon Hippenmeyer","last_name":"Hippenmeyer","first_name":"Simon","id":"37B36620-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-2279-1061"},{"first_name":"Vardhan","full_name":"Dani, Vardhan S.","last_name":"Dani"},{"first_name":"H.","full_name":"Zeng, H.","last_name":"Zeng"},{"last_name":"Joo","full_name":"Joo, William","first_name":"William"},{"first_name":"Hui","full_name":"Zong, Hui","last_name":"Zong"},{"full_name":"Chen-Tsai, Yanru","last_name":"Chen Tsai","first_name":"Yanru"},{"full_name":"Luo, Liqun","last_name":"Luo","first_name":"Liqun"}],"date_published":"2012-03-27T00:00:00Z","extern":1,"publication":"PLoS One","month":"03","abstract":[{"lang":"eng","text":"Mosaic Analysis with Double Markers (MADM) is a method for generating genetically mosaic mice, in which sibling mutant and wild-type cells are labeled with different fluorescent markers. It is a powerful tool that enables analysis of gene function at the single cell level in vivo. It requires transgenic cassettes to be located between the centromere and the mutation in the gene of interest on the same chromosome. Here we compare procedures for introduction of MADM cassettes into new loci in the mouse genome, and describe new approaches for expanding the utility of MADM. We show that: 1) Targeted homologous recombination outperforms random transgenesis in generation of reliably expressed MADM cassettes, 2) MADM cassettes in new genomic loci need to be validated for biallelic and ubiquitous expression, 3) Recombination between MADM cassettes on different chromosomes can be used to study reciprocal chromosomal deletions/duplications, and 4) MADM can be modified to permit transgene expression by combining it with a binary expression system. The advances described in this study expand current, and enable new and more versatile applications of MADM."}],"publisher":"Public Library of Science","intvolume":"         7","date_created":"2018-12-11T11:56:38Z","publist_id":"4683","year":"2012","date_updated":"2021-01-12T06:56:22Z","doi":"10.1371/journal.pone.0033332","acknowledgement":"This work was supported by a National Institutes of Health grant to LL (R01-NS050835). BT was a Damon Runyon Fellow and was supported by the Damon Runyon Cancer Research Foundation Grant DRG-1819-04. KM was supported by the Japan Society for the Promotion of Science program for Research Abroad and Human Frontier Science Program Organization (LT00300/2007-L). SH was supported by postdoctoral fellowships from the European Molecular Biology Organization (ALTF 851-2005), Human Frontier Science Program Organization (LT00805/2006-L), and Swiss National Science Foundation (PA00P3_124160 and PA00P3_136482). HZ is a Pew Scholar in Biomedical Sciences, supported by The Pew Charitable Trusts. LL is an investigator of the Howard Hughes Medical Institute. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.","_id":"2262","status":"public","publication_status":"published","type":"journal_article","title":"Extensions of MADM (Mosaic Analysis with Double Markers) in Mice "}]