[{"title":"Amino acid fermentation at the origin of the genetic code","author":[{"full_name":"Vladar, Harold","last_name":"Vladar","id":"2A181218-F248-11E8-B48F-1D18A9856A87","first_name":"Harold","orcid":"0000-0002-5985-7653"}],"isi":1,"ec_funded":1,"publist_id":"3518","type":"journal_article","has_accepted_license":"1","date_published":"2012-02-10T00:00:00Z","ddc":["570","576"],"publication":"Biology Direct","quality_controlled":"1","article_processing_charge":"No","acknowledgement":"The author was supported by the ERC-2009-AdG Grant for project 250152 SELECTIONINFORMATION. ","year":"2012","month":"02","date_updated":"2025-09-30T07:51:20Z","_id":"3166","citation":{"ieee":"H. de Vladar, “Amino acid fermentation at the origin of the genetic code,” Biology Direct, vol. 7. BioMed Central, 2012.","mla":"de Vladar, Harold. “Amino Acid Fermentation at the Origin of the Genetic Code.” Biology Direct, vol. 7, 6, BioMed Central, 2012, doi:10.1186/1745-6150-7-6.","ama":"de Vladar H. Amino acid fermentation at the origin of the genetic code. Biology Direct. 2012;7. doi:10.1186/1745-6150-7-6","ista":"de Vladar H. 2012. Amino acid fermentation at the origin of the genetic code. Biology Direct. 7, 6.","short":"H. de Vladar, Biology Direct 7 (2012).","apa":"de Vladar, H. (2012). Amino acid fermentation at the origin of the genetic code. Biology Direct. BioMed Central. https://doi.org/10.1186/1745-6150-7-6","chicago":"Vladar, Harold de. “Amino Acid Fermentation at the Origin of the Genetic Code.” Biology Direct. BioMed Central, 2012. https://doi.org/10.1186/1745-6150-7-6."},"corr_author":"1","publisher":"BioMed Central","language":[{"iso":"eng"}],"file":[{"access_level":"open_access","date_updated":"2020-07-14T12:46:02Z","content_type":"application/pdf","relation":"main_file","file_id":"5166","creator":"system","file_name":"IST-2012-99-v1+1_1745-6150-7-6.pdf","file_size":4099536,"checksum":"e511e401e239ef608a7fd79b21a06d78","date_created":"2018-12-12T10:15:44Z"}],"oa_version":"Published Version","article_number":"6","abstract":[{"lang":"eng","text":"There is evidence that the genetic code was established prior to the existence of proteins, when metabolism was powered by ribozymes. Also, early proto-organisms had to rely on simple anaerobic bioenergetic processes. In this work I propose that amino acid fermentation powered metabolism in the RNA world, and that this was facilitated by proto-adapters, the precursors of the tRNAs. Amino acids were used as carbon sources rather than as catalytic or structural elements. In modern bacteria, amino acid fermentation is known as the Stickland reaction. This pathway involves two amino acids: the first undergoes oxidative deamination, and the second acts as an electron acceptor through reductive deamination. This redox reaction results in two keto acids that are employed to synthesise ATP via substrate-level phosphorylation. The Stickland reaction is the basic bioenergetic pathway of some bacteria of the genus Clostridium. Two other facts support Stickland fermentation in the RNA world. First, several Stickland amino acid pairs are synthesised in abiotic amino acid synthesis. This suggests that amino acids that could be used as an energy substrate were freely available. Second, anticodons that have complementary sequences often correspond to amino acids that form Stickland pairs. The main hypothesis of this paper is that pairs of complementary proto-adapters were assigned to Stickland amino acids pairs. There are signatures of this hypothesis in the genetic code. Furthermore, it is argued that the proto-adapters formed double strands that brought amino acid pairs into proximity to facilitate their mutual redox reaction, structurally constraining the anticodon pairs that are assigned to these amino acid pairs. Significance tests which randomise the code are performed to study the extent of the variability of the energetic (ATP) yield. Random assignments can lead to a substantial yield of ATP and maintain enough variability, thus selection can act and refine the assignments into a proto-code that optimises the energetic yield. Monte Carlo simulations are performed to evaluate the establishment of these simple proto-codes, based on amino acid substitutions and codon swapping. In all cases, donor amino acids are assigned to anticodons composed of U+G, and have low redundancy (1-2 codons), whereas acceptor amino acids are assigned to the the remaining codons. These bioenergetic and structural constraints allow for a metabolic role for amino acids before their co-option as catalyst cofactors. Reviewers: this article was reviewed by Prof. William Martin, Prof. Eors Szathmary (nominated by Dr. Gaspar Jekely) and Dr. Adam Kun (nominated by Dr. Sandor Pongor)"}],"date_created":"2018-12-11T12:01:46Z","volume":7,"tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"external_id":{"isi":["000305269300001"]},"intvolume":" 7","oa":1,"file_date_updated":"2020-07-14T12:46:02Z","pubrep_id":"99","status":"public","publication_status":"published","day":"10","project":[{"name":"Limits to selection in biology and in evolutionary computation","_id":"25B07788-B435-11E9-9278-68D0E5697425","grant_number":"250152","call_identifier":"FP7"}],"doi":"10.1186/1745-6150-7-6","department":[{"_id":"NiBa"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345"},{"OA_type":"free access","pmid":1,"oa_version":"None","volume":336,"date_created":"2018-12-11T12:01:47Z","article_type":"letter_note","external_id":{"pmid":["22491839"]},"intvolume":" 336","popular_science":"1","issue":"6077","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1126/science.336.6077.32"}],"oa":1,"publication_status":"published","status":"public","doi":"10.1126/science.336.6077.32","department":[{"_id":"MiSi"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"06","publist_id":"3516","title":"NextGen speaks 13 ","author":[{"full_name":"Weber, Michele","last_name":"Weber","id":"3A3FC708-F248-11E8-B48F-1D18A9856A87","first_name":"Michele"}],"date_published":"2012-04-06T00:00:00Z","type":"journal_article","publication":"Science","article_processing_charge":"No","year":"2012","publisher":"American Association for the Advancement of Science","language":[{"iso":"eng"}],"month":"04","_id":"3167","page":"32-34","date_updated":"2025-05-20T07:14:51Z","citation":{"ista":"Weber M. 2012. NextGen speaks 13 . Science. 336(6077), 32–34.","short":"M. Weber, Science 336 (2012) 32–34.","apa":"Weber, M. (2012). NextGen speaks 13 . Science. American Association for the Advancement of Science. https://doi.org/10.1126/science.336.6077.32","ieee":"M. Weber, “NextGen speaks 13 ,” Science, vol. 336, no. 6077. American Association for the Advancement of Science, pp. 32–34, 2012.","mla":"Weber, Michele. “NextGen Speaks 13 .” Science, vol. 336, no. 6077, American Association for the Advancement of Science, 2012, pp. 32–34, doi:10.1126/science.336.6077.32.","ama":"Weber M. NextGen speaks 13 . Science. 2012;336(6077):32-34. doi:10.1126/science.336.6077.32","chicago":"Weber, Michele. “NextGen Speaks 13 .” Science. American Association for the Advancement of Science, 2012. https://doi.org/10.1126/science.336.6077.32."}},{"acknowledgement":"Funding for this project was obtained by the German Research Foundation DFG (http://www.dfg.de/en/index.jsp) as an Individual Research Grant (CR118/2-1 to SC) and the European Research Council (http://erc.europa.eu/) in form of two ERC Starting Grants (ERC-2009-StG240371-SocialVaccines to SC and ERC-2010-StG259294-LatentCauses to FJT). In addition, the Junge Akademie (Young Academy of the Berlin-Brandenburg Academy of Sciences and Humanities and the National Academy of Sciences Leopoldina (http://www.diejungeakademie.de/english/i​ndex.html) funded this joint Antnet project of SC and FJT. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.","year":"2012","publisher":"Public Library of Science","corr_author":"1","language":[{"iso":"eng"}],"month":"04","_id":"3242","citation":{"ieee":"M. Konrad et al., “Social transfer of pathogenic fungus promotes active immunisation in ant colonies,” PLoS Biology, vol. 10, no. 4. Public Library of Science, 2012.","ama":"Konrad M, Vyleta M, Theis F, et al. Social transfer of pathogenic fungus promotes active immunisation in ant colonies. PLoS Biology. 2012;10(4). doi:10.1371/journal.pbio.1001300","mla":"Konrad, Matthias, et al. “Social Transfer of Pathogenic Fungus Promotes Active Immunisation in Ant Colonies.” PLoS Biology, vol. 10, no. 4, e1001300, Public Library of Science, 2012, doi:10.1371/journal.pbio.1001300.","ista":"Konrad M, Vyleta M, Theis F, Stock M, Tragust S, Klatt M, Drescher V, Marr C, Ugelvig LV, Cremer S. 2012. Social transfer of pathogenic fungus promotes active immunisation in ant colonies. PLoS Biology. 10(4), e1001300.","short":"M. Konrad, M. Vyleta, F. Theis, M. Stock, S. Tragust, M. Klatt, V. Drescher, C. Marr, L.V. Ugelvig, S. Cremer, PLoS Biology 10 (2012).","apa":"Konrad, M., Vyleta, M., Theis, F., Stock, M., Tragust, S., Klatt, M., … Cremer, S. (2012). Social transfer of pathogenic fungus promotes active immunisation in ant colonies. PLoS Biology. Public Library of Science. https://doi.org/10.1371/journal.pbio.1001300","chicago":"Konrad, Matthias, Meghan Vyleta, Fabian Theis, Miriam Stock, Simon Tragust, Martina Klatt, Verena Drescher, Carsten Marr, Line V Ugelvig, and Sylvia Cremer. “Social Transfer of Pathogenic Fungus Promotes Active Immunisation in Ant Colonies.” PLoS Biology. Public Library of Science, 2012. https://doi.org/10.1371/journal.pbio.1001300."},"date_updated":"2025-09-30T07:50:01Z","file":[{"file_name":"IST-2012-96-v1+1_journal.pbio.1001300.pdf","file_size":674228,"checksum":"4ebacefd9fbab5c68adf829124115fd1","date_created":"2018-12-12T10:08:28Z","file_id":"4689","creator":"system","content_type":"application/pdf","relation":"main_file","date_updated":"2020-07-14T12:46:04Z","access_level":"open_access"}],"isi":1,"ec_funded":1,"publist_id":"3434","title":"Social transfer of pathogenic fungus promotes active immunisation in ant colonies","author":[{"full_name":"Konrad, Matthias","id":"46528076-F248-11E8-B48F-1D18A9856A87","first_name":"Matthias","last_name":"Konrad"},{"first_name":"Meghan","id":"418901AA-F248-11E8-B48F-1D18A9856A87","last_name":"Vyleta","full_name":"Vyleta, Meghan"},{"full_name":"Theis, Fabian","last_name":"Theis","first_name":"Fabian"},{"full_name":"Stock, Miriam","last_name":"Stock","id":"42462816-F248-11E8-B48F-1D18A9856A87","first_name":"Miriam"},{"full_name":"Tragust, Simon","id":"35A7A418-F248-11E8-B48F-1D18A9856A87","first_name":"Simon","last_name":"Tragust"},{"first_name":"Martina","id":"E60F29C6-E9AE-11E9-AF6E-D190C7302F38","last_name":"Klatt","full_name":"Klatt, Martina"},{"full_name":"Drescher, Verena","last_name":"Drescher","first_name":"Verena"},{"last_name":"Marr","first_name":"Carsten","full_name":"Marr, Carsten"},{"last_name":"Ugelvig","id":"3DC97C8E-F248-11E8-B48F-1D18A9856A87","first_name":"Line V","full_name":"Ugelvig, Line V","orcid":"0000-0003-1832-8883"},{"id":"2F64EC8C-F248-11E8-B48F-1D18A9856A87","first_name":"Sylvia","last_name":"Cremer","full_name":"Cremer, Sylvia","orcid":"0000-0002-2193-3868"}],"date_published":"2012-04-03T00:00:00Z","has_accepted_license":"1","type":"journal_article","publication":"PLoS Biology","ddc":["570","579"],"article_processing_charge":"No","quality_controlled":"1","issue":"4","pubrep_id":"96","oa":1,"file_date_updated":"2020-07-14T12:46:04Z","publication_status":"published","status":"public","doi":"10.1371/journal.pbio.1001300","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","department":[{"_id":"SyCr"}],"project":[{"name":"Host-Parasite Coevolution","grant_number":"CR-118/3-1","_id":"25DAF0B2-B435-11E9-9278-68D0E5697425"},{"_id":"25DC711C-B435-11E9-9278-68D0E5697425","grant_number":"243071","call_identifier":"FP7","name":"Social Vaccination in Ant Colonies: from Individual Mechanisms to Society Effects"},{"name":"Schnellboot Antnet Junge Akademie","_id":"25E0E184-B435-11E9-9278-68D0E5697425"}],"day":"03","oa_version":"Published Version","volume":10,"date_created":"2018-12-11T12:02:13Z","related_material":{"record":[{"relation":"research_data","id":"9755","status":"public"}]},"article_number":"e1001300","abstract":[{"lang":"eng","text":"Due to the omnipresent risk of epidemics, insect societies have evolved sophisticated disease defences at the individual and colony level. An intriguing yet little understood phenomenon is that social contact to pathogen-exposed individuals reduces susceptibility of previously naive nestmates to this pathogen. We tested whether such social immunisation in Lasius ants against the entomopathogenic fungus Metarhizium anisopliae is based on active upregulation of the immune system of nestmates following contact to an infectious individual or passive protection via transfer of immune effectors among group members—that is, active versus passive immunisation. We found no evidence for involvement of passive immunisation via transfer of antimicrobials among colony members. Instead, intensive allogrooming behaviour between naive and pathogen-exposed ants before fungal conidia firmly attached to their cuticle suggested passage of the pathogen from the exposed individuals to their nestmates. By tracing fluorescence-labelled conidia we indeed detected frequent pathogen transfer to the nestmates, where they caused low-level infections as revealed by growth of small numbers of fungal colony forming units from their dissected body content. These infections rarely led to death, but instead promoted an enhanced ability to inhibit fungal growth and an active upregulation of immune genes involved in antifungal defences (defensin and prophenoloxidase, PPO). Contrarily, there was no upregulation of the gene cathepsin L, which is associated with antibacterial and antiviral defences, and we found no increased antibacterial activity of nestmates of fungus-exposed ants. This indicates that social immunisation after fungal exposure is specific, similar to recent findings for individual-level immune priming in invertebrates. Epidemiological modeling further suggests that active social immunisation is adaptive, as it leads to faster elimination of the disease and lower death rates than passive immunisation. Interestingly, humans have also utilised the protective effect of low-level infections to fight smallpox by intentional transfer of low pathogen doses (“variolation” or “inoculation”)."}],"scopus_import":"1","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"external_id":{"isi":["000303541800006"]},"intvolume":" 10"},{"oa_version":"None","abstract":[{"lang":"eng","text":"How cells orchestrate their behavior during collective migration is a long-standing question. Using magnetic tweezers to apply mechanical stimuli to Xenopus mesendoderm cells, Weber etal. (2012) now reveal, in this issue of Developmental Cell, a cadherin-mediated mechanosensitive response that promotes cell polarization and movement persistence during the collective mesendoderm migration in gastrulation."}],"volume":22,"date_created":"2018-12-11T12:02:14Z","external_id":{"isi":["000299365800002"]},"scopus_import":"1","intvolume":" 22","issue":"1","status":"public","publication_status":"published","day":"17","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","department":[{"_id":"CaHe"}],"doi":"10.1016/j.devcel.2011.12.018","author":[{"last_name":"Behrndt","first_name":"Martin","id":"3ECECA3A-F248-11E8-B48F-1D18A9856A87","full_name":"Behrndt, Martin"},{"orcid":"0000-0002-0912-4566","first_name":"Carl-Philipp J","id":"39427864-F248-11E8-B48F-1D18A9856A87","last_name":"Heisenberg","full_name":"Heisenberg, Carl-Philipp J"}],"title":"Spurred by resistance mechanosensation in collective migration","publist_id":"3426","isi":1,"type":"journal_article","date_published":"2012-01-17T00:00:00Z","publication":"Developmental Cell","quality_controlled":"1","article_processing_charge":"No","year":"2012","citation":{"ieee":"M. Behrndt and C.-P. J. Heisenberg, “Spurred by resistance mechanosensation in collective migration,” Developmental Cell, vol. 22, no. 1. Cell Press, pp. 3–4, 2012.","mla":"Behrndt, Martin, and Carl-Philipp J. Heisenberg. “Spurred by Resistance Mechanosensation in Collective Migration.” Developmental Cell, vol. 22, no. 1, Cell Press, 2012, pp. 3–4, doi:10.1016/j.devcel.2011.12.018.","ama":"Behrndt M, Heisenberg C-PJ. Spurred by resistance mechanosensation in collective migration. Developmental Cell. 2012;22(1):3-4. doi:10.1016/j.devcel.2011.12.018","ista":"Behrndt M, Heisenberg C-PJ. 2012. Spurred by resistance mechanosensation in collective migration. Developmental Cell. 22(1), 3–4.","apa":"Behrndt, M., & Heisenberg, C.-P. J. (2012). Spurred by resistance mechanosensation in collective migration. Developmental Cell. Cell Press. https://doi.org/10.1016/j.devcel.2011.12.018","short":"M. Behrndt, C.-P.J. Heisenberg, Developmental Cell 22 (2012) 3–4.","chicago":"Behrndt, Martin, and Carl-Philipp J Heisenberg. “Spurred by Resistance Mechanosensation in Collective Migration.” Developmental Cell. Cell Press, 2012. https://doi.org/10.1016/j.devcel.2011.12.018."},"_id":"3245","page":"3 - 4","date_updated":"2025-09-30T07:48:41Z","month":"01","language":[{"iso":"eng"}],"publisher":"Cell Press","corr_author":"1"},{"article_processing_charge":"No","quality_controlled":"1","publication":"Conservation Genetics","date_published":"2012-02-01T00:00:00Z","type":"journal_article","isi":1,"publist_id":"3420","title":"Remaining genetic diversity in Brazilian Merganser (Mergus octosetaceus)","author":[{"first_name":"Sibelle","last_name":"Vilaça","full_name":"Vilaça, Sibelle"},{"full_name":"Fernandes Redondo, Rodrigo A","last_name":"Fernandes Redondo","id":"409D5C96-F248-11E8-B48F-1D18A9856A87","first_name":"Rodrigo A","orcid":"0000-0002-5837-2793"},{"last_name":"Lins","first_name":"Lívia","full_name":"Lins, Lívia"},{"full_name":"Santos, Fabrício","last_name":"Santos","first_name":"Fabrício"}],"publisher":"Springer","language":[{"iso":"eng"}],"month":"02","page":"293 - 298","_id":"3247","date_updated":"2025-09-30T07:47:07Z","citation":{"chicago":"Vilaça, Sibelle, Rodrigo A Fernandes Redondo, Lívia Lins, and Fabrício Santos. “Remaining Genetic Diversity in Brazilian Merganser (Mergus Octosetaceus).” Conservation Genetics. Springer, 2012. https://doi.org/10.1007/s10592-011-0262-5.","apa":"Vilaça, S., Fernandes Redondo, R. A., Lins, L., & Santos, F. (2012). Remaining genetic diversity in Brazilian Merganser (Mergus octosetaceus). Conservation Genetics. Springer. https://doi.org/10.1007/s10592-011-0262-5","short":"S. Vilaça, R.A. Fernandes Redondo, L. Lins, F. Santos, Conservation Genetics 13 (2012) 293–298.","ista":"Vilaça S, Fernandes Redondo RA, Lins L, Santos F. 2012. Remaining genetic diversity in Brazilian Merganser (Mergus octosetaceus). Conservation Genetics. 13(1), 293–298.","ama":"Vilaça S, Fernandes Redondo RA, Lins L, Santos F. Remaining genetic diversity in Brazilian Merganser (Mergus octosetaceus). Conservation Genetics. 2012;13(1):293-298. doi:10.1007/s10592-011-0262-5","mla":"Vilaça, Sibelle, et al. “Remaining Genetic Diversity in Brazilian Merganser (Mergus Octosetaceus).” Conservation Genetics, vol. 13, no. 1, Springer, 2012, pp. 293–98, doi:10.1007/s10592-011-0262-5.","ieee":"S. Vilaça, R. A. Fernandes Redondo, L. Lins, and F. Santos, “Remaining genetic diversity in Brazilian Merganser (Mergus octosetaceus),” Conservation Genetics, vol. 13, no. 1. Springer, pp. 293–298, 2012."},"year":"2012","acknowledgement":"The present study received grants from FAPEMIG, CNPq, Petrobras Ambiental and Fundação O Boticário de Conservação da Natureza, and followed all ethical guidelines and legal requirements of Brazil for sampling and studying an endangered species.\r\nWe thank the Specialist Work Group for the Conservation of Brazilian Merganser for valuable discussions and opinions on this manuscript. We also thank all the staff from Instituto Terra Brasilis and Funatura (Vivian S. Braz and Gislaine Disconzi) for collecting the samples at Serra da Canastra and Chapada dos Veadeiros, respectively; Dario A. Lijtmaerand and Pablo Tubaro for providing the samples from Argentina, Bradley C. Livezey for sending copies of his papers, and Geoff M. Hilton and Paulo de Tarso Z. Antas for useful suggestions that greatly improved this manuscript.","intvolume":" 13","scopus_import":"1","external_id":{"isi":["000303475800024"]},"date_created":"2018-12-11T12:02:15Z","volume":13,"abstract":[{"text":"The Brazilian Merganser is a very rare and threatened species that nowadays inhabits only a few protected areas and their surroundings in the Brazilian territory. In order to estimate the remaining genetic diversity and population structure in this species, two mitochondrial genes were sequenced in 39 individuals belonging to two populations and in one individual collected in Argentina in 1950. We found a highly significant divergence between two major remaining populations of Mergus octosetaceus, which suggests a historical population structure in this species. Furthermore, two deeply divergent lineages were found in a single location, which could due to current or historical secondary contact. Based on the available genetic data, we point out future directions which would contribute to design strategies for conservation and management of this threatened species.","lang":"eng"}],"oa_version":"None","doi":"10.1007/s10592-011-0262-5","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","department":[{"_id":"JoBo"}],"day":"01","publication_status":"published","status":"public","issue":"1"},{"status":"public","publication_status":"published","day":"01","doi":"10.1007/s11554-010-0168-3","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","department":[{"_id":"ChLa"}],"issue":"1","oa":1,"file_date_updated":"2020-07-14T12:46:04Z","external_id":{"isi":["000303242600004"]},"scopus_import":"1","intvolume":" 7","oa_version":"Submitted Version","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."}],"volume":7,"date_created":"2018-12-11T12:02:15Z","article_type":"original","month":"03","_id":"3248","date_updated":"2025-09-30T07:46:36Z","citation":{"chicago":"Lampert, Christoph, and Jan Peters. “Real-Time Detection of Colored Objects in Multiple Camera Streams with off-the-Shelf Hardware Components.” Journal of Real-Time Image Processing. Springer, 2012. https://doi.org/10.1007/s11554-010-0168-3.","ieee":"C. Lampert and J. Peters, “Real-time detection of colored objects in multiple camera streams with off-the-shelf hardware components,” Journal of Real-Time Image Processing, vol. 7, no. 1. Springer, pp. 31–41, 2012.","mla":"Lampert, Christoph, and Jan Peters. “Real-Time Detection of Colored Objects in Multiple Camera Streams with off-the-Shelf Hardware Components.” Journal of Real-Time Image Processing, vol. 7, no. 1, Springer, 2012, pp. 31–41, doi:10.1007/s11554-010-0168-3.","ama":"Lampert C, Peters J. Real-time detection of colored objects in multiple camera streams with off-the-shelf hardware components. Journal of Real-Time Image Processing. 2012;7(1):31-41. doi:10.1007/s11554-010-0168-3","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.","short":"C. Lampert, J. Peters, Journal of Real-Time Image Processing 7 (2012) 31–41.","apa":"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. Springer. https://doi.org/10.1007/s11554-010-0168-3"},"page":"31 - 41","corr_author":"1","publisher":"Springer","language":[{"iso":"eng"}],"file":[{"date_created":"2019-02-12T10:52:25Z","checksum":"241be47ea50e81a283bcf4c45b07e8cc","file_size":2933187,"file_name":"2012_Springer_Lampert.pdf","creator":"kschuh","file_id":"5958","relation":"main_file","content_type":"application/pdf","date_updated":"2020-07-14T12:46:04Z","access_level":"open_access"}],"year":"2012","ddc":["000"],"publication":"Journal of Real-Time Image Processing","publication_identifier":{"issn":["1861-8200"],"eissn":["1861-8219"]},"quality_controlled":"1","article_processing_charge":"No","title":"Real-time detection of colored objects in multiple camera streams with off-the-shelf hardware components","author":[{"full_name":"Lampert, Christoph","first_name":"Christoph","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","last_name":"Lampert","orcid":"0000-0001-8622-7887"},{"last_name":"Peters","first_name":"Jan","full_name":"Peters, Jan"}],"isi":1,"publist_id":"3417","has_accepted_license":"1","type":"journal_article","date_published":"2012-03-01T00:00:00Z"},{"publist_id":"3407","title":"Cryptography from learning parity with noise","alternative_title":["LNCS"],"oa_version":"None","author":[{"orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"date_created":"2018-12-11T12:02:15Z","volume":7147,"date_published":"2012-02-19T00:00:00Z","type":"conference","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 "provably secure" 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."}],"scopus_import":1,"quality_controlled":"1","intvolume":" 7147","conference":{"start_date":"2012-01-21","location":"Špindlerův Mlýn, Czech Republic","end_date":"2012-01-27","name":"SOFSEM: Current Trends in Theory and Practice of Computer Science"},"year":"2012","corr_author":"1","publisher":"Springer","language":[{"iso":"eng"}],"publication_status":"published","month":"02","_id":"3250","citation":{"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. https://doi.org/10.1007/978-3-642-27660-6_9","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.","ama":"Pietrzak KZ. Cryptography from learning parity with noise. In: Vol 7147. Springer; 2012:99-114. doi:10.1007/978-3-642-27660-6_9","mla":"Pietrzak, Krzysztof Z. Cryptography from Learning Parity with Noise. Vol. 7147, Springer, 2012, pp. 99–114, doi:10.1007/978-3-642-27660-6_9.","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. https://doi.org/10.1007/978-3-642-27660-6_9."},"status":"public","page":"99 - 114","date_updated":"2024-10-09T20:54:42Z","doi":"10.1007/978-3-642-27660-6_9","department":[{"_id":"KrPi"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","day":"19"},{"doi":"10.1007/978-3-642-27940-9_11","department":[{"_id":"KrCh"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"call_identifier":"FWF","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering"},{"name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","call_identifier":"FP7"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"day":"20","publication_status":"published","status":"public","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1004.2697"}],"oa":1,"intvolume":" 7148","scopus_import":"1","external_id":{"arxiv":["1004.2697"]},"date_created":"2018-12-11T12:02:16Z","volume":7148,"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"}],"oa_version":"Preprint","publisher":"Springer","language":[{"iso":"eng"}],"month":"01","_id":"3252","date_updated":"2025-06-11T08:06:25Z","citation":{"ama":"Chatterjee K, Raman V. Synthesizing protocols for digital contract signing. In: Vol 7148. Springer; 2012:152-168. doi:10.1007/978-3-642-27940-9_11","mla":"Chatterjee, Krishnendu, and Vishwanath Raman. Synthesizing Protocols for Digital Contract Signing. Vol. 7148, Springer, 2012, pp. 152–68, doi:10.1007/978-3-642-27940-9_11.","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.","apa":"Chatterjee, K., & 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. https://doi.org/10.1007/978-3-642-27940-9_11","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.","chicago":"Chatterjee, Krishnendu, and Vishwanath Raman. “Synthesizing Protocols for Digital Contract Signing,” 7148:152–68. Springer, 2012. https://doi.org/10.1007/978-3-642-27940-9_11."},"page":"152 - 168","conference":{"start_date":"2012-01-22","location":"Philadelphia, PA, USA","end_date":"2012-01-24","name":"VMCAI: Verification, Model Checking and Abstract Interpretation"},"year":"2012","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.","article_processing_charge":"No","quality_controlled":"1","date_published":"2012-01-20T00:00:00Z","type":"conference","arxiv":1,"ec_funded":1,"publist_id":"3405","title":"Synthesizing protocols for digital contract signing","alternative_title":["LNCS"],"author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"first_name":"Vishwanath","last_name":"Raman","full_name":"Raman, Vishwanath"}]},{"volume":7148,"date_published":"2012-02-26T00:00:00Z","date_created":"2018-12-11T12:02:17Z","type":"conference","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"}],"publist_id":"3404","alternative_title":["LNCS"],"title":"Abstract domains for automated reasoning about list manipulating programs with infinite data","oa_version":"None","author":[{"full_name":"Bouajjani, Ahmed","last_name":"Bouajjani","first_name":"Ahmed"},{"full_name":"Dragoi, Cezara","id":"2B2B5ED0-F248-11E8-B48F-1D18A9856A87","first_name":"Cezara","last_name":"Dragoi"},{"last_name":"Enea","first_name":"Constantin","full_name":"Enea, Constantin"},{"last_name":"Sighireanu","first_name":"Mihaela","full_name":"Sighireanu, Mihaela"}],"quality_controlled":"1","intvolume":" 7148","scopus_import":"1","conference":{"location":"Philadelphia, PA, USA","start_date":"2012-01-22","end_date":"2012-01-24","name":"VMCAI: Verification, Model Checking and Abstract Interpretation"},"year":"2012","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","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"ToHe"}],"day":"26","publisher":"Springer","publication_status":"published","language":[{"iso":"eng"}],"month":"02","status":"public","_id":"3253","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. https://doi.org/10.1007/978-3-642-27940-9_1.","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.","apa":"Bouajjani, A., Dragoi, C., Enea, C., & 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. https://doi.org/10.1007/978-3-642-27940-9_1","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.","mla":"Bouajjani, Ahmed, et al. Abstract Domains for Automated Reasoning about List Manipulating Programs with Infinite Data. Vol. 7148, Springer, 2012, pp. 1–22, doi:10.1007/978-3-642-27940-9_1.","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:10.1007/978-3-642-27940-9_1"},"date_updated":"2024-10-21T06:02:58Z","page":"1 - 22"},{"publication_status":"published","status":"public","doi":"10.1016/j.ic.2011.11.004","department":[{"_id":"KrCh"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","call_identifier":"FWF"},{"name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"day":"01","main_file_link":[{"url":"http://arise.or.at/pubpdf/The_complexity_of_stochastic_M___u_ller_games.pdf"}],"scopus_import":"1","external_id":{"isi":["000300468000002"]},"intvolume":" 211","oa_version":"None","date_created":"2018-12-11T12:02:17Z","volume":211,"abstract":[{"lang":"eng","text":"The theory of graph games with ω-regular winning conditions is the foundation for modeling and synthesizing reactive processes. In the case of stochastic reactive processes, the corresponding stochastic graph games have three players, two of them (System and Environment) behaving adversarially, and the third (Uncertainty) behaving probabilistically. We consider two problems for stochastic graph games: the qualitative problem asks for the set of states from which a player can win with probability 1 (almost-sure winning); and the quantitative problem asks for the maximal probability of winning (optimal winning) from each state. We consider ω-regular winning conditions formalized as Müller winning conditions. We present optimal memory bounds for pure (deterministic) almost-sure winning and optimal winning strategies in stochastic graph games with Müller winning conditions. We also study the complexity of stochastic Müller games and show that both the qualitative and quantitative analysis problems are PSPACE-complete. Our results are relevant in synthesis of stochastic reactive processes."}],"publisher":"Elsevier","corr_author":"1","language":[{"iso":"eng"}],"month":"02","citation":{"chicago":"Chatterjee, Krishnendu. “The Complexity of Stochastic Müller Games.” Information and Computation. Elsevier, 2012. https://doi.org/10.1016/j.ic.2011.11.004.","ieee":"K. Chatterjee, “The complexity of stochastic Müller games,” Information and Computation, vol. 211. Elsevier, pp. 29–48, 2012.","mla":"Chatterjee, Krishnendu. “The Complexity of Stochastic Müller Games.” Information and Computation, vol. 211, Elsevier, 2012, pp. 29–48, doi:10.1016/j.ic.2011.11.004.","ama":"Chatterjee K. The complexity of stochastic Müller games. Information and Computation. 2012;211:29-48. doi:10.1016/j.ic.2011.11.004","ista":"Chatterjee K. 2012. The complexity of stochastic Müller games. Information and Computation. 211, 29–48.","short":"K. Chatterjee, Information and Computation 211 (2012) 29–48.","apa":"Chatterjee, K. (2012). The complexity of stochastic Müller games. Information and Computation. Elsevier. https://doi.org/10.1016/j.ic.2011.11.004"},"_id":"3254","page":"29 - 48","date_updated":"2025-09-30T07:45:01Z","acknowledgement":"The research was supported by Austrian Science Fund (FWF) Grant No. P 23499-N23, FWF NFN Grant No. S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.","year":"2012","publication":"Information and Computation","article_processing_charge":"No","quality_controlled":"1","isi":1,"ec_funded":1,"publist_id":"3403","title":"The complexity of stochastic Müller games","author":[{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee"}],"date_published":"2012-02-01T00:00:00Z","type":"journal_article"},{"quality_controlled":"1","article_processing_charge":"No","ddc":["000"],"has_accepted_license":"1","type":"conference","date_published":"2012-01-01T00:00:00Z","author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Doyen, Laurent","last_name":"Doyen","first_name":"Laurent"}],"alternative_title":["LNCS"],"title":"Games and Markov decision processes with mean payoff parity and energy parity objectives","publist_id":"3400","file":[{"date_updated":"2020-07-14T12:46:05Z","access_level":"open_access","content_type":"application/pdf","relation":"main_file","file_id":"7863","creator":"dernst","file_name":"2012_MEMICS_Chatterjee.pdf","file_size":114060,"checksum":"eed2cc1e76b160418c977e76e8899a60","date_created":"2020-05-15T12:53:12Z"}],"_id":"3255","page":"37 - 46","date_updated":"2021-01-12T07:42:10Z","citation":{"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., & 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. https://doi.org/10.1007/978-3-642-25929-6_3","short":"K. Chatterjee, L. Doyen, in:, Springer, 2012, pp. 37–46.","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:10.1007/978-3-642-25929-6_3","mla":"Chatterjee, Krishnendu, and Laurent Doyen. Games and Markov Decision Processes with Mean Payoff Parity and Energy Parity Objectives. Vol. 7119, Springer, 2012, pp. 37–46, doi:10.1007/978-3-642-25929-6_3.","chicago":"Chatterjee, Krishnendu, and Laurent Doyen. “Games and Markov Decision Processes with Mean Payoff Parity and Energy Parity Objectives,” 7119:37–46. Springer, 2012. https://doi.org/10.1007/978-3-642-25929-6_3."},"month":"01","language":[{"iso":"eng"}],"publisher":"Springer","year":"2012","conference":{"end_date":"2011-10-16","location":"Lednice, Czech Republic","start_date":"2011-10-14","name":"MEMICS: Mathematical and Engineering Methods in Computer Science"},"acknowledgement":"This work was partially supported by FWF NFN Grant S11407-N23 (RiSE) and a Microsoft faculty fellowship.","intvolume":" 7119","scopus_import":1,"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."}],"volume":7119,"date_created":"2018-12-11T12:02:17Z","oa_version":"Submitted Version","day":"01","project":[{"grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Rigorous Systems Engineering"}],"department":[{"_id":"KrCh"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","doi":"10.1007/978-3-642-25929-6_3","status":"public","publication_status":"published","oa":1,"file_date_updated":"2020-07-14T12:46:05Z"},{"issue":"2","pubrep_id":"543","oa":1,"file_date_updated":"2020-07-14T12:46:05Z","publication_status":"published","status":"public","department":[{"_id":"HeEd"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","doi":"10.1007/s00454-011-9382-4","day":"01","oa_version":"Submitted Version","date_created":"2018-12-11T12:02:17Z","volume":47,"abstract":[{"text":"We use a distortion to define the dual complex of a cubical subdivision of ℝ n as an n-dimensional subcomplex of the nerve of the set of n-cubes. Motivated by the topological analysis of high-dimensional digital image data, we consider such subdivisions defined by generalizations of quad- and oct-trees to n dimensions. Assuming the subdivision is balanced, we show that mapping each vertex to the center of the corresponding n-cube gives a geometric realization of the dual complex in ℝ n.","lang":"eng"}],"scopus_import":"1","external_id":{"isi":["000299057200010"]},"intvolume":" 47","acknowledgement":"This research is partially supported by the Defense Advanced Research Projects Agency (DARPA) under grants HR0011-05-1-0057 and HR0011-09-0065 as well as the National Science Foundation (NSF) under grant DBI-0820624.","year":"2012","language":[{"iso":"eng"}],"publisher":"Springer","corr_author":"1","citation":{"chicago":"Edelsbrunner, Herbert, and Michael Kerber. “Dual Complexes of Cubical Subdivisions of ℝn.” Discrete & Computational Geometry. Springer, 2012. https://doi.org/10.1007/s00454-011-9382-4.","ista":"Edelsbrunner H, Kerber M. 2012. Dual complexes of cubical subdivisions of ℝn. Discrete & Computational Geometry. 47(2), 393–414.","short":"H. Edelsbrunner, M. Kerber, Discrete & Computational Geometry 47 (2012) 393–414.","apa":"Edelsbrunner, H., & Kerber, M. (2012). Dual complexes of cubical subdivisions of ℝn. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-011-9382-4","ieee":"H. Edelsbrunner and M. Kerber, “Dual complexes of cubical subdivisions of ℝn,” Discrete & Computational Geometry, vol. 47, no. 2. Springer, pp. 393–414, 2012.","mla":"Edelsbrunner, Herbert, and Michael Kerber. “Dual Complexes of Cubical Subdivisions of ℝn.” Discrete & Computational Geometry, vol. 47, no. 2, Springer, 2012, pp. 393–414, doi:10.1007/s00454-011-9382-4.","ama":"Edelsbrunner H, Kerber M. Dual complexes of cubical subdivisions of ℝn. Discrete & Computational Geometry. 2012;47(2):393-414. doi:10.1007/s00454-011-9382-4"},"_id":"3256","date_updated":"2025-09-30T07:43:46Z","page":"393 - 414","month":"03","file":[{"creator":"system","file_id":"4675","checksum":"76486f3b2c9e7fd81342f3832ca387e7","file_size":203636,"date_created":"2018-12-12T10:08:15Z","file_name":"IST-2016-543-v1+1_2012-J-08-HierarchyCubeComplex.pdf","date_updated":"2020-07-14T12:46:05Z","access_level":"open_access","relation":"main_file","content_type":"application/pdf"}],"publist_id":"3398","isi":1,"author":[{"full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833"},{"full_name":"Kerber, Michael","last_name":"Kerber","first_name":"Michael","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8030-9299"}],"title":"Dual complexes of cubical subdivisions of ℝn","date_published":"2012-03-01T00:00:00Z","has_accepted_license":"1","type":"journal_article","publication":"Discrete & Computational Geometry","ddc":["000"],"article_processing_charge":"No","quality_controlled":"1"},{"publication":"Discrete Applied Mathematics","article_processing_charge":"No","quality_controlled":"1","isi":1,"arxiv":1,"publist_id":"3397","title":"Generalized roof duality and bisubmodular functions","author":[{"full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","last_name":"Kolmogorov"}],"date_published":"2012-03-01T00:00:00Z","type":"journal_article","corr_author":"1","publisher":"Elsevier","language":[{"iso":"eng"}],"month":"03","citation":{"chicago":"Kolmogorov, Vladimir. “Generalized Roof Duality and Bisubmodular Functions.” Discrete Applied Mathematics. Elsevier, 2012. https://doi.org/10.1016/j.dam.2011.10.026.","apa":"Kolmogorov, V. (2012). Generalized roof duality and bisubmodular functions. Discrete Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2011.10.026","short":"V. Kolmogorov, Discrete Applied Mathematics 160 (2012) 416–426.","ista":"Kolmogorov V. 2012. Generalized roof duality and bisubmodular functions. Discrete Applied Mathematics. 160(4–5), 416–426.","mla":"Kolmogorov, Vladimir. “Generalized Roof Duality and Bisubmodular Functions.” Discrete Applied Mathematics, vol. 160, no. 4–5, Elsevier, 2012, pp. 416–26, doi:10.1016/j.dam.2011.10.026.","ama":"Kolmogorov V. Generalized roof duality and bisubmodular functions. Discrete Applied Mathematics. 2012;160(4-5):416-426. doi:10.1016/j.dam.2011.10.026","ieee":"V. Kolmogorov, “Generalized roof duality and bisubmodular functions,” Discrete Applied Mathematics, vol. 160, no. 4–5. Elsevier, pp. 416–426, 2012."},"_id":"3257","page":"416 - 426","date_updated":"2025-09-30T07:43:17Z","year":"2012","scopus_import":"1","external_id":{"arxiv":["1005.2305"],"isi":["000301211100006"]},"intvolume":" 160","oa_version":"Preprint","date_created":"2018-12-11T12:02:18Z","volume":160,"related_material":{"record":[{"relation":"earlier_version","id":"2934","status":"public"}]},"abstract":[{"text":"Consider a convex relaxation f̂ of a pseudo-Boolean function f. We say that the relaxation is totally half-integral if f̂(x) is a polyhedral function with half-integral extreme points x, and this property is preserved after adding an arbitrary combination of constraints of the form x i=x j, x i=1-x j, and x i=γ where γ∈{0,1,1/2} is a constant. A well-known example is the roof duality relaxation for quadratic pseudo-Boolean functions f. We argue that total half-integrality is a natural requirement for generalizations of roof duality to arbitrary pseudo-Boolean functions. Our contributions are as follows. First, we provide a complete characterization of totally half-integral relaxations f̂ by establishing a one-to-one correspondence with bisubmodular functions. Second, we give a new characterization of bisubmodular functions. Finally, we show some relationships between general totally half-integral relaxations and relaxations based on the roof duality. On the conceptual level, our results show that bisubmodular functions provide a natural generalization of the roof duality approach to higher-order terms. This can be viewed as a non-submodular analogue of the fact that submodular functions generalize the s-t minimum cut problem with non-negative weights to higher-order terms.","lang":"eng"}],"publication_status":"published","status":"public","doi":"10.1016/j.dam.2011.10.026","department":[{"_id":"VlKo"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","day":"01","issue":"4-5","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1005.2305"}],"oa":1},{"article_processing_charge":"No","quality_controlled":"1","publication":" Physical Review E statistical nonlinear and soft matter physics ","date_published":"2012-04-01T00:00:00Z","type":"journal_article","publist_id":"3386","arxiv":1,"isi":1,"author":[{"full_name":"Tkacik, Gasper","last_name":"Tkacik","first_name":"Gasper","id":"3D494DCA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6699-1455"},{"full_name":"Walczak, Aleksandra","first_name":"Aleksandra","last_name":"Walczak"},{"last_name":"Bialek","first_name":"William","full_name":"Bialek, William"}],"title":"Optimizing information flow in small genetic networks. III. A self-interacting gene","language":[{"iso":"eng"}],"corr_author":"1","publisher":"American Institute of Physics","date_updated":"2025-09-30T07:41:44Z","_id":"3262","citation":{"apa":"Tkačik, G., Walczak, A., & Bialek, W. (2012). Optimizing information flow in small genetic networks. III. A self-interacting gene. Physical Review E Statistical Nonlinear and Soft Matter Physics . American Institute of Physics. https://doi.org/10.1103/PhysRevE.85.041903","short":"G. Tkačik, A. Walczak, W. Bialek, Physical Review E Statistical Nonlinear and Soft Matter Physics 85 (2012).","ista":"Tkačik G, Walczak A, Bialek W. 2012. Optimizing information flow in small genetic networks. III. A self-interacting gene. Physical Review E statistical nonlinear and soft matter physics . 85(4), 041903.","mla":"Tkačik, Gašper, et al. “Optimizing Information Flow in Small Genetic Networks. III. A Self-Interacting Gene.” Physical Review E Statistical Nonlinear and Soft Matter Physics , vol. 85, no. 4, 041903, American Institute of Physics, 2012, doi:10.1103/PhysRevE.85.041903.","ama":"Tkačik G, Walczak A, Bialek W. Optimizing information flow in small genetic networks. III. A self-interacting gene. Physical Review E statistical nonlinear and soft matter physics . 2012;85(4). doi:10.1103/PhysRevE.85.041903","ieee":"G. Tkačik, A. Walczak, and W. Bialek, “Optimizing information flow in small genetic networks. III. A self-interacting gene,” Physical Review E statistical nonlinear and soft matter physics , vol. 85, no. 4. American Institute of Physics, 2012.","chicago":"Tkačik, Gašper, Aleksandra Walczak, and William Bialek. “Optimizing Information Flow in Small Genetic Networks. III. A Self-Interacting Gene.” Physical Review E Statistical Nonlinear and Soft Matter Physics . American Institute of Physics, 2012. https://doi.org/10.1103/PhysRevE.85.041903."},"month":"04","year":"2012","acknowledgement":"We thank T. Gregor, E. F. Wieschaus, and, especially, C. G. Callan for helpful discussions.\r\nWork at Princeton was supported in part by NSF Grants No. PHY–0957573 and No. CCF–0939370, by NIH Grant No. R01 GM077599, and by the W. M. Keck Foundation. For part of this work, G.T. was supported in part by NSF Grant No. EF–0928048 and by the Vice Provost for Research at the University of Pennsylvania.","intvolume":" 85","scopus_import":"1","external_id":{"isi":["000302410200006"],"arxiv":["1112.5026"]},"volume":85,"date_created":"2018-12-11T12:02:20Z","abstract":[{"lang":"eng","text":"Living cells must control the reading out or "expression" of information encoded in their genomes, and this regulation often is mediated by transcription factors--proteins that bind to DNA and either enhance or repress the expression of nearby genes. But the expression of transcription factor proteins is itself regulated, and many transcription factors regulate their own expression in addition to responding to other input signals. Here we analyze the simplest of such self-regulatory circuits, asking how parameters can be chosen to optimize information transmission from inputs to outputs in the steady state. Some nonzero level of self-regulation is almost always optimal, with self-activation dominant when transcription factor concentrations are low and self-repression dominant when concentrations are high. In steady state the optimal self-activation is never strong enough to induce bistability, although there is a limit in which the optimal parameters are very close to the critical point."}],"article_number":"041903","oa_version":"Preprint","department":[{"_id":"GaTk"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","doi":"10.1103/PhysRevE.85.041903","day":"01","publication_status":"published","status":"public","oa":1,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1112.5026"}],"issue":"4"},{"department":[{"_id":"HeEd"}],"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","doi":"10.1109/ICCV.2011.6126486","day":"12","language":[{"iso":"eng"}],"publication_status":"published","publisher":"IEEE","date_updated":"2021-01-12T07:42:15Z","_id":"3265","status":"public","citation":{"chicago":"Ion, Adrian, Joao Carreira, and Cristian Sminchisescu. “Image Segmentation by Figure-Ground Composition into Maximal Cliques.” IEEE, 2012. https://doi.org/10.1109/ICCV.2011.6126486.","short":"A. Ion, J. Carreira, C. Sminchisescu, in:, IEEE, 2012.","apa":"Ion, A., Carreira, J., & Sminchisescu, C. (2012). Image segmentation by figure-ground composition into maximal cliques. Presented at the ICCV: International Conference on Computer Vision, Barcelona, Spain: IEEE. https://doi.org/10.1109/ICCV.2011.6126486","ista":"Ion A, Carreira J, Sminchisescu C. 2012. Image segmentation by figure-ground composition into maximal cliques. ICCV: International Conference on Computer Vision, 6126486.","mla":"Ion, Adrian, et al. Image Segmentation by Figure-Ground Composition into Maximal Cliques. 6126486, IEEE, 2012, doi:10.1109/ICCV.2011.6126486.","ama":"Ion A, Carreira J, Sminchisescu C. Image segmentation by figure-ground composition into maximal cliques. In: IEEE; 2012. doi:10.1109/ICCV.2011.6126486","ieee":"A. Ion, J. Carreira, and C. Sminchisescu, “Image segmentation by figure-ground composition into maximal cliques,” presented at the ICCV: International Conference on Computer Vision, Barcelona, Spain, 2012."},"month":"01","year":"2012","conference":{"name":"ICCV: International Conference on Computer Vision","location":"Barcelona, Spain","start_date":"2011-11-06","end_date":"2011-11-13"},"quality_controlled":"1","date_created":"2018-12-11T12:02:21Z","date_published":"2012-01-12T00:00:00Z","abstract":[{"lang":"eng","text":"We propose a mid-level statistical model for image segmentation that composes multiple figure-ground hypotheses (FG) obtained by applying constraints at different locations and scales, into larger interpretations (tilings) of the entire image. Inference is cast as optimization over sets of maximal cliques sampled from a graph connecting all non-overlapping figure-ground segment hypotheses. Potential functions over cliques combine unary, Gestalt-based figure qualities, and pairwise compatibilities among spatially neighboring segments, constrained by T-junctions and the boundary interface statistics of real scenes. Learning the model parameters is based on maximum likelihood, alternating between sampling image tilings and optimizing their potential function parameters. State of the art results are reported on the Berkeley and Stanford segmentation datasets, as well as VOC2009, where a 28% improvement was achieved."}],"type":"conference","article_number":"6126486","publist_id":"3382","author":[{"full_name":"Ion, Adrian","last_name":"Ion","id":"29F89302-F248-11E8-B48F-1D18A9856A87","first_name":"Adrian"},{"first_name":"Joao","last_name":"Carreira","full_name":"Carreira, Joao"},{"full_name":"Sminchisescu, Cristian","last_name":"Sminchisescu","first_name":"Cristian"}],"oa_version":"None","title":"Image segmentation by figure-ground composition into maximal cliques"},{"corr_author":"1","publisher":"Elsevier","language":[{"iso":"eng"}],"month":"06","citation":{"chicago":"Rieckh, Georg, Wolfgang Kreuzer, Holger Waubke, and Peter Balazs. “A 2.5D-Fourier-BEM Model for Vibrations in a Tunnel Running through Layered Anisotropic Soil.” Engineering Analysis with Boundary Elements. Elsevier, 2012. https://doi.org/10.1016/j.enganabound.2011.12.014.","ieee":"G. Rieckh, W. Kreuzer, H. Waubke, and P. Balazs, “A 2.5D-Fourier-BEM model for vibrations in a tunnel running through layered anisotropic soil,” Engineering Analysis with Boundary Elements, vol. 36, no. 6. Elsevier, pp. 960–967, 2012.","mla":"Rieckh, Georg, et al. “A 2.5D-Fourier-BEM Model for Vibrations in a Tunnel Running through Layered Anisotropic Soil.” Engineering Analysis with Boundary Elements, vol. 36, no. 6, Elsevier, 2012, pp. 960–67, doi:10.1016/j.enganabound.2011.12.014.","ama":"Rieckh G, Kreuzer W, Waubke H, Balazs P. A 2.5D-Fourier-BEM model for vibrations in a tunnel running through layered anisotropic soil. Engineering Analysis with Boundary Elements. 2012;36(6):960-967. doi:10.1016/j.enganabound.2011.12.014","ista":"Rieckh G, Kreuzer W, Waubke H, Balazs P. 2012. A 2.5D-Fourier-BEM model for vibrations in a tunnel running through layered anisotropic soil. Engineering Analysis with Boundary Elements. 36(6), 960–967.","short":"G. Rieckh, W. Kreuzer, H. Waubke, P. Balazs, Engineering Analysis with Boundary Elements 36 (2012) 960–967.","apa":"Rieckh, G., Kreuzer, W., Waubke, H., & Balazs, P. (2012). A 2.5D-Fourier-BEM model for vibrations in a tunnel running through layered anisotropic soil. Engineering Analysis with Boundary Elements. Elsevier. https://doi.org/10.1016/j.enganabound.2011.12.014"},"_id":"3274","date_updated":"2025-09-30T07:41:13Z","page":"960 - 967","year":"2012","acknowledgement":"This work was supported by the Austrian Federal Ministry of Transport, Innovation and Technology under the Grant Bmvit-isb2 and the FFG under the project Pr. Nr. 809089.","article_processing_charge":"No","quality_controlled":"1","publication":" Engineering Analysis with Boundary Elements","date_published":"2012-06-01T00:00:00Z","type":"journal_article","isi":1,"publist_id":"3372","title":"A 2.5D-Fourier-BEM model for vibrations in a tunnel running through layered anisotropic soil","author":[{"full_name":"Rieckh, Georg","last_name":"Rieckh","first_name":"Georg","id":"34DA8BD6-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Kreuzer, Wolfgang","first_name":"Wolfgang","last_name":"Kreuzer"},{"last_name":"Waubke","first_name":"Holger","full_name":"Waubke, Holger"},{"full_name":"Balazs, Peter","last_name":"Balazs","first_name":"Peter"}],"doi":"10.1016/j.enganabound.2011.12.014","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","department":[{"_id":"GaTk"}],"day":"01","publication_status":"published","status":"public","issue":"6","intvolume":" 36","scopus_import":"1","external_id":{"isi":["000301691600005"]},"date_created":"2018-12-11T12:02:24Z","volume":36,"abstract":[{"text":"A boundary element model of a tunnel running through horizontally layered soil with anisotropic material properties is presented. Since there is no analytical fundamental solution for wave propagation inside a layered orthotropic medium in 3D, the fundamental displacements and stresses have to be calculated numerically. In our model this is done in the Fourier domain with respect to space and time. The assumption of a straight tunnel with infinite extension in the x direction makes it possible to decouple the system for every wave number kx, leading to a 2.5D-problem, which is suited for parallel computation. The special form of the fundamental solution, resulting from our Fourier ansatz, and the fact, that the calculation of the boundary integral equation is performed in the Fourier domain, enhances the stability and efficiency of the numerical calculations.","lang":"eng"}],"oa_version":"None"},{"day":"01","doi":"10.1007/978-94-007-4966-5_22","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"NiBa"}],"month":"01","_id":"3277","date_updated":"2024-10-09T20:54:39Z","status":"public","page":"387 - 405","citation":{"apa":"de Vladar, H., & Chela Flores, J. (2012). Can the evolution of multicellularity be anticipated in the exploration of the solar system? In Life on Earth and other planetary bodies (Vol. 24, pp. 387–405). Springer. https://doi.org/10.1007/978-94-007-4966-5_22","short":"H. de Vladar, J. Chela Flores, in:, Life on Earth and Other Planetary Bodies, Springer, 2012, pp. 387–405.","ista":"de Vladar H, Chela Flores J. 2012.Can the evolution of multicellularity be anticipated in the exploration of the solar system? In: Life on Earth and other planetary bodies. Cellular Origin, Life in Extreme Habitats and Astrobiology, vol. 24, 387–405.","ama":"de Vladar H, Chela Flores J. Can the evolution of multicellularity be anticipated in the exploration of the solar system? In: Life on Earth and Other Planetary Bodies. Vol 24. Springer; 2012:387-405. doi:10.1007/978-94-007-4966-5_22","mla":"de Vladar, Harold, and Julian Chela Flores. “Can the Evolution of Multicellularity Be Anticipated in the Exploration of the Solar System?” Life on Earth and Other Planetary Bodies, vol. 24, Springer, 2012, pp. 387–405, doi:10.1007/978-94-007-4966-5_22.","ieee":"H. de Vladar and J. Chela Flores, “Can the evolution of multicellularity be anticipated in the exploration of the solar system?,” in Life on Earth and other planetary bodies, vol. 24, Springer, 2012, pp. 387–405.","chicago":"Vladar, Harold de, and Julian Chela Flores. “Can the Evolution of Multicellularity Be Anticipated in the Exploration of the Solar System?” In Life on Earth and Other Planetary Bodies, 24:387–405. Springer, 2012. https://doi.org/10.1007/978-94-007-4966-5_22."},"publisher":"Springer","corr_author":"1","publication_status":"published","language":[{"iso":"eng"}],"year":"2012","quality_controlled":"1","intvolume":" 24","publication":"Life on Earth and other planetary bodies","type":"book_chapter","abstract":[{"text":"The problem of the origin of metazoa is becoming more urgent in the context of astrobiology. By now it is clear that clues to the understanding of this crucial transition in the evolution of life can arise in a fourth pathway besides the three possibilities in the quest for simplicity outlined by Bonner in his classical book. In other words, solar system exploration seems to be one way in the long-term to elucidate the simplicity of evolutionary development. We place these ideas in the context of different inheritance systems, namely the genotypic and phenotypic replicators with limited or unlimited heredity, and ask which of these can support multicellular development, and to which degree of complexity. However, the quest for evidence on the evolution of biotas from planets around other stars does not seem to be feasible with present technology with direct visualization of living organisms on exoplanets. But this may be attempted on the Galilean moons of Jupiter where there is a possibility of detecting reliable biomarkers in the next decade with the Europa Jupiter System Mission, in view of recent progress by landing micropenetrators on planetary, or satellite surfaces. Mars is a second possibility in the inner Solar System, in spite of the multiple difficulties faced by the fleet of past, present and future missions. We discuss a series of preliminary ideas for elucidating the origin of metazoan analogues with available instrumentation in potential payloads of feasible space missions to the Galilean moons.","lang":"eng"}],"date_created":"2018-12-11T12:02:25Z","date_published":"2012-01-01T00:00:00Z","volume":24,"alternative_title":["Cellular Origin, Life in Extreme Habitats and Astrobiology"],"title":"Can the evolution of multicellularity be anticipated in the exploration of the solar system?","author":[{"orcid":"0000-0002-5985-7653","full_name":"de Vladar, Harold","last_name":"de Vladar","id":"2A181218-F248-11E8-B48F-1D18A9856A87","first_name":"Harold"},{"first_name":"Julian","last_name":"Chela Flores","full_name":"Chela Flores, Julian"}],"oa_version":"None","publist_id":"3369"},{"intvolume":" 7194","scopus_import":1,"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"}],"date_created":"2018-12-11T12:02:25Z","volume":7194,"oa_version":"None","project":[{"name":"Provable Security for Physical Cryptography","grant_number":"259668","_id":"258C570E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"day":"04","doi":"10.1007/978-3-642-28914-9_21","department":[{"_id":"KrPi"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","status":"public","publication_status":"published","main_file_link":[{"url":"http://www.iacr.org/archive/tcc2012/tcc2012-index.html"}],"quality_controlled":"1","type":"conference","date_published":"2012-05-04T00:00:00Z","alternative_title":["LNCS"],"title":"Hardness preserving constructions of pseudorandom functions","author":[{"last_name":"Jain","first_name":"Abhishek","full_name":"Jain, Abhishek"},{"full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","orcid":"0000-0002-9139-1654"},{"full_name":"Tentes, Aris","last_name":"Tentes","first_name":"Aris"}],"publist_id":"3367","ec_funded":1,"month":"05","_id":"3279","citation":{"chicago":"Jain, Abhishek, Krzysztof Z Pietrzak, and Aris Tentes. “Hardness Preserving Constructions of Pseudorandom Functions,” 7194:369–82. Springer, 2012. https://doi.org/10.1007/978-3-642-28914-9_21.","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.","mla":"Jain, Abhishek, et al. Hardness Preserving Constructions of Pseudorandom Functions. Vol. 7194, Springer, 2012, pp. 369–82, doi:10.1007/978-3-642-28914-9_21.","ama":"Jain A, Pietrzak KZ, Tentes A. Hardness preserving constructions of pseudorandom functions. In: Vol 7194. Springer; 2012:369-382. doi:10.1007/978-3-642-28914-9_21","ista":"Jain A, Pietrzak KZ, Tentes A. 2012. Hardness preserving constructions of pseudorandom functions. TCC: Theory of Cryptography Conference, LNCS, vol. 7194, 369–382.","apa":"Jain, A., Pietrzak, K. Z., & 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. https://doi.org/10.1007/978-3-642-28914-9_21","short":"A. Jain, K.Z. Pietrzak, A. Tentes, in:, Springer, 2012, pp. 369–382."},"page":"369 - 382","date_updated":"2021-01-12T07:42:21Z","publisher":"Springer","language":[{"iso":"eng"}],"conference":{"end_date":"2012-03-21","start_date":"2012-03-19","location":"Taormina, Sicily, Italy","name":"TCC: Theory of Cryptography Conference"},"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)"},{"publication_status":"published","status":"public","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"KrPi"}],"doi":"10.1007/978-3-642-28914-9_31","project":[{"name":"Provable Security for Physical Cryptography","call_identifier":"FP7","_id":"258C570E-B435-11E9-9278-68D0E5697425","grant_number":"259668"}],"day":"04","oa":1,"main_file_link":[{"url":"http://www.iacr.org/archive/tcc2012/71940166/71940166.pdf","open_access":"1"}],"scopus_import":"1","intvolume":" 7194","oa_version":"Submitted Version","date_created":"2018-12-11T12:02:26Z","volume":7194,"abstract":[{"lang":"eng","text":"The (decisional) learning with errors problem (LWE) asks to distinguish "noisy" 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 "subspace LWE" (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. "}],"language":[{"iso":"eng"}],"publisher":"Springer","corr_author":"1","_id":"3280","date_updated":"2024-10-21T06:02:59Z","citation":{"apa":"Pietrzak, K. Z. (2012). Subspace LWE (Vol. 7194, pp. 548–563). Presented at the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy: Springer. https://doi.org/10.1007/978-3-642-28914-9_31","short":"K.Z. Pietrzak, in:, Springer, 2012, pp. 548–563.","ista":"Pietrzak KZ. 2012. Subspace LWE. TCC: Theory of Cryptography Conference, LNCS, vol. 7194, 548–563.","ama":"Pietrzak KZ. Subspace LWE. In: Vol 7194. Springer; 2012:548-563. doi:10.1007/978-3-642-28914-9_31","mla":"Pietrzak, Krzysztof Z. Subspace LWE. Vol. 7194, Springer, 2012, pp. 548–63, doi:10.1007/978-3-642-28914-9_31.","ieee":"K. Z. Pietrzak, “Subspace LWE,” presented at the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy, 2012, vol. 7194, pp. 548–563.","chicago":"Pietrzak, Krzysztof Z. “Subspace LWE,” 7194:548–63. Springer, 2012. https://doi.org/10.1007/978-3-642-28914-9_31."},"page":"548 - 563","month":"05","acknowledgement":"Supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013) / ERC Starting Grant (259668-PSPC).","year":"2012","conference":{"location":"Taormina, Sicily, Italy","start_date":"2012-03-19","end_date":"2012-03-21","name":"TCC: Theory of Cryptography Conference"},"quality_controlled":"1","publist_id":"3366","ec_funded":1,"author":[{"orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z"}],"title":"Subspace LWE","alternative_title":["LNCS"],"date_published":"2012-05-04T00:00:00Z","type":"conference"},{"language":[{"iso":"eng"}],"publication_status":"published","publisher":"Springer","_id":"3281","status":"public","date_updated":"2024-10-21T06:03:00Z","page":"458 - 475","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:10.1007/978-3-642-28914-9_26","mla":"Pietrzak, Krzysztof Z., et al. Lossy Functions Do Not Amplify Well. Vol. 7194, Springer, 2012, pp. 458–75, doi:10.1007/978-3-642-28914-9_26.","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.","apa":"Pietrzak, K. Z., Rosen, A., & 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. https://doi.org/10.1007/978-3-642-28914-9_26","chicago":"Pietrzak, Krzysztof Z, Alon Rosen, and Gil Segev. “Lossy Functions Do Not Amplify Well,” 7194:458–75. Springer, 2012. https://doi.org/10.1007/978-3-642-28914-9_26."},"month":"05","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"KrPi"}],"doi":"10.1007/978-3-642-28914-9_26","day":"04","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","year":"2012","conference":{"location":"Taormina, Sicily, Italy","start_date":"2012-03-19","end_date":"2012-03-21","name":"TCC: Theory of Cryptography Conference"},"main_file_link":[{"url":"http://www.iacr.org/archive/tcc2012/tcc2012-index.html"}],"scopus_import":"1","intvolume":" 7194","quality_controlled":"1","publist_id":"3365","oa_version":"None","author":[{"full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","orcid":"0000-0002-9139-1654"},{"full_name":"Rosen, Alon","first_name":"Alon","last_name":"Rosen"},{"full_name":"Segev, Gil","first_name":"Gil","last_name":"Segev"}],"title":"Lossy functions do not amplify well","alternative_title":["LNCS"],"volume":7194,"date_published":"2012-05-04T00:00:00Z","date_created":"2018-12-11T12:02:26Z","abstract":[{"lang":"eng","text":"We consider the problem of amplifying the "lossiness" 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 "lossy functions," 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."}],"type":"conference"}]