[{"month":"08","date_updated":"2023-02-23T14:01:41Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1803.08462"}],"oa":1,"article_type":"original","oa_version":"Preprint","day":"01","external_id":{"arxiv":["1803.08462"]},"_id":"9580","publication_status":"published","author":[{"full_name":"Conlon, David","first_name":"David","last_name":"Conlon"},{"first_name":"Jacob","full_name":"Fox, Jacob","last_name":"Fox"},{"last_name":"Kwan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","first_name":"Matthew Alan","orcid":"0000-0002-4003-7567","full_name":"Kwan, Matthew Alan"},{"full_name":"Sudakov, Benny","first_name":"Benny","last_name":"Sudakov"}],"publisher":"Springer","extern":"1","doi":"10.1007/s11856-019-1897-z","article_processing_charge":"No","abstract":[{"lang":"eng","text":"An r-cut of a k-uniform hypergraph H is a partition of the vertex set of H into r parts and the size of the cut is the number of edges which have a vertex in each part. A classical result of Edwards says that every m-edge graph has a 2-cut of size m/2+Ω)(m−−√) and this is best possible. That is, there exist cuts which exceed the expected size of a random cut by some multiple of the standard deviation. We study analogues of this and related results in hypergraphs. First, we observe that similarly to graphs, every m-edge k-uniform hypergraph has an r-cut whose size is Ω(m−−√) larger than the expected size of a random r-cut. Moreover, in the case where k = 3 and r = 2 this bound is best possible and is attained by Steiner triple systems. Surprisingly, for all other cases (that is, if k ≥ 4 or r ≥ 3), we show that every m-edge k-uniform hypergraph has an r-cut whose size is Ω(m5/9) larger than the expected size of a random r-cut. This is a significant difference in behaviour, since the amount by which the size of the largest cut exceeds the expected size of a random cut is now considerably larger than the standard deviation."}],"intvolume":" 233","date_published":"2019-08-01T00:00:00Z","page":"67-111","arxiv":1,"publication_identifier":{"eissn":["1565-8511"],"issn":["0021-2172"]},"scopus_import":"1","quality_controlled":"1","date_created":"2021-06-21T13:36:02Z","status":"public","volume":233,"citation":{"ama":"Conlon D, Fox J, Kwan MA, Sudakov B. Hypergraph cuts above the average. Israel Journal of Mathematics. 2019;233(1):67-111. doi:10.1007/s11856-019-1897-z","mla":"Conlon, David, et al. “Hypergraph Cuts above the Average.” Israel Journal of Mathematics, vol. 233, no. 1, Springer, 2019, pp. 67–111, doi:10.1007/s11856-019-1897-z.","ista":"Conlon D, Fox J, Kwan MA, Sudakov B. 2019. Hypergraph cuts above the average. Israel Journal of Mathematics. 233(1), 67–111.","short":"D. Conlon, J. Fox, M.A. Kwan, B. Sudakov, Israel Journal of Mathematics 233 (2019) 67–111.","chicago":"Conlon, David, Jacob Fox, Matthew Alan Kwan, and Benny Sudakov. “Hypergraph Cuts above the Average.” Israel Journal of Mathematics. Springer, 2019. https://doi.org/10.1007/s11856-019-1897-z.","ieee":"D. Conlon, J. Fox, M. A. Kwan, and B. Sudakov, “Hypergraph cuts above the average,” Israel Journal of Mathematics, vol. 233, no. 1. Springer, pp. 67–111, 2019.","apa":"Conlon, D., Fox, J., Kwan, M. A., & Sudakov, B. (2019). Hypergraph cuts above the average. Israel Journal of Mathematics. Springer. https://doi.org/10.1007/s11856-019-1897-z"},"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","year":"2019","issue":"1","type":"journal_article","publication":"Israel Journal of Mathematics","title":"Hypergraph cuts above the average","language":[{"iso":"eng"}]},{"title":"Data from: A multi-faceted approach testing the effects of previous bacterial exposure on resistance and tolerance","type":"research_data_reference","year":"2019","doi":"10.5061/dryad.9kj41f0","status":"public","abstract":[{"text":"1. Hosts can alter their strategy towards pathogens during their lifetime, i.e., they can show phenotypic plasticity in immunity or life history. Immune priming is one such example, where a previous encounter with a pathogen confers enhanced protection upon secondary challenge, resulting in reduced pathogen load (i.e. resistance) and improved host survival. However, an initial encounter might also enhance tolerance, particularly to less virulent opportunistic pathogens that establish persistent infections. In this scenario, individuals are better able to reduce the negative fitness consequences that result from a high pathogen load. Finally, previous exposure may also lead to life history adjustments, such as terminal investment into reproduction. 2. Using different Drosophila melanogaster host genotypes and two bacterial pathogens, Lactococcus lactis and Pseudomonas entomophila, we tested if previous exposure results in resistance or tolerance and whether it modifies immune gene expression during an acute-phase infection (one day post-challenge). We then asked if previous pathogen exposure affects chronic-phase pathogen persistence and longer-term survival (28 days post-challenge). 3. We predicted that previous exposure would increase host resistance to an early stage bacterial infection while it might come at a cost to host fecundity tolerance. We reasoned that resistance would be due in part to stronger immune gene expression after challenge. We expected that previous exposure would improve long-term survival, that it would reduce infection persistence, and we expected to find genetic variation in these responses. 4. We found that previous exposure to P. entomophila weakened host resistance to a second infection independent of genotype and had no effect on immune gene expression. Fecundity tolerance showed genotypic variation but was not influenced by previous exposure. However, L. lactis persisted as a chronic infection, whereas survivors cleared the more pathogenic P. entomophila infection. 5. To our knowledge, this is the first study that addresses host tolerance to bacteria in relation to previous exposure, taking a multi-faceted approach to address the topic. Our results suggest that previous exposure comes with transient costs to resistance during the early stage of infection in this host-pathogen system and that infection persistence may be bacterium-specific.","lang":"eng"}],"article_processing_charge":"No","citation":{"chicago":"Kutzer, Megan, Joachim Kurtz, and Sophie A.O. Armitage. “Data from: A Multi-Faceted Approach Testing the Effects of Previous Bacterial Exposure on Resistance and Tolerance.” Dryad, 2019. https://doi.org/10.5061/dryad.9kj41f0.","apa":"Kutzer, M., Kurtz, J., & Armitage, S. A. O. (2019). Data from: A multi-faceted approach testing the effects of previous bacterial exposure on resistance and tolerance. Dryad. https://doi.org/10.5061/dryad.9kj41f0","ieee":"M. Kutzer, J. Kurtz, and S. A. O. Armitage, “Data from: A multi-faceted approach testing the effects of previous bacterial exposure on resistance and tolerance.” Dryad, 2019.","mla":"Kutzer, Megan, et al. Data from: A Multi-Faceted Approach Testing the Effects of Previous Bacterial Exposure on Resistance and Tolerance. Dryad, 2019, doi:10.5061/dryad.9kj41f0.","ama":"Kutzer M, Kurtz J, Armitage SAO. Data from: A multi-faceted approach testing the effects of previous bacterial exposure on resistance and tolerance. 2019. doi:10.5061/dryad.9kj41f0","ista":"Kutzer M, Kurtz J, Armitage SAO. 2019. Data from: A multi-faceted approach testing the effects of previous bacterial exposure on resistance and tolerance, Dryad, 10.5061/dryad.9kj41f0.","short":"M. Kutzer, J. Kurtz, S.A.O. Armitage, (2019)."},"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","related_material":{"record":[{"relation":"used_in_publication","id":"6105","status":"public"}]},"day":"05","_id":"9806","publisher":"Dryad","author":[{"first_name":"Megan","orcid":"0000-0002-8696-6978","full_name":"Kutzer, Megan","last_name":"Kutzer","id":"29D0B332-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Kurtz","first_name":"Joachim","full_name":"Kurtz, Joachim"},{"full_name":"Armitage, Sophie A.O.","first_name":"Sophie A.O.","last_name":"Armitage"}],"date_created":"2021-08-06T12:06:40Z","oa_version":"Published Version","department":[{"_id":"SyCr"}],"oa":1,"date_published":"2019-02-05T00:00:00Z","main_file_link":[{"url":"https://doi.org/10.5061/dryad.9kj41f0","open_access":"1"}],"month":"02","date_updated":"2025-07-10T11:53:11Z"},{"date_published":"2019-04-16T00:00:00Z","page":"57-66","department":[{"_id":"ToHe"}],"publication_identifier":{"isbn":["9781450362825"]},"isi":1,"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ama":"Ferrere T, Nickovic D, Donzé A, Ito H, Kapinski J. Interface-aware signal temporal logic. In: Proceedings of the 2019 22nd ACM International Conference on Hybrid Systems: Computation and Control. ACM; 2019:57-66. doi:10.1145/3302504.3311800","mla":"Ferrere, Thomas, et al. “Interface-Aware Signal Temporal Logic.” Proceedings of the 2019 22nd ACM International Conference on Hybrid Systems: Computation and Control, ACM, 2019, pp. 57–66, doi:10.1145/3302504.3311800.","ista":"Ferrere T, Nickovic D, Donzé A, Ito H, Kapinski J. 2019. Interface-aware signal temporal logic. Proceedings of the 2019 22nd ACM International Conference on Hybrid Systems: Computation and Control. HSCC: Hybrid Systems - Computation and Control, 57–66.","short":"T. Ferrere, D. Nickovic, A. Donzé, H. Ito, J. Kapinski, in:, Proceedings of the 2019 22nd ACM International Conference on Hybrid Systems: Computation and Control, ACM, 2019, pp. 57–66.","chicago":"Ferrere, Thomas, Dejan Nickovic, Alexandre Donzé, Hisahiro Ito, and James Kapinski. “Interface-Aware Signal Temporal Logic.” In Proceedings of the 2019 22nd ACM International Conference on Hybrid Systems: Computation and Control, 57–66. ACM, 2019. https://doi.org/10.1145/3302504.3311800.","ieee":"T. Ferrere, D. Nickovic, A. Donzé, H. Ito, and J. Kapinski, “Interface-aware signal temporal logic,” in Proceedings of the 2019 22nd ACM International Conference on Hybrid Systems: Computation and Control, Montreal, Canada, 2019, pp. 57–66.","apa":"Ferrere, T., Nickovic, D., Donzé, A., Ito, H., & Kapinski, J. (2019). Interface-aware signal temporal logic. In Proceedings of the 2019 22nd ACM International Conference on Hybrid Systems: Computation and Control (pp. 57–66). Montreal, Canada: ACM. https://doi.org/10.1145/3302504.3311800"},"scopus_import":"1","quality_controlled":"1","date_created":"2019-05-13T08:13:46Z","title":"Interface-aware signal temporal logic","publication":"Proceedings of the 2019 22nd ACM International Conference on Hybrid Systems: Computation and Control","language":[{"iso":"eng"}],"file":[{"creator":"dernst","success":1,"access_level":"open_access","file_id":"8633","content_type":"application/pdf","date_created":"2020-10-08T17:25:45Z","date_updated":"2020-10-08T17:25:45Z","file_name":"2019_ACM_Ferrere.pdf","checksum":"b8e967081e051d1c55ca5d18fb187890","file_size":1055421,"relation":"main_file"}],"year":"2019","type":"conference","month":"04","date_updated":"2025-07-10T11:53:22Z","has_accepted_license":"1","oa_version":"Submitted Version","file_date_updated":"2020-10-08T17:25:45Z","oa":1,"abstract":[{"lang":"eng","text":"Safety and security are major concerns in the development of Cyber-Physical Systems (CPS). Signal temporal logic (STL) was proposedas a language to specify and monitor the correctness of CPS relativeto formalized requirements. Incorporating STL into a developmentprocess enables designers to automatically monitor and diagnosetraces, compute robustness estimates based on requirements, andperform requirement falsification, leading to productivity gains inverification and validation activities; however, in its current formSTL is agnostic to the input/output classification of signals, andthis negatively impacts the relevance of the analysis results.In this paper we propose to make the interface explicit in theSTL language by introducing input/output signal declarations. Wethen define new measures of input vacuity and output robustnessthat better reflect the nature of the system and the specification in-tent. The resulting framework, which we call interface-aware signaltemporal logic (IA-STL), aids verification and validation activities.We demonstrate the benefits of IA-STL on several CPS analysisactivities: (1) robustness-driven sensitivity analysis, (2) falsificationand (3) fault localization. We describe an implementation of our en-hancement to STL and associated notions of robustness and vacuityin a prototype extension of Breach, a MATLAB®/Simulink®toolboxfor CPS verification and validation. We explore these methodologi-cal improvements and evaluate our results on two examples fromthe automotive domain: a benchmark powertrain control systemand a hydrogen fuel cell system."}],"article_processing_charge":"No","doi":"10.1145/3302504.3311800","day":"16","conference":{"start_date":"2019-04-16","location":"Montreal, Canada","name":"HSCC: Hybrid Systems - Computation and Control","end_date":"2019-04-18"},"project":[{"name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","call_identifier":"FWF"},{"grant_number":"Z211","call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425","name":"Formal methods for the design and analysis of complex systems"}],"publisher":"ACM","_id":"6428","author":[{"first_name":"Thomas","orcid":"0000-0001-5199-3143","full_name":"Ferrere, Thomas","last_name":"Ferrere","id":"40960E6E-F248-11E8-B48F-1D18A9856A87"},{"id":"41BCEE5C-F248-11E8-B48F-1D18A9856A87","last_name":"Nickovic","full_name":"Nickovic, Dejan","first_name":"Dejan"},{"last_name":"Donzé","full_name":"Donzé, Alexandre","first_name":"Alexandre"},{"first_name":"Hisahiro","full_name":"Ito, Hisahiro","last_name":"Ito"},{"last_name":"Kapinski","full_name":"Kapinski, James","first_name":"James"}],"external_id":{"isi":["000516713900007"]},"publication_status":"published","ddc":["000"]},{"main_file_link":[{"url":"https://eprint.iacr.org/2018/426","open_access":"1"}],"date_updated":"2026-04-16T09:52:04Z","month":"04","oa_version":"Preprint","oa":1,"abstract":[{"text":"A proxy re-encryption (PRE) scheme is a public-key encryption scheme that allows the holder of a key pk to derive a re-encryption key for any other key 𝑝𝑘′. This re-encryption key lets anyone transform ciphertexts under pk into ciphertexts under 𝑝𝑘′ without having to know the underlying message, while transformations from 𝑝𝑘′ to pk should not be possible (unidirectional). Security is defined in a multi-user setting against an adversary that gets the users’ public keys and can ask for re-encryption keys and can corrupt users by requesting their secret keys. Any ciphertext that the adversary cannot trivially decrypt given the obtained secret and re-encryption keys should be secure.\r\n\r\nAll existing security proofs for PRE only show selective security, where the adversary must first declare the users it wants to corrupt. This can be lifted to more meaningful adaptive security by guessing the set of corrupted users among the n users, which loses a factor exponential in Open image in new window , rendering the result meaningless already for moderate Open image in new window .\r\n\r\nJafargholi et al. (CRYPTO’17) proposed a framework that in some cases allows to give adaptive security proofs for schemes which were previously only known to be selectively secure, while avoiding the exponential loss that results from guessing the adaptive choices made by an adversary. We apply their framework to PREs that satisfy some natural additional properties. Concretely, we give a more fine-grained reduction for several unidirectional PREs, proving adaptive security at a much smaller loss. The loss depends on the graph of users whose edges represent the re-encryption keys queried by the adversary. For trees and chains the loss is quasi-polynomial in the size and for general graphs it is exponential in their depth and indegree (instead of their size as for previous reductions). Fortunately, trees and low-depth graphs cover many, if not most, interesting applications.\r\n\r\nOur results apply e.g. to the bilinear-map based PRE schemes by Ateniese et al. (NDSS’05 and CT-RSA’09), Gentry’s FHE-based scheme (STOC’09) and the LWE-based scheme by Chandran et al. (PKC’14).","lang":"eng"}],"article_processing_charge":"No","doi":"10.1007/978-3-030-17259-6_11","_id":"6430","external_id":{"isi":["001299215500011"]},"publisher":"Springer Nature","publication_status":"published","author":[{"last_name":"Fuchsbauer","id":"46B4C3EE-F248-11E8-B48F-1D18A9856A87","first_name":"Georg","full_name":"Fuchsbauer, Georg"},{"first_name":"Chethan","full_name":"Kamath Hosdurg, Chethan","orcid":"0009-0006-6812-7317","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","last_name":"Kamath Hosdurg"},{"first_name":"Karen","full_name":"Klein, Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","last_name":"Klein"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654"}],"day":"06","conference":{"location":"Beijing, China","start_date":"2019-04-14","name":"PKC: Public-Key Cryptograhy","end_date":"2019-04-17"},"project":[{"name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815"}],"ec_funded":1,"page":"317-346","date_published":"2019-04-06T00:00:00Z","alternative_title":["LNCS"],"intvolume":" 11443","publication_identifier":{"eissn":["1611-3349"],"isbn":["9783030172589"],"issn":["0302-9743"]},"department":[{"_id":"KrPi"}],"isi":1,"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","citation":{"mla":"Fuchsbauer, Georg, et al. Adaptively Secure Proxy Re-Encryption. Vol. 11443, Springer Nature, 2019, pp. 317–46, doi:10.1007/978-3-030-17259-6_11.","ama":"Fuchsbauer G, Kamath Hosdurg C, Klein K, Pietrzak KZ. Adaptively secure proxy re-encryption. In: Vol 11443. Springer Nature; 2019:317-346. doi:10.1007/978-3-030-17259-6_11","short":"G. Fuchsbauer, C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, Springer Nature, 2019, pp. 317–346.","ista":"Fuchsbauer G, Kamath Hosdurg C, Klein K, Pietrzak KZ. 2019. Adaptively secure proxy re-encryption. PKC: Public-Key Cryptograhy, LNCS, vol. 11443, 317–346.","chicago":"Fuchsbauer, Georg, Chethan Kamath Hosdurg, Karen Klein, and Krzysztof Z Pietrzak. “Adaptively Secure Proxy Re-Encryption,” 11443:317–46. Springer Nature, 2019. https://doi.org/10.1007/978-3-030-17259-6_11.","apa":"Fuchsbauer, G., Kamath Hosdurg, C., Klein, K., & Pietrzak, K. Z. (2019). Adaptively secure proxy re-encryption (Vol. 11443, pp. 317–346). Presented at the PKC: Public-Key Cryptograhy, Beijing, China: Springer Nature. https://doi.org/10.1007/978-3-030-17259-6_11","ieee":"G. Fuchsbauer, C. Kamath Hosdurg, K. Klein, and K. Z. Pietrzak, “Adaptively secure proxy re-encryption,” presented at the PKC: Public-Key Cryptograhy, Beijing, China, 2019, vol. 11443, pp. 317–346."},"volume":11443,"status":"public","date_created":"2019-05-13T08:13:46Z","related_material":{"record":[{"relation":"dissertation_contains","id":"10035","status":"public"}]},"quality_controlled":"1","scopus_import":"1","language":[{"iso":"eng"}],"title":"Adaptively secure proxy re-encryption","year":"2019","type":"conference"},{"department":[{"_id":"ToHe"},{"_id":"KrCh"}],"publication_identifier":{"isbn":["9783030255398"],"issn":["0302-9743"]},"isi":1,"license":"https://creativecommons.org/licenses/by/4.0/","intvolume":" 11561","date_published":"2019-07-12T00:00:00Z","alternative_title":["LNCS"],"page":"630-649","type":"conference","year":"2019","title":"Run-time optimization for learned controllers through quantitative games","corr_author":"1","publication":"31st International Conference on Computer-Aided Verification","language":[{"iso":"eng"}],"file":[{"date_updated":"2020-07-14T12:47:31Z","date_created":"2019-08-14T09:35:24Z","content_type":"application/pdf","relation":"main_file","file_size":659766,"checksum":"c231579f2485c6fd4df17c9443a4d80b","file_name":"2019_CAV_Avni.pdf","creator":"dernst","file_id":"6816","access_level":"open_access"}],"quality_controlled":"1","scopus_import":"1","date_created":"2019-05-16T11:22:30Z","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"volume":11561,"status":"public","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"mla":"Avni, Guy, et al. “Run-Time Optimization for Learned Controllers through Quantitative Games.” 31st International Conference on Computer-Aided Verification, vol. 11561, Springer, 2019, pp. 630–49, doi:10.1007/978-3-030-25540-4_36.","ama":"Avni G, Bloem R, Chatterjee K, Henzinger TA, Konighofer B, Pranger S. Run-time optimization for learned controllers through quantitative games. In: 31st International Conference on Computer-Aided Verification. Vol 11561. Springer; 2019:630-649. doi:10.1007/978-3-030-25540-4_36","short":"G. Avni, R. Bloem, K. Chatterjee, T.A. Henzinger, B. Konighofer, S. Pranger, in:, 31st International Conference on Computer-Aided Verification, Springer, 2019, pp. 630–649.","ista":"Avni G, Bloem R, Chatterjee K, Henzinger TA, Konighofer B, Pranger S. 2019. Run-time optimization for learned controllers through quantitative games. 31st International Conference on Computer-Aided Verification. CAV: Computer Aided Verification, LNCS, vol. 11561, 630–649.","chicago":"Avni, Guy, Roderick Bloem, Krishnendu Chatterjee, Thomas A Henzinger, Bettina Konighofer, and Stefan Pranger. “Run-Time Optimization for Learned Controllers through Quantitative Games.” In 31st International Conference on Computer-Aided Verification, 11561:630–49. Springer, 2019. https://doi.org/10.1007/978-3-030-25540-4_36.","apa":"Avni, G., Bloem, R., Chatterjee, K., Henzinger, T. A., Konighofer, B., & Pranger, S. (2019). Run-time optimization for learned controllers through quantitative games. In 31st International Conference on Computer-Aided Verification (Vol. 11561, pp. 630–649). New York, NY, United States: Springer. https://doi.org/10.1007/978-3-030-25540-4_36","ieee":"G. Avni, R. Bloem, K. Chatterjee, T. A. Henzinger, B. Konighofer, and S. Pranger, “Run-time optimization for learned controllers through quantitative games,” in 31st International Conference on Computer-Aided Verification, New York, NY, United States, 2019, vol. 11561, pp. 630–649."},"oa":1,"oa_version":"Published Version","file_date_updated":"2020-07-14T12:47:31Z","month":"07","date_updated":"2025-04-15T06:26:05Z","has_accepted_license":"1","ddc":["000"],"day":"12","conference":{"end_date":"2019-07-18","name":"CAV: Computer Aided Verification","start_date":"2019-07-13","location":"New York, NY, United States"},"project":[{"grant_number":"M02369","call_identifier":"FWF","name":"Formal Methods meets Algorithmic Game Theory","_id":"264B3912-B435-11E9-9278-68D0E5697425"},{"grant_number":"Z211","call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425","name":"Formal methods for the design and analysis of complex systems"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","call_identifier":"FWF","grant_number":"S 11407_N23"}],"publication_status":"published","_id":"6462","external_id":{"isi":["000491468000036"]},"author":[{"first_name":"Guy","orcid":"0000-0001-5588-8287","full_name":"Avni, Guy","last_name":"Avni","id":"463C8BC2-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Roderick","full_name":"Bloem, Roderick","last_name":"Bloem"},{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Thomas A","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger"},{"last_name":"Konighofer","first_name":"Bettina","full_name":"Konighofer, Bettina"},{"first_name":"Stefan","full_name":"Pranger, Stefan","last_name":"Pranger"}],"publisher":"Springer","abstract":[{"text":"A controller is a device that interacts with a plant. At each time point,it reads the plant’s state and issues commands with the goal that the plant oper-ates optimally. Constructing optimal controllers is a fundamental and challengingproblem. Machine learning techniques have recently been successfully applied totrain controllers, yet they have limitations. Learned controllers are monolithic andhard to reason about. In particular, it is difficult to add features without retraining,to guarantee any level of performance, and to achieve acceptable performancewhen encountering untrained scenarios. These limitations can be addressed bydeploying quantitative run-timeshieldsthat serve as a proxy for the controller.At each time point, the shield reads the command issued by the controller andmay choose to alter it before passing it on to the plant. We show how optimalshields that interfere as little as possible while guaranteeing a desired level ofcontroller performance, can be generated systematically and automatically usingreactive synthesis. First, we abstract the plant by building a stochastic model.Second, we consider the learned controller to be a black box. Third, we mea-surecontroller performanceandshield interferenceby two quantitative run-timemeasures that are formally defined using weighted automata. Then, the problemof constructing a shield that guarantees maximal performance with minimal inter-ference is the problem of finding an optimal strategy in a stochastic2-player game“controller versus shield” played on the abstract state space of the plant with aquantitative objective obtained from combining the performance and interferencemeasures. We illustrate the effectiveness of our approach by automatically con-structing lightweight shields for learned traffic-light controllers in various roadnetworks. The shields we generate avoid liveness bugs, improve controller per-formance in untrained and changing traffic situations, and add features to learnedcontrollers, such as giving priority to emergency vehicles.","lang":"eng"}],"article_processing_charge":"No","doi":"10.1007/978-3-030-25540-4_36"},{"ddc":["004"],"_id":"6473","author":[{"last_name":"Cepeda Humerez","id":"3DEE19A4-F248-11E8-B48F-1D18A9856A87","full_name":"Cepeda Humerez, Sarah A","first_name":"Sarah A"}],"publication_status":"published","publisher":"Institute of Science and Technology Austria","day":"23","doi":"10.15479/AT:ISTA:6473","article_processing_charge":"No","abstract":[{"text":"Single cells are constantly interacting with their environment and each other, more importantly, the accurate perception of environmental cues is crucial for growth, survival, and reproduction. This communication between cells and their environment can be formalized in mathematical terms and be quantified as the information flow between them, as prescribed by information theory. \r\nThe recent availability of real–time dynamical patterns of signaling molecules in single cells has allowed us to identify encoding about the identity of the environment in the time–series. However, efficient estimation of the information transmitted by these signals has been a data–analysis challenge due to the high dimensionality of the trajectories and the limited number of samples. In the first part of this thesis, we develop and evaluate decoding–based estimation methods to lower bound the mutual information and derive model–based precise information estimates for biological reaction networks governed by the chemical master equation. This is followed by applying the decoding-based methods to study the intracellular representation of extracellular changes in budding yeast, by observing the transient dynamics of nuclear translocation of 10 transcription factors in response to 3 stress conditions. Additionally, we apply these estimators to previously published data on ERK and Ca2+ signaling and yeast stress response. We argue that this single cell decoding-based measure of information provides an unbiased, quantitative and interpretable measure for the fidelity of biological signaling processes. \r\nFinally, in the last section, we deal with gene regulation which is primarily controlled by transcription factors (TFs) that bind to the DNA to activate gene expression. The possibility that non-cognate TFs activate transcription diminishes the accuracy of regulation with potentially disastrous effects for the cell. This ’crosstalk’ acts as a previously unexplored source of noise in biochemical networks and puts a strong constraint on their performance. To mitigate erroneous initiation we propose an out of equilibrium scheme that implements kinetic proofreading. We show that such architectures are favored over their equilibrium counterparts for complex organisms despite introducing noise in gene expression. ","lang":"eng"}],"oa":1,"keyword":["Information estimation","Time-series","data analysis"],"file_date_updated":"2020-07-14T12:47:31Z","oa_version":"Published Version","has_accepted_license":"1","date_updated":"2026-04-16T08:37:38Z","month":"05","type":"dissertation","year":"2019","file":[{"date_updated":"2020-07-14T12:47:31Z","date_created":"2019-05-23T11:18:16Z","content_type":"application/zip","file_size":23937464,"relation":"source_file","checksum":"75f9184c1346e10a5de5f9cc7338309a","file_name":"Thesis_Cepeda.zip","creator":"scepeda","file_id":"6480","access_level":"closed"},{"creator":"scepeda","access_level":"open_access","file_id":"6481","content_type":"application/pdf","date_updated":"2020-07-14T12:47:31Z","date_created":"2019-05-23T11:18:13Z","checksum":"afdc0633ddbd71d5b13550d7fb4f4454","file_name":"CepedaThesis.pdf","file_size":16646985,"relation":"main_file"}],"language":[{"iso":"eng"}],"corr_author":"1","title":"Estimating information flow in single cells","date_created":"2019-05-21T00:11:23Z","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"degree_awarded":"PhD","related_material":{"record":[{"status":"public","id":"2016","relation":"dissertation_contains"},{"relation":"dissertation_contains","id":"281","status":"public"},{"id":"1576","status":"public","relation":"dissertation_contains"},{"id":"6900","status":"public","relation":"dissertation_contains"}]},"citation":{"chicago":"Cepeda Humerez, Sarah A. “Estimating Information Flow in Single Cells.” Institute of Science and Technology Austria, 2019. https://doi.org/10.15479/AT:ISTA:6473.","apa":"Cepeda Humerez, S. A. (2019). Estimating information flow in single cells. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:6473","ieee":"S. A. Cepeda Humerez, “Estimating information flow in single cells,” Institute of Science and Technology Austria, 2019.","mla":"Cepeda Humerez, Sarah A. Estimating Information Flow in Single Cells. Institute of Science and Technology Austria, 2019, doi:10.15479/AT:ISTA:6473.","ama":"Cepeda Humerez SA. Estimating information flow in single cells. 2019. doi:10.15479/AT:ISTA:6473","short":"S.A. Cepeda Humerez, Estimating Information Flow in Single Cells, Institute of Science and Technology Austria, 2019.","ista":"Cepeda Humerez SA. 2019. Estimating information flow in single cells. Institute of Science and Technology Austria."},"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","status":"public","department":[{"_id":"GaTk"}],"supervisor":[{"last_name":"Tkačik","id":"3D494DCA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6699-1455","full_name":"Tkačik, Gašper","first_name":"Gašper"}],"publication_identifier":{"issn":["2663-337X"]},"OA_place":"publisher","page":"135","alternative_title":["ISTA Thesis"],"date_published":"2019-05-23T00:00:00Z"},{"arxiv":1,"page":"244-259","alternative_title":["LNCS"],"date_published":"2019-02-14T00:00:00Z","intvolume":" 11269","publication_identifier":{"eissn":["1611-3349"],"isbn":["9783030129385","9783030129392"],"issn":["0302-9743"]},"department":[{"_id":"ChLa"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"mla":"Sun, Rémy, and Christoph Lampert. KS(Conf): A Light-Weight Test If a ConvNet Operates Outside of Its Specifications. Vol. 11269, Springer Nature, 2019, pp. 244–59, doi:10.1007/978-3-030-12939-2_18.","ama":"Sun R, Lampert C. KS(conf): A light-weight test if a ConvNet operates outside of Its specifications. In: Vol 11269. Springer Nature; 2019:244-259. doi:10.1007/978-3-030-12939-2_18","ista":"Sun R, Lampert C. 2019. KS(conf): A light-weight test if a ConvNet operates outside of Its specifications. GCPR: Conference on Pattern Recognition, LNCS, vol. 11269, 244–259.","short":"R. Sun, C. Lampert, in:, Springer Nature, 2019, pp. 244–259.","chicago":"Sun, Rémy, and Christoph Lampert. “KS(Conf): A Light-Weight Test If a ConvNet Operates Outside of Its Specifications,” 11269:244–59. Springer Nature, 2019. https://doi.org/10.1007/978-3-030-12939-2_18.","apa":"Sun, R., & Lampert, C. (2019). KS(conf): A light-weight test if a ConvNet operates outside of Its specifications (Vol. 11269, pp. 244–259). Presented at the GCPR: Conference on Pattern Recognition, Stuttgart, Germany: Springer Nature. https://doi.org/10.1007/978-3-030-12939-2_18","ieee":"R. Sun and C. Lampert, “KS(conf): A light-weight test if a ConvNet operates outside of Its specifications,” presented at the GCPR: Conference on Pattern Recognition, Stuttgart, Germany, 2019, vol. 11269, pp. 244–259."},"status":"public","volume":11269,"date_created":"2019-05-24T09:48:36Z","scopus_import":"1","quality_controlled":"1","related_material":{"record":[{"relation":"later_version","status":"public","id":"6944"}]},"language":[{"iso":"eng"}],"title":"KS(conf): A light-weight test if a ConvNet operates outside of Its specifications","type":"conference","year":"2019","main_file_link":[{"url":"https://arxiv.org/abs/1804.04171","open_access":"1"}],"date_updated":"2025-04-15T07:10:25Z","month":"02","oa_version":"Preprint","oa":1,"doi":"10.1007/978-3-030-12939-2_18","article_processing_charge":"No","abstract":[{"lang":"eng","text":"Computer vision systems for automatic image categorization have become accurate and reliable enough that they can run continuously for days or even years as components of real-world commercial applications. A major open problem in this context, however, is quality control. Good classification performance can only be expected if systems run under the specific conditions, in particular data distributions, that they were trained for. Surprisingly, none of the currently used deep network architectures have a built-in functionality that could detect if a network operates on data from a distribution it was not trained for, such that potentially a warning to the human users could be triggered. In this work, we describe KS(conf), a procedure for detecting such outside of specifications (out-of-specs) operation, based on statistical testing of the network outputs. We show by extensive experiments using the ImageNet, AwA2 and DAVIS datasets on a variety of ConvNets architectures that KS(conf) reliably detects out-of-specs situations. It furthermore has a number of properties that make it a promising candidate for practical deployment: it is easy to implement, adds almost no overhead to the system, works with all networks, including pretrained ones, and requires no a priori knowledge of how the data distribution could change. "}],"publication_status":"published","_id":"6482","author":[{"full_name":"Sun, Rémy","first_name":"Rémy","last_name":"Sun"},{"last_name":"Lampert","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","first_name":"Christoph","orcid":"0000-0001-8622-7887","full_name":"Lampert, Christoph"}],"publisher":"Springer Nature","external_id":{"arxiv":["1804.04171"]},"project":[{"name":"Lifelong Learning of Visual Scene Understanding","_id":"2532554C-B435-11E9-9278-68D0E5697425","grant_number":"308036","call_identifier":"FP7"}],"conference":{"end_date":"2018-10-12","name":"GCPR: Conference on Pattern Recognition","start_date":"2018-10-09","location":"Stuttgart, Germany"},"day":"14","ec_funded":1},{"month":"02","date_updated":"2024-12-11T11:42:22Z","date_published":"2019-02-01T00:00:00Z","page":"417-418","publication_identifier":{"isbn":["9781450362252"]},"department":[{"_id":"DaAl"}],"isi":1,"oa_version":"None","day":"01","conference":{"name":"PPoPP: Principles and Practice of Parallel Programming","start_date":"2019-02-16","location":"Washington, NY, United States","end_date":"2019-02-20"},"quality_controlled":"1","_id":"6485","date_created":"2019-05-24T10:09:12Z","publication_status":"published","publisher":"ACM","author":[{"first_name":"Nikita","full_name":"Koval, Nikita","last_name":"Koval","id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian"},{"first_name":"Roman","full_name":"Elizarov, Roman","last_name":"Elizarov"}],"external_id":{"isi":["000587604600044"]},"abstract":[{"lang":"eng","text":"Traditional concurrent programming involves manipulating shared mutable state. Alternatives to this programming style are communicating sequential processes (CSP) [1] and actor [2] models, which share data via explicit communication. Rendezvous channelis the common abstraction for communication between several processes, where senders and receivers perform a rendezvous handshake as a part of their protocol (senders wait for receivers and vice versa). Additionally to this, channels support the select expression. In this work, we present the first efficient lock-free channel algorithm, and compare it against Go [3] and Kotlin [4] baseline implementations."}],"article_processing_charge":"No","status":"public","doi":"10.1145/3293883.3297000","citation":{"ista":"Koval N, Alistarh D-A, Elizarov R. 2019. Lock-free channels for programming via communicating sequential processes, ACM,p.","short":"N. Koval, D.-A. Alistarh, R. Elizarov, Lock-Free Channels for Programming via Communicating Sequential Processes, ACM, 2019.","mla":"Koval, Nikita, et al. “Lock-Free Channels for Programming via Communicating Sequential Processes.” Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming, ACM, 2019, pp. 417–18, doi:10.1145/3293883.3297000.","ama":"Koval N, Alistarh D-A, Elizarov R. Lock-Free Channels for Programming via Communicating Sequential Processes. ACM; 2019:417-418. doi:10.1145/3293883.3297000","apa":"Koval, N., Alistarh, D.-A., & Elizarov, R. (2019). Lock-free channels for programming via communicating sequential processes. Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming (pp. 417–418). Washington, NY, United States: ACM. https://doi.org/10.1145/3293883.3297000","ieee":"N. Koval, D.-A. Alistarh, and R. Elizarov, Lock-free channels for programming via communicating sequential processes. ACM, 2019, pp. 417–418.","chicago":"Koval, Nikita, Dan-Adrian Alistarh, and Roman Elizarov. Lock-Free Channels for Programming via Communicating Sequential Processes. Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming. ACM, 2019. https://doi.org/10.1145/3293883.3297000."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference_poster","year":"2019","title":"Lock-free channels for programming via communicating sequential processes","publication":"Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming","language":[{"iso":"eng"}]},{"year":"2019","type":"conference","title":"Membership-based synthesis of linear hybrid automata","corr_author":"1","publication":"31st International Conference on Computer-Aided Verification","language":[{"iso":"eng"}],"file":[{"creator":"dernst","file_id":"6817","access_level":"open_access","date_updated":"2020-07-14T12:47:32Z","date_created":"2019-08-14T11:05:30Z","content_type":"application/pdf","relation":"main_file","file_size":674795,"checksum":"1f1d61b83a151031745ef70a501da3d6","file_name":"2019_CAV_GarciaSoto.pdf"}],"quality_controlled":"1","scopus_import":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_created":"2019-05-27T07:09:53Z","volume":11561,"status":"public","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"chicago":"Garcia Soto, Miriam, Thomas A Henzinger, Christian Schilling, and Luka Zeleznik. “Membership-Based Synthesis of Linear Hybrid Automata.” In 31st International Conference on Computer-Aided Verification, 11561:297–314. Springer, 2019. https://doi.org/10.1007/978-3-030-25540-4_16.","apa":"Garcia Soto, M., Henzinger, T. A., Schilling, C., & Zeleznik, L. (2019). Membership-based synthesis of linear hybrid automata. In 31st International Conference on Computer-Aided Verification (Vol. 11561, pp. 297–314). New York City, NY, USA: Springer. https://doi.org/10.1007/978-3-030-25540-4_16","ieee":"M. Garcia Soto, T. A. Henzinger, C. Schilling, and L. Zeleznik, “Membership-based synthesis of linear hybrid automata,” in 31st International Conference on Computer-Aided Verification, New York City, NY, USA, 2019, vol. 11561, pp. 297–314.","mla":"Garcia Soto, Miriam, et al. “Membership-Based Synthesis of Linear Hybrid Automata.” 31st International Conference on Computer-Aided Verification, vol. 11561, Springer, 2019, pp. 297–314, doi:10.1007/978-3-030-25540-4_16.","ama":"Garcia Soto M, Henzinger TA, Schilling C, Zeleznik L. Membership-based synthesis of linear hybrid automata. In: 31st International Conference on Computer-Aided Verification. Vol 11561. Springer; 2019:297-314. doi:10.1007/978-3-030-25540-4_16","ista":"Garcia Soto M, Henzinger TA, Schilling C, Zeleznik L. 2019. Membership-based synthesis of linear hybrid automata. 31st International Conference on Computer-Aided Verification. CAV: Computer-Aided Verification, LNCS, vol. 11561, 297–314.","short":"M. Garcia Soto, T.A. Henzinger, C. Schilling, L. Zeleznik, in:, 31st International Conference on Computer-Aided Verification, Springer, 2019, pp. 297–314."},"publication_identifier":{"isbn":["9783030255398"],"issn":["0302-9743"]},"department":[{"_id":"ToHe"}],"isi":1,"intvolume":" 11561","date_published":"2019-07-12T00:00:00Z","alternative_title":["LNCS"],"page":"297-314","ddc":["000"],"ec_funded":1,"conference":{"end_date":"2019-07-18","location":"New York City, NY, USA","start_date":"2019-07-15","name":"CAV: Computer-Aided Verification"},"day":"12","project":[{"grant_number":"754411","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425"},{"grant_number":"S 11407_N23","call_identifier":"FWF","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","grant_number":"Z211","name":"Formal methods for the design and analysis of complex systems","_id":"25F42A32-B435-11E9-9278-68D0E5697425"}],"publisher":"Springer","_id":"6493","author":[{"orcid":"0000−0003−2936−5719","full_name":"Garcia Soto, Miriam","first_name":"Miriam","last_name":"Garcia Soto","id":"4B3207F6-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","first_name":"Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"id":"3A2F4DCE-F248-11E8-B48F-1D18A9856A87","last_name":"Schilling","first_name":"Christian","full_name":"Schilling, Christian","orcid":"0000-0003-3658-1065"},{"last_name":"Zeleznik","id":"3ADCA2E4-F248-11E8-B48F-1D18A9856A87","full_name":"Zeleznik, Luka","first_name":"Luka"}],"publication_status":"published","external_id":{"isi":["000491468000016"]},"abstract":[{"lang":"eng","text":"We present two algorithmic approaches for synthesizing linear hybrid automata from experimental data. Unlike previous approaches, our algorithms work without a template and generate an automaton with nondeterministic guards and invariants, and with an arbitrary number and topology of modes. They thus construct a succinct model from the data and provide formal guarantees. In particular, (1) the generated automaton can reproduce the data up to a specified tolerance and (2) the automaton is tight, given the first guarantee. Our first approach encodes the synthesis problem as a logical formula in the theory of linear arithmetic, which can then be solved by an SMT solver. This approach minimizes the number of modes in the resulting model but is only feasible for limited data sets. To address scalability, we propose a second approach that does not enforce to find a minimal model. The algorithm constructs an initial automaton and then iteratively extends the automaton based on processing new data. Therefore the algorithm is well-suited for online and synthesis-in-the-loop applications. The core of the algorithm is a membership query that checks whether, within the specified tolerance, a given data set can result from the execution of a given automaton. We solve this membership problem for linear hybrid automata by repeated reachability computations. We demonstrate the effectiveness of the algorithm on synthetic data sets and on cardiac-cell measurements."}],"article_processing_charge":"No","doi":"10.1007/978-3-030-25540-4_16","oa":1,"oa_version":"Published Version","keyword":["Synthesis","Linear hybrid automaton","Membership"],"file_date_updated":"2020-07-14T12:47:32Z","month":"07","date_updated":"2025-04-15T06:26:13Z","has_accepted_license":"1"},{"oa":1,"file_date_updated":"2020-07-14T12:47:33Z","oa_version":"Published Version","month":"01","date_updated":"2025-07-10T11:53:29Z","has_accepted_license":"1","main_file_link":[{"url":"https://eprint.iacr.org/2018/627","open_access":"1"}],"ddc":["000"],"ec_funded":1,"conference":{"end_date":"2019-01-12","name":"ITCS: Innovations in Theoretical Computer Science","location":"San Diego, CA, United States","start_date":"2019-01-10"},"day":"10","project":[{"grant_number":"682815","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"_id":"6528","author":[{"first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak"}],"publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","article_processing_charge":"No","abstract":[{"lang":"eng","text":"We construct a verifiable delay function (VDF) by showing how the Rivest-Shamir-Wagner time-lock puzzle can be made publicly verifiable. Concretely, we give a statistically sound public-coin protocol to prove that a tuple (N,x,T,y) satisfies y=x2T (mod N) where the prover doesn’t know the factorization of N and its running time is dominated by solving the puzzle, that is, compute x2T, which is conjectured to require T sequential squarings. To get a VDF we make this protocol non-interactive using the Fiat-Shamir heuristic.The motivation for this work comes from the Chia blockchain design, which uses a VDF as akey ingredient. For typical parameters (T≤2 40, N= 2048), our proofs are of size around 10K B, verification cost around three RSA exponentiations and computing the proof is 8000 times faster than solving the puzzle even without any parallelism."}],"doi":"10.4230/LIPICS.ITCS.2019.60","department":[{"_id":"KrPi"}],"publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-095-8"]},"intvolume":" 124","article_number":"60","date_published":"2019-01-10T00:00:00Z","alternative_title":["LIPIcs"],"type":"conference","year":"2019","title":"Simple verifiable delay functions","publication":"10th Innovations in Theoretical Computer Science Conference","language":[{"iso":"eng"}],"file":[{"access_level":"open_access","file_id":"6529","creator":"dernst","file_name":"2019_LIPIcs_Pietrzak.pdf","checksum":"f0ae1bb161431d9db3dea5ace082bfb5","file_size":558770,"relation":"main_file","content_type":"application/pdf","date_created":"2019-06-06T14:22:04Z","date_updated":"2020-07-14T12:47:33Z"}],"scopus_import":"1","quality_controlled":"1","date_created":"2019-06-06T14:12:36Z","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"volume":124,"status":"public","citation":{"short":"K.Z. Pietrzak, in:, 10th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.","ista":"Pietrzak KZ. 2019. Simple verifiable delay functions. 10th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 124, 60.","mla":"Pietrzak, Krzysztof Z. “Simple Verifiable Delay Functions.” 10th Innovations in Theoretical Computer Science Conference, vol. 124, 60, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, doi:10.4230/LIPICS.ITCS.2019.60.","ama":"Pietrzak KZ. Simple verifiable delay functions. In: 10th Innovations in Theoretical Computer Science Conference. Vol 124. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:10.4230/LIPICS.ITCS.2019.60","apa":"Pietrzak, K. Z. (2019). Simple verifiable delay functions. In 10th Innovations in Theoretical Computer Science Conference (Vol. 124). San Diego, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ITCS.2019.60","ieee":"K. Z. Pietrzak, “Simple verifiable delay functions,” in 10th Innovations in Theoretical Computer Science Conference, San Diego, CA, United States, 2019, vol. 124.","chicago":"Pietrzak, Krzysztof Z. “Simple Verifiable Delay Functions.” In 10th Innovations in Theoretical Computer Science Conference, Vol. 124. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.ITCS.2019.60."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-104-7"]},"department":[{"_id":"UlWa"}],"intvolume":" 129","arxiv":1,"page":"44:1-44:20","date_published":"2019-06-01T00:00:00Z","alternative_title":["LIPIcs"],"year":"2019","type":"conference","language":[{"iso":"eng"}],"file":[{"file_id":"6557","access_level":"open_access","creator":"kschuh","relation":"main_file","file_size":905885,"file_name":"2019_LIPIcs-Huszar.pdf","checksum":"29d18c435368468aa85823dabb157e43","date_created":"2019-06-12T06:45:33Z","date_updated":"2020-07-14T12:47:33Z","content_type":"application/pdf"}],"title":"3-manifold triangulations with small treewidth","corr_author":"1","publication":"35th International Symposium on Computational Geometry","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_created":"2019-06-11T20:09:57Z","related_material":{"record":[{"id":"8032","status":"public","relation":"part_of_dissertation"}]},"scopus_import":"1","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ieee":"K. Huszár and J. Spreer, “3-manifold triangulations with small treewidth,” in 35th International Symposium on Computational Geometry, Portland, Oregon, United States, 2019, vol. 129, p. 44:1-44:20.","apa":"Huszár, K., & Spreer, J. (2019). 3-manifold triangulations with small treewidth. In 35th International Symposium on Computational Geometry (Vol. 129, p. 44:1-44:20). Portland, Oregon, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2019.44","chicago":"Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small Treewidth.” In 35th International Symposium on Computational Geometry, 129:44:1-44:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPIcs.SoCG.2019.44.","ista":"Huszár K, Spreer J. 2019. 3-manifold triangulations with small treewidth. 35th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 129, 44:1-44:20.","short":"K. Huszár, J. Spreer, in:, 35th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20.","ama":"Huszár K, Spreer J. 3-manifold triangulations with small treewidth. In: 35th International Symposium on Computational Geometry. Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:44:1-44:20. doi:10.4230/LIPIcs.SoCG.2019.44","mla":"Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small Treewidth.” 35th International Symposium on Computational Geometry, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20, doi:10.4230/LIPIcs.SoCG.2019.44."},"volume":129,"status":"public","oa":1,"file_date_updated":"2020-07-14T12:47:33Z","keyword":["computational 3-manifold topology","fixed-parameter tractability","layered triangulations","structural graph theory","treewidth","cutwidth","Heegaard genus"],"oa_version":"Published Version","date_updated":"2026-04-08T07:21:27Z","has_accepted_license":"1","month":"06","ddc":["516"],"external_id":{"arxiv":["1812.05528"]},"_id":"6556","author":[{"full_name":"Huszár, Kristóf","orcid":"0000-0002-5445-5057","first_name":"Kristóf","id":"33C26278-F248-11E8-B48F-1D18A9856A87","last_name":"Huszár"},{"last_name":"Spreer","full_name":"Spreer, Jonathan","first_name":"Jonathan"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","day":"01","conference":{"end_date":"2019-06-21","name":"SoCG: Symposium on Computational Geometry","start_date":"2019-06-18","location":"Portland, Oregon, United States"},"article_processing_charge":"No","abstract":[{"lang":"eng","text":"Motivated by fixed-parameter tractable (FPT) problems in computational topology, we consider the treewidth tw(M) of a compact, connected 3-manifold M, defined to be the minimum treewidth of the face pairing graph of any triangulation T of M. In this setting the relationship between the topology of a 3-manifold and its treewidth is of particular interest. First, as a corollary of work of Jaco and Rubinstein, we prove that for any closed, orientable 3-manifold M the treewidth tw(M) is at most 4g(M)-2, where g(M) denotes Heegaard genus of M. In combination with our earlier work with Wagner, this yields that for non-Haken manifolds the Heegaard genus and the treewidth are within a constant factor. Second, we characterize all 3-manifolds of treewidth one: These are precisely the lens spaces and a single other Seifert fibered space. Furthermore, we show that all remaining orientable Seifert fibered spaces over the 2-sphere or a non-orientable surface have treewidth two. In particular, for every spherical 3-manifold we exhibit a triangulation of treewidth at most two. Our results further validate the parameter of treewidth (and other related parameters such as cutwidth or congestion) to be useful for topological computing, and also shed more light on the scope of existing FPT-algorithms in the field."}],"doi":"10.4230/LIPIcs.SoCG.2019.44"},{"day":"01","conference":{"end_date":"2019-06-21","start_date":"2019-06-18","location":"Portland, OR, United States","name":"SoCG 2019: Symposium on Computational Geometry"},"project":[{"call_identifier":"FWF","grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425","name":"Eliminating intersections in drawings of graphs"}],"_id":"6647","publication_status":"published","external_id":{"arxiv":["1812.04911"]},"author":[{"first_name":"Radoslav","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Bernd","full_name":"Gärtner, Bernd","last_name":"Gärtner"},{"full_name":"Kupavskii, Andrey","first_name":"Andrey","last_name":"Kupavskii"},{"full_name":"Valtr, Pavel","first_name":"Pavel","last_name":"Valtr"},{"first_name":"Uli","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","abstract":[{"text":"The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r-1)+1 points in R^d, one can find a partition X=X_1 cup ... cup X_r of X, such that the convex hulls of the X_i, i=1,...,r, all share a common point. In this paper, we prove a strengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span floor[n/3] vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Alvarez-Rebollar et al. guarantees floor[n/6] pairwise crossing triangles. Our result generalizes to a result about simplices in R^d,d >=2.","lang":"eng"}],"doi":"10.4230/LIPICS.SOCG.2019.38","ddc":["000","510"],"month":"06","date_updated":"2025-04-14T13:52:36Z","has_accepted_license":"1","oa":1,"oa_version":"Published Version","file_date_updated":"2020-07-14T12:47:35Z","related_material":{"record":[{"id":"13974","status":"public","relation":"later_version"}]},"quality_controlled":"1","scopus_import":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_created":"2019-07-17T10:35:04Z","volume":129,"status":"public","citation":{"chicago":"Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner. “The Crossing Tverberg Theorem.” In 35th International Symposium on Computational Geometry, 129:38:1-38:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.SOCG.2019.38.","ieee":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing Tverberg theorem,” in 35th International Symposium on Computational Geometry, Portland, OR, United States, 2019, vol. 129, p. 38:1-38:13.","apa":"Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., & Wagner, U. (2019). The crossing Tverberg theorem. In 35th International Symposium on Computational Geometry (Vol. 129, p. 38:1-38:13). Portland, OR, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.SOCG.2019.38","ama":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg theorem. In: 35th International Symposium on Computational Geometry. Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:38:1-38:13. doi:10.4230/LIPICS.SOCG.2019.38","mla":"Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” 35th International Symposium on Computational Geometry, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 38:1-38:13, doi:10.4230/LIPICS.SOCG.2019.38.","ista":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2019. The crossing Tverberg theorem. 35th International Symposium on Computational Geometry. SoCG 2019: Symposium on Computational Geometry, LIPIcs, vol. 129, 38:1-38:13.","short":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, in:, 35th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 38:1-38:13."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2019","type":"conference","title":"The crossing Tverberg theorem","publication":"35th International Symposium on Computational Geometry","corr_author":"1","language":[{"iso":"eng"}],"file":[{"creator":"dernst","access_level":"open_access","file_id":"6667","date_updated":"2020-07-14T12:47:35Z","date_created":"2019-07-24T06:54:52Z","content_type":"application/pdf","file_size":559837,"relation":"main_file","checksum":"d6d017f8b41291b94d102294fa96ae9c","file_name":"2019_LIPICS_Fulek.pdf"}],"intvolume":" 129","date_published":"2019-06-01T00:00:00Z","alternative_title":["LIPIcs"],"arxiv":1,"page":"38:1-38:13","department":[{"_id":"UlWa"}],"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771047"]}},{"intvolume":" 65","date_published":"2019-05-01T00:00:00Z","page":"2782-2791","arxiv":1,"issue":"5","type":"journal_article","year":"2019","title":"Construction of polar codes with sublinear complexity","publication":"IEEE","language":[{"iso":"eng"}],"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"6729"}]},"quality_controlled":"1","date_created":"2019-07-23T07:32:57Z","volume":65,"status":"public","citation":{"ama":"Mondelli M, Hassani H, Urbanke R. Construction of polar codes with sublinear complexity. IEEE. 2019;65(5):2782-2791. doi:10.1109/tit.2018.2889667","mla":"Mondelli, Marco, et al. “Construction of Polar Codes with Sublinear Complexity.” IEEE, vol. 65, no. 5, IEEE, 2019, pp. 2782–91, doi:10.1109/tit.2018.2889667.","ista":"Mondelli M, Hassani H, Urbanke R. 2019. Construction of polar codes with sublinear complexity. IEEE. 65(5), 2782–2791.","short":"M. Mondelli, H. Hassani, R. Urbanke, IEEE 65 (2019) 2782–2791.","chicago":"Mondelli, Marco, Hamed Hassani, and Rudiger Urbanke. “Construction of Polar Codes with Sublinear Complexity.” IEEE. IEEE, 2019. https://doi.org/10.1109/tit.2018.2889667.","ieee":"M. Mondelli, H. Hassani, and R. Urbanke, “Construction of polar codes with sublinear complexity,” IEEE, vol. 65, no. 5. IEEE, pp. 2782–2791, 2019.","apa":"Mondelli, M., Hassani, H., & Urbanke, R. (2019). Construction of polar codes with sublinear complexity. IEEE. IEEE. https://doi.org/10.1109/tit.2018.2889667"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"oa_version":"Preprint","month":"05","date_updated":"2023-02-23T12:50:20Z","main_file_link":[{"url":"https://arxiv.org/abs/1612.05295","open_access":"1"}],"day":"01","extern":"1","publisher":"IEEE","external_id":{"arxiv":["1612.05295"]},"publication_status":"published","_id":"6663","author":[{"full_name":"Mondelli, Marco","orcid":"0000-0002-3242-7020","first_name":"Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","last_name":"Mondelli"},{"last_name":"Hassani","first_name":"Hamed","full_name":"Hassani, Hamed"},{"full_name":"Urbanke, Rudiger","first_name":"Rudiger","last_name":"Urbanke"}],"abstract":[{"text":"Consider the problem of constructing a polar code of block length N for a given transmission channel W. Previous approaches require one to compute the reliability of the N synthetic channels and then use only those that are sufficiently reliable. However, we know from two independent works by Schürch and by Bardet et al. that the synthetic channels are partially ordered with respect to degradation. Hence, it is natural to ask whether the partial order can be exploited to reduce the computational burden of the construction problem. We show that, if we take advantage of the partial order, we can construct a polar code by computing the reliability of roughly a fraction 1/ log 3/2 N of the synthetic channels. In particular, we prove that N/ log 3/2 N is a lower bound on the number of synthetic channels to be considered and such a bound is tight up to a multiplicative factor log log N. This set of roughly N/ log 3/2 N synthetic channels is universal, in the sense that it allows one to construct polar codes for any W, and it can be identified by solving a maximum matching problem on a bipartite graph. Our proof technique consists of reducing the construction problem to the problem of computing the maximum cardinality of an antichain for a suitable partially ordered set. As such, this method is general, and it can be used to further improve the complexity of the construction problem, in case a refined partial order on the synthetic channels of polar codes is discovered.","lang":"eng"}],"doi":"10.1109/tit.2018.2889667"},{"date_published":"2019-05-21T00:00:00Z","page":"1046-1097","arxiv":1,"intvolume":" 48","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"volume":48,"status":"public","citation":{"mla":"Boissonnat, Jean-Daniel, et al. “Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams.” SIAM Journal on Computing, vol. 48, no. 3, Society for Industrial & Applied Mathematics (SIAM), 2019, pp. 1046–97, doi:10.1137/17m1152292.","ama":"Boissonnat J-D, Rouxel-Labbé M, Wintraecken M. Anisotropic triangulations via discrete Riemannian Voronoi diagrams. SIAM Journal on Computing. 2019;48(3):1046-1097. doi:10.1137/17m1152292","ista":"Boissonnat J-D, Rouxel-Labbé M, Wintraecken M. 2019. Anisotropic triangulations via discrete Riemannian Voronoi diagrams. SIAM Journal on Computing. 48(3), 1046–1097.","short":"J.-D. Boissonnat, M. Rouxel-Labbé, M. Wintraecken, SIAM Journal on Computing 48 (2019) 1046–1097.","chicago":"Boissonnat, Jean-Daniel, Mael Rouxel-Labbé, and Mathijs Wintraecken. “Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics (SIAM), 2019. https://doi.org/10.1137/17m1152292.","apa":"Boissonnat, J.-D., Rouxel-Labbé, M., & Wintraecken, M. (2019). Anisotropic triangulations via discrete Riemannian Voronoi diagrams. SIAM Journal on Computing. Society for Industrial & Applied Mathematics (SIAM). https://doi.org/10.1137/17m1152292","ieee":"J.-D. Boissonnat, M. Rouxel-Labbé, and M. Wintraecken, “Anisotropic triangulations via discrete Riemannian Voronoi diagrams,” SIAM Journal on Computing, vol. 48, no. 3. Society for Industrial & Applied Mathematics (SIAM), pp. 1046–1097, 2019."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","date_created":"2019-07-24T08:42:12Z","title":"Anisotropic triangulations via discrete Riemannian Voronoi diagrams","publication":"SIAM Journal on Computing","language":[{"iso":"eng"}],"type":"journal_article","issue":"3","year":"2019","main_file_link":[{"url":"https://arxiv.org/abs/1703.06487","open_access":"1"}],"month":"05","date_updated":"2021-01-12T08:08:30Z","oa_version":"Preprint","oa":1,"abstract":[{"text":"The construction of anisotropic triangulations is desirable for various applications, such as the numerical solving of partial differential equations and the representation of surfaces in graphics. To solve this notoriously difficult problem in a practical way, we introduce the discrete Riemannian Voronoi diagram, a discrete structure that approximates the Riemannian Voronoi diagram. This structure has been implemented and was shown to lead to good triangulations in $\\mathbb{R}^2$ and on surfaces embedded in $\\mathbb{R}^3$ as detailed in our experimental companion paper. In this paper, we study theoretical aspects of our structure. Given a finite set of points $\\mathcal{P}$ in a domain $\\Omega$ equipped with a Riemannian metric, we compare the discrete Riemannian Voronoi diagram of $\\mathcal{P}$ to its Riemannian Voronoi diagram. Both diagrams have dual structures called the discrete Riemannian Delaunay and the Riemannian Delaunay complex. We provide conditions that guarantee that these dual structures are identical. It then follows from previous results that the discrete Riemannian Delaunay complex can be embedded in $\\Omega$ under sufficient conditions, leading to an anisotropic triangulation with curved simplices. Furthermore, we show that, under similar conditions, the simplices of this triangulation can be straightened.","lang":"eng"}],"doi":"10.1137/17m1152292","day":"21","extern":"1","author":[{"first_name":"Jean-Daniel","full_name":"Boissonnat, Jean-Daniel","last_name":"Boissonnat"},{"full_name":"Rouxel-Labbé, Mael","first_name":"Mael","last_name":"Rouxel-Labbé"},{"id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","last_name":"Wintraecken","full_name":"Wintraecken, Mathijs","orcid":"0000-0002-7472-2220","first_name":"Mathijs"}],"external_id":{"arxiv":["1703.06487"]},"publisher":"Society for Industrial & Applied Mathematics (SIAM)","publication_status":"published","_id":"6672"},{"oa_version":"Published Version","file_date_updated":"2020-07-14T12:47:37Z","oa":1,"month":"08","date_updated":"2026-04-16T12:20:40Z","has_accepted_license":"1","ddc":["514"],"article_processing_charge":"No","abstract":[{"lang":"eng","text":"The first part of the thesis considers the computational aspects of the homotopy groups πd(X) of a topological space X. It is well known that there is no algorithm to decide whether the fundamental group π1(X) of a given finite simplicial complex X is trivial. On the other hand, there are several algorithms that, given a finite simplicial complex X that is simply connected (i.e., with π1(X) trivial), compute the higher homotopy group πd(X) for any given d ≥ 2.\r\nHowever, these algorithms come with a caveat: They compute the isomorphism type of πd(X), d ≥ 2 as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of πd(X). We present an algorithm that, given a simply connected space X, computes πd(X) and represents its elements as simplicial maps from suitable triangulations of the d-sphere Sd to X. For fixed d, the algorithm runs in time exponential in size(X), the number of simplices of X. Moreover, we prove that this is optimal: For every fixed d ≥ 2,\r\nwe construct a family of simply connected spaces X such that for any simplicial map representing a generator of πd(X), the size of the triangulation of S d on which the map is defined, is exponential in size(X).\r\nIn the second part of the thesis, we prove that the following question is algorithmically undecidable for d < ⌊3(k+1)/2⌋, k ≥ 5 and (k, d) ̸= (5, 7), which covers essentially everything outside the meta-stable range: Given a finite simplicial complex K of dimension k, decide whether there exists a piecewise-linear (i.e., linear on an arbitrarily fine subdivision of K) embedding f : K ↪→ Rd of K into a d-dimensional Euclidean space."}],"doi":"10.15479/AT:ISTA:6681","day":"08","publication_status":"published","_id":"6681","author":[{"id":"3AA52972-F248-11E8-B48F-1D18A9856A87","last_name":"Zhechev","full_name":"Zhechev, Stephan Y","first_name":"Stephan Y"}],"publisher":"Institute of Science and Technology Austria","OA_place":"publisher","supervisor":[{"first_name":"Uli","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner"}],"department":[{"_id":"UlWa"}],"publication_identifier":{"issn":["2663-337X"]},"date_published":"2019-08-08T00:00:00Z","alternative_title":["ISTA Thesis"],"page":"104","title":"Algorithmic aspects of homotopy theory and embeddability","corr_author":"1","language":[{"iso":"eng"}],"file":[{"creator":"szhechev","file_id":"6771","access_level":"open_access","date_created":"2019-08-07T13:02:50Z","date_updated":"2020-07-14T12:47:37Z","content_type":"application/pdf","relation":"main_file","file_size":1464227,"file_name":"Stephan_Zhechev_thesis.pdf","checksum":"3231e7cbfca3b5687366f84f0a57a0c0"},{"content_type":"application/octet-stream","date_updated":"2020-07-14T12:47:37Z","date_created":"2019-08-07T13:03:22Z","checksum":"85d65eb27b4377a9e332ee37a70f08b6","file_name":"Stephan_Zhechev_thesis.tex","file_size":303988,"relation":"source_file","creator":"szhechev","access_level":"closed","file_id":"6772"},{"access_level":"closed","file_id":"6773","creator":"szhechev","file_name":"supplementary_material.zip","checksum":"86b374d264ca2dd53e712728e253ee75","file_size":1087004,"relation":"supplementary_material","content_type":"application/zip","date_created":"2019-08-07T13:03:34Z","date_updated":"2020-07-14T12:47:37Z"}],"type":"dissertation","year":"2019","status":"public","citation":{"apa":"Zhechev, S. Y. (2019). Algorithmic aspects of homotopy theory and embeddability. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:6681","ieee":"S. Y. Zhechev, “Algorithmic aspects of homotopy theory and embeddability,” Institute of Science and Technology Austria, 2019.","chicago":"Zhechev, Stephan Y. “Algorithmic Aspects of Homotopy Theory and Embeddability.” Institute of Science and Technology Austria, 2019. https://doi.org/10.15479/AT:ISTA:6681.","short":"S.Y. Zhechev, Algorithmic Aspects of Homotopy Theory and Embeddability, Institute of Science and Technology Austria, 2019.","ista":"Zhechev SY. 2019. Algorithmic aspects of homotopy theory and embeddability. Institute of Science and Technology Austria.","mla":"Zhechev, Stephan Y. Algorithmic Aspects of Homotopy Theory and Embeddability. Institute of Science and Technology Austria, 2019, doi:10.15479/AT:ISTA:6681.","ama":"Zhechev SY. Algorithmic aspects of homotopy theory and embeddability. 2019. doi:10.15479/AT:ISTA:6681"},"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","degree_awarded":"PhD","related_material":{"record":[{"relation":"part_of_dissertation","id":"6774","status":"public"}]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_created":"2019-07-26T11:14:34Z"},{"quality_controlled":"1","scopus_import":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_created":"2019-07-29T12:23:29Z","status":"public","volume":132,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Kolmogorov, Vladimir. “Testing the Complexity of a Valued CSP Language.” In 46th International Colloquium on Automata, Languages and Programming, 132:77:1-77:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.ICALP.2019.77.","apa":"Kolmogorov, V. (2019). Testing the complexity of a valued CSP language. In 46th International Colloquium on Automata, Languages and Programming (Vol. 132, p. 77:1-77:12). Patras, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ICALP.2019.77","ieee":"V. Kolmogorov, “Testing the complexity of a valued CSP language,” in 46th International Colloquium on Automata, Languages and Programming, Patras, Greece, 2019, vol. 132, p. 77:1-77:12.","mla":"Kolmogorov, Vladimir. “Testing the Complexity of a Valued CSP Language.” 46th International Colloquium on Automata, Languages and Programming, vol. 132, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 77:1-77:12, doi:10.4230/LIPICS.ICALP.2019.77.","ama":"Kolmogorov V. Testing the complexity of a valued CSP language. In: 46th International Colloquium on Automata, Languages and Programming. Vol 132. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:77:1-77:12. doi:10.4230/LIPICS.ICALP.2019.77","short":"V. Kolmogorov, in:, 46th International Colloquium on Automata, Languages and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 77:1-77:12.","ista":"Kolmogorov V. 2019. Testing the complexity of a valued CSP language. 46th International Colloquium on Automata, Languages and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 132, 77:1-77:12."},"year":"2019","type":"conference","publication":"46th International Colloquium on Automata, Languages and Programming","title":"Testing the complexity of a valued CSP language","file":[{"file_id":"6738","access_level":"open_access","creator":"dernst","checksum":"f5ebee8eec6ae09e30365578ee63a492","file_name":"2019_LIPICS_Kolmogorov.pdf","file_size":575475,"relation":"main_file","content_type":"application/pdf","date_updated":"2020-07-14T12:47:38Z","date_created":"2019-07-31T07:01:45Z"}],"language":[{"iso":"eng"}],"intvolume":" 132","alternative_title":["LIPIcs"],"date_published":"2019-07-01T00:00:00Z","arxiv":1,"page":"77:1-77:12","department":[{"_id":"VlKo"}],"publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-109-2"]},"project":[{"name":"Discrete Optimization in Computer Vision: Theory and Practice","_id":"25FBA906-B435-11E9-9278-68D0E5697425","grant_number":"616160","call_identifier":"FP7"}],"day":"01","conference":{"start_date":"2019-07-08","location":"Patras, Greece","name":"ICALP: Automata, Languages and Programming","end_date":"2019-07-12"},"_id":"6725","author":[{"full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","external_id":{"arxiv":["1803.02289"]},"publication_status":"published","doi":"10.4230/LIPICS.ICALP.2019.77","article_processing_charge":"No","abstract":[{"lang":"eng","text":"A Valued Constraint Satisfaction Problem (VCSP) provides a common framework that can express a wide range of discrete optimization problems. A VCSP instance is given by a finite set of variables, a finite domain of labels, and an objective function to be minimized. This function is represented as a sum of terms where each term depends on a subset of the variables. To obtain different classes of optimization problems, one can restrict all terms to come from a fixed set Γ of cost functions, called a language. \r\nRecent breakthrough results have established a complete complexity classification of such classes with respect to language Γ: if all cost functions in Γ satisfy a certain algebraic condition then all Γ-instances can be solved in polynomial time, otherwise the problem is NP-hard. Unfortunately, testing this condition for a given language Γ is known to be NP-hard. We thus study exponential algorithms for this meta-problem. We show that the tractability condition of a finite-valued language Γ can be tested in O(3‾√3|D|⋅poly(size(Γ))) time, where D is the domain of Γ and poly(⋅) is some fixed polynomial. We also obtain a matching lower bound under the Strong Exponential Time Hypothesis (SETH). More precisely, we prove that for any constant δ<1 there is no O(3‾√3δ|D|) algorithm, assuming that SETH holds."}],"ddc":["000"],"ec_funded":1,"month":"07","has_accepted_license":"1","date_updated":"2025-07-10T11:53:47Z","oa":1,"oa_version":"Published Version","file_date_updated":"2020-07-14T12:47:38Z"},{"month":"06","date_updated":"2025-09-10T10:38:28Z","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/068"}],"oa":1,"editor":[{"full_name":"Buchmann, J","first_name":"J","last_name":"Buchmann"},{"first_name":"A","full_name":"Nitaj, A","last_name":"Nitaj"},{"first_name":"T","full_name":"Rachidi, T","last_name":"Rachidi"}],"oa_version":"Preprint","project":[{"grant_number":"682815","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"day":"29","conference":{"end_date":"2019-07-11","name":"AFRICACRYPT: International Conference on Cryptology in Africa","location":"Rabat, Morocco","start_date":"2019-07-09"},"external_id":{"isi":["001299240700009"]},"_id":"6726","publication_status":"published","author":[{"first_name":"Michael","full_name":"Walter, Michael","orcid":"0000-0003-3186-2482","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","last_name":"Walter"}],"publisher":"Springer Nature","doi":"10.1007/978-3-030-23696-0_9","abstract":[{"lang":"eng","text":"Randomness is an essential part of any secure cryptosystem, but many constructions rely on distributions that are not uniform. This is particularly true for lattice based cryptosystems, which more often than not make use of discrete Gaussian distributions over the integers. For practical purposes it is crucial to evaluate the impact that approximation errors have on the security of a scheme to provide the best possible trade-off between security and performance. Recent years have seen surprising results allowing to use relatively low precision while maintaining high levels of security. A key insight in these results is that sampling a distribution with low relative error can provide very strong security guarantees. Since floating point numbers provide guarantees on the relative approximation error, they seem a suitable tool in this setting, but it is not obvious which sampling algorithms can actually profit from them. While previous works have shown that inversion sampling can be adapted to provide a low relative error (Pöppelmann et al., CHES 2014; Prest, ASIACRYPT 2017), other works have called into question if this is possible for other sampling techniques (Zheng et al., Eprint report 2018/309). In this work, we consider all sampling algorithms that are popular in the cryptographic setting and analyze the relationship of floating point precision and the resulting relative error. We show that all of the algorithms either natively achieve a low relative error or can be adapted to do so."}],"article_processing_charge":"No","place":"Cham","ec_funded":1,"intvolume":" 11627","date_published":"2019-06-29T00:00:00Z","page":"157-180","isi":1,"department":[{"_id":"KrPi"}],"publication_identifier":{"eisbn":["978-3-0302-3696-0"],"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["978-3-0302-3695-3"]},"quality_controlled":"1","scopus_import":"1","series_title":"LNCS","date_created":"2019-07-29T12:25:31Z","status":"public","volume":11627,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","citation":{"chicago":"Walter, Michael. “Sampling the Integers with Low Relative Error.” In Progress in Cryptology – AFRICACRYPT 2019, edited by J Buchmann, A Nitaj, and T Rachidi, 11627:157–80. LNCS. Cham: Springer Nature, 2019. https://doi.org/10.1007/978-3-030-23696-0_9.","ieee":"M. Walter, “Sampling the integers with low relative error,” in Progress in Cryptology – AFRICACRYPT 2019, vol. 11627, J. Buchmann, A. Nitaj, and T. Rachidi, Eds. Cham: Springer Nature, 2019, pp. 157–180.","apa":"Walter, M. (2019). Sampling the integers with low relative error. In J. Buchmann, A. Nitaj, & T. Rachidi (Eds.), Progress in Cryptology – AFRICACRYPT 2019 (Vol. 11627, pp. 157–180). Cham: Springer Nature. https://doi.org/10.1007/978-3-030-23696-0_9","ama":"Walter M. Sampling the integers with low relative error. In: Buchmann J, Nitaj A, Rachidi T, eds. Progress in Cryptology – AFRICACRYPT 2019. Vol 11627. LNCS. Cham: Springer Nature; 2019:157-180. doi:10.1007/978-3-030-23696-0_9","mla":"Walter, Michael. “Sampling the Integers with Low Relative Error.” Progress in Cryptology – AFRICACRYPT 2019, edited by J Buchmann et al., vol. 11627, Springer Nature, 2019, pp. 157–80, doi:10.1007/978-3-030-23696-0_9.","short":"M. Walter, in:, J. Buchmann, A. Nitaj, T. Rachidi (Eds.), Progress in Cryptology – AFRICACRYPT 2019, Springer Nature, Cham, 2019, pp. 157–180.","ista":"Walter M. 2019.Sampling the integers with low relative error. In: Progress in Cryptology – AFRICACRYPT 2019. vol. 11627, 157–180."},"type":"book_chapter","year":"2019","publication":"Progress in Cryptology – AFRICACRYPT 2019","title":"Sampling the integers with low relative error","language":[{"iso":"eng"}]},{"isi":1,"publication_identifier":{"issn":["0004-6361"],"eissn":["1432-0746"]},"department":[{"_id":"HeEd"}],"OA_place":"publisher","intvolume":" 627","article_number":"A163","date_published":"2019-07-17T00:00:00Z","arxiv":1,"year":"2019","type":"journal_article","publication":"Astronomy and Astrophysics","title":"Unexpected topology of the temperature fluctuations in the cosmic microwave background","file":[{"file_id":"6766","access_level":"open_access","creator":"dernst","file_name":"2019_AstronomyAstrophysics_Pranav.pdf","checksum":"83b9209ed9eefbdcefd89019c5a97805","file_size":14420451,"relation":"main_file","content_type":"application/pdf","date_created":"2019-08-05T08:08:59Z","date_updated":"2020-07-14T12:47:39Z"}],"language":[{"iso":"eng"}],"quality_controlled":"1","scopus_import":"1","date_created":"2019-08-04T21:59:18Z","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"status":"public","volume":627,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ama":"Pranav P, Adler RJ, Buchert T, et al. Unexpected topology of the temperature fluctuations in the cosmic microwave background. Astronomy and Astrophysics. 2019;627. doi:10.1051/0004-6361/201834916","mla":"Pranav, Pratyush, et al. “Unexpected Topology of the Temperature Fluctuations in the Cosmic Microwave Background.” Astronomy and Astrophysics, vol. 627, A163, EDP Sciences, 2019, doi:10.1051/0004-6361/201834916.","short":"P. Pranav, R.J. Adler, T. Buchert, H. Edelsbrunner, B.J.T. Jones, A. Schwartzman, H. Wagner, R. Van De Weygaert, Astronomy and Astrophysics 627 (2019).","ista":"Pranav P, Adler RJ, Buchert T, Edelsbrunner H, Jones BJT, Schwartzman A, Wagner H, Van De Weygaert R. 2019. Unexpected topology of the temperature fluctuations in the cosmic microwave background. Astronomy and Astrophysics. 627, A163.","chicago":"Pranav, Pratyush, Robert J. Adler, Thomas Buchert, Herbert Edelsbrunner, Bernard J.T. Jones, Armin Schwartzman, Hubert Wagner, and Rien Van De Weygaert. “Unexpected Topology of the Temperature Fluctuations in the Cosmic Microwave Background.” Astronomy and Astrophysics. EDP Sciences, 2019. https://doi.org/10.1051/0004-6361/201834916.","ieee":"P. Pranav et al., “Unexpected topology of the temperature fluctuations in the cosmic microwave background,” Astronomy and Astrophysics, vol. 627. EDP Sciences, 2019.","apa":"Pranav, P., Adler, R. J., Buchert, T., Edelsbrunner, H., Jones, B. J. T., Schwartzman, A., … Van De Weygaert, R. (2019). Unexpected topology of the temperature fluctuations in the cosmic microwave background. Astronomy and Astrophysics. EDP Sciences. https://doi.org/10.1051/0004-6361/201834916"},"article_type":"original","oa":1,"oa_version":"Published Version","file_date_updated":"2020-07-14T12:47:39Z","month":"07","has_accepted_license":"1","date_updated":"2025-05-20T08:01:55Z","acknowledgement":"PP is grateful to Julian Borill from the Planck consortium for providing the data, and for the illuminating discussions and inputs. PP also thanks Hans Kristen Eriksen, Anne Ducout, and Francois R. Bouchet for significantly helpful discussions at various stages. The authors collectively thank the anonymous referee for the invaluable comments and suggestions that have added significant value to the contents of the manuscript. PP and RA acknowledge the support of ERC advanced grant Understanding Random Systems through Algebraic Topology (URSAT) (no: 320422, PI: RA). This work is also part of a project that has received funding for PP and TB from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement ERC advanced grant 740021– Advances in Research on THeories of the dark UniverSe (ARTHUS), PI: TB). HE and HW acknowledge the support by the Office of Naval Research, through grant N62909-18-1-2038, and by the DFG Collaborative Research Center TRR 109, “Discretization in Geometry and Dynamics”, through grant I02979-N35 of the Austrian Science Fund (FWF). PP acknowledges the support and use of resources at the NERSC computing center.","OA_type":"hybrid","ddc":["520","530"],"project":[{"_id":"265683E4-B435-11E9-9278-68D0E5697425","name":"Toward Computational Information Topology","grant_number":"M62909-18-1-2038"},{"grant_number":"I02979-N35","call_identifier":"FWF","name":"Persistence and stability of geometric complexes","_id":"2561EBF4-B435-11E9-9278-68D0E5697425"}],"day":"17","_id":"6756","external_id":{"isi":["000475839300003"],"arxiv":["1812.07678"]},"publication_status":"published","author":[{"full_name":"Pranav, Pratyush","first_name":"Pratyush","last_name":"Pranav"},{"first_name":"Robert J.","full_name":"Adler, Robert J.","last_name":"Adler"},{"last_name":"Buchert","first_name":"Thomas","full_name":"Buchert, Thomas"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833"},{"last_name":"Jones","full_name":"Jones, Bernard J.T.","first_name":"Bernard J.T."},{"last_name":"Schwartzman","first_name":"Armin","full_name":"Schwartzman, Armin"},{"last_name":"Wagner","id":"379CA8B8-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Hubert","first_name":"Hubert"},{"full_name":"Van De Weygaert, Rien","first_name":"Rien","last_name":"Van De Weygaert"}],"publisher":"EDP Sciences","doi":"10.1051/0004-6361/201834916","article_processing_charge":"No","abstract":[{"lang":"eng","text":"We study the topology generated by the temperature fluctuations of the cosmic microwave background (CMB) radiation, as quantified by the number of components and holes, formally given by the Betti numbers, in the growing excursion sets. We compare CMB maps observed by the Planck satellite with a thousand simulated maps generated according to the ΛCDM paradigm with Gaussian distributed fluctuations. The comparison is multi-scale, being performed on a sequence of degraded maps with mean pixel separation ranging from 0.05 to 7.33°. The survey of the CMB over 𝕊2 is incomplete due to obfuscation effects by bright point sources and other extended foreground objects like our own galaxy. To deal with such situations, where analysis in the presence of “masks” is of importance, we introduce the concept of relative homology. The parametric χ2-test shows differences between observations and simulations, yielding p-values at percent to less than permil levels roughly between 2 and 7°, with the difference in the number of components and holes peaking at more than 3σ sporadically at these scales. The highest observed deviation between the observations and simulations for b0 and b1 is approximately between 3σ and 4σ at scales of 3–7°. There are reports of mildly unusual behaviour of the Euler characteristic at 3.66° in the literature, computed from independent measurements of the CMB temperature fluctuations by Planck’s predecessor, the Wilkinson Microwave Anisotropy Probe (WMAP) satellite. The mildly anomalous behaviour of the Euler characteristic is phenomenologically related to the strongly anomalous behaviour of components and holes, or the zeroth and first Betti numbers, respectively. Further, since these topological descriptors show consistent anomalous behaviour over independent measurements of Planck and WMAP, instrumental and systematic errors may be an unlikely source. These are also the scales at which the observed maps exhibit low variance compared to the simulations, and approximately the range of scales at which the power spectrum exhibits a dip with respect to the theoretical model. Non-parametric tests show even stronger differences at almost all scales. Crucially, Gaussian simulations based on power-spectrum matching the characteristics of the observed dipped power spectrum are not able to resolve the anomaly. Understanding the origin of the anomalies in the CMB, whether cosmological in nature or arising due to late-time effects, is an extremely challenging task. Regardless, beyond the trivial possibility that this may still be a manifestation of an extreme Gaussian case, these observations, along with the super-horizon scales involved, may motivate the study of primordial non-Gaussianity. Alternative scenarios worth exploring may be models with non-trivial topology, including topological defect models."}]},{"oa":1,"file_date_updated":"2020-07-14T12:47:40Z","oa_version":"Published Version","month":"08","has_accepted_license":"1","date_updated":"2023-02-23T14:08:14Z","ddc":["570"],"day":"08","_id":"6819","author":[{"last_name":"Antoniou","full_name":"Antoniou, Michael N.","first_name":"Michael N."},{"full_name":"Nicolas, Armel","first_name":"Armel","last_name":"Nicolas","id":"2A103192-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Mesnage","first_name":"Robin","full_name":"Mesnage, Robin"},{"full_name":"Biserni, Martina","first_name":"Martina","last_name":"Biserni"},{"last_name":"Rao","first_name":"Francesco V.","full_name":"Rao, Francesco V."},{"last_name":"Martin","full_name":"Martin, Cristina Vazquez","first_name":"Cristina Vazquez"}],"external_id":{"pmid":["31395095"]},"publisher":"BioMed Central","publication_status":"published","doi":"10.1186/s13104-019-4534-3","abstract":[{"text":"Glyphosate (N-phosphonomethyl glycine) and its commercial herbicide formulations have been shown to exert toxicity via various mechanisms. It has been asserted that glyphosate substitutes for glycine in polypeptide chains leading to protein misfolding and toxicity. However, as no direct evidence exists for glycine to glyphosate substitution in proteins, including in mammalian organisms, we tested this claim by conducting a proteomics analysis of MDA-MB-231 human breast cancer cells grown in the presence of 100 mg/L glyphosate for 6 days. Protein extracts from three treated and three untreated cell cultures were analysed as one TMT-6plex labelled sample, to highlight a specific pattern (+/+/+/−/−/−) of reporter intensities for peptides bearing true glyphosate treatment induced-post translational modifications as well as allowing an investigation of the total proteome.","lang":"eng"}],"article_processing_charge":"No","department":[{"_id":"LifeSc"}],"publication_identifier":{"eissn":["1756-0500"]},"intvolume":" 12","date_published":"2019-08-08T00:00:00Z","article_number":"494","pmid":1,"type":"journal_article","year":"2019","publication":"BMC Research Notes","title":"Glyphosate does not substitute for glycine in proteins of actively dividing mammalian cells","file":[{"creator":"dernst","file_id":"6829","access_level":"open_access","date_created":"2019-08-23T11:10:35Z","date_updated":"2020-07-14T12:47:40Z","content_type":"application/pdf","file_size":1177482,"relation":"main_file","file_name":"2019_BMC_Antoniou.pdf","checksum":"4a2bb7994b7f2c432bf44f5127ea3102"}],"language":[{"iso":"eng"}],"scopus_import":1,"quality_controlled":"1","related_material":{"record":[{"status":"public","id":"9784","relation":"research_data"}]},"date_created":"2019-08-18T22:00:39Z","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"status":"public","volume":12,"citation":{"ista":"Antoniou MN, Nicolas A, Mesnage R, Biserni M, Rao FV, Martin CV. 2019. Glyphosate does not substitute for glycine in proteins of actively dividing mammalian cells. BMC Research Notes. 12, 494.","short":"M.N. Antoniou, A. Nicolas, R. Mesnage, M. Biserni, F.V. Rao, C.V. Martin, BMC Research Notes 12 (2019).","mla":"Antoniou, Michael N., et al. “Glyphosate Does Not Substitute for Glycine in Proteins of Actively Dividing Mammalian Cells.” BMC Research Notes, vol. 12, 494, BioMed Central, 2019, doi:10.1186/s13104-019-4534-3.","ama":"Antoniou MN, Nicolas A, Mesnage R, Biserni M, Rao FV, Martin CV. Glyphosate does not substitute for glycine in proteins of actively dividing mammalian cells. BMC Research Notes. 2019;12. doi:10.1186/s13104-019-4534-3","apa":"Antoniou, M. N., Nicolas, A., Mesnage, R., Biserni, M., Rao, F. V., & Martin, C. V. (2019). Glyphosate does not substitute for glycine in proteins of actively dividing mammalian cells. BMC Research Notes. BioMed Central. https://doi.org/10.1186/s13104-019-4534-3","ieee":"M. N. Antoniou, A. Nicolas, R. Mesnage, M. Biserni, F. V. Rao, and C. V. Martin, “Glyphosate does not substitute for glycine in proteins of actively dividing mammalian cells,” BMC Research Notes, vol. 12. BioMed Central, 2019.","chicago":"Antoniou, Michael N., Armel Nicolas, Robin Mesnage, Martina Biserni, Francesco V. Rao, and Cristina Vazquez Martin. “Glyphosate Does Not Substitute for Glycine in Proteins of Actively Dividing Mammalian Cells.” BMC Research Notes. BioMed Central, 2019. https://doi.org/10.1186/s13104-019-4534-3."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87"},{"language":[{"iso":"eng"}],"file":[{"creator":"gavni","file_id":"6823","access_level":"open_access","date_updated":"2020-07-14T12:47:41Z","date_created":"2019-08-19T07:56:40Z","content_type":"application/pdf","file_size":436635,"relation":"main_file","checksum":"45ebbc709af2b247d28c7c293c01504b","file_name":"prob.pdf"}],"title":"Bidding games on Markov decision processes","publication":" Proceedings of the 13th International Conference of Reachability Problems","type":"conference","year":"2019","citation":{"apa":"Avni, G., Henzinger, T. A., Ibsen-Jensen, R., & Novotny, P. (2019). Bidding games on Markov decision processes. In Proceedings of the 13th International Conference of Reachability Problems (Vol. 11674, pp. 1–12). Brussels, Belgium: Springer. https://doi.org/10.1007/978-3-030-30806-3_1","ieee":"G. Avni, T. A. Henzinger, R. Ibsen-Jensen, and P. Novotny, “Bidding games on Markov decision processes,” in Proceedings of the 13th International Conference of Reachability Problems, Brussels, Belgium, 2019, vol. 11674, pp. 1–12.","chicago":"Avni, Guy, Thomas A Henzinger, Rasmus Ibsen-Jensen, and Petr Novotny. “Bidding Games on Markov Decision Processes.” In Proceedings of the 13th International Conference of Reachability Problems, 11674:1–12. Springer, 2019. https://doi.org/10.1007/978-3-030-30806-3_1.","short":"G. Avni, T.A. Henzinger, R. Ibsen-Jensen, P. Novotny, in:, Proceedings of the 13th International Conference of Reachability Problems, Springer, 2019, pp. 1–12.","ista":"Avni G, Henzinger TA, Ibsen-Jensen R, Novotny P. 2019. Bidding games on Markov decision processes. Proceedings of the 13th International Conference of Reachability Problems. RP: Reachability Problems, LNCS, vol. 11674, 1–12.","mla":"Avni, Guy, et al. “Bidding Games on Markov Decision Processes.” Proceedings of the 13th International Conference of Reachability Problems, vol. 11674, Springer, 2019, pp. 1–12, doi:10.1007/978-3-030-30806-3_1.","ama":"Avni G, Henzinger TA, Ibsen-Jensen R, Novotny P. Bidding games on Markov decision processes. In: Proceedings of the 13th International Conference of Reachability Problems. Vol 11674. Springer; 2019:1-12. doi:10.1007/978-3-030-30806-3_1"},"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","volume":11674,"status":"public","date_created":"2019-08-19T07:58:10Z","quality_controlled":"1","scopus_import":"1","publication_identifier":{"issn":["0302-9743"],"isbn":["978-303030805-6"]},"department":[{"_id":"ToHe"}],"isi":1,"page":"1-12","date_published":"2019-09-06T00:00:00Z","alternative_title":["LNCS"],"intvolume":" 11674","ddc":["000"],"article_processing_charge":"No","abstract":[{"text":"In two-player games on graphs, the players move a token through a graph to produce an infinite path, which determines the qualitative winner or quantitative payoff of the game. In bidding games, in each turn, we hold an auction between the two players to determine which player moves the token. Bidding games have largely been studied with concrete bidding mechanisms that are variants of a first-price auction: in each turn both players simultaneously submit bids, the higher\r\nbidder moves the token, and pays his bid to the lower bidder in Richman bidding, to the bank in poorman bidding, and in taxman bidding, the bid is split between the other player and the bank according to a predefined constant factor. Bidding games are deterministic games. They have an intriguing connection with a fragment of stochastic games called \r\n randomturn games. We study, for the first time, a combination of bidding games with probabilistic behavior; namely, we study bidding games that are played on Markov decision processes, where the players bid for the right to choose the next action, which determines the probability distribution according to which the next vertex is chosen. We study parity and meanpayoff bidding games on MDPs and extend results from the deterministic bidding setting to the probabilistic one.","lang":"eng"}],"doi":"10.1007/978-3-030-30806-3_1","publisher":"Springer","_id":"6822","external_id":{"isi":["001333747500001"]},"author":[{"last_name":"Avni","id":"463C8BC2-F248-11E8-B48F-1D18A9856A87","first_name":"Guy","orcid":"0000-0001-5588-8287","full_name":"Avni, Guy"},{"orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","first_name":"Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Rasmus","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen","id":"3B699956-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Novotny","first_name":"Petr","full_name":"Novotny, Petr"}],"publication_status":"published","day":"06","conference":{"location":"Brussels, Belgium","start_date":"2019-09-11","name":"RP: Reachability Problems","end_date":"2019-09-13"},"project":[{"grant_number":"M02369","call_identifier":"FWF","_id":"264B3912-B435-11E9-9278-68D0E5697425","name":"Formal Methods meets Algorithmic Game Theory"},{"grant_number":"S11402-N23","call_identifier":"FWF","_id":"25F2ACDE-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering"},{"call_identifier":"FWF","grant_number":"Z211","name":"Formal methods for the design and analysis of complex systems","_id":"25F42A32-B435-11E9-9278-68D0E5697425"}],"oa_version":"Submitted Version","file_date_updated":"2020-07-14T12:47:41Z","oa":1,"date_updated":"2025-09-10T10:39:56Z","has_accepted_license":"1","month":"09"}]