[{"doi":"10.1105/tpc.112.098905","month":"06","page":"2497 - 2514","citation":{"ama":"Dai M, Zhang C, Kania U, et al. A PP6 type phosphatase holoenzyme directly regulates PIN phosphorylation and auxin efflux in Arabidopsis. <i>Plant Cell</i>. 2012;24(6):2497-2514. doi:<a href=\"https://doi.org/10.1105/tpc.112.098905\">10.1105/tpc.112.098905</a>","ieee":"M. Dai <i>et al.</i>, “A PP6 type phosphatase holoenzyme directly regulates PIN phosphorylation and auxin efflux in Arabidopsis,” <i>Plant Cell</i>, vol. 24, no. 6. American Society of Plant Biologists, pp. 2497–2514, 2012.","chicago":"Dai, Mingqiu, Chen Zhang, Urszula Kania, Fang Chen, Qin Xue, Tyra Mccray, Gang Li, et al. “A PP6 Type Phosphatase Holoenzyme Directly Regulates PIN Phosphorylation and Auxin Efflux in Arabidopsis.” <i>Plant Cell</i>. American Society of Plant Biologists, 2012. <a href=\"https://doi.org/10.1105/tpc.112.098905\">https://doi.org/10.1105/tpc.112.098905</a>.","ista":"Dai M, Zhang C, Kania U, Chen F, Xue Q, Mccray T, Li G, Qin G, Wakeley M, Terzaghi W, Wan J, Zhao Y, Xu J, Friml J, Deng X, Wang H. 2012. A PP6 type phosphatase holoenzyme directly regulates PIN phosphorylation and auxin efflux in Arabidopsis. Plant Cell. 24(6), 2497–2514.","apa":"Dai, M., Zhang, C., Kania, U., Chen, F., Xue, Q., Mccray, T., … Wang, H. (2012). A PP6 type phosphatase holoenzyme directly regulates PIN phosphorylation and auxin efflux in Arabidopsis. <i>Plant Cell</i>. American Society of Plant Biologists. <a href=\"https://doi.org/10.1105/tpc.112.098905\">https://doi.org/10.1105/tpc.112.098905</a>","short":"M. Dai, C. Zhang, U. Kania, F. Chen, Q. Xue, T. Mccray, G. Li, G. Qin, M. Wakeley, W. Terzaghi, J. Wan, Y. Zhao, J. Xu, J. Friml, X. Deng, H. Wang, Plant Cell 24 (2012) 2497–2514.","mla":"Dai, Mingqiu, et al. “A PP6 Type Phosphatase Holoenzyme Directly Regulates PIN Phosphorylation and Auxin Efflux in Arabidopsis.” <i>Plant Cell</i>, vol. 24, no. 6, American Society of Plant Biologists, 2012, pp. 2497–514, doi:<a href=\"https://doi.org/10.1105/tpc.112.098905\">10.1105/tpc.112.098905</a>."},"date_published":"2012-06-01T00:00:00Z","_id":"3110","abstract":[{"lang":"eng","text":"The directional transport of the phytohormone auxin depends on the phosphorylation status and polar localization of PIN-FORMED (PIN) auxin efflux proteins. While PINIOD (PID) kinase is directly involved in the phosphorylation of PIN proteins, the phosphatase holoenzyme complexes that dephosphorylate PIN proteins remain elusive. Here, we demonstrate that mutations simultaneously disrupting the function of Arabidopsis thaliana FyPP1 (for Phytochrome-associated serine/threonine protein phosphatase1) and FyPP3, two homologous genes encoding the catalytic subunits of protein phosphatase6 (PP6), cause elevated accumulation of phosphorylated PIN proteins, correlating with a basal-to-apical shift in subcellular PIN localization. The changes in PIN polarity result in increased root basipetal auxin transport and severe defects, including shorter roots, fewer lateral roots, defective columella cells, root meristem collapse, abnormal cotyledons (small, cup-shaped, or fused cotyledons), and altered leaf venation. Our molecular, biochemical, and genetic data support the notion that FyPP1/3, SAL (for SAPS DOMAIN-LIKE), and PP2AA proteins (RCN1 [for ROOTS CURL IN NAPHTHYLPHTHALAMIC ACID1] or PP2AA1, PP2AA2, and PP2AA3) physically interact to form a novel PP6-type heterotrimeric holoenzyme complex. We also show that FyPP1/3, SAL, and PP2AA interact with a subset of PIN proteins and that for SAL the strength of the interaction depends on the PIN phosphorylation status. Thus, an Arabidopsis PP6-type phosphatase holoenzyme acts antagonistically with PID to direct auxin transport polarity and plant development by directly regulating PIN phosphorylation. "}],"date_updated":"2021-01-12T07:41:08Z","issue":"6","type":"journal_article","date_created":"2018-12-11T12:01:27Z","publist_id":"3589","day":"01","title":"A PP6 type phosphatase holoenzyme directly regulates PIN phosphorylation and auxin efflux in Arabidopsis","status":"public","publisher":"American Society of Plant Biologists","publication_status":"published","publication":"Plant Cell","volume":24,"author":[{"first_name":"Mingqiu","last_name":"Dai","full_name":"Dai, Mingqiu"},{"last_name":"Zhang","first_name":"Chen","full_name":"Zhang, Chen"},{"first_name":"Urszula","last_name":"Kania","id":"4AE5C486-F248-11E8-B48F-1D18A9856A87","full_name":"Urszula Kania"},{"full_name":"Chen, Fang","last_name":"Chen","first_name":"Fang"},{"last_name":"Xue","first_name":"Qin","full_name":"Xue, Qin"},{"full_name":"McCray, Tyra","last_name":"Mccray","first_name":"Tyra"},{"full_name":"Li, Gang","first_name":"Gang","last_name":"Li"},{"first_name":"Genji","last_name":"Qin","full_name":"Qin, Genji"},{"last_name":"Wakeley","first_name":"Michelle","full_name":"Wakeley, Michelle"},{"first_name":"William","last_name":"Terzaghi","full_name":"Terzaghi, William"},{"full_name":"Wan, Jianmin","first_name":"Jianmin","last_name":"Wan"},{"last_name":"Zhao","first_name":"Yunde","full_name":"Zhao, Yunde"},{"first_name":"Jian","last_name":"Xu","full_name":"Xu, Jian"},{"id":"4159519E-F248-11E8-B48F-1D18A9856A87","full_name":"Jirí Friml","first_name":"Jirí","orcid":"0000-0002-8302-7596","last_name":"Friml"},{"full_name":"Deng, Xing W","first_name":"Xing","last_name":"Deng"},{"full_name":"Wang, Haiyang","first_name":"Haiyang","last_name":"Wang"}],"quality_controlled":0,"intvolume":"        24","extern":1,"year":"2012"},{"intvolume":"        22","quality_controlled":0,"author":[{"last_name":"Lin","first_name":"Deshu","full_name":"Lin, Deshu"},{"full_name":"Nagawa, Shingo","last_name":"Nagawa","first_name":"Shingo"},{"full_name":"Chen, Jisheng","first_name":"Jisheng","last_name":"Chen"},{"last_name":"Cao","first_name":"Lingyan","full_name":"Cao, Lingyan"},{"id":"4E5ADCAA-F248-11E8-B48F-1D18A9856A87","full_name":"Xu Chen","last_name":"Chen","first_name":"Xu"},{"last_name":"Xu","first_name":"Tongda","full_name":"Xu, Tongda"},{"first_name":"Hongjiang","last_name":"Li","orcid":"0000-0001-5039-9660","id":"33CA54A6-F248-11E8-B48F-1D18A9856A87","full_name":"Hongjiang Li"},{"full_name":"Dhonukshe, Pankaj","last_name":"Dhonukshe","first_name":"Pankaj"},{"last_name":"Yamamuro","first_name":"Chizuko","full_name":"Yamamuro, Chizuko"},{"last_name":"Friml","orcid":"0000-0002-8302-7596","first_name":"Jirí","id":"4159519E-F248-11E8-B48F-1D18A9856A87","full_name":"Jirí Friml"},{"last_name":"Scheres","first_name":"Ben","full_name":"Scheres, Ben"},{"last_name":"Fu","first_name":"Ying","full_name":"Fu, Ying"},{"last_name":"Yang","first_name":"Zhenbiao","full_name":"Yang, Zhenbiao"}],"extern":1,"year":"2012","day":"24","title":"A ROP GTPase dependent auxin signaling pathway regulates the subcellular distribution of PIN2 in Arabidopsis roots","status":"public","publisher":"Cell Press","publication_status":"published","publication":"Current Biology","volume":22,"issue":"14","type":"journal_article","publist_id":"3588","date_created":"2018-12-11T12:01:27Z","doi":"10.1016/j.cub.2012.05.019","month":"07","page":"1319 - 1325","citation":{"ama":"Lin D, Nagawa S, Chen J, et al. A ROP GTPase dependent auxin signaling pathway regulates the subcellular distribution of PIN2 in Arabidopsis roots. <i>Current Biology</i>. 2012;22(14):1319-1325. doi:<a href=\"https://doi.org/10.1016/j.cub.2012.05.019\">10.1016/j.cub.2012.05.019</a>","ieee":"D. Lin <i>et al.</i>, “A ROP GTPase dependent auxin signaling pathway regulates the subcellular distribution of PIN2 in Arabidopsis roots,” <i>Current Biology</i>, vol. 22, no. 14. Cell Press, pp. 1319–1325, 2012.","ista":"Lin D, Nagawa S, Chen J, Cao L, Chen X, Xu T, Li H, Dhonukshe P, Yamamuro C, Friml J, Scheres B, Fu Y, Yang Z. 2012. A ROP GTPase dependent auxin signaling pathway regulates the subcellular distribution of PIN2 in Arabidopsis roots. Current Biology. 22(14), 1319–1325.","chicago":"Lin, Deshu, Shingo Nagawa, Jisheng Chen, Lingyan Cao, Xu Chen, Tongda Xu, Hongjiang Li, et al. “A ROP GTPase Dependent Auxin Signaling Pathway Regulates the Subcellular Distribution of PIN2 in Arabidopsis Roots.” <i>Current Biology</i>. Cell Press, 2012. <a href=\"https://doi.org/10.1016/j.cub.2012.05.019\">https://doi.org/10.1016/j.cub.2012.05.019</a>.","mla":"Lin, Deshu, et al. “A ROP GTPase Dependent Auxin Signaling Pathway Regulates the Subcellular Distribution of PIN2 in Arabidopsis Roots.” <i>Current Biology</i>, vol. 22, no. 14, Cell Press, 2012, pp. 1319–25, doi:<a href=\"https://doi.org/10.1016/j.cub.2012.05.019\">10.1016/j.cub.2012.05.019</a>.","short":"D. Lin, S. Nagawa, J. Chen, L. Cao, X. Chen, T. Xu, H. Li, P. Dhonukshe, C. Yamamuro, J. Friml, B. Scheres, Y. Fu, Z. Yang, Current Biology 22 (2012) 1319–1325.","apa":"Lin, D., Nagawa, S., Chen, J., Cao, L., Chen, X., Xu, T., … Yang, Z. (2012). A ROP GTPase dependent auxin signaling pathway regulates the subcellular distribution of PIN2 in Arabidopsis roots. <i>Current Biology</i>. Cell Press. <a href=\"https://doi.org/10.1016/j.cub.2012.05.019\">https://doi.org/10.1016/j.cub.2012.05.019</a>"},"date_published":"2012-07-24T00:00:00Z","date_updated":"2021-01-12T07:41:08Z","_id":"3111","abstract":[{"text":"PIN-FORMED (PIN) protein-mediated auxin polar transport is critically important for development, pattern formation, and morphogenesis in plants. Auxin has been implicated in the regulation of polar auxin transport by inhibiting PIN endocytosis [1, 2], but how auxin regulates this process is poorly understood. Our genetic screen identified the Arabidopsis SPIKE1 (SPK1) gene whose loss-of-function mutations increased lateral root density and retarded gravitropic responses, as do pin2 knockout mutations [3]. SPK1 belongs to the conserved DHR2-Dock family of Rho guanine nucleotide exchange factors [4-6]. The spk1 mutations induced PIN2 internalization that was not suppressed by auxin, as did the loss-of-function mutations for Rho-like GTPase from Plants 6 (ROP6)-GTPase or its effector RIC1. Furthermore, SPK1 was required for auxin induction of ROP6 activation. Our results have established a Rho GTPase-based auxin signaling pathway that maintains PIN2 polar distribution to the plasma membrane via inhibition of its internalization in Arabidopsis roots. Our findings provide new insights into signaling mechanisms that underlie the regulation of the dynamic trafficking of PINs required for long-distance auxin transport and that link auxin signaling to PIN-mediated pattern formation and morphogenesis.","lang":"eng"}]},{"doi":"10.1016/j.cub.2012.05.020","month":"07","abstract":[{"text":"The dynamic spatial and temporal distribution of the crucial plant signaling molecule auxin is achieved by feedback coordination of auxin signaling and intercellular auxin transport pathways [1, 2]. Developmental roles of auxin have been attributed predominantly to its effect on transcription; however, an alternative pathway involving AUXIN BINDING PROTEIN1 (ABP1) has been proposed to regulate clathrin-mediated endocytosis in roots and Rho-like GTPase (ROP)-dependent pavement cell interdigitation in leaves [3, 4]. In this study, we show that ROP6 and its downstream effector RIC1 regulate clathrin association with the plasma membrane for clathrin-mediated endocytosis, as well as for its feedback regulation by auxin. Genetic analysis revealed that ROP6/RIC1 acts downstream of ABP1 to regulate endocytosis. This signaling circuit is also involved in the feedback regulation of PIN-FORMED 1 (PIN1) and PIN2 auxin transporters activity (via its constitutive endocytosis) and corresponding auxin transport-mediated processes, including root gravitropism and leave vascular tissue patterning. Our findings suggest that the signaling module auxin-ABP1-ROP6/RIC1-clathrin-PIN1/PIN2 is a shared component of the feedback regulation of auxin transport during both root and aerial development.","lang":"eng"}],"_id":"3112","date_updated":"2021-01-12T07:41:08Z","date_published":"2012-07-24T00:00:00Z","citation":{"ieee":"X. Chen <i>et al.</i>, “ABP1 and ROP6 GTPase signaling regulate clathrin mediated endocytosis in Arabidopsis roots,” <i>Current Biology</i>, vol. 22, no. 14. Cell Press, pp. 1326–1332, 2012.","ama":"Chen X, Naramoto S, Robert S, et al. ABP1 and ROP6 GTPase signaling regulate clathrin mediated endocytosis in Arabidopsis roots. <i>Current Biology</i>. 2012;22(14):1326-1332. doi:<a href=\"https://doi.org/10.1016/j.cub.2012.05.020\">10.1016/j.cub.2012.05.020</a>","chicago":"Chen, Xu, Satoshi Naramoto, Stéphanie Robert, Ricardo Tejos, Christian Löfke, Deshu Lin, Zhenbiao Yang, and Jiří Friml. “ABP1 and ROP6 GTPase Signaling Regulate Clathrin Mediated Endocytosis in Arabidopsis Roots.” <i>Current Biology</i>. Cell Press, 2012. <a href=\"https://doi.org/10.1016/j.cub.2012.05.020\">https://doi.org/10.1016/j.cub.2012.05.020</a>.","ista":"Chen X, Naramoto S, Robert S, Tejos R, Löfke C, Lin D, Yang Z, Friml J. 2012. ABP1 and ROP6 GTPase signaling regulate clathrin mediated endocytosis in Arabidopsis roots. Current Biology. 22(14), 1326–1332.","apa":"Chen, X., Naramoto, S., Robert, S., Tejos, R., Löfke, C., Lin, D., … Friml, J. (2012). ABP1 and ROP6 GTPase signaling regulate clathrin mediated endocytosis in Arabidopsis roots. <i>Current Biology</i>. Cell Press. <a href=\"https://doi.org/10.1016/j.cub.2012.05.020\">https://doi.org/10.1016/j.cub.2012.05.020</a>","short":"X. Chen, S. Naramoto, S. Robert, R. Tejos, C. Löfke, D. Lin, Z. Yang, J. Friml, Current Biology 22 (2012) 1326–1332.","mla":"Chen, Xu, et al. “ABP1 and ROP6 GTPase Signaling Regulate Clathrin Mediated Endocytosis in Arabidopsis Roots.” <i>Current Biology</i>, vol. 22, no. 14, Cell Press, 2012, pp. 1326–32, doi:<a href=\"https://doi.org/10.1016/j.cub.2012.05.020\">10.1016/j.cub.2012.05.020</a>."},"page":"1326 - 1332","issue":"14","type":"journal_article","date_created":"2018-12-11T12:01:27Z","publist_id":"3587","title":"ABP1 and ROP6 GTPase signaling regulate clathrin mediated endocytosis in Arabidopsis roots","status":"public","day":"24","publication_status":"published","publisher":"Cell Press","volume":22,"publication":"Current Biology","quality_controlled":0,"intvolume":"        22","author":[{"last_name":"Chen","first_name":"Xu","full_name":"Xu Chen","id":"4E5ADCAA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Naramoto, Satoshi","first_name":"Satoshi","last_name":"Naramoto"},{"full_name":"Robert, Stéphanie","first_name":"Stéphanie","last_name":"Robert"},{"last_name":"Tejos","first_name":"Ricardo","full_name":"Tejos, Ricardo"},{"first_name":"Christian","last_name":"Löfke","full_name":"Löfke, Christian"},{"last_name":"Lin","first_name":"Deshu","full_name":"Lin, Deshu"},{"last_name":"Yang","first_name":"Zhenbiao","full_name":"Yang, Zhenbiao"},{"last_name":"Friml","orcid":"0000-0002-8302-7596","first_name":"Jirí","id":"4159519E-F248-11E8-B48F-1D18A9856A87","full_name":"Jirí Friml"}],"extern":1,"year":"2012"},{"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","title":"Fano 3 folds in codimension 4 Tom and Jerry Part I","scopus_import":"1","article_processing_charge":"No","year":"2012","intvolume":"       148","author":[{"full_name":"Brown, Gavin","first_name":"Gavin","last_name":"Brown"},{"id":"36E4574A-F248-11E8-B48F-1D18A9856A87","full_name":"Kerber, Michael","orcid":"0000-0002-8030-9299","last_name":"Kerber","first_name":"Michael"},{"first_name":"Miles","last_name":"Reid","full_name":"Reid, Miles"}],"abstract":[{"lang":"eng","text":"We introduce a strategy based on Kustin-Miller unprojection that allows us to construct many hundreds of Gorenstein codimension 4 ideals with 9 × 16 resolutions (that is, nine equations and sixteen first syzygies). Our two basic games are called Tom and Jerry; the main application is the biregular construction of most of the anticanonically polarised Mori Fano 3-folds of Altinok's thesis. There are 115 cases whose numerical data (in effect, the Hilbert series) allow a Type I projection. In every case, at least one Tom and one Jerry construction works, providing at least two deformation families of quasismooth Fano 3-folds having the same numerics but different topology. © 2012 Copyright Foundation Compositio Mathematica."}],"_id":"3120","date_updated":"2025-09-30T07:59:55Z","department":[{"_id":"HeEd"}],"date_published":"2012-07-01T00:00:00Z","page":"1171 - 1194","citation":{"ista":"Brown G, Kerber M, Reid M. 2012. Fano 3 folds in codimension 4 Tom and Jerry Part I. Compositio Mathematica. 148(4), 1171–1194.","chicago":"Brown, Gavin, Michael Kerber, and Miles Reid. “Fano 3 Folds in Codimension 4 Tom and Jerry Part I.” <i>Compositio Mathematica</i>. Cambridge University Press, 2012. <a href=\"https://doi.org/10.1112/S0010437X11007226\">https://doi.org/10.1112/S0010437X11007226</a>.","ieee":"G. Brown, M. Kerber, and M. Reid, “Fano 3 folds in codimension 4 Tom and Jerry Part I,” <i>Compositio Mathematica</i>, vol. 148, no. 4. Cambridge University Press, pp. 1171–1194, 2012.","ama":"Brown G, Kerber M, Reid M. Fano 3 folds in codimension 4 Tom and Jerry Part I. <i>Compositio Mathematica</i>. 2012;148(4):1171-1194. doi:<a href=\"https://doi.org/10.1112/S0010437X11007226\">10.1112/S0010437X11007226</a>","short":"G. Brown, M. Kerber, M. Reid, Compositio Mathematica 148 (2012) 1171–1194.","mla":"Brown, Gavin, et al. “Fano 3 Folds in Codimension 4 Tom and Jerry Part I.” <i>Compositio Mathematica</i>, vol. 148, no. 4, Cambridge University Press, 2012, pp. 1171–94, doi:<a href=\"https://doi.org/10.1112/S0010437X11007226\">10.1112/S0010437X11007226</a>.","apa":"Brown, G., Kerber, M., &#38; Reid, M. (2012). Fano 3 folds in codimension 4 Tom and Jerry Part I. <i>Compositio Mathematica</i>. Cambridge University Press. <a href=\"https://doi.org/10.1112/S0010437X11007226\">https://doi.org/10.1112/S0010437X11007226</a>"},"language":[{"iso":"eng"}],"date_created":"2018-12-11T12:01:30Z","oa_version":"Preprint","type":"journal_article","issue":"4","isi":1,"oa":1,"volume":148,"publication":"Compositio Mathematica","publication_status":"published","publisher":"Cambridge University Press","status":"public","day":"01","arxiv":1,"quality_controlled":"1","acknowledgement":"This research is supported by the Korean Government WCU Grant R33-2008-000-10101-0.","external_id":{"isi":["000307176400007"],"arxiv":["1009.4313"]},"month":"07","doi":"10.1112/S0010437X11007226","publist_id":"3579","main_file_link":[{"url":"http://arxiv.org/abs/1009.4313","open_access":"1"}]},{"publist_id":"3574","month":"10","file_date_updated":"2020-07-14T12:46:00Z","doi":"10.1007/978-3-642-33715-4_18","ddc":["000"],"quality_controlled":"1","publication_status":"published","publisher":"Springer","volume":7576,"file":[{"date_created":"2020-05-15T12:29:04Z","relation":"main_file","file_id":"7861","content_type":"application/pdf","checksum":"bccdbe0663780d25a1e0524002b2d896","date_updated":"2020-07-14T12:46:00Z","creator":"dernst","access_level":"open_access","file_name":"2012_ECCV_Sharmanska.pdf","file_size":6073897}],"status":"public","day":"01","type":"conference","date_created":"2018-12-11T12:01:32Z","oa_version":"Submitted Version","oa":1,"issue":"PART 5","language":[{"iso":"eng"}],"has_accepted_license":"1","date_updated":"2023-02-23T11:13:25Z","_id":"3125","abstract":[{"lang":"eng","text":"We propose a new learning method to infer a mid-level feature representation that combines the advantage of semantic attribute representations with the higher expressive power of non-semantic features. The idea lies in augmenting an existing attribute-based representation with additional dimensions for which an autoencoder model is coupled with a large-margin principle. This construction allows a smooth transition between the zero-shot regime with no training example, the unsupervised regime with training examples but without class labels, and the supervised regime with training examples and with class labels. The resulting optimization problem can be solved efficiently, because several of the necessity steps have closed-form solutions. Through extensive experiments we show that the augmented representation achieves better results in terms of object categorization accuracy than the semantic representation alone."}],"date_published":"2012-10-01T00:00:00Z","page":"242 - 255","department":[{"_id":"ChLa"}],"citation":{"mla":"Sharmanska, Viktoriia, et al. <i>Augmented Attribute Representations</i>. Vol. 7576, no. PART 5, Springer, 2012, pp. 242–55, doi:<a href=\"https://doi.org/10.1007/978-3-642-33715-4_18\">10.1007/978-3-642-33715-4_18</a>.","short":"V. Sharmanska, N. Quadrianto, C. Lampert, in:, Springer, 2012, pp. 242–255.","apa":"Sharmanska, V., Quadrianto, N., &#38; Lampert, C. (2012). Augmented attribute representations (Vol. 7576, pp. 242–255). Presented at the ECCV: European Conference on Computer Vision, Florence, Italy: Springer. <a href=\"https://doi.org/10.1007/978-3-642-33715-4_18\">https://doi.org/10.1007/978-3-642-33715-4_18</a>","ista":"Sharmanska V, Quadrianto N, Lampert C. 2012. Augmented attribute representations. ECCV: European Conference on Computer Vision, LNCS, vol. 7576, 242–255.","chicago":"Sharmanska, Viktoriia, Novi Quadrianto, and Christoph Lampert. “Augmented Attribute Representations,” 7576:242–55. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-33715-4_18\">https://doi.org/10.1007/978-3-642-33715-4_18</a>.","ama":"Sharmanska V, Quadrianto N, Lampert C. Augmented attribute representations. In: Vol 7576. Springer; 2012:242-255. doi:<a href=\"https://doi.org/10.1007/978-3-642-33715-4_18\">10.1007/978-3-642-33715-4_18</a>","ieee":"V. Sharmanska, N. Quadrianto, and C. Lampert, “Augmented attribute representations,” presented at the ECCV: European Conference on Computer Vision, Florence, Italy, 2012, vol. 7576, no. PART 5, pp. 242–255."},"article_processing_charge":"No","year":"2012","intvolume":"      7576","author":[{"first_name":"Viktoriia","last_name":"Sharmanska","orcid":"0000-0003-0192-9308","full_name":"Sharmanska, Viktoriia","id":"2EA6D09E-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Novi","last_name":"Quadrianto","full_name":"Quadrianto, Novi"},{"id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","full_name":"Lampert, Christoph","first_name":"Christoph","orcid":"0000-0001-8622-7887","last_name":"Lampert"}],"alternative_title":["LNCS"],"scopus_import":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Augmented attribute representations","conference":{"location":"Florence, Italy","start_date":"2012-10-07","end_date":"2012-10-13","name":"ECCV: European Conference on Computer Vision"}},{"quality_controlled":"1","author":[{"first_name":"Andreas","last_name":"Müller","full_name":"Müller, Andreas"},{"full_name":"Nowozin, Sebastian","first_name":"Sebastian","last_name":"Nowozin"},{"first_name":"Christoph","last_name":"Lampert","orcid":"0000-0001-8622-7887","full_name":"Lampert, Christoph","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87"}],"intvolume":"      7476","year":"2012","conference":{"start_date":"2012-08-28","location":"Graz, Austria","end_date":"2012-08-31","name":"DAGM: German Association For Pattern Recognition"},"day":"14","status":"public","title":"Information theoretic clustering using minimal spanning trees","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","scopus_import":1,"volume":7476,"alternative_title":["LNCS"],"publisher":"Springer","publication_status":"published","oa_version":"None","publist_id":"3573","date_created":"2018-12-11T12:01:32Z","type":"conference","doi":"10.1007/978-3-642-32717-9_21","department":[{"_id":"ChLa"}],"citation":{"chicago":"Müller, Andreas, Sebastian Nowozin, and Christoph Lampert. “Information Theoretic Clustering Using Minimal Spanning Trees,” 7476:205–15. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-32717-9_21\">https://doi.org/10.1007/978-3-642-32717-9_21</a>.","ista":"Müller A, Nowozin S, Lampert C. 2012. Information theoretic clustering using minimal spanning trees. DAGM: German Association For Pattern Recognition, LNCS, vol. 7476, 205–215.","ieee":"A. Müller, S. Nowozin, and C. Lampert, “Information theoretic clustering using minimal spanning trees,” presented at the DAGM: German Association For Pattern Recognition, Graz, Austria, 2012, vol. 7476, pp. 205–215.","ama":"Müller A, Nowozin S, Lampert C. Information theoretic clustering using minimal spanning trees. In: Vol 7476. Springer; 2012:205-215. doi:<a href=\"https://doi.org/10.1007/978-3-642-32717-9_21\">10.1007/978-3-642-32717-9_21</a>","apa":"Müller, A., Nowozin, S., &#38; Lampert, C. (2012). Information theoretic clustering using minimal spanning trees (Vol. 7476, pp. 205–215). Presented at the DAGM: German Association For Pattern Recognition, Graz, Austria: Springer. <a href=\"https://doi.org/10.1007/978-3-642-32717-9_21\">https://doi.org/10.1007/978-3-642-32717-9_21</a>","short":"A. Müller, S. Nowozin, C. Lampert, in:, Springer, 2012, pp. 205–215.","mla":"Müller, Andreas, et al. <i>Information Theoretic Clustering Using Minimal Spanning Trees</i>. Vol. 7476, Springer, 2012, pp. 205–15, doi:<a href=\"https://doi.org/10.1007/978-3-642-32717-9_21\">10.1007/978-3-642-32717-9_21</a>."},"page":"205 - 215","date_published":"2012-08-14T00:00:00Z","abstract":[{"lang":"eng","text":"In this work we propose a new information-theoretic clustering algorithm that infers cluster memberships by direct optimization of a non-parametric mutual information estimate between data distribution and cluster assignment. Although the optimization objective has a solid theoretical foundation it is hard to optimize. We propose an approximate optimization formulation that leads to an efficient algorithm with low runtime complexity. The algorithm has a single free parameter, the number of clusters to find. We demonstrate superior performance on several synthetic and real datasets.\r\n"}],"_id":"3126","date_updated":"2021-01-12T07:41:14Z","month":"08","language":[{"iso":"eng"}]},{"arxiv":1,"scopus_import":"1","conference":{"location":"Edinburgh, United Kingdom","start_date":"2012-06-26","name":"ICML: International Conference on Machine Learning","end_date":"2012-07-01"},"day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","title":"The most persistent soft-clique in a set of sampled graphs","publisher":"ML Research Press","publication_status":"published","publication":"Proceedings of the 29th International Conference on Machine Learning","external_id":{"arxiv":["1206.4652"]},"author":[{"full_name":"Quadrianto, Novi","last_name":"Quadrianto","first_name":"Novi"},{"id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","full_name":"Lampert, Christoph","last_name":"Lampert","orcid":"0000-0001-8622-7887","first_name":"Christoph"},{"first_name":"Chao","last_name":"Chen","id":"3E92416E-F248-11E8-B48F-1D18A9856A87","full_name":"Chen, Chao"}],"quality_controlled":"1","year":"2012","article_processing_charge":"No","month":"06","language":[{"iso":"eng"}],"page":"211-218","date_published":"2012-06-01T00:00:00Z","citation":{"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.","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.","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.","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.","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."},"department":[{"_id":"ChLa"},{"_id":"HeEd"}],"_id":"3127","abstract":[{"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.","lang":"eng"}],"date_updated":"2025-06-11T08:09:42Z","oa":1,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1206.4652"}],"type":"conference","publist_id":"3572","date_created":"2018-12-11T12:01:33Z","oa_version":"Preprint"},{"publist_id":"3569","main_file_link":[{"url":"http://arxiv.org/abs/1107.3793","open_access":"1"}],"month":"06","doi":"10.1007/978-3-642-31155-0_17","quality_controlled":"1","acknowledgement":"Research was partially supported by the Slovenian Research Agency, program P1-0297 and NSF grant CCF 1064416.","external_id":{"arxiv":["1107.3793"]},"volume":7357,"publication_status":"published","publisher":"Springer","status":"public","day":"19","arxiv":1,"date_created":"2018-12-11T12:01:33Z","oa_version":"Preprint","type":"conference","oa":1,"_id":"3129","date_updated":"2025-06-26T08:59:21Z","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","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>.","short":"O. Busaryev, S. Cabello, C. Chen, T. Dey, Y. Wang, in:, Springer, 2012, pp. 189–200.","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>","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.","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>."},"page":"189 - 200","department":[{"_id":"HeEd"}],"language":[{"iso":"eng"}],"article_processing_charge":"No","year":"2012","intvolume":"      7357","author":[{"first_name":"Oleksiy","last_name":"Busaryev","full_name":"Busaryev, Oleksiy"},{"last_name":"Cabello","first_name":"Sergio","full_name":"Cabello, Sergio"},{"last_name":"Chen","first_name":"Chao","full_name":"Chen, Chao","id":"3E92416E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Dey, Tamal","first_name":"Tamal","last_name":"Dey"},{"full_name":"Wang, Yusu","first_name":"Yusu","last_name":"Wang"}],"alternative_title":["LNCS"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Annotating simplices with a homology basis and its applications","conference":{"name":"SWAT: Symposium and Workshops on Algorithm Theory","end_date":"2012-07-06","start_date":"2012-07-04","location":"Helsinki, Finland"},"scopus_import":"1"},{"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).","external_id":{"arxiv":["1202.0796"]},"quality_controlled":"1","arxiv":1,"status":"public","day":"01","publication_status":"published","publisher":"Springer","volume":7358,"ec_funded":1,"main_file_link":[{"url":"http://arxiv.org/abs/1202.0796","open_access":"1"}],"publist_id":"3562","project":[{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"}],"doi":"10.1007/978-3-642-31424-7_8","month":"07","intvolume":"      7358","author":[{"first_name":"Brázdil","last_name":"Brázdil","full_name":"Brázdil, Brázdil"},{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"full_name":"Kučera, Antonín","last_name":"Kučera","first_name":"Antonín"},{"first_name":"Petr","last_name":"Novotny","full_name":"Novotny, Petr","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87"}],"article_processing_charge":"No","year":"2012","scopus_import":"1","title":"Efficient controller synthesis for consumption games with multiple resource types","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"start_date":"2012-07-07","location":"Berkeley, CA, USA","end_date":"2012-07-13","name":"CAV: Computer Aided Verification"},"alternative_title":["LNCS"],"oa":1,"type":"conference","date_created":"2018-12-11T12:01:35Z","oa_version":"Preprint","language":[{"iso":"eng"}],"abstract":[{"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. ","lang":"eng"}],"_id":"3135","date_updated":"2025-06-11T08:10:20Z","date_published":"2012-07-01T00:00:00Z","department":[{"_id":"KrCh"}],"citation":{"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>","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>.","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>.","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.","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>","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."},"page":"23 - 38"},{"alternative_title":["LNCS"],"scopus_import":1,"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","title":"Delayed continuous time Markov chains for genetic regulatory circuits","conference":{"start_date":"2012-07-07","location":"Berkeley, CA, USA","name":"CAV: Computer Aided Verification","end_date":"2012-07-13"},"year":"2012","author":[{"full_name":"Guet, Calin C","id":"47F8433E-F248-11E8-B48F-1D18A9856A87","first_name":"Calin C","last_name":"Guet","orcid":"0000-0001-6220-2052"},{"first_name":"Ashutosh","last_name":"Gupta","id":"335E5684-F248-11E8-B48F-1D18A9856A87","full_name":"Gupta, Ashutosh"},{"orcid":"0000−0002−2985−7724","last_name":"Henzinger","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A"},{"first_name":"Maria","last_name":"Mateescu","full_name":"Mateescu, Maria","id":"3B43276C-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Ali","last_name":"Sezgin","id":"4C7638DA-F248-11E8-B48F-1D18A9856A87","full_name":"Sezgin, Ali"}],"language":[{"iso":"eng"}],"_id":"3136","date_updated":"2024-10-09T20:54:47Z","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."}],"citation":{"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>.","short":"C.C. Guet, A. Gupta, T.A. Henzinger, M. Mateescu, A. Sezgin, in:, Springer, 2012, pp. 294–309.","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>","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.","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.","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>"},"date_published":"2012-07-01T00:00:00Z","page":"294 - 309","department":[{"_id":"CaGu"},{"_id":"ToHe"}],"type":"conference","date_created":"2018-12-11T12:01:36Z","oa_version":"None","publication_status":"published","publisher":"Springer","volume":"7358 ","status":"public","day":"01","acknowledgement":"This work was supported by the ERC Advanced Investigator grant on Quantitative Reactive Modeling (QUAREM) and by the Swiss National Science Foundation.","quality_controlled":"1","month":"07","project":[{"call_identifier":"FP7","grant_number":"267989","name":"Quantitative Reactive Modeling","_id":"25EE3708-B435-11E9-9278-68D0E5697425"}],"doi":"10.1007/978-3-642-31424-7_24","corr_author":"1","publist_id":"3561","ec_funded":1},{"doi":"10.1007/978-3-642-30793-5_13","file_date_updated":"2020-07-14T12:46:01Z","pubrep_id":"88","month":"06","publist_id":"3539","day":"01","status":"public","file":[{"relation":"main_file","date_created":"2018-12-12T10:11:25Z","file_id":"4879","content_type":"application/pdf","checksum":"feae2e07f2d9a59843f8ddabf25d179f","creator":"system","date_updated":"2020-07-14T12:46:01Z","file_name":"IST-2012-88-v1+1_Synchronous_interface_theories_and_time_triggered_scheduling.pdf","access_level":"open_access","file_size":493198}],"volume":7273,"publisher":"Springer","publication_status":"published","quality_controlled":"1","ddc":["004"],"acknowledgement":"Research partially supported by the Danish-Chinese Center for Cyber Physical Systems (Grant No.61061130541) and VKR Center of Excellence MT-LAB.","date_published":"2012-06-01T00:00:00Z","citation":{"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>.","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.","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.","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>","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."},"page":"203 - 218","department":[{"_id":"ToHe"}],"_id":"3155","abstract":[{"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.","lang":"eng"}],"date_updated":"2021-01-12T07:41:26Z","has_accepted_license":"1","language":[{"iso":"eng"}],"oa":1,"oa_version":"Submitted Version","date_created":"2018-12-11T12:01:43Z","type":"conference","conference":{"location":"Stockholm, Sweden","start_date":"2012-06-13","end_date":"2012-06-16","name":"FORTE: Formal Techniques for Networked and Distributed Systems & FMOODS: Formal Methods for Open Object-Based Distributed Systems "},"title":"Synchronous interface theories and time triggered scheduling","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","scopus_import":1,"alternative_title":["LNCS"],"author":[{"first_name":"Benoît","last_name":"Delahaye","full_name":"Delahaye, Benoît"},{"first_name":"Uli","last_name":"Fahrenberg","full_name":"Fahrenberg, Uli"},{"last_name":"Henzinger","orcid":"0000−0002−2985−7724","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A"},{"first_name":"Axel","last_name":"Legay","full_name":"Legay, Axel"},{"first_name":"Dejan","last_name":"Nickovic","full_name":"Nickovic, Dejan","id":"41BCEE5C-F248-11E8-B48F-1D18A9856A87"}],"intvolume":"      7273","year":"2012"},{"language":[{"iso":"eng"}],"_id":"3160","date_updated":"2025-09-30T07:53:56Z","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"}],"department":[{"_id":"ToBo"}],"citation":{"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.","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>","ista":"Pantazis P, Bollenbach MT. 2012. Transcription factor kinetics and the emerging asymmetry in the early mammalian embryo. Cell Cycle. 11(11), 2055–2058.","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>.","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>","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."},"date_published":"2012-06-01T00:00:00Z","page":"2055 - 2058","isi":1,"issue":"11","type":"journal_article","date_created":"2018-12-11T12:01:44Z","oa_version":"None","scopus_import":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","title":"Transcription factor kinetics and the emerging asymmetry in the early mammalian embryo","author":[{"first_name":"Periklis","last_name":"Pantazis","full_name":"Pantazis, Periklis"},{"id":"3E6DB97A-F248-11E8-B48F-1D18A9856A87","full_name":"Bollenbach, Tobias","orcid":"0000-0003-4398-476X","last_name":"Bollenbach","first_name":"Tobias"}],"intvolume":"        11","article_processing_charge":"No","year":"2012","doi":"10.4161/cc.20118","month":"06","corr_author":"1","publist_id":"3531","status":"public","day":"01","publication_status":"published","publisher":"Taylor and Francis","volume":11,"publication":"Cell Cycle","external_id":{"isi":["000304770100011"]},"quality_controlled":"1"},{"has_accepted_license":"1","language":[{"iso":"eng"}],"date_published":"2012-01-01T00:00:00Z","department":[{"_id":"ToHe"}],"page":"147 - 160","citation":{"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>","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>.","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>.","ista":"Asarin E, Donzé A, Maler O, Nickovic D. 2012. Parametric identification of temporal properties. RV: Runtime Verification, LNCS, vol. 7186, 147–160.","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."},"_id":"3162","abstract":[{"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.","lang":"eng"}],"date_updated":"2021-01-12T07:41:29Z","type":"conference","oa_version":"Submitted Version","date_created":"2018-12-11T12:01:45Z","oa":1,"alternative_title":["LNCS"],"scopus_import":1,"conference":{"start_date":"2011-09-27","location":"San Francisco, CA, United States","end_date":"2011-09-30","name":"RV: Runtime Verification"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Parametric identification of temporal properties","year":"2012","article_processing_charge":"No","author":[{"last_name":"Asarin","first_name":"Eugene","full_name":"Asarin, Eugene"},{"full_name":"Donzé, Alexandre","first_name":"Alexandre","last_name":"Donzé"},{"last_name":"Maler","first_name":"Oded","full_name":"Maler, Oded"},{"last_name":"Nickovic","first_name":"Dejan","full_name":"Nickovic, Dejan","id":"41BCEE5C-F248-11E8-B48F-1D18A9856A87"}],"intvolume":"      7186","month":"01","doi":"10.1007/978-3-642-29860-8_12","file_date_updated":"2020-07-14T12:46:01Z","publist_id":"3525","publisher":"Springer","publication_status":"published","volume":7186,"file":[{"access_level":"open_access","file_name":"2012_RV_Asarin.pdf","file_size":374726,"content_type":"application/pdf","checksum":"ba4a75287008fc64b8fbf78a7476ec32","creator":"dernst","date_updated":"2020-07-14T12:46:01Z","file_id":"7862","relation":"main_file","date_created":"2020-05-15T12:50:15Z"}],"day":"01","status":"public","ddc":["000"],"quality_controlled":"1"},{"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.","external_id":{"arxiv":["1109.5018"]},"quality_controlled":"1","arxiv":1,"status":"public","day":"01","publication_status":"published","publisher":"SIAM","publication":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","ec_funded":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1109.5018"}],"OA_place":"repository","corr_author":"1","publist_id":"3519","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":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"OA_type":"green","pubrep_id":"15","doi":"10.1137/1.9781611973099.109","month":"01","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"5379"},{"relation":"later_version","id":"2141","status":"public"}]},"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","first_name":"Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger"}],"article_processing_charge":"No","year":"2012","title":"An O(n2) time algorithm for alternating Büchi games","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"start_date":"2012-01-17","location":"Kyoto, Japan","name":"SODA: Symposium on Discrete Algorithms","end_date":"2012-01-19"},"oa":1,"type":"conference","date_created":"2018-12-11T12:01:46Z","oa_version":"Preprint","language":[{"iso":"eng"}],"_id":"3165","date_updated":"2025-09-29T11:45:12Z","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","page":"1386 - 1399","citation":{"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>","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>.","short":"K. Chatterjee, M. Henzinger, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2012, pp. 1386–1399.","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.","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>","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>.","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."},"department":[{"_id":"KrCh"}]},{"title":"Real-time detection of colored objects in multiple camera streams with off-the-shelf hardware components","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","scopus_import":"1","article_processing_charge":"No","year":"2012","intvolume":"         7","author":[{"first_name":"Christoph","last_name":"Lampert","orcid":"0000-0001-8622-7887","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","full_name":"Lampert, Christoph"},{"full_name":"Peters, Jan","first_name":"Jan","last_name":"Peters"}],"article_type":"original","_id":"3248","date_updated":"2025-09-30T07:46:36Z","abstract":[{"lang":"eng","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."}],"citation":{"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>.","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.","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>","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>","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>.","short":"C. Lampert, J. Peters, Journal of Real-Time Image Processing 7 (2012) 31–41."},"page":"31 - 41","department":[{"_id":"ChLa"}],"date_published":"2012-03-01T00:00:00Z","language":[{"iso":"eng"}],"has_accepted_license":"1","oa_version":"Submitted Version","date_created":"2018-12-11T12:02:15Z","type":"journal_article","issue":"1","isi":1,"oa":1,"volume":7,"publication":"Journal of Real-Time Image Processing","publication_status":"published","publisher":"Springer","status":"public","day":"01","publication_identifier":{"issn":["1861-8200"],"eissn":["1861-8219"]},"file":[{"file_id":"5958","date_created":"2019-02-12T10:52:25Z","relation":"main_file","file_size":2933187,"file_name":"2012_Springer_Lampert.pdf","access_level":"open_access","date_updated":"2020-07-14T12:46:04Z","creator":"kschuh","checksum":"241be47ea50e81a283bcf4c45b07e8cc","content_type":"application/pdf"}],"quality_controlled":"1","ddc":["000"],"external_id":{"isi":["000303242600004"]},"month":"03","file_date_updated":"2020-07-14T12:46:04Z","doi":"10.1007/s11554-010-0168-3","publist_id":"3417","corr_author":"1"},{"author":[{"first_name":"Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"intvolume":"      7147","quality_controlled":"1","year":"2012","title":"Cryptography from learning parity with noise","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","status":"public","conference":{"start_date":"2012-01-21","location":"Špindlerův Mlýn, Czech Republic","name":"SOFSEM: Current Trends in Theory and Practice of Computer Science","end_date":"2012-01-27"},"day":"19","scopus_import":1,"volume":7147,"publication_status":"published","alternative_title":["LNCS"],"publisher":"Springer","publist_id":"3407","date_created":"2018-12-11T12:02:15Z","oa_version":"None","corr_author":"1","type":"conference","doi":"10.1007/978-3-642-27660-6_9","_id":"3250","abstract":[{"lang":"eng","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."}],"date_updated":"2024-10-09T20:54:42Z","citation":{"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.","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>","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>.","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>.","short":"K.Z. Pietrzak, in:, Springer, 2012, pp. 99–114."},"department":[{"_id":"KrPi"}],"page":"99 - 114","date_published":"2012-02-19T00:00:00Z","language":[{"iso":"eng"}],"month":"02"},{"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.","external_id":{"arxiv":["1004.2697"]},"quality_controlled":"1","arxiv":1,"status":"public","day":"20","publication_status":"published","publisher":"Springer","volume":7148,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1004.2697"}],"ec_funded":1,"publist_id":"3405","project":[{"call_identifier":"FWF","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"doi":"10.1007/978-3-642-27940-9_11","month":"01","intvolume":"      7148","author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"last_name":"Raman","first_name":"Vishwanath","full_name":"Raman, Vishwanath"}],"article_processing_charge":"No","year":"2012","scopus_import":"1","title":"Synthesizing protocols for digital contract signing","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"name":"VMCAI: Verification, Model Checking and Abstract Interpretation","end_date":"2012-01-24","start_date":"2012-01-22","location":"Philadelphia, PA, USA"},"alternative_title":["LNCS"],"oa":1,"type":"conference","oa_version":"Preprint","date_created":"2018-12-11T12:02:16Z","language":[{"iso":"eng"}],"_id":"3252","abstract":[{"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.","lang":"eng"}],"date_updated":"2025-06-11T08:06:25Z","citation":{"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>","ista":"Chatterjee K, Raman V. 2012. Synthesizing protocols for digital contract signing. VMCAI: Verification, Model Checking and Abstract Interpretation, LNCS, vol. 7148, 152–168.","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>.","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>.","short":"K. Chatterjee, V. Raman, in:, Springer, 2012, pp. 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>"},"date_published":"2012-01-20T00:00:00Z","page":"152 - 168","department":[{"_id":"KrCh"}]},{"doi":"10.1007/978-3-642-27940-9_1","department":[{"_id":"ToHe"}],"citation":{"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>.","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.","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>","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.","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>","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>."},"page":"1 - 22","date_published":"2012-02-26T00:00:00Z","_id":"3253","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"}],"date_updated":"2024-10-21T06:02:58Z","month":"02","language":[{"iso":"eng"}],"date_created":"2018-12-11T12:02:17Z","publist_id":"3404","oa_version":"None","type":"conference","conference":{"name":"VMCAI: Verification, Model Checking and Abstract Interpretation","end_date":"2012-01-24","start_date":"2012-01-22","location":"Philadelphia, PA, USA"},"day":"26","status":"public","title":"Abstract domains for automated reasoning about list manipulating programs with infinite data","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","scopus_import":"1","volume":7148,"publisher":"Springer","alternative_title":["LNCS"],"publication_status":"published","author":[{"first_name":"Ahmed","last_name":"Bouajjani","full_name":"Bouajjani, Ahmed"},{"last_name":"Dragoi","first_name":"Cezara","id":"2B2B5ED0-F248-11E8-B48F-1D18A9856A87","full_name":"Dragoi, Cezara"},{"first_name":"Constantin","last_name":"Enea","full_name":"Enea, Constantin"},{"first_name":"Mihaela","last_name":"Sighireanu","full_name":"Sighireanu, Mihaela"}],"intvolume":"      7148","quality_controlled":"1","acknowledgement":"This work was partly supported by the French National Research Agency (ANR) project Veridyc (ANR-09-SEGI-016).","year":"2012"},{"quality_controlled":"1","acknowledgement":"This work was partially supported by FWF NFN Grant S11407-N23 (RiSE) and a Microsoft faculty fellowship.","ddc":["000"],"status":"public","day":"01","file":[{"file_size":114060,"access_level":"open_access","file_name":"2012_MEMICS_Chatterjee.pdf","creator":"dernst","date_updated":"2020-07-14T12:46:05Z","checksum":"eed2cc1e76b160418c977e76e8899a60","content_type":"application/pdf","file_id":"7863","relation":"main_file","date_created":"2020-05-15T12:53:12Z"}],"volume":7119,"publication_status":"published","publisher":"Springer","publist_id":"3400","file_date_updated":"2020-07-14T12:46:05Z","doi":"10.1007/978-3-642-25929-6_3","project":[{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF"}],"month":"01","author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Doyen","first_name":"Laurent","full_name":"Doyen, Laurent"}],"intvolume":"      7119","article_processing_charge":"No","year":"2012","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Games and Markov decision processes with mean payoff parity and energy parity objectives","conference":{"start_date":"2011-10-14","location":"Lednice, Czech Republic","end_date":"2011-10-16","name":"MEMICS: Mathematical and Engineering Methods in Computer Science"},"scopus_import":1,"alternative_title":["LNCS"],"oa":1,"date_created":"2018-12-11T12:02:17Z","oa_version":"Submitted Version","type":"conference","_id":"3255","date_updated":"2021-01-12T07:42:10Z","abstract":[{"lang":"eng","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."}],"department":[{"_id":"KrCh"}],"page":"37 - 46","date_published":"2012-01-01T00:00:00Z","citation":{"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.","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>","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>.","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.","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."},"language":[{"iso":"eng"}],"has_accepted_license":"1"},{"oa_version":"None","date_created":"2018-12-11T12:02:25Z","type":"conference","date_published":"2012-05-04T00:00:00Z","citation":{"ista":"Jain A, Pietrzak KZ, Tentes A. 2012. Hardness preserving constructions of pseudorandom functions. TCC: Theory of Cryptography Conference, LNCS, vol. 7194, 369–382.","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.","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>","short":"A. Jain, K.Z. Pietrzak, A. Tentes, in:, Springer, 2012, pp. 369–382.","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>.","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>"},"department":[{"_id":"KrPi"}],"page":"369 - 382","abstract":[{"lang":"eng","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"}],"_id":"3279","date_updated":"2021-01-12T07:42:21Z","language":[{"iso":"eng"}],"year":"2012","author":[{"last_name":"Jain","first_name":"Abhishek","full_name":"Jain, Abhishek"},{"orcid":"0000-0002-9139-1654","last_name":"Pietrzak","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z"},{"last_name":"Tentes","first_name":"Aris","full_name":"Tentes, Aris"}],"intvolume":"      7194","alternative_title":["LNCS"],"conference":{"name":"TCC: Theory of Cryptography Conference","end_date":"2012-03-21","start_date":"2012-03-19","location":"Taormina, Sicily, Italy"},"title":"Hardness preserving constructions of pseudorandom functions","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","scopus_import":1,"publist_id":"3367","ec_funded":1,"main_file_link":[{"url":"http://www.iacr.org/archive/tcc2012/tcc2012-index.html"}],"month":"05","doi":"10.1007/978-3-642-28914-9_21","project":[{"name":"Provable Security for Physical Cryptography","grant_number":"259668","call_identifier":"FP7","_id":"258C570E-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","acknowledgement":"Supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013) / ERC Starting Grant (259668-PSPC)","volume":7194,"publisher":"Springer","publication_status":"published","day":"04","status":"public"}]