[{"date_created":"2022-07-27T11:37:23Z","status":"public","publication":"ACM Transactions on Algorithms","day":"01","month":"10","article_type":"original","language":[{"iso":"eng"}],"oa":1,"external_id":{"arxiv":["1512.08147"]},"acknowledgement":"We thank the reviewers of ICALP 2013 for pointing to related articles and to an error in an example\r\ngiven in a previous version of this article. We also thank one of the reviewers of Transactions on\r\nAlgorithms for very detailed comments.","quality_controlled":"1","article_processing_charge":"No","intvolume":"        13","date_published":"2017-10-01T00:00:00Z","main_file_link":[{"url":"https://arxiv.org/abs/1512.08147","open_access":"1"}],"issue":"4","date_updated":"2022-09-09T11:57:42Z","article_number":"51","title":"Sublinear-time maintenance of breadth-first spanning trees in partially dynamic networks","abstract":[{"text":"We study the problem of maintaining a breadth-first spanning tree (BFS tree) in partially dynamic distributed networks modeling a sequence of either failures or additions of communication links (but not both). We present deterministic (1+ϵ)-approximation algorithms whose amortized time (over some number of link changes) is sublinear in D, the maximum diameter of the network.\r\n\r\nOur technique also leads to a deterministic (1+ϵ)-approximate incremental algorithm for single-source shortest paths in the sequential (usual RAM) model. Prior to our work, the state of the art was the classic exact algorithm of Even and Shiloach (1981), which is optimal under some assumptions (Roditty and Zwick 2011; Henzinger et al. 2015). Our result is the first to show that, in the incremental setting, this bound can be beaten in certain cases if some approximation is allowed.","lang":"eng"}],"type":"journal_article","publication_identifier":{"eissn":["1549-6333"],"issn":["1549-6325"]},"scopus_import":"1","year":"2017","volume":13,"oa_version":"Preprint","citation":{"ista":"Henzinger MH, Krinninger S, Nanongkai D. 2017. Sublinear-time maintenance of breadth-first spanning trees in partially dynamic networks. ACM Transactions on Algorithms. 13(4), 51.","chicago":"Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks.” <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery, 2017. <a href=\"https://doi.org/10.1145/3146550\">https://doi.org/10.1145/3146550</a>.","apa":"Henzinger, M. H., Krinninger, S., &#38; Nanongkai, D. (2017). Sublinear-time maintenance of breadth-first spanning trees in partially dynamic networks. <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3146550\">https://doi.org/10.1145/3146550</a>","ama":"Henzinger MH, Krinninger S, Nanongkai D. Sublinear-time maintenance of breadth-first spanning trees in partially dynamic networks. <i>ACM Transactions on Algorithms</i>. 2017;13(4). doi:<a href=\"https://doi.org/10.1145/3146550\">10.1145/3146550</a>","ieee":"M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Sublinear-time maintenance of breadth-first spanning trees in partially dynamic networks,” <i>ACM Transactions on Algorithms</i>, vol. 13, no. 4. Association for Computing Machinery, 2017.","mla":"Henzinger, Monika H., et al. “Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks.” <i>ACM Transactions on Algorithms</i>, vol. 13, no. 4, 51, Association for Computing Machinery, 2017, doi:<a href=\"https://doi.org/10.1145/3146550\">10.1145/3146550</a>.","short":"M.H. Henzinger, S. Krinninger, D. Nanongkai, ACM Transactions on Algorithms 13 (2017)."},"author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H"},{"last_name":"Krinninger","first_name":"Sebastian","full_name":"Krinninger, Sebastian"},{"full_name":"Nanongkai, Danupon","last_name":"Nanongkai","first_name":"Danupon"}],"publication_status":"published","arxiv":1,"publisher":"Association for Computing Machinery","doi":"10.1145/3146550","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"11665","extern":"1"},{"author":[{"full_name":"Dvořák, Wolfgang","first_name":"Wolfgang","last_name":"Dvořák"},{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger"},{"first_name":"David P.","last_name":"Williamson","full_name":"Williamson, David P."}],"publication_status":"published","publisher":"Springer Nature","arxiv":1,"doi":"10.1007/s00453-015-0066-y","_id":"11676","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","issue":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1611.05753"}],"date_published":"2017-01-01T00:00:00Z","date_updated":"2022-09-12T08:58:16Z","title":"Maximizing a submodular function with viability constraints","abstract":[{"lang":"eng","text":"We study the problem of maximizing a monotone submodular function with viability constraints. This problem originates from computational biology, where we are given a phylogenetic tree over a set of species and a directed graph, the so-called food web, encoding viability constraints between these species. These food webs usually have constant depth. The goal is to select a subset of k species that satisfies the viability constraints and has maximal phylogenetic diversity. As this problem is known to be NP-hard, we investigate approximation algorithms. We present the first constant factor approximation algorithm if the depth is constant. Its approximation ratio is (1−1e√). This algorithm not only applies to phylogenetic trees with viability constraints but for arbitrary monotone submodular set functions with viability constraints. Second, we show that there is no (1−1/e+ϵ)-approximation algorithm for our problem setting (even for additive functions) and that there is no approximation algorithm for a slight extension of this setting."}],"publication_identifier":{"issn":["0178-4617"],"eissn":["1432-0541"]},"type":"journal_article","year":"2017","volume":77,"scopus_import":"1","keyword":["Approximation algorithms","Submodular functions","Phylogenetic diversity","Viability constraints"],"citation":{"ista":"Dvořák W, Henzinger MH, Williamson DP. 2017. Maximizing a submodular function with viability constraints. Algorithmica. 77(1), 152–172.","chicago":"Dvořák, Wolfgang, Monika H Henzinger, and David P. Williamson. “Maximizing a Submodular Function with Viability Constraints.” <i>Algorithmica</i>. Springer Nature, 2017. <a href=\"https://doi.org/10.1007/s00453-015-0066-y\">https://doi.org/10.1007/s00453-015-0066-y</a>.","apa":"Dvořák, W., Henzinger, M. H., &#38; Williamson, D. P. (2017). Maximizing a submodular function with viability constraints. <i>Algorithmica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00453-015-0066-y\">https://doi.org/10.1007/s00453-015-0066-y</a>","ama":"Dvořák W, Henzinger MH, Williamson DP. Maximizing a submodular function with viability constraints. <i>Algorithmica</i>. 2017;77(1):152-172. doi:<a href=\"https://doi.org/10.1007/s00453-015-0066-y\">10.1007/s00453-015-0066-y</a>","ieee":"W. Dvořák, M. H. Henzinger, and D. P. Williamson, “Maximizing a submodular function with viability constraints,” <i>Algorithmica</i>, vol. 77, no. 1. Springer Nature, pp. 152–172, 2017.","mla":"Dvořák, Wolfgang, et al. “Maximizing a Submodular Function with Viability Constraints.” <i>Algorithmica</i>, vol. 77, no. 1, Springer Nature, 2017, pp. 152–72, doi:<a href=\"https://doi.org/10.1007/s00453-015-0066-y\">10.1007/s00453-015-0066-y</a>.","short":"W. Dvořák, M.H. Henzinger, D.P. Williamson, Algorithmica 77 (2017) 152–172."},"oa_version":"Preprint","oa":1,"external_id":{"arxiv":["1611.05753"]},"article_processing_charge":"No","quality_controlled":"1","acknowledgement":"The research leading to these results has received funding from the European Research\r\nCouncil under the European Union’s Seventh Framework Programme (FP/2007-2013)/ERC Grant Agreement No. 340506.","intvolume":"        77","date_created":"2022-07-27T14:37:24Z","status":"public","page":"152-172","publication":"Algorithmica","day":"01","month":"01","article_type":"original","language":[{"iso":"eng"}]},{"file_date_updated":"2020-07-14T12:44:37Z","acknowledgement":"This work has been supported by the project ANR-2011-IS01-001-01 “DESIRE” and Austrian Science Fund (FWF) I833-N18. Open access funding is provided by the Austrian Science Fund (FWF). ","article_processing_charge":"No","quality_controlled":"1","intvolume":"        26","oa":1,"file":[{"file_size":56664,"access_level":"open_access","date_created":"2018-12-12T10:16:13Z","file_name":"IST-2017-739-v1+2_10260_2016_375_MOESM1_ESM.pdf","file_id":"5199","checksum":"0b2d1b647ca96e9ef13a14b8b6775e0f","date_updated":"2020-07-14T12:44:37Z","creator":"system","content_type":"application/pdf","relation":"main_file"},{"creator":"system","content_type":"application/pdf","file_id":"5200","date_updated":"2020-07-14T12:44:37Z","checksum":"3321ef34e02e28acfc427f77cf32812a","file_size":688953,"file_name":"IST-2017-739-v1+3_s10260-016-0375-6.pdf","access_level":"open_access","date_created":"2018-12-12T10:16:14Z","relation":"main_file"}],"external_id":{"isi":["000407973200004"]},"isi":1,"has_accepted_license":"1","publist_id":"6189","month":"08","pubrep_id":"739","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"language":[{"iso":"eng"}],"date_created":"2018-12-11T11:50:31Z","status":"public","publication":"Statistical Methods and Applications","page":"403 - 418","day":"01","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"1168","author":[{"orcid":"0000-0003-0370-9835","full_name":"Perrone, Elisa","id":"2A5F8724-F248-11E8-B48F-1D18A9856A87","first_name":"Elisa","last_name":"Perrone"},{"full_name":"Rappold, Andreas","last_name":"Rappold","first_name":"Andreas"},{"last_name":"Müller","first_name":"Werner","full_name":"Müller, Werner"}],"publication_status":"published","department":[{"_id":"CaUh"}],"publisher":"Springer","doi":"10.1007/s10260-016-0375-6","type":"journal_article","scopus_import":"1","volume":26,"year":"2017","citation":{"ieee":"E. Perrone, A. Rappold, and W. Müller, “D inf s optimality in copula models,” <i>Statistical Methods and Applications</i>, vol. 26, no. 3. Springer, pp. 403–418, 2017.","mla":"Perrone, Elisa, et al. “D Inf s Optimality in Copula Models.” <i>Statistical Methods and Applications</i>, vol. 26, no. 3, Springer, 2017, pp. 403–18, doi:<a href=\"https://doi.org/10.1007/s10260-016-0375-6\">10.1007/s10260-016-0375-6</a>.","short":"E. Perrone, A. Rappold, W. Müller, Statistical Methods and Applications 26 (2017) 403–418.","ama":"Perrone E, Rappold A, Müller W. D inf s optimality in copula models. <i>Statistical Methods and Applications</i>. 2017;26(3):403-418. doi:<a href=\"https://doi.org/10.1007/s10260-016-0375-6\">10.1007/s10260-016-0375-6</a>","apa":"Perrone, E., Rappold, A., &#38; Müller, W. (2017). D inf s optimality in copula models. <i>Statistical Methods and Applications</i>. Springer. <a href=\"https://doi.org/10.1007/s10260-016-0375-6\">https://doi.org/10.1007/s10260-016-0375-6</a>","chicago":"Perrone, Elisa, Andreas Rappold, and Werner Müller. “D Inf s Optimality in Copula Models.” <i>Statistical Methods and Applications</i>. Springer, 2017. <a href=\"https://doi.org/10.1007/s10260-016-0375-6\">https://doi.org/10.1007/s10260-016-0375-6</a>.","ista":"Perrone E, Rappold A, Müller W. 2017. D inf s optimality in copula models. Statistical Methods and Applications. 26(3), 403–418."},"oa_version":"Submitted Version","date_published":"2017-08-01T00:00:00Z","ddc":["519"],"issue":"3","date_updated":"2023-09-20T11:25:09Z","title":"D inf s optimality in copula models","license":"https://creativecommons.org/licenses/by/4.0/","abstract":[{"lang":"eng","text":"Optimum experimental design theory has recently been extended for parameter estimation in copula models. The use of these models allows one to gain in flexibility by considering the model parameter set split into marginal and dependence parameters. However, this separation also leads to the natural issue of estimating only a subset of all model parameters. In this work, we treat this problem with the application of the (Formula presented.)-optimality to copula models. First, we provide an extension of the corresponding equivalence theory. Then, we analyze a wide range of flexible copula models to highlight the usefulness of (Formula presented.)-optimality in many possible scenarios. Finally, we discuss how the usage of the introduced design criterion also relates to the more general issue of copula selection and optimal design for model discrimination."}]},{"language":[{"iso":"eng"}],"pubrep_id":"727","month":"01","day":"01","page":"367 - 374","publication":"Genetics","status":"public","date_created":"2018-12-11T11:50:31Z","intvolume":"       205","quality_controlled":"1","article_processing_charge":"No","file_date_updated":"2020-07-14T12:44:37Z","publist_id":"6188","has_accepted_license":"1","isi":1,"file":[{"content_type":"application/pdf","creator":"system","date_created":"2018-12-12T10:10:43Z","file_name":"IST-2016-727-v1+1_SFC_Genetics_final.pdf","access_level":"open_access","file_size":361500,"checksum":"7c8ab79cda1f92760bbbbe0f53175bfc","date_updated":"2020-07-14T12:44:37Z","file_id":"4833","relation":"main_file"}],"external_id":{"isi":["000393677300025"]},"oa":1,"citation":{"ista":"Novak S, Kollár R. 2017. Spatial gene frequency waves under genotype dependent dispersal. Genetics. 205(1), 367–374.","chicago":"Novak, Sebastian, and Richard Kollár. “Spatial Gene Frequency Waves under Genotype Dependent Dispersal.” <i>Genetics</i>. Genetics Society of America, 2017. <a href=\"https://doi.org/10.1534/genetics.116.193946\">https://doi.org/10.1534/genetics.116.193946</a>.","apa":"Novak, S., &#38; Kollár, R. (2017). Spatial gene frequency waves under genotype dependent dispersal. <i>Genetics</i>. Genetics Society of America. <a href=\"https://doi.org/10.1534/genetics.116.193946\">https://doi.org/10.1534/genetics.116.193946</a>","ama":"Novak S, Kollár R. Spatial gene frequency waves under genotype dependent dispersal. <i>Genetics</i>. 2017;205(1):367-374. doi:<a href=\"https://doi.org/10.1534/genetics.116.193946\">10.1534/genetics.116.193946</a>","short":"S. Novak, R. Kollár, Genetics 205 (2017) 367–374.","mla":"Novak, Sebastian, and Richard Kollár. “Spatial Gene Frequency Waves under Genotype Dependent Dispersal.” <i>Genetics</i>, vol. 205, no. 1, Genetics Society of America, 2017, pp. 367–74, doi:<a href=\"https://doi.org/10.1534/genetics.116.193946\">10.1534/genetics.116.193946</a>.","ieee":"S. Novak and R. Kollár, “Spatial gene frequency waves under genotype dependent dispersal,” <i>Genetics</i>, vol. 205, no. 1. Genetics Society of America, pp. 367–374, 2017."},"oa_version":"Submitted Version","year":"2017","volume":205,"scopus_import":"1","publication_identifier":{"issn":["00166731"]},"type":"journal_article","abstract":[{"lang":"eng","text":"Dispersal is a crucial factor in natural evolution, since it determines the habitat experienced by any population and defines the spatial scale of interactions between individuals. There is compelling evidence for systematic differences in dispersal characteristics within the same population, i.e., genotype-dependent dispersal. The consequences of genotype-dependent dispersal on other evolutionary phenomena, however, are poorly understood. In this article we investigate the effect of genotype-dependent dispersal on spatial gene frequency patterns, using a generalization of the classical diffusion model of selection and dispersal. Dispersal is characterized by the variance of dispersal (diffusion coefficient) and the mean displacement (directional advection term). We demonstrate that genotype-dependent dispersal may change the qualitative behavior of Fisher waves, which change from being “pulled” to being “pushed” wave fronts as the discrepancy in dispersal between genotypes increases. The speed of any wave is partitioned into components due to selection, genotype-dependent variance of dispersal, and genotype-dependent mean displacement. We apply our findings to wave fronts maintained by selection against heterozygotes. Furthermore, we identify a benefit of increased variance of dispersal, quantify its effect on the speed of the wave, and discuss the implications for the evolution of dispersal strategies."}],"title":"Spatial gene frequency waves under genotype dependent dispersal","date_updated":"2025-05-28T11:42:46Z","ddc":["576"],"issue":"1","date_published":"2017-01-01T00:00:00Z","_id":"1169","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","project":[{"grant_number":"618091","name":"Speed of Adaptation in Population Genetics and Evolutionary Computation","_id":"25B1EC9E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"call_identifier":"FP7","_id":"25B07788-B435-11E9-9278-68D0E5697425","grant_number":"250152","name":"Limits to selection in biology and in evolutionary computation"}],"doi":"10.1534/genetics.116.193946","publisher":"Genetics Society of America","ec_funded":1,"department":[{"_id":"NiBa"}],"publication_status":"published","author":[{"full_name":"Novak, Sebastian","orcid":"0000-0002-2519-824X","id":"461468AE-F248-11E8-B48F-1D18A9856A87","first_name":"Sebastian","last_name":"Novak"},{"first_name":"Richard","last_name":"Kollár","full_name":"Kollár, Richard"}]},{"oa_version":"Submitted Version","citation":{"mla":"Edelsbrunner, Herbert, et al. “The Voronoi Functional Is Maximized by the Delaunay Triangulation in the Plane.” <i>Combinatorica</i>, vol. 37, no. 5, Springer, 2017, pp. 887–910, doi:<a href=\"https://doi.org/10.1007/s00493-016-3308-y\">10.1007/s00493-016-3308-y</a>.","ieee":"H. Edelsbrunner, A. Glazyrin, O. Musin, and A. Nikitenko, “The Voronoi functional is maximized by the Delaunay triangulation in the plane,” <i>Combinatorica</i>, vol. 37, no. 5. Springer, pp. 887–910, 2017.","short":"H. Edelsbrunner, A. Glazyrin, O. Musin, A. Nikitenko, Combinatorica 37 (2017) 887–910.","ama":"Edelsbrunner H, Glazyrin A, Musin O, Nikitenko A. The Voronoi functional is maximized by the Delaunay triangulation in the plane. <i>Combinatorica</i>. 2017;37(5):887-910. doi:<a href=\"https://doi.org/10.1007/s00493-016-3308-y\">10.1007/s00493-016-3308-y</a>","apa":"Edelsbrunner, H., Glazyrin, A., Musin, O., &#38; Nikitenko, A. (2017). The Voronoi functional is maximized by the Delaunay triangulation in the plane. <i>Combinatorica</i>. Springer. <a href=\"https://doi.org/10.1007/s00493-016-3308-y\">https://doi.org/10.1007/s00493-016-3308-y</a>","chicago":"Edelsbrunner, Herbert, Alexey Glazyrin, Oleg Musin, and Anton Nikitenko. “The Voronoi Functional Is Maximized by the Delaunay Triangulation in the Plane.” <i>Combinatorica</i>. Springer, 2017. <a href=\"https://doi.org/10.1007/s00493-016-3308-y\">https://doi.org/10.1007/s00493-016-3308-y</a>.","ista":"Edelsbrunner H, Glazyrin A, Musin O, Nikitenko A. 2017. The Voronoi functional is maximized by the Delaunay triangulation in the plane. Combinatorica. 37(5), 887–910."},"year":"2017","volume":37,"scopus_import":"1","publication_identifier":{"issn":["02099683"]},"type":"journal_article","abstract":[{"lang":"eng","text":"We introduce the Voronoi functional of a triangulation of a finite set of points in the Euclidean plane and prove that among all geometric triangulations of the point set, the Delaunay triangulation maximizes the functional. This result neither extends to topological triangulations in the plane nor to geometric triangulations in three and higher dimensions."}],"title":"The Voronoi functional is maximized by the Delaunay triangulation in the plane","date_updated":"2023-09-20T11:23:53Z","issue":"5","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1411.6337"}],"date_published":"2017-10-01T00:00:00Z","_id":"1173","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","project":[{"call_identifier":"FP7","_id":"255D761E-B435-11E9-9278-68D0E5697425","name":"Topological Complex Systems","grant_number":"318493"}],"doi":"10.1007/s00493-016-3308-y","publisher":"Springer","ec_funded":1,"department":[{"_id":"HeEd"}],"author":[{"full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","last_name":"Edelsbrunner"},{"full_name":"Glazyrin, Alexey","last_name":"Glazyrin","first_name":"Alexey"},{"full_name":"Musin, Oleg","first_name":"Oleg","last_name":"Musin"},{"id":"3E4FF1BA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-0659-3201","full_name":"Nikitenko, Anton","last_name":"Nikitenko","first_name":"Anton"}],"publication_status":"published","language":[{"iso":"eng"}],"month":"10","day":"01","page":"887 - 910","publication":"Combinatorica","status":"public","date_created":"2018-12-11T11:50:32Z","intvolume":"        37","article_processing_charge":"No","quality_controlled":"1","acknowledgement":"This research is partially supported by the Russian Government under the Mega Project 11.G34.31.0053, by the Toposys project FP7-ICT-318493-STREP, by ESF under the ACAT Research Network Programme, by RFBR grant 11-01-00735, and by NSF grants DMS-1101688, DMS-1400876.","publist_id":"6182","isi":1,"external_id":{"isi":["000418056000005"]},"oa":1},{"project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"1174","publication_status":"published","author":[{"first_name":"Maciej","last_name":"Skórski","full_name":"Skórski, Maciej","id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD"}],"department":[{"_id":"KrPi"}],"alternative_title":["LIPIcs"],"ec_funded":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","doi":"10.4230/LIPIcs.STACS.2017.57","type":"conference","publication_identifier":{"issn":["18688969"]},"scopus_import":"1","year":"2017","volume":66,"citation":{"chicago":"Skórski, Maciej. “Lower Bounds on Key Derivation for Square-Friendly Applications,” Vol. 66. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2017.57\">https://doi.org/10.4230/LIPIcs.STACS.2017.57</a>.","ista":"Skórski M. 2017. Lower bounds on key derivation for square-friendly applications. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 66, 57.","short":"M. Skórski, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","mla":"Skórski, Maciej. <i>Lower Bounds on Key Derivation for Square-Friendly Applications</i>. Vol. 66, 57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2017.57\">10.4230/LIPIcs.STACS.2017.57</a>.","ieee":"M. Skórski, “Lower bounds on key derivation for square-friendly applications,” presented at the STACS: Symposium on Theoretical Aspects of Computer Science, Hannover, Germany, 2017, vol. 66.","apa":"Skórski, M. (2017). Lower bounds on key derivation for square-friendly applications (Vol. 66). Presented at the STACS: Symposium on Theoretical Aspects of Computer Science, Hannover, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2017.57\">https://doi.org/10.4230/LIPIcs.STACS.2017.57</a>","ama":"Skórski M. Lower bounds on key derivation for square-friendly applications. In: Vol 66. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2017.57\">10.4230/LIPIcs.STACS.2017.57</a>"},"oa_version":"Submitted Version","main_file_link":[{"open_access":"1","url":"http://drops.dagstuhl.de/opus/volltexte/2017/6976"}],"date_published":"2017-03-01T00:00:00Z","date_updated":"2023-09-20T11:23:15Z","title":"Lower bounds on key derivation for square-friendly applications","article_number":"57","abstract":[{"lang":"eng","text":"Security of cryptographic applications is typically defined by security games. The adversary, within certain resources, cannot win with probability much better than 0 (for unpredictability applications, like one-way functions) or much better than 1/2 (indistinguishability applications for instance encryption schemes). In so called squared-friendly applications the winning probability of the adversary, for different values of the application secret randomness, is not only close to 0 or 1/2 on average, but also concentrated in the sense that its second central moment is small. The class of squared-friendly applications, which contains all unpredictability applications and many indistinguishability applications, is particularly important for key derivation. Barak et al. observed that for square-friendly applications one can beat the &quot;RT-bound&quot;, extracting secure keys with significantly smaller entropy loss. In turn Dodis and Yu showed that in squared-friendly applications one can directly use a &quot;weak&quot; key, which has only high entropy, as a secure key. In this paper we give sharp lower bounds on square security assuming security for &quot;weak&quot; keys. We show that any application which is either (a) secure with weak keys or (b) allows for entropy savings for keys derived by universal hashing, must be square-friendly. Quantitatively, our lower bounds match the positive results of Dodis and Yu and Barak et al. (TCC\\'13, CRYPTO\\'11) Hence, they can be understood as a general characterization of squared-friendly applications. While the positive results on squared-friendly applications where derived by one clever application of the Cauchy-Schwarz Inequality, for tight lower bounds we need more machinery. In our approach we use convex optimization techniques and some theory of circular matrices."}],"quality_controlled":"1","article_processing_charge":"No","intvolume":"        66","oa":1,"external_id":{"isi":["000521077300057"]},"isi":1,"publist_id":"6180","month":"03","language":[{"iso":"eng"}],"date_created":"2018-12-11T11:50:32Z","status":"public","conference":{"name":"STACS: Symposium on Theoretical Aspects of Computer Science","end_date":"2017-03-11","start_date":"2017-03-08","location":"Hannover, Germany"},"day":"01"},{"has_accepted_license":"1","publist_id":"6179","file":[{"relation":"main_file","creator":"system","content_type":"application/pdf","file_size":557769,"access_level":"open_access","file_name":"IST-2018-927-v1+1_LIPIcs-ITCS-2017-38.pdf","date_created":"2018-12-12T10:17:11Z","file_id":"5263","date_updated":"2020-07-14T12:44:37Z","checksum":"dbc94810be07c2fb1945d5c2a6130e6c"}],"oa":1,"intvolume":"        67","file_date_updated":"2020-07-14T12:44:37Z","quality_controlled":"1","day":"01","conference":{"end_date":"2017-01-11","name":"ITCS: Innovations in Theoretical Computer Science","location":"Berkeley, CA, United States","start_date":"2017-01-09"},"page":"38:1-38-21","status":"public","date_created":"2018-12-11T11:50:33Z","language":[{"iso":"eng"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"pubrep_id":"927","month":"01","doi":"10.4230/LIPIcs.ITCS.2017.38","alternative_title":["LIPIcs"],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"KrPi"}],"author":[{"first_name":"Joel F","last_name":"Alwen","full_name":"Alwen, Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87"},{"full_name":"De Rezende, Susanna","first_name":"Susanna","last_name":"De Rezende"},{"full_name":"Nordstrom, Jakob","last_name":"Nordstrom","first_name":"Jakob"},{"last_name":"Vinyals","first_name":"Marc","full_name":"Vinyals, Marc"}],"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"1175","abstract":[{"text":"We study space complexity and time-space trade-offs with a focus not on peak memory usage but on overall memory consumption throughout the computation.  Such a cumulative space measure was introduced for the computational model of parallel black pebbling by [Alwen and Serbinenko ’15] as a tool for obtaining results in cryptography. We consider instead the non- deterministic black-white pebble game and prove optimal cumulative space lower bounds and trade-offs, where in order to minimize pebbling time the space has to remain large during a significant fraction of the pebbling. We also initiate the study of cumulative space in proof complexity, an area where other space complexity measures have been extensively studied during the last 10–15 years. Using and extending the connection between proof complexity and pebble games in [Ben-Sasson and Nordström ’08, ’11] we obtain several strong cumulative space results for (even parallel versions of) the resolution proof system, and outline some possible future directions of study of this, in our opinion, natural and interesting space measure.","lang":"eng"}],"title":"Cumulative space in black-white pebbling and resolution","date_updated":"2021-01-12T06:48:51Z","editor":[{"first_name":"Christos","last_name":"Papadimitriou","full_name":"Papadimitriou, Christos"}],"date_published":"2017-01-01T00:00:00Z","ddc":["005","600"],"citation":{"apa":"Alwen, J. F., De Rezende, S., Nordstrom, J., &#38; Vinyals, M. (2017). Cumulative space in black-white pebbling and resolution. In C. Papadimitriou (Ed.) (Vol. 67, p. 38:1-38-21). Presented at the ITCS: Innovations in Theoretical Computer Science, Berkeley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2017.38\">https://doi.org/10.4230/LIPIcs.ITCS.2017.38</a>","ama":"Alwen JF, De Rezende S, Nordstrom J, Vinyals M. Cumulative space in black-white pebbling and resolution. In: Papadimitriou C, ed. Vol 67. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017:38:1-38-21. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2017.38\">10.4230/LIPIcs.ITCS.2017.38</a>","short":"J.F. Alwen, S. De Rezende, J. Nordstrom, M. Vinyals, in:, C. Papadimitriou (Ed.), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, p. 38:1-38-21.","mla":"Alwen, Joel F., et al. <i>Cumulative Space in Black-White Pebbling and Resolution</i>. Edited by Christos Papadimitriou, vol. 67, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, p. 38:1-38-21, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2017.38\">10.4230/LIPIcs.ITCS.2017.38</a>.","ieee":"J. F. Alwen, S. De Rezende, J. Nordstrom, and M. Vinyals, “Cumulative space in black-white pebbling and resolution,” presented at the ITCS: Innovations in Theoretical Computer Science, Berkeley, CA, United States, 2017, vol. 67, p. 38:1-38-21.","ista":"Alwen JF, De Rezende S, Nordstrom J, Vinyals M. 2017. Cumulative space in black-white pebbling and resolution. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 67, 38:1-38-21.","chicago":"Alwen, Joel F, Susanna De Rezende, Jakob Nordstrom, and Marc Vinyals. “Cumulative Space in Black-White Pebbling and Resolution.” edited by Christos Papadimitriou, 67:38:1-38-21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2017.38\">https://doi.org/10.4230/LIPIcs.ITCS.2017.38</a>."},"oa_version":"Published Version","scopus_import":1,"volume":67,"year":"2017","type":"conference","publication_identifier":{"issn":["18688969"]}},{"abstract":[{"lang":"eng","text":"The algorithm Argon2i-B of Biryukov, Dinu and Khovratovich is currently being considered by the IRTF (Internet Research Task Force) as a new de-facto standard for password hashing. An older version (Argon2i-A) of the same algorithm was chosen as the winner of the recent Password Hashing Competition. An important competitor to Argon2i-B is the recently introduced Balloon Hashing (BH) algorithm of Corrigan-Gibs, Boneh and Schechter. A key security desiderata for any such algorithm is that evaluating it (even using a custom device) requires a large amount of memory amortized across multiple instances. Alwen and Blocki (CRYPTO 2016) introduced a class of theoretical attacks against Argon2i-A and BH. While these attacks yield large asymptotic reductions in the amount of memory, it was not, a priori, clear if (1) they can be extended to the newer Argon2i-B, (2) the attacks are effective on any algorithm for practical parameter ranges (e.g., 1GB of memory) and (3) if they can be effectively instantiated against any algorithm under realistic hardware constrains. In this work we answer all three of these questions in the affirmative for all three algorithms. This is also the first work to analyze the security of Argon2i-B. In more detail, we extend the theoretical attacks of Alwen and Blocki (CRYPTO 2016) to the recent Argon2i-B proposal demonstrating severe asymptotic deficiencies in its security. Next we introduce several novel heuristics for improving the attack's concrete memory efficiency even when on-chip memory bandwidth is bounded. We then simulate our attacks on randomly sampled Argon2i-A, Argon2i-B and BH instances and measure the resulting memory consumption for various practical parameter ranges and for a variety of upperbounds on the amount of parallelism available to the attacker. Finally we describe, implement, and test a new heuristic for applying the Alwen-Blocki attack to functions employing a technique developed by Corrigan-Gibs et al. for improving concrete security of memory-hard functions. We analyze the collected data and show the effects various parameters have on the memory consumption of the attack. In particular, we can draw several interesting conclusions about the level of security provided by these functions. · For the Alwen-Blocki attack to fail against practical memory parameters, Argon2i-B must be instantiated with more than 10 passes on memory - beyond the \"paranoid\" parameter setting in the current IRTF proposal. · The technique of Corrigan-Gibs for improving security can also be overcome by the Alwen-Blocki attack under realistic hardware constraints. · On a positive note, both the asymptotic and concrete security of Argon2i-B seem to improve on that of Argon2i-A."}],"article_number":"7961977","title":"Towards practical attacks on Argon2i and balloon hashing","date_updated":"2023-09-20T11:22:25Z","date_published":"2017-07-03T00:00:00Z","main_file_link":[{"url":"https://eprint.iacr.org/2016/759","open_access":"1"}],"oa_version":"Submitted Version","citation":{"ama":"Alwen JF, Blocki J. Towards practical attacks on Argon2i and balloon hashing. In: IEEE; 2017. doi:<a href=\"https://doi.org/10.1109/EuroSP.2017.47\">10.1109/EuroSP.2017.47</a>","apa":"Alwen, J. F., &#38; Blocki, J. (2017). Towards practical attacks on Argon2i and balloon hashing. Presented at the EuroS&#38;P: European Symposium on Security and Privacy, Paris, France: IEEE. <a href=\"https://doi.org/10.1109/EuroSP.2017.47\">https://doi.org/10.1109/EuroSP.2017.47</a>","mla":"Alwen, Joel F., and Jeremiah Blocki. <i>Towards Practical Attacks on Argon2i and Balloon Hashing</i>. 7961977, IEEE, 2017, doi:<a href=\"https://doi.org/10.1109/EuroSP.2017.47\">10.1109/EuroSP.2017.47</a>.","ieee":"J. F. Alwen and J. Blocki, “Towards practical attacks on Argon2i and balloon hashing,” presented at the EuroS&#38;P: European Symposium on Security and Privacy, Paris, France, 2017.","short":"J.F. Alwen, J. Blocki, in:, IEEE, 2017.","ista":"Alwen JF, Blocki J. 2017. Towards practical attacks on Argon2i and balloon hashing. EuroS&#38;P: European Symposium on Security and Privacy, 7961977.","chicago":"Alwen, Joel F, and Jeremiah Blocki. “Towards Practical Attacks on Argon2i and Balloon Hashing.” IEEE, 2017. <a href=\"https://doi.org/10.1109/EuroSP.2017.47\">https://doi.org/10.1109/EuroSP.2017.47</a>."},"year":"2017","scopus_import":"1","publication_identifier":{"isbn":["978-150905761-0"]},"type":"conference","doi":"10.1109/EuroSP.2017.47","publisher":"IEEE","department":[{"_id":"KrPi"}],"author":[{"last_name":"Alwen","first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F"},{"first_name":"Jeremiah","last_name":"Blocki","full_name":"Blocki, Jeremiah"}],"publication_status":"published","_id":"1176","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","day":"03","conference":{"end_date":"2017-04-28","name":"EuroS&P: European Symposium on Security and Privacy","location":"Paris, France","start_date":"2017-04-26"},"status":"public","date_created":"2018-12-11T11:50:33Z","language":[{"iso":"eng"}],"month":"07","publist_id":"6178","isi":1,"external_id":{"isi":["000424197300011"]},"oa":1,"article_processing_charge":"No","quality_controlled":"1"},{"author":[{"last_name":"Henzinger","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"}],"publication_status":"published","doi":"10.1007/978-3-319-73117-9_3","publisher":"Springer Nature","alternative_title":["LNCS"],"extern":"1","intvolume":"     10706","_id":"11772","quality_controlled":"1","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-02-10T08:36:03Z","status":"public","date_created":"2022-08-08T13:16:37Z","date_published":"2017-12-22T00:00:00Z","abstract":[{"text":"A dynamic graph algorithm is a data structure that supports operations on dynamically changing graphs.","lang":"eng"}],"day":"22","page":"40–44","publication":"44th International Conference on Current Trends in Theory and Practice of Computer Science","conference":{"end_date":"2018-02-02","name":"SOFSEM: Theory and Practice of Computer Science","start_date":"2018-01-29","location":"Krems, Austria"},"title":"The state of the art in dynamic graph algorithms","year":"2017","volume":10706,"scopus_import":"1","month":"12","publication_identifier":{"issn":["0302-9743"],"eisbn":["9783319731179"],"isbn":["9783319731162"]},"type":"conference","language":[{"iso":"eng"}],"oa_version":"None","citation":{"short":"M.H. Henzinger, in:, 44th International Conference on Current Trends in Theory and Practice of Computer Science, Springer Nature, 2017, pp. 40–44.","mla":"Henzinger, Monika H. “The State of the Art in Dynamic Graph Algorithms.” <i>44th International Conference on Current Trends in Theory and Practice of Computer Science</i>, vol. 10706, Springer Nature, 2017, pp. 40–44, doi:<a href=\"https://doi.org/10.1007/978-3-319-73117-9_3\">10.1007/978-3-319-73117-9_3</a>.","ieee":"M. H. Henzinger, “The state of the art in dynamic graph algorithms,” in <i>44th International Conference on Current Trends in Theory and Practice of Computer Science</i>, Krems, Austria, 2017, vol. 10706, pp. 40–44.","apa":"Henzinger, M. H. (2017). The state of the art in dynamic graph algorithms. In <i>44th International Conference on Current Trends in Theory and Practice of Computer Science</i> (Vol. 10706, pp. 40–44). Krems, Austria: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-319-73117-9_3\">https://doi.org/10.1007/978-3-319-73117-9_3</a>","ama":"Henzinger MH. The state of the art in dynamic graph algorithms. In: <i>44th International Conference on Current Trends in Theory and Practice of Computer Science</i>. Vol 10706. Springer Nature; 2017:40–44. doi:<a href=\"https://doi.org/10.1007/978-3-319-73117-9_3\">10.1007/978-3-319-73117-9_3</a>","chicago":"Henzinger, Monika H. “The State of the Art in Dynamic Graph Algorithms.” In <i>44th International Conference on Current Trends in Theory and Practice of Computer Science</i>, 10706:40–44. Springer Nature, 2017. <a href=\"https://doi.org/10.1007/978-3-319-73117-9_3\">https://doi.org/10.1007/978-3-319-73117-9_3</a>.","ista":"Henzinger MH. 2017. The state of the art in dynamic graph algorithms. 44th International Conference on Current Trends in Theory and Practice of Computer Science. SOFSEM: Theory and Practice of Computer Science, LNCS, vol. 10706, 40–44."}},{"abstract":[{"lang":"eng","text":"For any pair (X, Z) of correlated random variables we can think of Z as a randomized function of X. If the domain of Z is small, one can make this function computationally efficient by allowing it to be only approximately correct. In folklore this problem is known as simulating auxiliary inputs. This idea of simulating auxiliary information turns out to be a very usefull tool, finding applications in complexity theory, cryptography, pseudorandomness and zero-knowledge. In this paper we revisit this problem, achieving the following results: (a) We present a novel boosting algorithm for constructing the simulator. This boosting proof is of independent interest, as it shows how to handle “negative mass” issues when constructing probability measures by shifting distinguishers in descent algorithms. Our technique essentially fixes the flaw in the TCC’14 paper “How to Fake Auxiliary Inputs”. (b) The complexity of our simulator is better than in previous works, including results derived from the uniform min-max theorem due to Vadhan and Zheng. To achieve (s,ϵ) -indistinguishability we need the complexity O(s⋅25ℓϵ−2) in time/circuit size, which improve previous bounds by a factor of ϵ−2. In particular, with we get meaningful provable security for the EUROCRYPT’09 leakage-resilient stream cipher instantiated with a standard 256-bit block cipher, like "}],"title":"Simulating auxiliary inputs, revisited","date_updated":"2023-09-20T11:21:57Z","date_published":"2017-01-01T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2016/808.pdf "}],"citation":{"chicago":"Skórski, Maciej. “Simulating Auxiliary Inputs, Revisited,” 9985:159–79. Springer, 2017. <a href=\"https://doi.org/10.1007/978-3-662-53641-4_7\">https://doi.org/10.1007/978-3-662-53641-4_7</a>.","ista":"Skórski M. 2017. Simulating auxiliary inputs, revisited. TCC: Theory of Cryptography Conference, LNCS, vol. 9985, 159–179.","short":"M. Skórski, in:, Springer, 2017, pp. 159–179.","ieee":"M. Skórski, “Simulating auxiliary inputs, revisited,” presented at the TCC: Theory of Cryptography Conference, 2017, vol. 9985, pp. 159–179.","mla":"Skórski, Maciej. <i>Simulating Auxiliary Inputs, Revisited</i>. Vol. 9985, Springer, 2017, pp. 159–79, doi:<a href=\"https://doi.org/10.1007/978-3-662-53641-4_7\">10.1007/978-3-662-53641-4_7</a>.","ama":"Skórski M. Simulating auxiliary inputs, revisited. In: Vol 9985. Springer; 2017:159-179. doi:<a href=\"https://doi.org/10.1007/978-3-662-53641-4_7\">10.1007/978-3-662-53641-4_7</a>","apa":"Skórski, M. (2017). Simulating auxiliary inputs, revisited (Vol. 9985, pp. 159–179). Presented at the TCC: Theory of Cryptography Conference, Springer. <a href=\"https://doi.org/10.1007/978-3-662-53641-4_7\">https://doi.org/10.1007/978-3-662-53641-4_7</a>"},"oa_version":"Submitted Version","year":"2017","volume":9985,"type":"conference","doi":"10.1007/978-3-662-53641-4_7","alternative_title":["LNCS"],"publisher":"Springer","publication_status":"published","author":[{"first_name":"Maciej","last_name":"Skórski","full_name":"Skórski, Maciej","id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD"}],"extern":"1","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"1178","day":"01","conference":{"name":"TCC: Theory of Cryptography Conference"},"page":"159 - 179","status":"public","date_created":"2018-12-11T11:50:34Z","language":[{"iso":"eng"}],"month":"01","publist_id":"6176","external_id":{"isi":["000390176000007"]},"isi":1,"oa":1,"intvolume":"      9985","acknowledgement":"This work was supported by the National Science Center, Poland (2015/17/N/ST6/03564).","article_processing_charge":"No","quality_controlled":"1"},{"date_published":"2017-02-21T00:00:00Z","main_file_link":[{"url":"https://arxiv.org/abs/1508.07594","open_access":"1"}],"date_updated":"2023-09-20T11:21:27Z","title":"Algebraic vertices of non-convex polyhedra","abstract":[{"lang":"eng","text":"In this article we define an algebraic vertex of a generalized polyhedron and show that the set of algebraic vertices is the smallest set of points needed to define the polyhedron. We prove that the indicator function of a generalized polytope P is a linear combination of indicator functions of simplices whose vertices are algebraic vertices of P. We also show that the indicator function of any generalized polyhedron is a linear combination, with integer coefficients, of indicator functions of cones with apices at algebraic vertices and line-cones. The concept of an algebraic vertex is closely related to the Fourier–Laplace transform. We show that a point v is an algebraic vertex of a generalized polyhedron P if and only if the tangent cone of P, at v, has non-zero Fourier–Laplace transform."}],"publication_identifier":{"issn":["00018708"]},"type":"journal_article","year":"2017","volume":308,"scopus_import":"1","oa_version":"Submitted Version","citation":{"ista":"Akopyan A, Bárány I, Robins S. 2017. Algebraic vertices of non-convex polyhedra. Advances in Mathematics. 308, 627–644.","chicago":"Akopyan, Arseniy, Imre Bárány, and Sinai Robins. “Algebraic Vertices of Non-Convex Polyhedra.” <i>Advances in Mathematics</i>. Academic Press, 2017. <a href=\"https://doi.org/10.1016/j.aim.2016.12.026\">https://doi.org/10.1016/j.aim.2016.12.026</a>.","ama":"Akopyan A, Bárány I, Robins S. Algebraic vertices of non-convex polyhedra. <i>Advances in Mathematics</i>. 2017;308:627-644. doi:<a href=\"https://doi.org/10.1016/j.aim.2016.12.026\">10.1016/j.aim.2016.12.026</a>","apa":"Akopyan, A., Bárány, I., &#38; Robins, S. (2017). Algebraic vertices of non-convex polyhedra. <i>Advances in Mathematics</i>. Academic Press. <a href=\"https://doi.org/10.1016/j.aim.2016.12.026\">https://doi.org/10.1016/j.aim.2016.12.026</a>","short":"A. Akopyan, I. Bárány, S. Robins, Advances in Mathematics 308 (2017) 627–644.","mla":"Akopyan, Arseniy, et al. “Algebraic Vertices of Non-Convex Polyhedra.” <i>Advances in Mathematics</i>, vol. 308, Academic Press, 2017, pp. 627–44, doi:<a href=\"https://doi.org/10.1016/j.aim.2016.12.026\">10.1016/j.aim.2016.12.026</a>.","ieee":"A. Akopyan, I. Bárány, and S. Robins, “Algebraic vertices of non-convex polyhedra,” <i>Advances in Mathematics</i>, vol. 308. Academic Press, pp. 627–644, 2017."},"publication_status":"published","author":[{"full_name":"Akopyan, Arseniy","orcid":"0000-0002-2548-617X","id":"430D2C90-F248-11E8-B48F-1D18A9856A87","first_name":"Arseniy","last_name":"Akopyan"},{"full_name":"Bárány, Imre","last_name":"Bárány","first_name":"Imre"},{"full_name":"Robins, Sinai","last_name":"Robins","first_name":"Sinai"}],"department":[{"_id":"HeEd"}],"publisher":"Academic Press","ec_funded":1,"doi":"10.1016/j.aim.2016.12.026","project":[{"grant_number":"291734","name":"International IST Postdoc Fellowship Programme","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"_id":"1180","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","date_created":"2018-12-11T11:50:34Z","status":"public","page":"627 - 644","publication":"Advances in Mathematics","day":"21","month":"02","language":[{"iso":"eng"}],"oa":1,"isi":1,"external_id":{"isi":["000409292900015"]},"publist_id":"6173","article_processing_charge":"No","quality_controlled":"1","intvolume":"       308"},{"day":"28","conference":{"location":"Berkley, CA, United States","start_date":"2017-01-09","end_date":"2017-01-11","name":"ITCS: Innovations in Theoretical Computer Science Conference"},"publication":"8th Innovations in Theoretical Computer Science Conference","status":"public","date_created":"2022-08-12T08:55:33Z","language":[{"iso":"eng"}],"month":"11","external_id":{"arxiv":["1703.01638"]},"oa":1,"intvolume":"        67","quality_controlled":"1","article_processing_charge":"No","abstract":[{"lang":"eng","text":"In recent years it has become popular to study dynamic problems in a sensitivity setting: Instead of allowing for an arbitrary sequence of updates, the sensitivity model only allows to apply batch updates of small size to the original input data. The sensitivity model is particularly appealing since recent strong conditional lower bounds ruled out fast algorithms for many dynamic problems, such as shortest paths, reachability, or subgraph connectivity.\r\n\r\nIn this paper we prove conditional lower bounds for these and additional problems in a sensitivity setting. For example, we show that under the Boolean Matrix Multiplication (BMM) conjecture combinatorial algorithms cannot compute the (4/3-\\varepsilon)-approximate diameter of an undirected unweighted dense graph with truly subcubic preprocessing time and truly subquadratic update/query time. This result is surprising since in the static setting it is not clear whether a reduction from BMM to diameter is possible. We further show under the BMM conjecture that many problems, such as reachability or approximate shortest paths, cannot be solved faster than by recomputation from scratch even after only one or two edge insertions. We extend our reduction from BMM to Diameter to give a reduction from All Pairs Shortest Paths to Diameter under one deletion in weighted graphs. This is intriguing, as in the static setting it is a big open problem whether Diameter is as hard as APSP. We further get a nearly tight lower bound for shortest paths after two edge deletions based on the APSP conjecture. We give more lower bounds under the Strong Exponential Time Hypothesis. Many of our lower bounds also hold for static oracle data structures where no sensitivity is required.\r\n\r\nFinally, we give the first algorithm for the (1+\\varepsilon)-approximate radius, diameter, and eccentricity problems in directed or undirected unweighted graphs in case of single edges failures. The algorithm has a truly subcubic running time for graphs with a truly subquadratic number of edges; it is tight w.r.t. the conditional lower bounds we obtain."}],"title":"Conditional hardness for sensitivity problems","article_number":"26","date_updated":"2023-02-16T11:49:15Z","date_published":"2017-11-28T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPICS.ITCS.2017.26"}],"citation":{"ieee":"M. H. Henzinger, A. Lincoln, S. Neumann, and V. Vassilevska Williams, “Conditional hardness for sensitivity problems,” in <i>8th Innovations in Theoretical Computer Science Conference</i>, Berkley, CA, United States, 2017, vol. 67.","mla":"Henzinger, Monika H., et al. “Conditional Hardness for Sensitivity Problems.” <i>8th Innovations in Theoretical Computer Science Conference</i>, vol. 67, 26, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href=\"https://doi.org/10.4230/LIPICS.ITCS.2017.26\">10.4230/LIPICS.ITCS.2017.26</a>.","short":"M.H. Henzinger, A. Lincoln, S. Neumann, V. Vassilevska Williams, in:, 8th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","ama":"Henzinger MH, Lincoln A, Neumann S, Vassilevska Williams V. Conditional hardness for sensitivity problems. In: <i>8th Innovations in Theoretical Computer Science Conference</i>. Vol 67. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:<a href=\"https://doi.org/10.4230/LIPICS.ITCS.2017.26\">10.4230/LIPICS.ITCS.2017.26</a>","apa":"Henzinger, M. H., Lincoln, A., Neumann, S., &#38; Vassilevska Williams, V. (2017). Conditional hardness for sensitivity problems. In <i>8th Innovations in Theoretical Computer Science Conference</i> (Vol. 67). Berkley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.ITCS.2017.26\">https://doi.org/10.4230/LIPICS.ITCS.2017.26</a>","chicago":"Henzinger, Monika H, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska Williams. “Conditional Hardness for Sensitivity Problems.” In <i>8th Innovations in Theoretical Computer Science Conference</i>, Vol. 67. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPICS.ITCS.2017.26\">https://doi.org/10.4230/LIPICS.ITCS.2017.26</a>.","ista":"Henzinger MH, Lincoln A, Neumann S, Vassilevska Williams V. 2017. Conditional hardness for sensitivity problems. 8th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science Conference, LIPIcs, vol. 67, 26."},"oa_version":"Published Version","scopus_import":"1","volume":67,"year":"2017","type":"conference","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959770293"]},"doi":"10.4230/LIPICS.ITCS.2017.26","alternative_title":["LIPIcs"],"arxiv":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","author":[{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger"},{"full_name":"Lincoln, Andrea","last_name":"Lincoln","first_name":"Andrea"},{"first_name":"Stefan","last_name":"Neumann","full_name":"Neumann, Stefan"},{"last_name":"Vassilevska Williams","first_name":"Virginia","full_name":"Vassilevska Williams, Virginia"}],"publication_status":"published","extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"11829"},{"article_processing_charge":"No","quality_controlled":"1","intvolume":"        87","external_id":{"arxiv":["1702.01136"]},"oa":1,"language":[{"iso":"eng"}],"month":"09","conference":{"end_date":"2017-09-06","name":"ESA: Annual European Symposium on Algorithms","start_date":"2017-09-04","location":"Vienna, Austria"},"related_material":{"record":[{"status":"public","id":"11894","relation":"later_version"}]},"publication":"25th Annual European Symposium on Algorithms","day":"01","date_created":"2022-08-12T09:27:11Z","status":"public","_id":"11831","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","alternative_title":["LIPIcs"],"arxiv":1,"doi":"10.4230/LIPICS.ESA.2017.44","publication_status":"published","author":[{"first_name":"Gramoz","last_name":"Goranci","full_name":"Goranci, Gramoz"},{"last_name":"Henzinger","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"full_name":"Peng, Pan","last_name":"Peng","first_name":"Pan"}],"citation":{"apa":"Goranci, G., Henzinger, M. H., &#38; Peng, P. (2017). Improved guarantees for vertex sparsification in planar graphs. In <i>25th Annual European Symposium on Algorithms</i> (Vol. 87). Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.ESA.2017.44\">https://doi.org/10.4230/LIPICS.ESA.2017.44</a>","ama":"Goranci G, Henzinger MH, Peng P. Improved guarantees for vertex sparsification in planar graphs. In: <i>25th Annual European Symposium on Algorithms</i>. Vol 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:<a href=\"https://doi.org/10.4230/LIPICS.ESA.2017.44\">10.4230/LIPICS.ESA.2017.44</a>","ieee":"G. Goranci, M. H. Henzinger, and P. Peng, “Improved guarantees for vertex sparsification in planar graphs,” in <i>25th Annual European Symposium on Algorithms</i>, Vienna, Austria, 2017, vol. 87.","mla":"Goranci, Gramoz, et al. “Improved Guarantees for Vertex Sparsification in Planar Graphs.” <i>25th Annual European Symposium on Algorithms</i>, vol. 87, 44, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href=\"https://doi.org/10.4230/LIPICS.ESA.2017.44\">10.4230/LIPICS.ESA.2017.44</a>.","short":"G. Goranci, M.H. Henzinger, P. Peng, in:, 25th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","ista":"Goranci G, Henzinger MH, Peng P. 2017. Improved guarantees for vertex sparsification in planar graphs. 25th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 87, 44.","chicago":"Goranci, Gramoz, Monika H Henzinger, and Pan Peng. “Improved Guarantees for Vertex Sparsification in Planar Graphs.” In <i>25th Annual European Symposium on Algorithms</i>, Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPICS.ESA.2017.44\">https://doi.org/10.4230/LIPICS.ESA.2017.44</a>."},"oa_version":"Published Version","publication_identifier":{"isbn":["978-3-95977-049-1"],"issn":["1868-8969"]},"type":"conference","year":"2017","volume":87,"scopus_import":"1","title":"Improved guarantees for vertex sparsification in planar graphs","article_number":"44","abstract":[{"text":"Graph Sparsification aims at compressing large graphs into smaller ones while (approximately) preserving important characteristics of the input graph. In this work we study Vertex Sparsifiers, i.e., sparsifiers whose goal is to reduce the number of vertices. Given a weighted graph G=(V,E), and a terminal set K with |K|=k, a quality-q vertex cut sparsifier of G is a graph H with K contained in V_H that preserves the value of minimum cuts separating any bipartition of K, up to a factor of q. We show that planar graphs with all the k terminals lying on the same face admit quality-1 vertex cut sparsifier of size O(k^2) that are also planar. Our result extends to vertex flow and distance sparsifiers. It improves the previous best known bound of O(k^2 2^(2k)) for cut and flow sparsifiers by an exponential factor, and matches an Omega(k^2) lower-bound for this class of graphs.\r\n\r\nWe also study vertex reachability sparsifiers for directed graphs. Given a digraph G=(V,E) and a terminal set K, a vertex reachability sparsifier of G is a digraph H=(V_H,E_H), K contained in V_H that preserves all reachability information among terminal pairs. We introduce the notion of reachability-preserving minors, i.e., we require H to be a minor of G. Among others, for general planar digraphs, we construct reachability-preserving minors of size O(k^2 log^2 k). We complement our upper-bound by showing that there exists an infinite family of acyclic planar digraphs such that any reachability-preserving minor must have Omega(k^2) vertices.","lang":"eng"}],"date_published":"2017-09-01T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPIcs.ESA.2017.44"}],"date_updated":"2023-02-21T16:32:16Z"},{"oa":1,"external_id":{"arxiv":["1707.02577"]},"intvolume":"        87","article_processing_charge":"No","quality_controlled":"1","status":"public","date_created":"2022-08-12T09:58:46Z","day":"01","publication":"25th Annual European Symposium on Algorithms","conference":{"name":"ESA: Annual European Symposium on Algorithms","end_date":"2017-09-06","location":"Vienna, Austria","start_date":"2017-09-04"},"month":"09","language":[{"iso":"eng"}],"author":[{"last_name":"Henzinger","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"full_name":"Leniowski, Dariusz","first_name":"Dariusz","last_name":"Leniowski"},{"last_name":"Mathieu","first_name":"Claire","full_name":"Mathieu, Claire"}],"publication_status":"published","doi":"10.4230/LIPICS.ESA.2017.48","alternative_title":["LIPIcs"],"arxiv":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"11832","date_updated":"2023-02-16T11:54:12Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPICS.ESA.2017.48"}],"date_published":"2017-09-01T00:00:00Z","abstract":[{"lang":"eng","text":"In this paper, we study the problem of opening centers to cluster a set of clients in a metric space so as to minimize the sum of the costs of the centers and of the cluster radii, in a dynamic environment where clients arrive and depart, and the solution must be updated efficiently while remaining competitive with respect to the current optimal solution. We call this dynamic sum-of-radii clustering problem.\r\n\r\nWe present a data structure that maintains a solution whose cost is within a constant factor of the cost of an optimal solution in metric spaces with bounded doubling dimension and whose worst-case update time is logarithmic in the parameters of the problem."}],"title":"Dynamic clustering to minimize the sum of radii","article_number":"48","scopus_import":"1","year":"2017","volume":87,"type":"conference","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-049-1"]},"citation":{"short":"M.H. Henzinger, D. Leniowski, C. Mathieu, in:, 25th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","mla":"Henzinger, Monika H., et al. “Dynamic Clustering to Minimize the Sum of Radii.” <i>25th Annual European Symposium on Algorithms</i>, vol. 87, 48, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href=\"https://doi.org/10.4230/LIPICS.ESA.2017.48\">10.4230/LIPICS.ESA.2017.48</a>.","ieee":"M. H. Henzinger, D. Leniowski, and C. Mathieu, “Dynamic clustering to minimize the sum of radii,” in <i>25th Annual European Symposium on Algorithms</i>, Vienna, Austria, 2017, vol. 87.","apa":"Henzinger, M. H., Leniowski, D., &#38; Mathieu, C. (2017). Dynamic clustering to minimize the sum of radii. In <i>25th Annual European Symposium on Algorithms</i> (Vol. 87). Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.ESA.2017.48\">https://doi.org/10.4230/LIPICS.ESA.2017.48</a>","ama":"Henzinger MH, Leniowski D, Mathieu C. Dynamic clustering to minimize the sum of radii. In: <i>25th Annual European Symposium on Algorithms</i>. Vol 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:<a href=\"https://doi.org/10.4230/LIPICS.ESA.2017.48\">10.4230/LIPICS.ESA.2017.48</a>","chicago":"Henzinger, Monika H, Dariusz Leniowski, and Claire Mathieu. “Dynamic Clustering to Minimize the Sum of Radii.” In <i>25th Annual European Symposium on Algorithms</i>, Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPICS.ESA.2017.48\">https://doi.org/10.4230/LIPICS.ESA.2017.48</a>.","ista":"Henzinger MH, Leniowski D, Mathieu C. 2017. Dynamic clustering to minimize the sum of radii. 25th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 87, 48."},"oa_version":"Published Version"},{"oa_version":"Published Version","citation":{"ista":"Goranci G, Henzinger MH, Peng P. 2017. The power of vertex sparsifiers in dynamic graph algorithms. 25th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 87, 45.","chicago":"Goranci, Gramoz, Monika H Henzinger, and Pan Peng. “The Power of Vertex Sparsifiers in Dynamic Graph Algorithms.” In <i>25th Annual European Symposium on Algorithms</i>, Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPICS.ESA.2017.45\">https://doi.org/10.4230/LIPICS.ESA.2017.45</a>.","apa":"Goranci, G., Henzinger, M. H., &#38; Peng, P. (2017). The power of vertex sparsifiers in dynamic graph algorithms. In <i>25th Annual European Symposium on Algorithms</i> (Vol. 87). Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.ESA.2017.45\">https://doi.org/10.4230/LIPICS.ESA.2017.45</a>","ama":"Goranci G, Henzinger MH, Peng P. The power of vertex sparsifiers in dynamic graph algorithms. In: <i>25th Annual European Symposium on Algorithms</i>. Vol 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:<a href=\"https://doi.org/10.4230/LIPICS.ESA.2017.45\">10.4230/LIPICS.ESA.2017.45</a>","short":"G. Goranci, M.H. Henzinger, P. Peng, in:, 25th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","mla":"Goranci, Gramoz, et al. “The Power of Vertex Sparsifiers in Dynamic Graph Algorithms.” <i>25th Annual European Symposium on Algorithms</i>, vol. 87, 45, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href=\"https://doi.org/10.4230/LIPICS.ESA.2017.45\">10.4230/LIPICS.ESA.2017.45</a>.","ieee":"G. Goranci, M. H. Henzinger, and P. Peng, “The power of vertex sparsifiers in dynamic graph algorithms,” in <i>25th Annual European Symposium on Algorithms</i>, Vienna, Austria, 2017, vol. 87."},"type":"conference","publication_identifier":{"isbn":["978-3-95977-049-1"],"issn":["1868-8969"]},"scopus_import":"1","year":"2017","volume":87,"title":"The power of vertex sparsifiers in dynamic graph algorithms","article_number":"45","abstract":[{"lang":"eng","text":"We introduce a new algorithmic framework for designing dynamic graph algorithms in minor-free graphs, by exploiting the structure of such graphs and a tool called vertex sparsification, which is a way to compress large graphs into small ones that well preserve relevant properties among a subset of vertices and has previously mainly been used in the design of approximation algorithms.\r\n\r\nUsing this framework, we obtain a Monte Carlo randomized fully dynamic algorithm for (1 + epsilon)-approximating the energy of electrical flows in n-vertex planar graphs with tilde{O}(r epsilon^{-2}) worst-case update time and tilde{O}((r + n / sqrt{r}) epsilon^{-2}) worst-case query time, for any r larger than some constant. For r=n^{2/3}, this gives tilde{O}(n^{2/3} epsilon^{-2}) update time and tilde{O}(n^{2/3} epsilon^{-2}) query time. We also extend this algorithm to work for minor-free graphs with similar approximation and running time guarantees. Furthermore, we illustrate our framework on the all-pairs max flow and shortest path problems by giving corresponding dynamic algorithms in minor-free graphs with both sublinear update and query times. To the best of our knowledge, our results are the first to systematically establish such a connection between dynamic graph algorithms and vertex sparsification.\r\n\r\nWe also present both upper bound and lower bound for maintaining the energy of electrical flows in the incremental subgraph model, where updates consist of only vertex activations, which might be of independent interest."}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPIcs.ESA.2017.45"}],"date_published":"2017-09-01T00:00:00Z","date_updated":"2023-02-16T11:56:37Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"11833","extern":"1","alternative_title":["LIPIcs"],"arxiv":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","doi":"10.4230/LIPICS.ESA.2017.45","author":[{"last_name":"Goranci","first_name":"Gramoz","full_name":"Goranci, Gramoz"},{"first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"Peng, Pan","first_name":"Pan","last_name":"Peng"}],"publication_status":"published","language":[{"iso":"eng"}],"month":"09","conference":{"location":"Vienna, Austria","start_date":"2017-09-04","name":"ESA: Annual European Symposium on Algorithms","end_date":"2017-09-06"},"publication":"25th Annual European Symposium on Algorithms","day":"01","date_created":"2022-08-12T10:46:26Z","status":"public","quality_controlled":"1","article_processing_charge":"No","intvolume":"        87","external_id":{"arxiv":["1712.06473"]},"oa":1},{"date_created":"2018-12-11T11:50:37Z","status":"public","publication":"Journal of Cryptology","related_material":{"record":[{"relation":"earlier_version","id":"3238","status":"public"}]},"page":"1238 - 1275","day":"01","month":"10","article_type":"original","language":[{"iso":"eng"}],"oa":1,"external_id":{"isi":["000410788600007"]},"file":[{"relation":"main_file","file_name":"2017_JournalCrypto_Kiltz.pdf","date_created":"2020-05-14T16:30:17Z","access_level":"open_access","file_size":516959,"checksum":"c647520d115b772a1682fc06fa273eb1","date_updated":"2020-07-14T12:44:37Z","file_id":"7843","content_type":"application/pdf","creator":"dernst"}],"isi":1,"has_accepted_license":"1","publist_id":"6166","file_date_updated":"2020-07-14T12:44:37Z","article_processing_charge":"No","quality_controlled":"1","intvolume":"        30","date_published":"2017-10-01T00:00:00Z","ddc":["000"],"issue":"4","date_updated":"2023-09-20T11:20:58Z","title":"Efficient authentication from hard learning problems","abstract":[{"lang":"eng","text":"We construct efficient authentication protocols and message authentication codes (MACs) whose security can be reduced to the learning parity with noise (LPN) problem. Despite a large body of work—starting with the (Formula presented.) protocol of Hopper and Blum in 2001—until now it was not even known how to construct an efficient authentication protocol from LPN which is secure against man-in-the-middle attacks. A MAC implies such a (two-round) protocol."}],"type":"journal_article","scopus_import":"1","year":"2017","volume":30,"oa_version":"Submitted Version","citation":{"ama":"Kiltz E, Pietrzak KZ, Venturi D, Cash D, Jain A. Efficient authentication from hard learning problems. <i>Journal of Cryptology</i>. 2017;30(4):1238-1275. doi:<a href=\"https://doi.org/10.1007/s00145-016-9247-3\">10.1007/s00145-016-9247-3</a>","apa":"Kiltz, E., Pietrzak, K. Z., Venturi, D., Cash, D., &#38; Jain, A. (2017). Efficient authentication from hard learning problems. <i>Journal of Cryptology</i>. Springer. <a href=\"https://doi.org/10.1007/s00145-016-9247-3\">https://doi.org/10.1007/s00145-016-9247-3</a>","ieee":"E. Kiltz, K. Z. Pietrzak, D. Venturi, D. Cash, and A. Jain, “Efficient authentication from hard learning problems,” <i>Journal of Cryptology</i>, vol. 30, no. 4. Springer, pp. 1238–1275, 2017.","mla":"Kiltz, Eike, et al. “Efficient Authentication from Hard Learning Problems.” <i>Journal of Cryptology</i>, vol. 30, no. 4, Springer, 2017, pp. 1238–75, doi:<a href=\"https://doi.org/10.1007/s00145-016-9247-3\">10.1007/s00145-016-9247-3</a>.","short":"E. Kiltz, K.Z. Pietrzak, D. Venturi, D. Cash, A. Jain, Journal of Cryptology 30 (2017) 1238–1275.","ista":"Kiltz E, Pietrzak KZ, Venturi D, Cash D, Jain A. 2017. Efficient authentication from hard learning problems. Journal of Cryptology. 30(4), 1238–1275.","chicago":"Kiltz, Eike, Krzysztof Z Pietrzak, Daniele Venturi, David Cash, and Abhishek Jain. “Efficient Authentication from Hard Learning Problems.” <i>Journal of Cryptology</i>. Springer, 2017. <a href=\"https://doi.org/10.1007/s00145-016-9247-3\">https://doi.org/10.1007/s00145-016-9247-3</a>."},"author":[{"last_name":"Kiltz","first_name":"Eike","full_name":"Kiltz, Eike"},{"first_name":"Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Venturi","first_name":"Daniele","full_name":"Venturi, Daniele"},{"full_name":"Cash, David","last_name":"Cash","first_name":"David"},{"full_name":"Jain, Abhishek","last_name":"Jain","first_name":"Abhishek"}],"publication_status":"published","department":[{"_id":"KrPi"}],"ec_funded":1,"publisher":"Springer","doi":"10.1007/s00145-016-9247-3","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020"},{"call_identifier":"FP7","_id":"258C570E-B435-11E9-9278-68D0E5697425","grant_number":"259668","name":"Provable Security for Physical Cryptography"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"1187"},{"oa_version":"Preprint","citation":{"chicago":"Henzinger, Monika H, Satish Rao, and Di Wang. “Local Flow Partitioning for Faster Edge Connectivity.” In <i>28th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 1919–38. Society for Industrial and Applied Mathematics, 2017. <a href=\"https://doi.org/10.1137/1.9781611974782.125\">https://doi.org/10.1137/1.9781611974782.125</a>.","ista":"Henzinger MH, Rao S, Wang D. 2017. Local flow partitioning for faster edge connectivity. 28th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1919–1938.","ieee":"M. H. Henzinger, S. Rao, and D. Wang, “Local flow partitioning for faster edge connectivity,” in <i>28th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Barcelona, Spain, 2017, pp. 1919–1938.","mla":"Henzinger, Monika H., et al. “Local Flow Partitioning for Faster Edge Connectivity.” <i>28th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Society for Industrial and Applied Mathematics, 2017, pp. 1919–38, doi:<a href=\"https://doi.org/10.1137/1.9781611974782.125\">10.1137/1.9781611974782.125</a>.","short":"M.H. Henzinger, S. Rao, D. Wang, in:, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2017, pp. 1919–1938.","ama":"Henzinger MH, Rao S, Wang D. Local flow partitioning for faster edge connectivity. In: <i>28th Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Society for Industrial and Applied Mathematics; 2017:1919-1938. doi:<a href=\"https://doi.org/10.1137/1.9781611974782.125\">10.1137/1.9781611974782.125</a>","apa":"Henzinger, M. H., Rao, S., &#38; Wang, D. (2017). Local flow partitioning for faster edge connectivity. In <i>28th Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 1919–1938). Barcelona, Spain: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611974782.125\">https://doi.org/10.1137/1.9781611974782.125</a>"},"scopus_import":"1","year":"2017","type":"conference","publication_identifier":{"eisbn":["978-161197478-2"]},"abstract":[{"lang":"eng","text":"We study the problem of computing a minimum cut in a simple, undirected graph and give a deterministic O(m log2 n log log2 n) time algorithm. This improves both on the best previously known deterministic running time of O(m log12 n) (Kawarabayashi and Thorup [12]) and the best previously known randomized running time of O(mlog3n) (Karger [11]) for this problem, though Karger's algorithm can be further applied to weighted graphs.\r\n\r\nOur approach is using the Kawarabayashi and Tho- rup graph compression technique, which repeatedly finds low-conductance cuts. To find these cuts they use a diffusion-based local algorithm. We use instead a flow- based local algorithm and suitably adjust their framework to work with our flow-based subroutine. Both flow and diffusion based methods have a long history of being applied to finding low conductance cuts. Diffusion algorithms have several variants that are naturally local while it is more complicated to make flow methods local. Some prior work has proven nice properties for local flow based algorithms with respect to improving or cleaning up low conductance cuts. Our flow subroutine, however, is the first that is both local and produces low conductance cuts. Thus, it may be of independent interest."}],"title":"Local flow partitioning for faster edge connectivity","date_updated":"2023-02-21T16:32:01Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1704.01254"}],"date_published":"2017-01-01T00:00:00Z","extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"11873","doi":"10.1137/1.9781611974782.125","arxiv":1,"publisher":"Society for Industrial and Applied Mathematics","publication_status":"published","author":[{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger"},{"full_name":"Rao, Satish","first_name":"Satish","last_name":"Rao"},{"full_name":"Wang, Di","last_name":"Wang","first_name":"Di"}],"language":[{"iso":"eng"}],"month":"01","day":"01","conference":{"name":"SODA: Symposium on Discrete Algorithms","end_date":"2017-01-19","location":"Barcelona, Spain","start_date":"2017-01-16"},"related_material":{"record":[{"relation":"earlier_version","id":"11889","status":"public"}]},"publication":"28th Annual ACM-SIAM Symposium on Discrete Algorithms","page":"1919-1938","status":"public","date_created":"2022-08-16T12:20:59Z","article_processing_charge":"No","quality_controlled":"1","external_id":{"arxiv":["1704.01254"]},"oa":1},{"extern":"1","_id":"11874","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","doi":"10.1137/1.9781611974782.30","publisher":"Society for Industrial and Applied Mathematics","arxiv":1,"author":[{"last_name":"Bhattacharya","first_name":"Sayan","full_name":"Bhattacharya, Sayan"},{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger"},{"last_name":"Nanongkai","first_name":"Danupon","full_name":"Nanongkai, Danupon"}],"publication_status":"published","oa_version":"Preprint","citation":{"ieee":"S. Bhattacharya, M. H. Henzinger, and D. Nanongkai, “Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time,” in <i>28th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Barcelona, Spain, 2017, vol. 0, pp. 470–489.","mla":"Bhattacharya, Sayan, et al. “Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in o(Log3 n) Worst Case Update Time.” <i>28th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, vol. 0, Society for Industrial and Applied Mathematics, 2017, pp. 470–89, doi:<a href=\"https://doi.org/10.1137/1.9781611974782.30\">10.1137/1.9781611974782.30</a>.","short":"S. Bhattacharya, M.H. Henzinger, D. Nanongkai, in:, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2017, pp. 470–489.","apa":"Bhattacharya, S., Henzinger, M. H., &#38; Nanongkai, D. (2017). Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time. In <i>28th Annual ACM-SIAM Symposium on Discrete Algorithms</i> (Vol. 0, pp. 470–489). Barcelona, Spain: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611974782.30\">https://doi.org/10.1137/1.9781611974782.30</a>","ama":"Bhattacharya S, Henzinger MH, Nanongkai D. Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time. In: <i>28th Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Vol 0. Society for Industrial and Applied Mathematics; 2017:470-489. doi:<a href=\"https://doi.org/10.1137/1.9781611974782.30\">10.1137/1.9781611974782.30</a>","chicago":"Bhattacharya, Sayan, Monika H Henzinger, and Danupon Nanongkai. “Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in o(Log3 n) Worst Case Update Time.” In <i>28th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 0:470–89. Society for Industrial and Applied Mathematics, 2017. <a href=\"https://doi.org/10.1137/1.9781611974782.30\">https://doi.org/10.1137/1.9781611974782.30</a>.","ista":"Bhattacharya S, Henzinger MH, Nanongkai D. 2017. Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time. 28th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 0, 470–489."},"year":"2017","volume":"0","scopus_import":"1","publication_identifier":{"eisbn":["978-161197478-2"]},"type":"conference","abstract":[{"text":"We consider the problem of maintaining an approximately maximum (fractional) matching and an approximately minimum vertex cover in a dynamic graph. Starting with the seminal paper by Onak and Rubinfeld [STOC 2010], this problem has received significant attention in recent years. There remains, however, a polynomial gap between the best known worst case update time and the best known amortised update time for this problem, even after allowing for randomisation. Specifically, Bernstein and Stein [ICALP 2015, SODA 2016] have the best known worst case update time. They present a deterministic data structure with approximation ratio (3/2 + ∊) and worst case update time O(m1/4/ ∊2), where m is the number of edges in the graph. In recent past, Gupta and Peng [FOCS 2013] gave a deterministic data structure with approximation ratio (1+ ∊) and worst case update time  No known randomised data structure beats the worst case update times of these two results. In contrast, the paper by Onak and Rubinfeld [STOC 2010] gave a randomised data structure with approximation ratio O(1) and amortised update time O(log2 n), where n is the number of nodes in the graph. This was later improved by Baswana, Gupta and Sen [FOCS 2011] and Solomon [FOCS 2016], leading to a randomised date structure with approximation ratio 2 and amortised update time O(1).\r\n\r\nWe bridge the polynomial gap between the worst case and amortised update times for this problem, without using any randomisation. We present a deterministic data structure with approximation ratio (2 + ∊) and worst case update time O(log3 n), for all sufficiently small constants ∊.","lang":"eng"}],"title":"Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time","date_updated":"2023-02-17T11:54:22Z","main_file_link":[{"url":"https://arxiv.org/abs/1704.02844","open_access":"1"}],"date_published":"2017-01-01T00:00:00Z","quality_controlled":"1","article_processing_charge":"No","external_id":{"arxiv":["1704.02844"]},"oa":1,"language":[{"iso":"eng"}],"month":"01","day":"01","page":"470 - 489","publication":"28th Annual ACM-SIAM Symposium on Discrete Algorithms","conference":{"location":"Barcelona, Spain","start_date":"2017-01-16","end_date":"2017-01-19","name":"SODA: Symposium on Discrete Algorithms"},"status":"public","date_created":"2022-08-16T12:28:27Z"},{"_id":"11903","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","publisher":"Springer Nature","doi":"10.1007/s00224-017-9759-8","publication_status":"published","author":[{"last_name":"Bhattacharya","first_name":"Sayan","full_name":"Bhattacharya, Sayan"},{"full_name":"Dvořák, Wolfgang","first_name":"Wolfgang","last_name":"Dvořák"},{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger"},{"first_name":"Martin","last_name":"Starnberger","full_name":"Starnberger, Martin"}],"citation":{"apa":"Bhattacharya, S., Dvořák, W., Henzinger, M. H., &#38; Starnberger, M. (2017). Welfare maximization with friends-of-friends network externalities. <i>Theory of Computing Systems</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00224-017-9759-8\">https://doi.org/10.1007/s00224-017-9759-8</a>","ama":"Bhattacharya S, Dvořák W, Henzinger MH, Starnberger M. Welfare maximization with friends-of-friends network externalities. <i>Theory of Computing Systems</i>. 2017;61(4):948-986. doi:<a href=\"https://doi.org/10.1007/s00224-017-9759-8\">10.1007/s00224-017-9759-8</a>","ieee":"S. Bhattacharya, W. Dvořák, M. H. Henzinger, and M. Starnberger, “Welfare maximization with friends-of-friends network externalities,” <i>Theory of Computing Systems</i>, vol. 61, no. 4. Springer Nature, pp. 948–986, 2017.","mla":"Bhattacharya, Sayan, et al. “Welfare Maximization with Friends-of-Friends Network Externalities.” <i>Theory of Computing Systems</i>, vol. 61, no. 4, Springer Nature, 2017, pp. 948–86, doi:<a href=\"https://doi.org/10.1007/s00224-017-9759-8\">10.1007/s00224-017-9759-8</a>.","short":"S. Bhattacharya, W. Dvořák, M.H. Henzinger, M. Starnberger, Theory of Computing Systems 61 (2017) 948–986.","ista":"Bhattacharya S, Dvořák W, Henzinger MH, Starnberger M. 2017. Welfare maximization with friends-of-friends network externalities. Theory of Computing Systems. 61(4), 948–986.","chicago":"Bhattacharya, Sayan, Wolfgang Dvořák, Monika H Henzinger, and Martin Starnberger. “Welfare Maximization with Friends-of-Friends Network Externalities.” <i>Theory of Computing Systems</i>. Springer Nature, 2017. <a href=\"https://doi.org/10.1007/s00224-017-9759-8\">https://doi.org/10.1007/s00224-017-9759-8</a>."},"oa_version":"Published Version","publication_identifier":{"eissn":["1433-0490"],"issn":["1432-4350"]},"type":"journal_article","year":"2017","volume":61,"scopus_import":"1","title":"Welfare maximization with friends-of-friends network externalities","abstract":[{"text":"Online social networks allow the collection of large amounts of data about the influence between users connected by a friendship-like relationship. When distributing items among agents forming a social network, this information allows us to exploit network externalities that each agent receives from his neighbors that get the same item. In this paper we consider Friends-of-Friends (2-hop) network externalities, i.e., externalities that not only depend on the neighbors that get the same item but also on neighbors of neighbors. For these externalities we study a setting where multiple different items are assigned to unit-demand agents. Specifically, we study the problem of welfare maximization under different types of externality functions. Let n be the number of agents and m be the number of items. Our contributions are the following: (1) We show that welfare maximization is APX-hard; we show that even for step functions with 2-hop (and also with 1-hop) externalities it is NP-hard to approximate social welfare better than (1−1/e). (2) On the positive side we present (i) an 𝑂(𝑛√)-approximation algorithm for general concave externality functions, (ii) an O(log m)-approximation algorithm for linear externality functions, and (iii) a 518(1−1/𝑒)-approximation algorithm for 2-hop step function externalities. We also improve the result from [7] for 1-hop step function externalities by giving a 12(1−1/𝑒)-approximation algorithm.","lang":"eng"}],"issue":"4","date_published":"2017-11-01T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1007/s00224-017-9759-8"}],"date_updated":"2023-02-21T16:29:58Z","article_processing_charge":"No","quality_controlled":"1","intvolume":"        61","oa":1,"language":[{"iso":"eng"}],"article_type":"original","month":"11","page":"948-986","publication":"Theory of Computing Systems","related_material":{"record":[{"id":"11837","relation":"earlier_version","status":"public"}]},"day":"01","date_created":"2022-08-17T11:14:12Z","status":"public"},{"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"1191","project":[{"call_identifier":"FP7","_id":"25B1EC9E-B435-11E9-9278-68D0E5697425","name":"Speed of Adaptation in Population Genetics and Evolutionary Computation","grant_number":"618091"},{"call_identifier":"FP7","name":"Limits to selection in biology and in evolutionary computation","grant_number":"250152","_id":"25B07788-B435-11E9-9278-68D0E5697425"}],"doi":"10.1007/s11538-016-0244-3","ec_funded":1,"publisher":"Springer","department":[{"_id":"NiBa"}],"publication_status":"published","author":[{"first_name":"Richard","last_name":"Kollár","full_name":"Kollár, Richard"},{"id":"461468AE-F248-11E8-B48F-1D18A9856A87","full_name":"Novak, Sebastian","orcid":"0000-0002-2519-824X","last_name":"Novak","first_name":"Sebastian"}],"citation":{"chicago":"Kollár, Richard, and Sebastian Novak. “Existence of Traveling Waves for the Generalized F–KPP Equation.” <i>Bulletin of Mathematical Biology</i>. Springer, 2017. <a href=\"https://doi.org/10.1007/s11538-016-0244-3\">https://doi.org/10.1007/s11538-016-0244-3</a>.","ista":"Kollár R, Novak S. 2017. Existence of traveling waves for the generalized F–KPP equation. Bulletin of Mathematical Biology. 79(3), 525–559.","mla":"Kollár, Richard, and Sebastian Novak. “Existence of Traveling Waves for the Generalized F–KPP Equation.” <i>Bulletin of Mathematical Biology</i>, vol. 79, no. 3, Springer, 2017, pp. 525–59, doi:<a href=\"https://doi.org/10.1007/s11538-016-0244-3\">10.1007/s11538-016-0244-3</a>.","ieee":"R. Kollár and S. Novak, “Existence of traveling waves for the generalized F–KPP equation,” <i>Bulletin of Mathematical Biology</i>, vol. 79, no. 3. Springer, pp. 525–559, 2017.","short":"R. Kollár, S. Novak, Bulletin of Mathematical Biology 79 (2017) 525–559.","ama":"Kollár R, Novak S. Existence of traveling waves for the generalized F–KPP equation. <i>Bulletin of Mathematical Biology</i>. 2017;79(3):525-559. doi:<a href=\"https://doi.org/10.1007/s11538-016-0244-3\">10.1007/s11538-016-0244-3</a>","apa":"Kollár, R., &#38; Novak, S. (2017). Existence of traveling waves for the generalized F–KPP equation. <i>Bulletin of Mathematical Biology</i>. Springer. <a href=\"https://doi.org/10.1007/s11538-016-0244-3\">https://doi.org/10.1007/s11538-016-0244-3</a>"},"oa_version":"Preprint","scopus_import":1,"volume":79,"year":"2017","type":"journal_article","abstract":[{"text":"Variation in genotypes may be responsible for differences in dispersal rates, directional biases, and growth rates of individuals. These traits may favor certain genotypes and enhance their spatiotemporal spreading into areas occupied by the less advantageous genotypes. We study how these factors influence the speed of spreading in the case of two competing genotypes under the assumption that spatial variation of the total population is small compared to the spatial variation of the frequencies of the genotypes in the population. In that case, the dynamics of the frequency of one of the genotypes is approximately described by a generalized Fisher–Kolmogorov–Petrovskii–Piskunov (F–KPP) equation. This generalized F–KPP equation with (nonlinear) frequency-dependent diffusion and advection terms admits traveling wave solutions that characterize the invasion of the dominant genotype. Our existence results generalize the classical theory for traveling waves for the F–KPP with constant coefficients. Moreover, in the particular case of the quadratic (monostable) nonlinear growth–decay rate in the generalized F–KPP we study in detail the influence of the variance in diffusion and mean displacement rates of the two genotypes on the minimal wave propagation speed.","lang":"eng"}],"title":"Existence of traveling waves for the generalized F–KPP equation","date_updated":"2025-05-28T11:42:46Z","date_published":"2017-03-01T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1607.00944"}],"issue":"3","intvolume":"        79","acknowledgement":"We thank Nick Barton, Katarína Bod’ová, and Sr\r\n-\r\ndan Sarikas for constructive feed-\r\nback and support. Furthermore, we would like to express our deep gratitude to the anonymous referees (one\r\nof whom, Jimmy Garnier, agreed to reveal his identity) and the editor Max Souza, for very helpful and\r\ndetailed comments and suggestions that significantly helped us to improve the manuscript. This project has\r\nreceived funding from the European Union’s Seventh Framework Programme for research, technological\r\ndevelopment and demonstration under Grant Agreement 618091 Speed of Adaptation in Population Genet-\r\nics and Evolutionary Computation (SAGE) and the European Research Council (ERC) Grant No. 250152\r\n(SN), from the Scientific Grant Agency of the Slovak Republic under the Grant 1/0459/13 and by the Slovak\r\nResearch and Development Agency under the Contract No. APVV-14-0378 (RK). RK would also like to\r\nthank IST Austria for its hospitality during the work on this project.","quality_controlled":"1","publist_id":"6160","oa":1,"language":[{"iso":"eng"}],"month":"03","day":"01","publication":"Bulletin of Mathematical Biology","page":"525-559","status":"public","date_created":"2018-12-11T11:50:38Z"}]