[{"oa_version":"Submitted Version","publication_status":"published","ddc":["000"],"page":"1343-1348","abstract":[{"lang":"eng","text":"We present a secure approach for maintaining andreporting credit history records on the Blockchain. Our ap-proach removes third-parties such as credit reporting agen-cies from the lending process and replaces them with smartcontracts. This allows customers to interact directly with thelenders or banks while ensuring the integrity, unmalleabilityand privacy of their credit data. Additionally, each customerhas full control over complete or selective disclosure of hercredit records, eliminating the risk of privacy violations or databreaches. Moreover, our approach provides strong guaranteesfor the lenders as well. A lender can check both correctness andcompleteness of the credit data disclosed to her. This is the firstapproach that can perform all credit reporting tasks withouta central authority or changing the financial mechanisms*."}],"has_accepted_license":"1","day":"01","doi":"10.1109/Cybermatics_2018.2018.00231","conference":{"location":"Halifax, Canada","name":"IEEE International Conference on Blockchain","start_date":"2018-07-30","end_date":"2018-08-03"},"department":[{"_id":"KrCh"}],"isi":1,"scopus_import":"1","publication":"Proceedings of the IEEE International Conference on Blockchain","publication_identifier":{"isbn":["978-1-5386-7975-3 "]},"status":"public","oa":1,"date_updated":"2026-07-04T22:31:08Z","author":[{"orcid":"0000-0003-1702-6584","id":"391365CE-F248-11E8-B48F-1D18A9856A87","last_name":"Goharshady","first_name":"Amir Kafshdar","full_name":"Goharshady, Amir Kafshdar"},{"first_name":"Ali","full_name":"Behrouz, Ali","last_name":"Behrouz"},{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"}],"project":[{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","grant_number":"ICT15-003","name":"Efficient Algorithms for Computer Aided Verification"},{"name":"Quantitative Game-theoretic Analysis of Blockchain Applications and Smart Contracts","_id":"266EEEC0-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"}],"related_material":{"record":[{"status":"public","id":"8934","relation":"dissertation_contains"}]},"publisher":"IEEE","citation":{"apa":"Goharshady, A. K., Behrouz, A., & Chatterjee, K. (2018). Secure Credit Reporting on the Blockchain. In Proceedings of the IEEE International Conference on Blockchain (pp. 1343–1348). Halifax, Canada: IEEE. https://doi.org/10.1109/Cybermatics_2018.2018.00231","short":"A.K. Goharshady, A. Behrouz, K. Chatterjee, in:, Proceedings of the IEEE International Conference on Blockchain, IEEE, 2018, pp. 1343–1348.","ista":"Goharshady AK, Behrouz A, Chatterjee K. 2018. Secure Credit Reporting on the Blockchain. Proceedings of the IEEE International Conference on Blockchain. IEEE International Conference on Blockchain, 1343–1348.","chicago":"Goharshady, Amir Kafshdar, Ali Behrouz, and Krishnendu Chatterjee. “Secure Credit Reporting on the Blockchain.” In Proceedings of the IEEE International Conference on Blockchain, 1343–48. IEEE, 2018. https://doi.org/10.1109/Cybermatics_2018.2018.00231.","ieee":"A. K. Goharshady, A. Behrouz, and K. Chatterjee, “Secure Credit Reporting on the Blockchain,” in Proceedings of the IEEE International Conference on Blockchain, Halifax, Canada, 2018, pp. 1343–1348.","mla":"Goharshady, Amir Kafshdar, et al. “Secure Credit Reporting on the Blockchain.” Proceedings of the IEEE International Conference on Blockchain, IEEE, 2018, pp. 1343–48, doi:10.1109/Cybermatics_2018.2018.00231.","ama":"Goharshady AK, Behrouz A, Chatterjee K. Secure Credit Reporting on the Blockchain. In: Proceedings of the IEEE International Conference on Blockchain. IEEE; 2018:1343-1348. doi:10.1109/Cybermatics_2018.2018.00231"},"quality_controlled":"1","ec_funded":1,"type":"conference","date_created":"2019-04-18T10:37:35Z","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","article_processing_charge":"No","file":[{"file_id":"6341","date_updated":"2020-07-14T12:47:27Z","relation":"main_file","file_name":"blockchain2018.pdf","access_level":"open_access","date_created":"2019-04-18T10:36:39Z","creator":"akafshda","file_size":624338,"content_type":"application/pdf","checksum":"b25c9bb7cf6e7e6634e692d26d41ead8"}],"month":"09","language":[{"iso":"eng"}],"_id":"6340","date_published":"2018-09-01T00:00:00Z","file_date_updated":"2020-07-14T12:47:27Z","external_id":{"arxiv":["1805.09104"],"isi":["000481634500196"]},"year":"2018","tmp":{"name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","image":"/images/cc_by_nc_nd.png","short":"CC BY-NC-ND (4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode"},"title":"Secure Credit Reporting on the Blockchain","arxiv":1},{"ec_funded":1,"quality_controlled":"1","project":[{"grant_number":"306589","name":"Decoding the complexity of turbulence at its origin","_id":"25152F3A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"call_identifier":"H2020","_id":"25104D44-B435-11E9-9278-68D0E5697425","name":"Eliminating turbulence in oil pipelines","grant_number":"737549"}],"date_updated":"2026-07-04T22:31:16Z","author":[{"first_name":"Jakob","full_name":"Kühnen, Jakob","id":"3A47AE32-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4312-0179","last_name":"Kühnen"},{"first_name":"Baofang","full_name":"Song, Baofang","last_name":"Song"},{"first_name":"Davide","full_name":"Scarselli, Davide","id":"40315C30-F248-11E8-B48F-1D18A9856A87","last_name":"Scarselli","orcid":"0000-0001-5227-4271"},{"first_name":"Nazmi B","full_name":"Budanur, Nazmi B","id":"3EA1010E-F248-11E8-B48F-1D18A9856A87","last_name":"Budanur","orcid":"0000-0003-0423-5010"},{"full_name":"Riedl, Michael","first_name":"Michael","id":"3BE60946-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4844-6311","last_name":"Riedl"},{"full_name":"Willis, Ashley","first_name":"Ashley","last_name":"Willis"},{"last_name":"Avila","full_name":"Avila, Marc","first_name":"Marc"},{"first_name":"Björn","full_name":"Hof, Björn","last_name":"Hof","id":"3A374330-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-2057-2754"}],"citation":{"ista":"Kühnen J, Song B, Scarselli D, Budanur NB, Riedl M, Willis A, Avila M, Hof B. 2018. Destabilizing turbulence in pipe flow. Nature Physics. 14, 386–390.","ieee":"J. Kühnen et al., “Destabilizing turbulence in pipe flow,” Nature Physics, vol. 14. Nature Publishing Group, pp. 386–390, 2018.","chicago":"Kühnen, Jakob, Baofang Song, Davide Scarselli, Nazmi B Budanur, Michael Riedl, Ashley Willis, Marc Avila, and Björn Hof. “Destabilizing Turbulence in Pipe Flow.” Nature Physics. Nature Publishing Group, 2018. https://doi.org/10.1038/s41567-017-0018-3.","short":"J. Kühnen, B. Song, D. Scarselli, N.B. Budanur, M. Riedl, A. Willis, M. Avila, B. Hof, Nature Physics 14 (2018) 386–390.","apa":"Kühnen, J., Song, B., Scarselli, D., Budanur, N. B., Riedl, M., Willis, A., … Hof, B. (2018). Destabilizing turbulence in pipe flow. Nature Physics. Nature Publishing Group. https://doi.org/10.1038/s41567-017-0018-3","ama":"Kühnen J, Song B, Scarselli D, et al. Destabilizing turbulence in pipe flow. Nature Physics. 2018;14:386-390. doi:10.1038/s41567-017-0018-3","mla":"Kühnen, Jakob, et al. “Destabilizing Turbulence in Pipe Flow.” Nature Physics, vol. 14, Nature Publishing Group, 2018, pp. 386–90, doi:10.1038/s41567-017-0018-3."},"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"12726"},{"id":"14530","status":"public","relation":"dissertation_contains"},{"id":"7258","status":"public","relation":"dissertation_contains"}]},"publisher":"Nature Publishing Group","status":"public","oa":1,"acknowledgement":"We acknowledge the European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013)/ERC Grant Agreement 306589, the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement no. 737549) and the Deutsche Forschungsgemeinschaft (Project No. FOR 1182) for financial support. We thank our technician P. Maier for providing highly valuable ideas and greatly supporting us in all technical aspects. We thank M. Schaner for technical drawings, construction and design. We thank M. Schwegel for a Matlab code to post-process experimental data.","publication":"Nature Physics","scopus_import":"1","department":[{"_id":"BjHo"}],"isi":1,"day":"08","publist_id":"7360","doi":"10.1038/s41567-017-0018-3","publication_status":"published","page":"386-390","abstract":[{"text":"Turbulence is the major cause of friction losses in transport processes and it is responsible for a drastic drag increase in flows over bounding surfaces. While much effort is invested into developing ways to control and reduce turbulence intensities, so far no methods exist to altogether eliminate turbulence if velocities are sufficiently large. We demonstrate for pipe flow that appropriate distortions to the velocity profile lead to a complete collapse of turbulence and subsequently friction losses are reduced by as much as 90%. Counterintuitively, the return to laminar motion is accomplished by initially increasing turbulence intensities or by transiently amplifying wall shear. Since neither the Reynolds number nor the shear stresses decrease (the latter often increase), these measures are not indicative of turbulence collapse. Instead, an amplification mechanism measuring the interaction between eddies and the mean shear is found to set a threshold below which turbulence is suppressed beyond recovery.","lang":"eng"}],"corr_author":"1","oa_version":"Preprint","year":"2018","title":"Destabilizing turbulence in pipe flow","arxiv":1,"external_id":{"isi":["000429434100020"],"arxiv":["1711.06543"]},"_id":"461","date_published":"2018-01-08T00:00:00Z","volume":14,"language":[{"iso":"eng"}],"intvolume":" 14","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1711.06543"}],"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"01","type":"journal_article","date_created":"2018-12-11T11:46:36Z"},{"_id":"11066","date_published":"2017-12-21T00:00:00Z","external_id":{"pmid":["29269482"]},"year":"2017","title":"Nup98 recruits the Wdr82–Set1A/COMPASS complex to promoters to regulate H3K4 trimethylation in hematopoietic progenitor cells","type":"journal_article","date_created":"2022-04-07T07:45:59Z","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"12","article_type":"original","main_file_link":[{"url":"https://doi.org/10.1101/gad.306753.117","open_access":"1"}],"issue":"22","volume":31,"language":[{"iso":"eng"}],"intvolume":" 31","scopus_import":"1","publication":"Genes & Development","publication_identifier":{"issn":["0890-9369","1549-5477"]},"status":"public","oa":1,"author":[{"first_name":"Tobias M.","full_name":"Franks, Tobias M.","last_name":"Franks"},{"full_name":"McCloskey, Asako","first_name":"Asako","last_name":"McCloskey"},{"full_name":"Shokhirev, Maxim Nikolaievich","first_name":"Maxim Nikolaievich","last_name":"Shokhirev"},{"last_name":"Benner","first_name":"Chris","full_name":"Benner, Chris"},{"last_name":"Rathore","full_name":"Rathore, Annie","first_name":"Annie"},{"last_name":"HETZER","orcid":"0000-0002-2111-992X","id":"86c0d31b-b4eb-11ec-ac5a-eae7b2e135ed","first_name":"Martin W","full_name":"HETZER, Martin W"}],"date_updated":"2024-10-14T11:20:24Z","citation":{"short":"T.M. Franks, A. McCloskey, M.N. Shokhirev, C. Benner, A. Rathore, M. Hetzer, Genes & Development 31 (2017) 2222–2234.","apa":"Franks, T. M., McCloskey, A., Shokhirev, M. N., Benner, C., Rathore, A., & Hetzer, M. (2017). Nup98 recruits the Wdr82–Set1A/COMPASS complex to promoters to regulate H3K4 trimethylation in hematopoietic progenitor cells. Genes & Development. Cold Spring Harbor Laboratory. https://doi.org/10.1101/gad.306753.117","ieee":"T. M. Franks, A. McCloskey, M. N. Shokhirev, C. Benner, A. Rathore, and M. Hetzer, “Nup98 recruits the Wdr82–Set1A/COMPASS complex to promoters to regulate H3K4 trimethylation in hematopoietic progenitor cells,” Genes & Development, vol. 31, no. 22. Cold Spring Harbor Laboratory, pp. 2222–2234, 2017.","ista":"Franks TM, McCloskey A, Shokhirev MN, Benner C, Rathore A, Hetzer M. 2017. Nup98 recruits the Wdr82–Set1A/COMPASS complex to promoters to regulate H3K4 trimethylation in hematopoietic progenitor cells. Genes & Development. 31(22), 2222–2234.","chicago":"Franks, Tobias M., Asako McCloskey, Maxim Nikolaievich Shokhirev, Chris Benner, Annie Rathore, and Martin Hetzer. “Nup98 Recruits the Wdr82–Set1A/COMPASS Complex to Promoters to Regulate H3K4 Trimethylation in Hematopoietic Progenitor Cells.” Genes & Development. Cold Spring Harbor Laboratory, 2017. https://doi.org/10.1101/gad.306753.117.","mla":"Franks, Tobias M., et al. “Nup98 Recruits the Wdr82–Set1A/COMPASS Complex to Promoters to Regulate H3K4 Trimethylation in Hematopoietic Progenitor Cells.” Genes & Development, vol. 31, no. 22, Cold Spring Harbor Laboratory, 2017, pp. 2222–34, doi:10.1101/gad.306753.117.","ama":"Franks TM, McCloskey A, Shokhirev MN, Benner C, Rathore A, Hetzer M. Nup98 recruits the Wdr82–Set1A/COMPASS complex to promoters to regulate H3K4 trimethylation in hematopoietic progenitor cells. Genes & Development. 2017;31(22):2222-2234. doi:10.1101/gad.306753.117"},"publisher":"Cold Spring Harbor Laboratory","quality_controlled":"1","pmid":1,"oa_version":"Published Version","publication_status":"published","keyword":["Developmental Biology","Genetics"],"page":"2222-2234","abstract":[{"text":"Recent studies have shown that a subset of nucleoporins (Nups) can detach from the nuclear pore complex and move into the nuclear interior to regulate transcription. One such dynamic Nup, called Nup98, has been implicated in gene activation in healthy cells and has been shown to drive leukemogenesis when mutated in patients with acute myeloid leukemia (AML). Here we show that in hematopoietic cells, Nup98 binds predominantly to transcription start sites to recruit the Wdr82–Set1A/COMPASS (complex of proteins associated with Set1) complex, which is required for deposition of the histone 3 Lys4 trimethyl (H3K4me3)-activating mark. Depletion of Nup98 or Wdr82 abolishes Set1A recruitment to chromatin and subsequently ablates H3K4me3 at adjacent promoters. Furthermore, expression of a Nup98 fusion protein implicated in aggressive AML causes mislocalization of H3K4me3 at abnormal regions and up-regulation of associated genes. Our findings establish a function of Nup98 in hematopoietic gene activation and provide mechanistic insight into which Nup98 leukemic fusion proteins promote AML.","lang":"eng"}],"day":"21","doi":"10.1101/gad.306753.117","extern":"1"},{"publication":"Scientific Reports","scopus_import":"1","acknowledgement":"European Research Council (project ERC-2011-StG-20101109-PSDP), European Social Fund (CZ.1.07/2.3.00/20.0043) and the Czech Science Foundation (GA13-40637S) [JF].","oa":1,"status":"public","publication_identifier":{"issn":["2045-2322"]},"citation":{"mla":"Kuhn, Benjamin, et al. “Flavonol-Induced Changes in PIN2 Polarity and Auxin Transport in the Arabidopsis Thaliana Rol1-2 Mutant Require Phosphatase Activity.” Scientific Reports, vol. 7, 41906, Nature Publishing Group, 2017, doi:10.1038/srep41906.","ama":"Kuhn B, Nodzyński T, Errafi S, et al. Flavonol-induced changes in PIN2 polarity and auxin transport in the Arabidopsis thaliana rol1-2 mutant require phosphatase activity. Scientific Reports. 2017;7. doi:10.1038/srep41906","short":"B. Kuhn, T. Nodzyński, S. Errafi, R. Bucher, S. Gupta, B. Aryal, P. Dobrev, L. Bigler, M. Geisler, E. Zažímalová, J. Friml, C. Ringli, Scientific Reports 7 (2017).","apa":"Kuhn, B., Nodzyński, T., Errafi, S., Bucher, R., Gupta, S., Aryal, B., … Ringli, C. (2017). Flavonol-induced changes in PIN2 polarity and auxin transport in the Arabidopsis thaliana rol1-2 mutant require phosphatase activity. Scientific Reports. Nature Publishing Group. https://doi.org/10.1038/srep41906","ieee":"B. Kuhn et al., “Flavonol-induced changes in PIN2 polarity and auxin transport in the Arabidopsis thaliana rol1-2 mutant require phosphatase activity,” Scientific Reports, vol. 7. Nature Publishing Group, 2017.","chicago":"Kuhn, Benjamin, Tomasz Nodzyński, Sanae Errafi, Rahel Bucher, Shibu Gupta, Bibek Aryal, Petre Dobrev, et al. “Flavonol-Induced Changes in PIN2 Polarity and Auxin Transport in the Arabidopsis Thaliana Rol1-2 Mutant Require Phosphatase Activity.” Scientific Reports. Nature Publishing Group, 2017. https://doi.org/10.1038/srep41906.","ista":"Kuhn B, Nodzyński T, Errafi S, Bucher R, Gupta S, Aryal B, Dobrev P, Bigler L, Geisler M, Zažímalová E, Friml J, Ringli C. 2017. Flavonol-induced changes in PIN2 polarity and auxin transport in the Arabidopsis thaliana rol1-2 mutant require phosphatase activity. Scientific Reports. 7, 41906."},"publisher":"Nature Publishing Group","project":[{"call_identifier":"FP7","name":"Polarity and subcellular dynamics in plants","_id":"25716A02-B435-11E9-9278-68D0E5697425","grant_number":"282300"}],"date_updated":"2025-07-10T11:50:06Z","pubrep_id":"803","author":[{"full_name":"Kuhn, Benjamin","first_name":"Benjamin","last_name":"Kuhn"},{"first_name":"Tomasz","full_name":"Nodzyński, Tomasz","last_name":"Nodzyński"},{"full_name":"Errafi, Sanae","first_name":"Sanae","last_name":"Errafi"},{"last_name":"Bucher","full_name":"Bucher, Rahel","first_name":"Rahel"},{"first_name":"Shibu","full_name":"Gupta, Shibu","last_name":"Gupta"},{"last_name":"Aryal","first_name":"Bibek","full_name":"Aryal, Bibek"},{"last_name":"Dobrev","first_name":"Petre","full_name":"Dobrev, Petre"},{"full_name":"Bigler, Laurent","first_name":"Laurent","last_name":"Bigler"},{"last_name":"Geisler","full_name":"Geisler, Markus","first_name":"Markus"},{"full_name":"Zažímalová, Eva","first_name":"Eva","last_name":"Zažímalová"},{"full_name":"Friml, Jirí","first_name":"Jirí","orcid":"0000-0002-8302-7596","last_name":"Friml","id":"4159519E-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Christoph","full_name":"Ringli, Christoph","last_name":"Ringli"}],"quality_controlled":"1","ec_funded":1,"oa_version":"Published Version","abstract":[{"text":"The phytohormone auxin is a major determinant and regulatory component important for plant development. Auxin transport between cells is mediated by a complex system of transporters such as AUX1/LAX, PIN, and ABCB proteins, and their localization and activity is thought to be influenced by phosphatases and kinases. Flavonols have been shown to alter auxin transport activity and changes in flavonol accumulation in the Arabidopsis thaliana rol1-2 mutant cause defects in auxin transport and seedling development. A new mutation in ROOTS CURL IN NPA 1 (RCN1), encoding a regulatory subunit of the phosphatase PP2A, was found to suppress the growth defects of rol1-2 without changing the flavonol content. rol1-2 rcn1-3 double mutants show wild type-like auxin transport activity while levels of free auxin are not affected by rcn1-3. In the rol1-2 mutant, PIN2 shows a flavonol-induced basal-to-apical shift in polar localization which is reversed in the rol1-2 rcn1-3 to basal localization. In vivo analysis of PINOID action, a kinase known to influence PIN protein localization in a PP2A-antagonistic manner, revealed a negative impact of flavonols on PINOID activity. Together, these data suggest that flavonols affect auxin transport by modifying the antagonistic kinase/phosphatase equilibrium.","lang":"eng"}],"ddc":["581"],"publication_status":"published","article_number":"41906","doi":"10.1038/srep41906","has_accepted_license":"1","day":"06","publist_id":"6258","isi":1,"department":[{"_id":"JiFr"}],"date_published":"2017-02-06T00:00:00Z","_id":"1110","external_id":{"isi":["000393367600001"]},"file_date_updated":"2018-12-12T10:18:09Z","title":"Flavonol-induced changes in PIN2 polarity and auxin transport in the Arabidopsis thaliana rol1-2 mutant require phosphatase activity","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"year":"2017","date_created":"2018-12-11T11:50:12Z","type":"journal_article","file":[{"file_id":"5328","date_updated":"2018-12-12T10:18:09Z","relation":"main_file","file_name":"IST-2017-803-v1+1_srep41906.pdf","access_level":"open_access","date_created":"2018-12-12T10:18:09Z","creator":"system","file_size":1654496,"content_type":"application/pdf"}],"month":"02","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","language":[{"iso":"eng"}],"intvolume":" 7","volume":7},{"doi":"10.1007/978-3-662-54580-5_10","publist_id":"6246","day":"31","has_accepted_license":"1","department":[{"_id":"ToHe"}],"isi":1,"conference":{"name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems","location":"Uppsala, Sweden","start_date":"2017-04-22","end_date":"2017-04-29"},"oa_version":"Submitted Version","page":"169 - 187","corr_author":"1","abstract":[{"lang":"eng","text":"Time-triggered switched networks are a deterministic communication infrastructure used by real-time distributed embedded systems. Due to the criticality of the applications running over them, developers need to ensure that end-to-end communication is dependable and predictable. Traditional approaches assume static networks that are not flexible to changes caused by reconfigurations or, more importantly, faults, which are dealt with in the application using redundancy. We adopt the concept of handling faults in the switches from non-real-time networks while maintaining the required predictability. \r\n\r\nWe study a class of forwarding schemes that can handle various types of failures. We consider probabilistic failures. We study a class of forwarding schemes that can handle various types of failures. We consider probabilistic failures. For a given network with a forwarding scheme and a constant ℓ, we compute the {\\em score} of the scheme, namely the probability (induced by faults) that at least ℓ messages arrive on time. We reduce the scoring problem to a reachability problem on a Markov chain with a "product-like" structure. Its special structure allows us to reason about it symbolically, and reduce the scoring problem to #SAT. Our solution is generic and can be adapted to different networks and other contexts. Also, we show the computational complexity of the scoring problem is #P-complete, and we study methods to estimate the score. We evaluate the effectiveness of our techniques with an implementation. "}],"publication_status":"published","ddc":["000"],"publisher":"Springer","citation":{"ama":"Avni G, Goel S, Henzinger TA, Rodríguez Navas G. Computing scores of forwarding schemes in switched networks with probabilistic faults. In: Vol 10206. Springer; 2017:169-187. doi:10.1007/978-3-662-54580-5_10","mla":"Avni, Guy, et al. Computing Scores of Forwarding Schemes in Switched Networks with Probabilistic Faults. Vol. 10206, Springer, 2017, pp. 169–87, doi:10.1007/978-3-662-54580-5_10.","chicago":"Avni, Guy, Shubham Goel, Thomas A Henzinger, and Guillermo Rodríguez Navas. “Computing Scores of Forwarding Schemes in Switched Networks with Probabilistic Faults,” 10206:169–87. Springer, 2017. https://doi.org/10.1007/978-3-662-54580-5_10.","ieee":"G. Avni, S. Goel, T. A. Henzinger, and G. Rodríguez Navas, “Computing scores of forwarding schemes in switched networks with probabilistic faults,” presented at the TACAS: Tools and Algorithms for the Construction and Analysis of Systems, Uppsala, Sweden, 2017, vol. 10206, pp. 169–187.","ista":"Avni G, Goel S, Henzinger TA, Rodríguez Navas G. 2017. Computing scores of forwarding schemes in switched networks with probabilistic faults. TACAS: Tools and Algorithms for the Construction and Analysis of Systems, LNCS, vol. 10206, 169–187.","apa":"Avni, G., Goel, S., Henzinger, T. A., & Rodríguez Navas, G. (2017). Computing scores of forwarding schemes in switched networks with probabilistic faults (Vol. 10206, pp. 169–187). Presented at the TACAS: Tools and Algorithms for the Construction and Analysis of Systems, Uppsala, Sweden: Springer. https://doi.org/10.1007/978-3-662-54580-5_10","short":"G. Avni, S. Goel, T.A. Henzinger, G. Rodríguez Navas, in:, Springer, 2017, pp. 169–187."},"project":[{"call_identifier":"FWF","name":"Moderne Concurrency Paradigms","grant_number":"S11402-N23","_id":"25F5A88A-B435-11E9-9278-68D0E5697425"},{"name":"Formal methods for the design and analysis of complex systems","grant_number":"Z211","_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"pubrep_id":"758","date_updated":"2026-04-16T09:56:24Z","author":[{"id":"463C8BC2-F248-11E8-B48F-1D18A9856A87","last_name":"Avni","orcid":"0000-0001-5588-8287","first_name":"Guy","full_name":"Avni, Guy"},{"full_name":"Goel, Shubham","first_name":"Shubham","last_name":"Goel"},{"full_name":"Henzinger, Thomas A","first_name":"Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Rodríguez Navas","first_name":"Guillermo","full_name":"Rodríguez Navas, Guillermo"}],"quality_controlled":"1","scopus_import":"1","alternative_title":["LNCS"],"oa":1,"publication_identifier":{"issn":["0302-9743"]},"status":"public","intvolume":" 10206","language":[{"iso":"eng"}],"volume":10206,"date_created":"2018-12-11T11:50:14Z","type":"conference","month":"03","file":[{"file_name":"IST-2017-758-v1+1_tacas-cr.pdf","date_updated":"2018-12-12T10:08:37Z","relation":"main_file","file_id":"4698","file_size":321800,"content_type":"application/pdf","date_created":"2018-12-12T10:08:37Z","access_level":"open_access","creator":"system"}],"article_processing_charge":"No","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","external_id":{"isi":["000440733400010"]},"file_date_updated":"2018-12-12T10:08:37Z","title":"Computing scores of forwarding schemes in switched networks with probabilistic faults","year":"2017","date_published":"2017-03-31T00:00:00Z","_id":"1116"},{"external_id":{"isi":["000404315200029"]},"year":"2017","title":"Comparison of the effects of nicotinic acid and nicotinamide degradation on plasma betaine and choline levels","_id":"1146","date_published":"2017-08-01T00:00:00Z","issue":"4","volume":36,"language":[{"iso":"eng"}],"intvolume":" 36","type":"journal_article","date_created":"2018-12-11T11:50:24Z","article_processing_charge":"No","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","month":"08","date_updated":"2025-09-22T09:59:49Z","author":[{"last_name":"Sun","first_name":"Wuping","full_name":"Sun, Wuping"},{"last_name":"Zhai","id":"34009CFA-F248-11E8-B48F-1D18A9856A87","full_name":"Zhai, Ming-Zhu","first_name":"Ming-Zhu"},{"last_name":"Li","first_name":"Da","full_name":"Li, Da"},{"full_name":"Zhou, Yiming","first_name":"Yiming","last_name":"Zhou"},{"last_name":"Chen","first_name":"Nana","full_name":"Chen, Nana"},{"first_name":"Ming","full_name":"Guo, Ming","last_name":"Guo"},{"last_name":"Zhou","first_name":"Shisheng","full_name":"Zhou, Shisheng"}],"citation":{"mla":"Sun, Wuping, et al. “Comparison of the Effects of Nicotinic Acid and Nicotinamide Degradation on Plasma Betaine and Choline Levels.” Clinical Nutrition, vol. 36, no. 4, Elsevier, 2017, pp. 1136–42, doi:10.1016/j.clnu.2016.07.016.","ama":"Sun W, Zhai M-Z, Li D, et al. Comparison of the effects of nicotinic acid and nicotinamide degradation on plasma betaine and choline levels. Clinical Nutrition. 2017;36(4):1136-1142. doi:10.1016/j.clnu.2016.07.016","short":"W. Sun, M.-Z. Zhai, D. Li, Y. Zhou, N. Chen, M. Guo, S. Zhou, Clinical Nutrition 36 (2017) 1136–1142.","apa":"Sun, W., Zhai, M.-Z., Li, D., Zhou, Y., Chen, N., Guo, M., & Zhou, S. (2017). Comparison of the effects of nicotinic acid and nicotinamide degradation on plasma betaine and choline levels. Clinical Nutrition. Elsevier. https://doi.org/10.1016/j.clnu.2016.07.016","ieee":"W. Sun et al., “Comparison of the effects of nicotinic acid and nicotinamide degradation on plasma betaine and choline levels,” Clinical Nutrition, vol. 36, no. 4. Elsevier, pp. 1136–1142, 2017.","ista":"Sun W, Zhai M-Z, Li D, Zhou Y, Chen N, Guo M, Zhou S. 2017. Comparison of the effects of nicotinic acid and nicotinamide degradation on plasma betaine and choline levels. Clinical Nutrition. 36(4), 1136–1142.","chicago":"Sun, Wuping, Ming-Zhu Zhai, Da Li, Yiming Zhou, Nana Chen, Ming Guo, and Shisheng Zhou. “Comparison of the Effects of Nicotinic Acid and Nicotinamide Degradation on Plasma Betaine and Choline Levels.” Clinical Nutrition. Elsevier, 2017. https://doi.org/10.1016/j.clnu.2016.07.016."},"publisher":"Elsevier","quality_controlled":"1","publication":"Clinical Nutrition","scopus_import":"1","publication_identifier":{"issn":["0261-5614"]},"status":"public","acknowledgement":"We thank all the participants for their contribution to this study and volunteers from the Nursing School of Dalian University for their supporting to collect blood and urine samples of the participants. We also thank Dr. Yasunori Takayama from National Institute for Physiological Sciences of Japan for his kind help.","publist_id":"6212","day":"01","doi":"10.1016/j.clnu.2016.07.016","department":[{"_id":"RySh"}],"isi":1,"oa_version":"None","publication_status":"published","page":"1136-1142","abstract":[{"text":"Aim: The present study was to compare the effects of nicotinic acid and nicotinamide on the plasma methyl donors, choline and betaine. Methods: Thirty adult subjects were randomly divided into three groups of equal size, and orally received purified water (C group), nicotinic acid (300 mg, NA group) or nicotinamide (300 mg, NM group). Plasma nicotinamide, N 1-methylnicotinamide, homocysteine, betaine and choline levels before and 1.5-h and 3-h post-dosing, plasma normetanephrine and metanephrine concentrations at 3-h post-dosing, and the urinary excretion of N 1-methyl-2-pyridone-5-carboxamide during the test period were examined. Results: The level of 3-h plasma nicotinamide, N 1-methylnicotinamide, homocysteine, the urinary excretion of N 1-methyl-2-pyridone-5-carboxamide and pulse pressure (PP) in the NM group was 221%, 3972%, 61%, 1728% and 21.2% higher than that of the control group (P < 0.01, except homocysteine and PP P < 0.05), while the 3-h plasma betaine, normetanephrine and metanephrine level in the NM group was 24.4%, 9.4% and 11.7% lower (P < 0.05, except betaine P < 0.01), without significant difference in choline levels. Similar but less pronounced changes were observed in the NA group, with a lower level of 3-h plasma N 1-methylnicotinamide (1.90 ± 0.20 μmol/l vs. 3.62 ± 0.27 μmol/l, P < 0.01) and homocysteine (12.85 ± 1.39 μmol/l vs. 18.08 ± 1.02 μmol/l, P < 0.05) but a higher level of betaine (27.44 ± 0.71 μmol/l vs. 23.52 ± 0.61 μmol/l, P < 0.05) than that of the NM group. Conclusion: The degradation of nicotinamide consumes more betaine than that of nicotinic acid at identical doses. This difference should be taken into consideration in niacin fortification. © 2016 Elsevier Ltd and European Society for Clinical Nutrition and Metabolism.","lang":"eng"}]},{"extern":"1","day":"01","doi":"10.1093/mnras/stx1569","publication_status":"published","keyword":["Space and Planetary Science","Astronomy and Astrophysics galaxies","active","galaxies","evolution","galaxies","high-redshift","galaxies","luminosity function","mass function","galaxies: star formation"],"page":"629-649","abstract":[{"text":"We present a sample of ∼1000 emission-line galaxies at z = 0.4–4.7 from the ∼0.7deg2 High-z Emission-Line Survey in the Boötes field identified with a suite of six narrow-band filters at ≈0.4–2.1 μm. These galaxies have been selected on their Ly α (73), [O II] (285), H β/[O III] (387) or H α (362) emission line, and have been classified with optical to near-infrared colours. A subsample of 98 sources have reliable redshifts from multiple narrow-band (e.g. [O II]–H α) detections and/or spectroscopy. In this survey paper, we present the observations, selection and catalogues of emitters. We measure number densities of Ly α, [O II], H β/[O III] and H α and confirm strong luminosity evolution in star-forming galaxies from z ∼ 0.4 to ∼5, in agreement with previous results. To demonstrate the usefulness of dual-line emitters, we use the sample of dual [O II]–H α emitters to measure the observed [O II]/H α ratio at z = 1.47. The observed [O II]/H α ratio increases significantly from 0.40 ± 0.01 at z = 0.1 to 0.52 ± 0.05 at z = 1.47, which we attribute to either decreasing dust attenuation with redshift, or due to a bias in the (typically) fibre measurements in the local Universe that only measure the central kpc regions. At the bright end, we find that both the H α and Ly α number densities at z ≈ 2.2 deviate significantly from a Schechter form, following a power law. We show that this is driven entirely by an increasing X-ray/active galactic nucleus fraction with line luminosity, which reaches ≈100 per cent at line luminosities L ≳ 3 × 1044 erg s−1.","lang":"eng"}],"oa_version":"Preprint","quality_controlled":"1","date_updated":"2024-10-14T11:34:07Z","author":[{"first_name":"Jorryt J","full_name":"Matthee, Jorryt J","orcid":"0000-0003-2871-127X","last_name":"Matthee","id":"7439a258-f3c0-11ec-9501-9df22fe06720"},{"first_name":"David","full_name":"Sobral, David","last_name":"Sobral"},{"full_name":"Best, Philip","first_name":"Philip","last_name":"Best"},{"full_name":"Smail, Ian","first_name":"Ian","last_name":"Smail"},{"full_name":"Bian, Fuyan","first_name":"Fuyan","last_name":"Bian"},{"last_name":"Darvish","first_name":"Behnam","full_name":"Darvish, Behnam"},{"first_name":"Huub","full_name":"Röttgering, Huub","last_name":"Röttgering"},{"full_name":"Fan, Xiaohui","first_name":"Xiaohui","last_name":"Fan"}],"citation":{"mla":"Matthee, Jorryt J., et al. “Boötes-HiZELS: An Optical to near-Infrared Survey of Emission-Line Galaxies at z = 0.4–4.7.” Monthly Notices of the Royal Astronomical Society, vol. 471, no. 1, Oxford University Press, 2017, pp. 629–49, doi:10.1093/mnras/stx1569.","ama":"Matthee JJ, Sobral D, Best P, et al. Boötes-HiZELS: An optical to near-infrared survey of emission-line galaxies at z = 0.4–4.7. Monthly Notices of the Royal Astronomical Society. 2017;471(1):629-649. doi:10.1093/mnras/stx1569","short":"J.J. Matthee, D. Sobral, P. Best, I. Smail, F. Bian, B. Darvish, H. Röttgering, X. Fan, Monthly Notices of the Royal Astronomical Society 471 (2017) 629–649.","apa":"Matthee, J. J., Sobral, D., Best, P., Smail, I., Bian, F., Darvish, B., … Fan, X. (2017). Boötes-HiZELS: An optical to near-infrared survey of emission-line galaxies at z = 0.4–4.7. Monthly Notices of the Royal Astronomical Society. Oxford University Press. https://doi.org/10.1093/mnras/stx1569","ista":"Matthee JJ, Sobral D, Best P, Smail I, Bian F, Darvish B, Röttgering H, Fan X. 2017. Boötes-HiZELS: An optical to near-infrared survey of emission-line galaxies at z = 0.4–4.7. Monthly Notices of the Royal Astronomical Society. 471(1), 629–649.","chicago":"Matthee, Jorryt J, David Sobral, Philip Best, Ian Smail, Fuyan Bian, Behnam Darvish, Huub Röttgering, and Xiaohui Fan. “Boötes-HiZELS: An Optical to near-Infrared Survey of Emission-Line Galaxies at z = 0.4–4.7.” Monthly Notices of the Royal Astronomical Society. Oxford University Press, 2017. https://doi.org/10.1093/mnras/stx1569.","ieee":"J. J. Matthee et al., “Boötes-HiZELS: An optical to near-infrared survey of emission-line galaxies at z = 0.4–4.7,” Monthly Notices of the Royal Astronomical Society, vol. 471, no. 1. Oxford University Press, pp. 629–649, 2017."},"publisher":"Oxford University Press","publication_identifier":{"issn":["0035-8711","1365-2966"]},"status":"public","oa":1,"publication":"Monthly Notices of the Royal Astronomical Society","scopus_import":"1","volume":471,"language":[{"iso":"eng"}],"intvolume":" 471","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1702.04721"}],"issue":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","article_type":"original","month":"10","type":"journal_article","date_created":"2022-07-12T11:01:35Z","year":"2017","title":"Boötes-HiZELS: An optical to near-infrared survey of emission-line galaxies at z = 0.4–4.7","arxiv":1,"external_id":{"arxiv":["1702.04721"]},"_id":"11561","date_published":"2017-10-01T00:00:00Z"},{"issue":"1","main_file_link":[{"url":"https://arxiv.org/abs/1609.05897","open_access":"1"}],"intvolume":" 466","language":[{"iso":"eng"}],"volume":466,"date_created":"2022-07-12T12:04:16Z","type":"journal_article","article_type":"original","month":"04","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["1609.05897"]},"arxiv":1,"title":"The CALYMHA survey: Lyα luminosity function and global escape fraction of Lyα photons at z = 2.23","year":"2017","date_published":"2017-04-01T00:00:00Z","_id":"11562","doi":"10.1093/mnras/stw3090","day":"01","extern":"1","oa_version":"Preprint","abstract":[{"lang":"eng","text":"We present the CAlibrating LYMan-α with Hα (CALYMHA) pilot survey and new results on Lyman α (Lyα) selected galaxies at z ∼ 2. We use a custom-built Lyα narrow-band filter at the Isaac Newton Telescope, designed to provide a matched volume coverage to the z = 2.23 Hα HiZELS survey. Here, we present the first results for the COSMOS and UDS fields. Our survey currently reaches a 3σ line flux limit of ∼4 × 10−17 erg s−1 cm−2, and a Lyα luminosity limit of ∼1042.3 erg s−1. We find 188 Lyα emitters over 7.3 × 105 Mpc3, but also find significant numbers of other line-emitting sources corresponding to He II, C III] and C IV emission lines. These sources are important contaminants, and we carefully remove them, unlike most previous studies. We find that the Lyα luminosity function at z = 2.23 is very well described by a Schechter function up to LLy α ≈ 1043 erg s−1 with L∗=1042.59+0.16−0.08 erg s−1, ϕ∗=10−3.09+0.14−0.34 Mpc−3 and α = −1.75 ± 0.25. Above LLy α ≈ 1043 erg s−1, the Lyα luminosity function becomes power-law like, driven by X-ray AGN. We find that Lyα-selected emitters have a high escape fraction of 37 ± 7 per cent, anticorrelated with Lyα luminosity and correlated with Lyα equivalent width. Lyα emitters have ubiquitous large (≈40 kpc) Lyα haloes, ∼2 times larger than their Hα extents. By directly comparing our Lyα and Hα luminosity functions, we find that the global/overall escape fraction of Lyα photons (within a 13 kpc radius) from the full population of star-forming galaxies is 5.1 ± 0.2 per cent at the peak of the star formation history. An extra 3.3 ± 0.3 per cent of Lyα photons likely still escape, but at larger radii."}],"page":"1242-1258","keyword":["Space and Planetary Science","Astronomy and Astrophysics","galaxies: evolution","galaxies: haloes","galaxies: high-redshift","galaxies: luminosity function","mass function","galaxies: statistics","cosmology: observations"],"publication_status":"published","publisher":"Oxford University Press","citation":{"short":"D. Sobral, J.J. Matthee, P. Best, A. Stroe, H. Röttgering, I. Oteo, I. Smail, L. Morabito, A. Paulino-Afonso, Monthly Notices of the Royal Astronomical Society 466 (2017) 1242–1258.","apa":"Sobral, D., Matthee, J. J., Best, P., Stroe, A., Röttgering, H., Oteo, I., … Paulino-Afonso, A. (2017). The CALYMHA survey: Lyα luminosity function and global escape fraction of Lyα photons at z = 2.23. Monthly Notices of the Royal Astronomical Society. Oxford University Press. https://doi.org/10.1093/mnras/stw3090","ieee":"D. Sobral et al., “The CALYMHA survey: Lyα luminosity function and global escape fraction of Lyα photons at z = 2.23,” Monthly Notices of the Royal Astronomical Society, vol. 466, no. 1. Oxford University Press, pp. 1242–1258, 2017.","ista":"Sobral D, Matthee JJ, Best P, Stroe A, Röttgering H, Oteo I, Smail I, Morabito L, Paulino-Afonso A. 2017. The CALYMHA survey: Lyα luminosity function and global escape fraction of Lyα photons at z = 2.23. Monthly Notices of the Royal Astronomical Society. 466(1), 1242–1258.","chicago":"Sobral, David, Jorryt J Matthee, Philip Best, Andra Stroe, Huub Röttgering, Iván Oteo, Ian Smail, Leah Morabito, and Ana Paulino-Afonso. “The CALYMHA Survey: Lyα Luminosity Function and Global Escape Fraction of Lyα Photons at z = 2.23.” Monthly Notices of the Royal Astronomical Society. Oxford University Press, 2017. https://doi.org/10.1093/mnras/stw3090.","mla":"Sobral, David, et al. “The CALYMHA Survey: Lyα Luminosity Function and Global Escape Fraction of Lyα Photons at z = 2.23.” Monthly Notices of the Royal Astronomical Society, vol. 466, no. 1, Oxford University Press, 2017, pp. 1242–58, doi:10.1093/mnras/stw3090.","ama":"Sobral D, Matthee JJ, Best P, et al. The CALYMHA survey: Lyα luminosity function and global escape fraction of Lyα photons at z = 2.23. Monthly Notices of the Royal Astronomical Society. 2017;466(1):1242-1258. doi:10.1093/mnras/stw3090"},"author":[{"first_name":"David","full_name":"Sobral, David","last_name":"Sobral"},{"first_name":"Jorryt J","full_name":"Matthee, Jorryt J","last_name":"Matthee","orcid":"0000-0003-2871-127X","id":"7439a258-f3c0-11ec-9501-9df22fe06720"},{"full_name":"Best, Philip","first_name":"Philip","last_name":"Best"},{"last_name":"Stroe","full_name":"Stroe, Andra","first_name":"Andra"},{"first_name":"Huub","full_name":"Röttgering, Huub","last_name":"Röttgering"},{"last_name":"Oteo","full_name":"Oteo, Iván","first_name":"Iván"},{"last_name":"Smail","first_name":"Ian","full_name":"Smail, Ian"},{"last_name":"Morabito","first_name":"Leah","full_name":"Morabito, Leah"},{"last_name":"Paulino-Afonso","first_name":"Ana","full_name":"Paulino-Afonso, Ana"}],"date_updated":"2024-10-14T11:35:37Z","quality_controlled":"1","publication":"Monthly Notices of the Royal Astronomical Society","scopus_import":"1","acknowledgement":"We thank the reviewer for his/her helpful comments and suggestions that have greatly improved this work. DS and JM acknowledge financial support from the Netherlands Organisation for Scientific research (NWO) through a Veni fellowship. DS also acknowledges funding from FCT through an FCT Investigator Starting Grant and Start-up Grant (IF/01154/2012/CP0189/CT0010). PNB is grateful for support from the UK STFC via grant ST/M001229/1. IRS acknowledges support from STFC (ST/L00075X/1), the ERC Advanced Investigator programme DUSTYGAL 321334 and a Royal Society/Wolfson merit award. We thank Matthew Hayes, Ryan Trainor, Kimihiko Nakajima and Anne Verhamme for many helpful discussions and Ana Sobral, Carolina Duarte and Miguel Domingos for taking part in observations with the NB392 filter. We also thank Sergio Santos for helpful comments. This research is based on observations obtained on the Isaac Newton Telescope (INT), programs: I13AN002, I14AN002, 088-INT7/14A, I14BN006, 118-INT13/14B & I15AN008. The authors acknowledge the award of time from programmes: I13AN002, I14AN002, 088-INT7/14A, I14BN006, 118-INT13/14B, I15AN008 on the INT. INT is operated on the island of La Palma by the Isaac Newton Group in the Spanish Observatorio del Roque de los Muchachos of the Instituto de Astrofisica de Canarias. Based on observations made with ESO Telescopes at the La Silla Paranal Observatory under programme ID 098.A 0819. We have benefited greatly from the publicly available programming language PYTHON, including the NUMPY, MATPLOTLIB, PYFITS, SCIPY and ASTROPY packages, the astronomical imaging tools SEXTRACTOR, SWARP (Bertin & Arnouts 1996; Bertin 2010), SCAMP (Bertin 2006) and TOPCAT (Taylor 2005). Dedicated to the memory of M. L. Nicolau and M. C. Serrano.","oa":1,"status":"public","publication_identifier":{"issn":["0035-8711"],"eissn":["1365-2966"]}},{"publication_identifier":{"issn":["0035-8711"],"eissn":["1365-2966"]},"status":"public","oa":1,"acknowledgement":"We thank the referee for the many helpful and constructive comments which have significantly improved this paper. JM acknowledges the support of a Huygens PhD fellowship from Leiden University. DS acknowledges financial support from the Netherlands Organization for Scientific research (NWO) through a Veni fellowship and from FCT through an FCT Investigator Starting Grant and Start-up Grant (IF/01154/2012/CP0189/CT0010). PNB is grateful for support from the UK STFC via grant ST/M001229/1. IO acknowledges support from the European Research Council in the form of the Advanced Investigator Programme, 321302, COSMICISM. The authors thank Andreas Faisst, Michael Rutkowski and Andreas Sandberg for answering questions related to this work and Daniel Schaerer and Mark Dijkstra for discussions. We acknowledge the work that has been done by both the COSMOS team in assembling such large, state-of-the-art multi-wavelength data set, as this has been crucial for the results presented in this paper. We have benefited greatly from the public available programming language PYTHON, including the NUMPY, MATPLOTLIB, PYFITS, SCIPY (Jones et al. 2001; Hunter 2007; Van Der Walt, Colbert & Varoquaux 2011) and ASTROPY (Astropy Collaboration et al. 2013) packages, the astronomical imaging tools SEXTRACTOR and SWARP (Bertin & Arnouts 1996;\r\nBertin 2010) and the TOPCAT analysis program (Taylor 2013).","scopus_import":"1","publication":"Monthly Notices of the Royal Astronomical Society","quality_controlled":"1","author":[{"full_name":"Matthee, Jorryt J","first_name":"Jorryt J","id":"7439a258-f3c0-11ec-9501-9df22fe06720","last_name":"Matthee","orcid":"0000-0003-2871-127X"},{"first_name":"David","full_name":"Sobral, David","last_name":"Sobral"},{"last_name":"Best","first_name":"Philip","full_name":"Best, Philip"},{"first_name":"Ali Ahmad","full_name":"Khostovan, Ali Ahmad","last_name":"Khostovan"},{"full_name":"Oteo, Iván","first_name":"Iván","last_name":"Oteo"},{"full_name":"Bouwens, Rychard","first_name":"Rychard","last_name":"Bouwens"},{"last_name":"Röttgering","first_name":"Huub","full_name":"Röttgering, Huub"}],"date_updated":"2024-10-14T11:35:49Z","publisher":"Oxford University Press","citation":{"ama":"Matthee JJ, Sobral D, Best P, et al. The production and escape of Lyman-Continuum radiation from star-forming galaxies at z ∼ 2 and their redshift evolution. Monthly Notices of the Royal Astronomical Society. 2017;465(3):3637-3655. doi:10.1093/mnras/stw2973","mla":"Matthee, Jorryt J., et al. “The Production and Escape of Lyman-Continuum Radiation from Star-Forming Galaxies at z ∼ 2 and Their Redshift Evolution.” Monthly Notices of the Royal Astronomical Society, vol. 465, no. 3, Oxford University Press, 2017, pp. 3637–55, doi:10.1093/mnras/stw2973.","ista":"Matthee JJ, Sobral D, Best P, Khostovan AA, Oteo I, Bouwens R, Röttgering H. 2017. The production and escape of Lyman-Continuum radiation from star-forming galaxies at z ∼ 2 and their redshift evolution. Monthly Notices of the Royal Astronomical Society. 465(3), 3637–3655.","ieee":"J. J. Matthee et al., “The production and escape of Lyman-Continuum radiation from star-forming galaxies at z ∼ 2 and their redshift evolution,” Monthly Notices of the Royal Astronomical Society, vol. 465, no. 3. Oxford University Press, pp. 3637–3655, 2017.","chicago":"Matthee, Jorryt J, David Sobral, Philip Best, Ali Ahmad Khostovan, Iván Oteo, Rychard Bouwens, and Huub Röttgering. “The Production and Escape of Lyman-Continuum Radiation from Star-Forming Galaxies at z ∼ 2 and Their Redshift Evolution.” Monthly Notices of the Royal Astronomical Society. Oxford University Press, 2017. https://doi.org/10.1093/mnras/stw2973.","short":"J.J. Matthee, D. Sobral, P. Best, A.A. Khostovan, I. Oteo, R. Bouwens, H. Röttgering, Monthly Notices of the Royal Astronomical Society 465 (2017) 3637–3655.","apa":"Matthee, J. J., Sobral, D., Best, P., Khostovan, A. A., Oteo, I., Bouwens, R., & Röttgering, H. (2017). The production and escape of Lyman-Continuum radiation from star-forming galaxies at z ∼ 2 and their redshift evolution. Monthly Notices of the Royal Astronomical Society. Oxford University Press. https://doi.org/10.1093/mnras/stw2973"},"publication_status":"published","keyword":["Space and Planetary Science","Astronomy and Astrophysics","galaxies: evolution","galaxies: high-redshift","cosmology: observations","dark ages","reionization","first stars"],"page":"3637-3655","abstract":[{"text":"We study the production rate of ionizing photons of a sample of 588 Hα emitters (HAEs) and 160 Lyman-α emitters (LAEs) at z = 2.2 in the COSMOS field in order to assess the implied emissivity from galaxies, based on their ultraviolet (UV) luminosity. By exploring the rest-frame Lyman Continuum (LyC) with GALEX/NUV data, we find fesc < 2.8 (6.4) per cent through median (mean) stacking. By combining the Hα luminosity density with intergalactic medium emissivity measurements from absorption studies, we find a globally averaged 〈fesc〉 of 5.9+14.5−4.2 per cent at z = 2.2 if we assume HAEs are the only source of ionizing photons. We find similarly low values of the global 〈fesc〉 at z ≈ 3–5, also ruling out a high 〈fesc〉 at z < 5. These low escape fractions allow us to measure ξion, the number of produced ionizing photons per unit UV luminosity, and investigate how this depends on galaxy properties. We find a typical ξion ≈ 1024.77 ± 0.04 Hz erg−1 for HAEs and ξion ≈ 1025.14 ± 0.09 Hz erg−1 for LAEs. LAEs and low-mass HAEs at z = 2.2 show similar values of ξion as typically assumed in the reionization era, while the typical HAE is three times less ionizing. Due to an increasing ξion with increasing EW(Hα), ξion likely increases with redshift. This evolution alone is fully in line with the observed evolution of ξion between z ≈ 2 and 5, indicating a typical value of ξion ≈ 1025.4 Hz erg−1 in the reionization era.","lang":"eng"}],"oa_version":"Preprint","extern":"1","day":"01","doi":"10.1093/mnras/stw2973","_id":"11564","date_published":"2017-03-01T00:00:00Z","year":"2017","title":"The production and escape of Lyman-Continuum radiation from star-forming galaxies at z ∼ 2 and their redshift evolution","arxiv":1,"external_id":{"arxiv":["1605.08782"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","month":"03","article_type":"original","type":"journal_article","date_created":"2022-07-12T12:12:14Z","volume":465,"language":[{"iso":"eng"}],"intvolume":" 465","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1605.08782"}],"issue":"3"},{"month":"11","article_type":"original","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2022-07-13T09:47:39Z","type":"journal_article","intvolume":" 472","language":[{"iso":"eng"}],"volume":472,"issue":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1706.06591"}],"date_published":"2017-11-01T00:00:00Z","_id":"11572","arxiv":1,"title":"Spectroscopic properties of luminous Ly α emitters at z ≈ 6–7 and comparison to the Lyman-break population","year":"2017","external_id":{"arxiv":["1706.06591"]},"abstract":[{"lang":"eng","text":"We present spectroscopic follow-up of candidate luminous Ly α emitters (LAEs) at z = 5.7–6.6 in the SA22 field with VLT/X-SHOOTER. We confirm two new luminous LAEs at z = 5.676 (SR6) and z = 6.532 (VR7), and also present HST follow-up of both sources. These sources have luminosities LLy α ≈ 3 × 1043 erg s−1, very high rest-frame equivalent widths of EW0 ≳ 200 Å and narrow Ly α lines (200–340 km s−1). VR7 is the most UV-luminous LAE at z > 6.5, with M1500 = −22.5, even brighter in the UV than CR7. Besides Ly α, we do not detect any other rest-frame UV lines in the spectra of SR6 and VR7, and argue that rest-frame UV lines are easier to observe in bright galaxies with low Ly α equivalent widths. We confirm that Ly α line widths increase with Ly α luminosity at z = 5.7, while there are indications that Ly α lines of faint LAEs become broader at z = 6.6, potentially due to reionization. We find a large spread of up to 3 dex in UV luminosity for >L⋆ LAEs, but find that the Ly α luminosity of the brightest LAEs is strongly related to UV luminosity at z = 6.6. Under basic assumptions, we find that several LAEs at z ≈ 6–7 have Ly α escape fractions ≳ 100 per cent, indicating bursty star formation histories, alternative Ly α production mechanisms, or dust attenuating Ly α emission differently than UV emission. Finally, we present a method to compute ξion, the production efficiency of ionizing photons, and find that LAEs at z ≈ 6–7 have high values of log10(ξion/Hz erg−1) ≈ 25.51 ± 0.09 that may alleviate the need for high Lyman-Continuum escape fractions required for reionization."}],"page":"772-787","keyword":["Space and Planetary Science","Astronomy and Astrophysics","galaxies: evolution – galaxies: high-redshift","dark ages","reionization","first stars","cosmology: observations"],"publication_status":"published","oa_version":"Preprint","extern":"1","doi":"10.1093/mnras/stx2061","day":"01","acknowledgement":"We thank the referee for a constructive report that has improved the quality and clarity of this work. The authors thank Grecco Oyarzún for discussions. JM acknowledges the support of a Huygens PhD fellowship from Leiden University. DS acknowledges financial support from the Netherlands Organisation for Scientific research (NWO) through a Veni fellowship and from Lancaster University through an Early Career Internal Grant A100679. BD acknowledges financial support from NASA through the Astrophysics Data Analysis Program (ADAP), grant number NNX12AE20G. We thank Kasper Schmidt for providing measurements. Based on observations with the W.M. Keck Observatory through programme C267D. The W.M. Keck Observatory is operated as a scientific partnership amongst the California Institute of Technology, the University of California and the National Aeronautics and Space Administration. Based on observations made with ESO Telescopes at the La Silla Paranal Observatory under programme IDs 097.A-0943, 294.A 5018 and 098.A-0819 and on data products produced by TERAPIX and the Cambridge Astronomy Survey Unit on behalf of the UltraVISTA consortium. The authors acknowledge the award of observing time (W16AN004) and of service time (SW2014b20) on the William Herschel Telescope (WHT). WHT and its service programme are operated on the island of La Palma by the Isaac Newton Group in the Spanish Observatorio del Roque de los Muchachos of the Instituto de Astrofisica de Canarias. Based on observations made with the NASA/ESA HST, obtained (from the Data Archive) at the Space Telescope Science Institute, which is operated by the Association of Universities for Research in Astronomy, Inc., under NASA contract NAS 5-26555. These observations are associated with programme #14699. We are grateful for the excellent data sets from the COSMOS, UltraVISTA, SXDS, UDS and CFHTLS survey teams; without these legacy surveys, this research would have been impossible. We have benefited from the public available programming language PYTHON, including the NUMPY, MATPLOTLIB, PYFITS, SCIPY and ASTROPY packages, the astronomical imaging tools SEXTRACTOR, SWARP and SCAMP and the TOPCAT analysis tool (Taylor 2013).","oa":1,"status":"public","publication_identifier":{"eissn":["1365-2966"],"issn":["0035-8711"]},"publication":"Monthly Notices of the Royal Astronomical Society","scopus_import":"1","quality_controlled":"1","publisher":"Oxford University Press","citation":{"chicago":"Matthee, Jorryt J, David Sobral, Behnam Darvish, Sérgio Santos, Bahram Mobasher, Ana Paulino-Afonso, Huub Röttgering, and Lara Alegre. “Spectroscopic Properties of Luminous Ly α Emitters at z ≈ 6–7 and Comparison to the Lyman-Break Population.” Monthly Notices of the Royal Astronomical Society. Oxford University Press, 2017. https://doi.org/10.1093/mnras/stx2061.","ieee":"J. J. Matthee et al., “Spectroscopic properties of luminous Ly α emitters at z ≈ 6–7 and comparison to the Lyman-break population,” Monthly Notices of the Royal Astronomical Society, vol. 472, no. 1. Oxford University Press, pp. 772–787, 2017.","ista":"Matthee JJ, Sobral D, Darvish B, Santos S, Mobasher B, Paulino-Afonso A, Röttgering H, Alegre L. 2017. Spectroscopic properties of luminous Ly α emitters at z ≈ 6–7 and comparison to the Lyman-break population. Monthly Notices of the Royal Astronomical Society. 472(1), 772–787.","apa":"Matthee, J. J., Sobral, D., Darvish, B., Santos, S., Mobasher, B., Paulino-Afonso, A., … Alegre, L. (2017). Spectroscopic properties of luminous Ly α emitters at z ≈ 6–7 and comparison to the Lyman-break population. Monthly Notices of the Royal Astronomical Society. Oxford University Press. https://doi.org/10.1093/mnras/stx2061","short":"J.J. Matthee, D. Sobral, B. Darvish, S. Santos, B. Mobasher, A. Paulino-Afonso, H. Röttgering, L. Alegre, Monthly Notices of the Royal Astronomical Society 472 (2017) 772–787.","ama":"Matthee JJ, Sobral D, Darvish B, et al. Spectroscopic properties of luminous Ly α emitters at z ≈ 6–7 and comparison to the Lyman-break population. Monthly Notices of the Royal Astronomical Society. 2017;472(1):772-787. doi:10.1093/mnras/stx2061","mla":"Matthee, Jorryt J., et al. “Spectroscopic Properties of Luminous Ly α Emitters at z ≈ 6–7 and Comparison to the Lyman-Break Population.” Monthly Notices of the Royal Astronomical Society, vol. 472, no. 1, Oxford University Press, 2017, pp. 772–87, doi:10.1093/mnras/stx2061."},"author":[{"first_name":"Jorryt J","full_name":"Matthee, Jorryt J","orcid":"0000-0003-2871-127X","id":"7439a258-f3c0-11ec-9501-9df22fe06720","last_name":"Matthee"},{"last_name":"Sobral","first_name":"David","full_name":"Sobral, David"},{"last_name":"Darvish","first_name":"Behnam","full_name":"Darvish, Behnam"},{"full_name":"Santos, Sérgio","first_name":"Sérgio","last_name":"Santos"},{"last_name":"Mobasher","full_name":"Mobasher, Bahram","first_name":"Bahram"},{"first_name":"Ana","full_name":"Paulino-Afonso, Ana","last_name":"Paulino-Afonso"},{"last_name":"Röttgering","full_name":"Röttgering, Huub","first_name":"Huub"},{"full_name":"Alegre, Lara","first_name":"Lara","last_name":"Alegre"}],"date_updated":"2024-10-14T11:36:26Z"},{"month":"11","abstract":[{"lang":"eng","text":"Our understanding of stars through asteroseismic data analysis is limited by our ability to take advantage of the huge amount of observed stars provided by space missions such as CoRoT, Kepler , K2, and soon TESS and PLATO. Global seismic pipelines provide global stellar parameters such as mass and radius using the mean seismic parameters, as well as the effective temperature. These pipelines are commonly used automatically on thousands of stars observed by K2 for 3 months (and soon TESS for at least ∼ 1 month). However, pipelines are not immune from misidentifying noise peaks and stellar oscillations. Therefore, new validation techniques are required to assess the quality of these results. We present a new metric called FliPer (Flicker in Power), which takes into account the average variability at all measured time scales. The proper calibration of FliPer enables us to obtain good estimations of global stellar parameters such as surface gravity that are robust against the influence of noise peaks and hence are an excellent way to find faults in asteroseismic pipelines."}],"publication_status":"submitted","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","keyword":["asteroseismology - methods","data analysis - stars","oscillations"],"date_created":"2022-07-21T07:13:13Z","oa_version":"Preprint","type":"preprint","language":[{"iso":"eng"}],"extern":"1","doi":"10.48550/arXiv.1711.02890","article_number":"1711.02890","day":"08","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1711.02890","open_access":"1"}],"oa":1,"status":"public","date_published":"2017-11-08T00:00:00Z","publication":"arXiv","_id":"11633","title":"FliPer: Checking the reliability of global seismic parameters from automatic pipelines","arxiv":1,"year":"2017","citation":{"mla":"Bugnet, Lisa Annabelle, et al. “FliPer: Checking the Reliability of Global Seismic Parameters from Automatic Pipelines.” ArXiv, 1711.02890, doi:10.48550/arXiv.1711.02890.","ama":"Bugnet LA, Garcia RA, Davies GR, Mathur S, Corsaro E. FliPer: Checking the reliability of global seismic parameters from automatic pipelines. arXiv. doi:10.48550/arXiv.1711.02890","apa":"Bugnet, L. A., Garcia, R. A., Davies, G. R., Mathur, S., & Corsaro, E. (n.d.). FliPer: Checking the reliability of global seismic parameters from automatic pipelines. arXiv. https://doi.org/10.48550/arXiv.1711.02890","short":"L.A. Bugnet, R.A. Garcia, G.R. Davies, S. Mathur, E. Corsaro, ArXiv (n.d.).","ista":"Bugnet LA, Garcia RA, Davies GR, Mathur S, Corsaro E. FliPer: Checking the reliability of global seismic parameters from automatic pipelines. arXiv, 1711.02890.","ieee":"L. A. Bugnet, R. A. Garcia, G. R. Davies, S. Mathur, and E. Corsaro, “FliPer: Checking the reliability of global seismic parameters from automatic pipelines,” arXiv. .","chicago":"Bugnet, Lisa Annabelle, R. A. Garcia, G. R. Davies, S. Mathur, and E. Corsaro. “FliPer: Checking the Reliability of Global Seismic Parameters from Automatic Pipelines.” ArXiv, n.d. https://doi.org/10.48550/arXiv.1711.02890."},"external_id":{"arxiv":["1711.02890"]},"date_updated":"2022-08-22T08:45:42Z","author":[{"full_name":"Bugnet, Lisa Annabelle","first_name":"Lisa Annabelle","orcid":"0000-0003-0142-4000","last_name":"Bugnet","id":"d9edb345-f866-11ec-9b37-d119b5234501"},{"last_name":"Garcia","first_name":"R. A.","full_name":"Garcia, R. A."},{"last_name":"Davies","full_name":"Davies, G. R.","first_name":"G. R."},{"first_name":"S.","full_name":"Mathur, S.","last_name":"Mathur"},{"full_name":"Corsaro, E.","first_name":"E.","last_name":"Corsaro"}]},{"date_published":"2017-07-03T00:00:00Z","_id":"1176","title":"Towards practical attacks on Argon2i and balloon hashing","year":"2017","external_id":{"isi":["000424197300011"]},"month":"07","article_processing_charge":"No","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","date_created":"2018-12-11T11:50:33Z","type":"conference","language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2016/759"}],"oa":1,"publication_identifier":{"isbn":["978-150905761-0"]},"status":"public","scopus_import":"1","quality_controlled":"1","citation":{"ama":"Alwen JF, Blocki J. Towards practical attacks on Argon2i and balloon hashing. In: IEEE; 2017. doi:10.1109/EuroSP.2017.47","mla":"Alwen, Joel F., and Jeremiah Blocki. Towards Practical Attacks on Argon2i and Balloon Hashing. 7961977, IEEE, 2017, doi:10.1109/EuroSP.2017.47.","ista":"Alwen JF, Blocki J. 2017. Towards practical attacks on Argon2i and balloon hashing. EuroS&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. https://doi.org/10.1109/EuroSP.2017.47.","ieee":"J. F. Alwen and J. Blocki, “Towards practical attacks on Argon2i and balloon hashing,” presented at the EuroS&P: European Symposium on Security and Privacy, Paris, France, 2017.","apa":"Alwen, J. F., & Blocki, J. (2017). Towards practical attacks on Argon2i and balloon hashing. Presented at the EuroS&P: European Symposium on Security and Privacy, Paris, France: IEEE. https://doi.org/10.1109/EuroSP.2017.47","short":"J.F. Alwen, J. Blocki, in:, IEEE, 2017."},"publisher":"IEEE","date_updated":"2023-09-20T11:22:25Z","author":[{"last_name":"Alwen","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F","first_name":"Joel F"},{"last_name":"Blocki","full_name":"Blocki, Jeremiah","first_name":"Jeremiah"}],"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."}],"publication_status":"published","oa_version":"Submitted Version","department":[{"_id":"KrPi"}],"isi":1,"conference":{"end_date":"2017-04-28","start_date":"2017-04-26","name":"EuroS&P: European Symposium on Security and Privacy","location":"Paris, France"},"doi":"10.1109/EuroSP.2017.47","article_number":"7961977","day":"03","publist_id":"6178"},{"status":"public","publication_identifier":{"eisbn":["9783319731179"],"issn":["0302-9743"],"isbn":["9783319731162"]},"alternative_title":["LNCS"],"scopus_import":"1","publication":"44th International Conference on Current Trends in Theory and Practice of Computer Science","date_published":"2017-12-22T00:00:00Z","_id":"11772","title":"The state of the art in dynamic graph algorithms","year":"2017","quality_controlled":"1","publisher":"Springer Nature","citation":{"short":"M. Henzinger, in:, 44th International Conference on Current Trends in Theory and Practice of Computer Science, Springer Nature, 2017, pp. 40–44.","apa":"Henzinger, M. (2017). The state of the art in dynamic graph algorithms. In 44th International Conference on Current Trends in Theory and Practice of Computer Science (Vol. 10706, pp. 40–44). Krems, Austria: Springer Nature. https://doi.org/10.1007/978-3-319-73117-9_3","chicago":"Henzinger, Monika. “The State of the Art in Dynamic Graph Algorithms.” In 44th International Conference on Current Trends in Theory and Practice of Computer Science, 10706:40–44. Springer Nature, 2017. https://doi.org/10.1007/978-3-319-73117-9_3.","ieee":"M. Henzinger, “The state of the art in dynamic graph algorithms,” in 44th International Conference on Current Trends in Theory and Practice of Computer Science, Krems, Austria, 2017, vol. 10706, pp. 40–44.","ista":"Henzinger M. 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.","mla":"Henzinger, Monika. “The State of the Art in Dynamic Graph Algorithms.” 44th International Conference on Current Trends in Theory and Practice of Computer Science, vol. 10706, Springer Nature, 2017, pp. 40–44, doi:10.1007/978-3-319-73117-9_3.","ama":"Henzinger M. The state of the art in dynamic graph algorithms. In: 44th International Conference on Current Trends in Theory and Practice of Computer Science. Vol 10706. Springer Nature; 2017:40–44. doi:10.1007/978-3-319-73117-9_3"},"author":[{"full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"}],"date_updated":"2024-11-06T08:15:42Z","abstract":[{"text":"A dynamic graph algorithm is a data structure that supports operations on dynamically changing graphs.","lang":"eng"}],"month":"12","page":"40–44","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","oa_version":"None","date_created":"2022-08-08T13:16:37Z","type":"conference","extern":"1","language":[{"iso":"eng"}],"intvolume":" 10706","conference":{"name":"SOFSEM: Theory and Practice of Computer Science","location":"Krems, Austria","end_date":"2018-02-02","start_date":"2018-01-29"},"volume":10706,"doi":"10.1007/978-3-319-73117-9_3","day":"22"},{"doi":"10.1007/978-3-662-53641-4_7","publist_id":"6176","day":"01","isi":1,"extern":"1","conference":{"name":"TCC: Theory of Cryptography Conference"},"oa_version":"Submitted Version","abstract":[{"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 ","lang":"eng"}],"page":"159 - 179","publication_status":"published","citation":{"ista":"Skórski M. 2017. Simulating auxiliary inputs, revisited. TCC: Theory of Cryptography Conference, LNCS, vol. 9985, 159–179.","ieee":"M. Skórski, “Simulating auxiliary inputs, revisited,” presented at the TCC: Theory of Cryptography Conference, 2017, vol. 9985, pp. 159–179.","chicago":"Skórski, Maciej. “Simulating Auxiliary Inputs, Revisited,” 9985:159–79. Springer, 2017. https://doi.org/10.1007/978-3-662-53641-4_7.","apa":"Skórski, M. (2017). Simulating auxiliary inputs, revisited (Vol. 9985, pp. 159–179). Presented at the TCC: Theory of Cryptography Conference, Springer. https://doi.org/10.1007/978-3-662-53641-4_7","short":"M. Skórski, in:, Springer, 2017, pp. 159–179.","ama":"Skórski M. Simulating auxiliary inputs, revisited. In: Vol 9985. Springer; 2017:159-179. doi:10.1007/978-3-662-53641-4_7","mla":"Skórski, Maciej. Simulating Auxiliary Inputs, Revisited. Vol. 9985, Springer, 2017, pp. 159–79, doi:10.1007/978-3-662-53641-4_7."},"publisher":"Springer","date_updated":"2023-09-20T11:21:57Z","author":[{"first_name":"Maciej","full_name":"Skórski, Maciej","last_name":"Skórski","id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD"}],"quality_controlled":"1","alternative_title":["LNCS"],"oa":1,"acknowledgement":"This work was supported by the National Science Center, Poland (2015/17/N/ST6/03564).","status":"public","main_file_link":[{"url":"https://eprint.iacr.org/2016/808.pdf ","open_access":"1"}],"intvolume":" 9985","language":[{"iso":"eng"}],"volume":9985,"date_created":"2018-12-11T11:50:34Z","type":"conference","month":"01","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","article_processing_charge":"No","external_id":{"isi":["000390176000007"]},"title":"Simulating auxiliary inputs, revisited","year":"2017","date_published":"2017-01-01T00:00:00Z","_id":"1178"},{"article_number":"26","doi":"10.4230/LIPICS.ITCS.2017.26","day":"28","extern":"1","conference":{"end_date":"2017-01-11","start_date":"2017-01-09","location":"Berkley, CA, United States","name":"ITCS: Innovations in Theoretical Computer Science Conference"},"oa_version":"Published Version","abstract":[{"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.","lang":"eng"}],"publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"ama":"Henzinger M, Lincoln A, Neumann S, Vassilevska Williams V. Conditional hardness for sensitivity problems. In: 8th Innovations in Theoretical Computer Science Conference. Vol 67. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ITCS.2017.26","mla":"Henzinger, Monika, et al. “Conditional Hardness for Sensitivity Problems.” 8th Innovations in Theoretical Computer Science Conference, vol. 67, 26, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPICS.ITCS.2017.26.","chicago":"Henzinger, Monika, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska Williams. “Conditional Hardness for Sensitivity Problems.” In 8th Innovations in Theoretical Computer Science Conference, Vol. 67. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPICS.ITCS.2017.26.","ieee":"M. Henzinger, A. Lincoln, S. Neumann, and V. Vassilevska Williams, “Conditional hardness for sensitivity problems,” in 8th Innovations in Theoretical Computer Science Conference, Berkley, CA, United States, 2017, vol. 67.","ista":"Henzinger M, 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.","apa":"Henzinger, M., Lincoln, A., Neumann, S., & Vassilevska Williams, V. (2017). Conditional hardness for sensitivity problems. In 8th Innovations in Theoretical Computer Science Conference (Vol. 67). Berkley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ITCS.2017.26","short":"M. Henzinger, A. Lincoln, S. Neumann, V. Vassilevska Williams, in:, 8th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017."},"date_updated":"2024-11-06T11:56:09Z","author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","orcid":"0000-0002-5008-6530","first_name":"Monika H","full_name":"Henzinger, Monika H"},{"full_name":"Lincoln, Andrea","first_name":"Andrea","last_name":"Lincoln"},{"full_name":"Neumann, Stefan","first_name":"Stefan","last_name":"Neumann"},{"first_name":"Virginia","full_name":"Vassilevska Williams, Virginia","last_name":"Vassilevska Williams"}],"quality_controlled":"1","alternative_title":["LIPIcs"],"publication":"8th Innovations in Theoretical Computer Science Conference","scopus_import":"1","oa":1,"status":"public","publication_identifier":{"isbn":["9783959770293"],"issn":["1868-8969"]},"main_file_link":[{"url":"https://doi.org/10.4230/LIPICS.ITCS.2017.26","open_access":"1"}],"intvolume":" 67","language":[{"iso":"eng"}],"volume":67,"date_created":"2022-08-12T08:55:33Z","type":"conference","month":"11","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["1703.01638"]},"arxiv":1,"title":"Conditional hardness for sensitivity problems","year":"2017","date_published":"2017-11-28T00:00:00Z","_id":"11829"},{"year":"2017","arxiv":1,"title":"Improved guarantees for vertex sparsification in planar graphs","external_id":{"arxiv":["1702.01136"]},"_id":"11831","date_published":"2017-09-01T00:00:00Z","volume":87,"language":[{"iso":"eng"}],"intvolume":" 87","main_file_link":[{"url":"https://doi.org/10.4230/LIPIcs.ESA.2017.44","open_access":"1"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","month":"09","type":"conference","date_created":"2022-08-12T09:27:11Z","quality_controlled":"1","author":[{"first_name":"Gramoz","full_name":"Goranci, Gramoz","last_name":"Goranci"},{"full_name":"Henzinger, Monika H","first_name":"Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"Peng, Pan","first_name":"Pan","last_name":"Peng"}],"date_updated":"2024-11-06T11:57:54Z","citation":{"ama":"Goranci G, Henzinger M, Peng P. Improved guarantees for vertex sparsification in planar graphs. In: 25th Annual European Symposium on Algorithms. Vol 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ESA.2017.44","mla":"Goranci, Gramoz, et al. “Improved Guarantees for Vertex Sparsification in Planar Graphs.” 25th Annual European Symposium on Algorithms, vol. 87, 44, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPICS.ESA.2017.44.","ieee":"G. Goranci, M. Henzinger, and P. Peng, “Improved guarantees for vertex sparsification in planar graphs,” in 25th Annual European Symposium on Algorithms, Vienna, Austria, 2017, vol. 87.","chicago":"Goranci, Gramoz, Monika Henzinger, and Pan Peng. “Improved Guarantees for Vertex Sparsification in Planar Graphs.” In 25th Annual European Symposium on Algorithms, Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPICS.ESA.2017.44.","ista":"Goranci G, Henzinger M, 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.","short":"G. Goranci, M. Henzinger, P. Peng, in:, 25th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","apa":"Goranci, G., Henzinger, M., & Peng, P. (2017). Improved guarantees for vertex sparsification in planar graphs. In 25th Annual European Symposium on Algorithms (Vol. 87). Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ESA.2017.44"},"related_material":{"record":[{"relation":"later_version","status":"public","id":"11894"}]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","status":"public","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-049-1"]},"oa":1,"alternative_title":["LIPIcs"],"publication":"25th Annual European Symposium on Algorithms","scopus_import":"1","conference":{"location":"Vienna, Austria","name":"ESA: Annual European Symposium on Algorithms","start_date":"2017-09-04","end_date":"2017-09-06"},"extern":"1","day":"01","article_number":"44","doi":"10.4230/LIPICS.ESA.2017.44","publication_status":"published","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"}],"oa_version":"Published Version"},{"intvolume":" 87","language":[{"iso":"eng"}],"volume":87,"main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPICS.ESA.2017.48"}],"month":"09","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","date_created":"2022-08-12T09:58:46Z","type":"conference","arxiv":1,"title":"Dynamic clustering to minimize the sum of radii","year":"2017","external_id":{"arxiv":["1707.02577"]},"date_published":"2017-09-01T00:00:00Z","_id":"11832","extern":"1","conference":{"name":"ESA: Annual European Symposium on Algorithms","location":"Vienna, Austria","end_date":"2017-09-06","start_date":"2017-09-04"},"article_number":"48","doi":"10.4230/LIPICS.ESA.2017.48","day":"01","abstract":[{"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.","lang":"eng"}],"publication_status":"published","oa_version":"Published Version","quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"mla":"Henzinger, Monika, et al. “Dynamic Clustering to Minimize the Sum of Radii.” 25th Annual European Symposium on Algorithms, vol. 87, 48, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPICS.ESA.2017.48.","ama":"Henzinger M, Leniowski D, Mathieu C. Dynamic clustering to minimize the sum of radii. In: 25th Annual European Symposium on Algorithms. Vol 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ESA.2017.48","apa":"Henzinger, M., Leniowski, D., & Mathieu, C. (2017). Dynamic clustering to minimize the sum of radii. In 25th Annual European Symposium on Algorithms (Vol. 87). Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ESA.2017.48","short":"M. Henzinger, D. Leniowski, C. Mathieu, in:, 25th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","ieee":"M. Henzinger, D. Leniowski, and C. Mathieu, “Dynamic clustering to minimize the sum of radii,” in 25th Annual European Symposium on Algorithms, Vienna, Austria, 2017, vol. 87.","chicago":"Henzinger, Monika, Dariusz Leniowski, and Claire Mathieu. “Dynamic Clustering to Minimize the Sum of Radii.” In 25th Annual European Symposium on Algorithms, Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPICS.ESA.2017.48.","ista":"Henzinger M, 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."},"date_updated":"2024-11-06T11:59:20Z","author":[{"full_name":"Henzinger, Monika H","first_name":"Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"first_name":"Dariusz","full_name":"Leniowski, Dariusz","last_name":"Leniowski"},{"last_name":"Mathieu","first_name":"Claire","full_name":"Mathieu, Claire"}],"oa":1,"status":"public","publication_identifier":{"isbn":["978-3-95977-049-1"],"issn":["1868-8969"]},"alternative_title":["LIPIcs"],"scopus_import":"1","publication":"25th Annual European Symposium on Algorithms"},{"quality_controlled":"1","date_updated":"2024-11-06T11:58:29Z","author":[{"last_name":"Goranci","first_name":"Gramoz","full_name":"Goranci, Gramoz"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H"},{"full_name":"Peng, Pan","first_name":"Pan","last_name":"Peng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"chicago":"Goranci, Gramoz, Monika Henzinger, and Pan Peng. “The Power of Vertex Sparsifiers in Dynamic Graph Algorithms.” In 25th Annual European Symposium on Algorithms, Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPICS.ESA.2017.45.","ieee":"G. Goranci, M. Henzinger, and P. Peng, “The power of vertex sparsifiers in dynamic graph algorithms,” in 25th Annual European Symposium on Algorithms, Vienna, Austria, 2017, vol. 87.","ista":"Goranci G, Henzinger M, 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.","apa":"Goranci, G., Henzinger, M., & Peng, P. (2017). The power of vertex sparsifiers in dynamic graph algorithms. In 25th Annual European Symposium on Algorithms (Vol. 87). Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ESA.2017.45","short":"G. Goranci, M. Henzinger, P. Peng, in:, 25th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","ama":"Goranci G, Henzinger M, Peng P. The power of vertex sparsifiers in dynamic graph algorithms. In: 25th Annual European Symposium on Algorithms. Vol 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ESA.2017.45","mla":"Goranci, Gramoz, et al. “The Power of Vertex Sparsifiers in Dynamic Graph Algorithms.” 25th Annual European Symposium on Algorithms, vol. 87, 45, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPICS.ESA.2017.45."},"status":"public","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-049-1"]},"oa":1,"alternative_title":["LIPIcs"],"publication":"25th Annual European Symposium on Algorithms","scopus_import":"1","conference":{"start_date":"2017-09-04","end_date":"2017-09-06","location":"Vienna, Austria","name":"ESA: Annual European Symposium on Algorithms"},"extern":"1","day":"01","article_number":"45","doi":"10.4230/LIPICS.ESA.2017.45","publication_status":"published","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."}],"oa_version":"Published Version","year":"2017","arxiv":1,"title":"The power of vertex sparsifiers in dynamic graph algorithms","external_id":{"arxiv":["1712.06473"]},"_id":"11833","date_published":"2017-09-01T00:00:00Z","volume":87,"language":[{"iso":"eng"}],"intvolume":" 87","main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPIcs.ESA.2017.45"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","month":"09","type":"conference","date_created":"2022-08-12T10:46:26Z"},{"article_processing_charge":"No","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","month":"10","article_type":"original","file":[{"file_name":"2017_JournalCrypto_Kiltz.pdf","date_updated":"2020-07-14T12:44:37Z","relation":"main_file","file_id":"7843","checksum":"c647520d115b772a1682fc06fa273eb1","file_size":516959,"content_type":"application/pdf","access_level":"open_access","creator":"dernst","date_created":"2020-05-14T16:30:17Z"}],"type":"journal_article","date_created":"2018-12-11T11:50:37Z","volume":30,"intvolume":" 30","language":[{"iso":"eng"}],"issue":"4","_id":"1187","date_published":"2017-10-01T00:00:00Z","year":"2017","title":"Efficient authentication from hard learning problems","file_date_updated":"2020-07-14T12:44:37Z","external_id":{"isi":["000410788600007"]},"publication_status":"published","ddc":["000"],"page":"1238 - 1275","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."}],"oa_version":"Submitted Version","department":[{"_id":"KrPi"}],"isi":1,"day":"01","publist_id":"6166","has_accepted_license":"1","doi":"10.1007/s00145-016-9247-3","status":"public","oa":1,"scopus_import":"1","publication":"Journal of Cryptology","quality_controlled":"1","ec_funded":1,"author":[{"last_name":"Kiltz","full_name":"Kiltz, Eike","first_name":"Eike"},{"orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z"},{"full_name":"Venturi, Daniele","first_name":"Daniele","last_name":"Venturi"},{"first_name":"David","full_name":"Cash, David","last_name":"Cash"},{"last_name":"Jain","full_name":"Jain, Abhishek","first_name":"Abhishek"}],"project":[{"call_identifier":"H2020","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks"},{"name":"Provable Security for Physical Cryptography","grant_number":"259668","_id":"258C570E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"date_updated":"2025-04-14T07:22:06Z","publisher":"Springer","related_material":{"record":[{"relation":"earlier_version","id":"3238","status":"public"}]},"citation":{"mla":"Kiltz, Eike, et al. “Efficient Authentication from Hard Learning Problems.” Journal of Cryptology, vol. 30, no. 4, Springer, 2017, pp. 1238–75, doi:10.1007/s00145-016-9247-3.","ama":"Kiltz E, Pietrzak KZ, Venturi D, Cash D, Jain A. Efficient authentication from hard learning problems. Journal of Cryptology. 2017;30(4):1238-1275. doi:10.1007/s00145-016-9247-3","apa":"Kiltz, E., Pietrzak, K. Z., Venturi, D., Cash, D., & Jain, A. (2017). Efficient authentication from hard learning problems. Journal of Cryptology. Springer. https://doi.org/10.1007/s00145-016-9247-3","short":"E. Kiltz, K.Z. Pietrzak, D. Venturi, D. Cash, A. Jain, Journal of Cryptology 30 (2017) 1238–1275.","ieee":"E. Kiltz, K. Z. Pietrzak, D. Venturi, D. Cash, and A. Jain, “Efficient authentication from hard learning problems,” Journal of Cryptology, vol. 30, no. 4. Springer, pp. 1238–1275, 2017.","chicago":"Kiltz, Eike, Krzysztof Z Pietrzak, Daniele Venturi, David Cash, and Abhishek Jain. “Efficient Authentication from Hard Learning Problems.” Journal of Cryptology. Springer, 2017. https://doi.org/10.1007/s00145-016-9247-3.","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."}},{"arxiv":1,"title":"Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time","year":"2017","external_id":{"arxiv":["1704.02844"]},"date_published":"2017-01-01T00:00:00Z","_id":"11874","language":[{"iso":"eng"}],"volume":"0","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1704.02844"}],"month":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","date_created":"2022-08-16T12:28:27Z","type":"conference","quality_controlled":"1","publisher":"Society for Industrial and Applied Mathematics","citation":{"short":"S. Bhattacharya, M. 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., & Nanongkai, D. (2017). Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time. In 28th Annual ACM-SIAM Symposium on Discrete Algorithms (Vol. 0, pp. 470–489). Barcelona, Spain: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611974782.30","chicago":"Bhattacharya, Sayan, Monika Henzinger, and Danupon Nanongkai. “Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in o(Log3 n) Worst Case Update Time.” In 28th Annual ACM-SIAM Symposium on Discrete Algorithms, 0:470–89. Society for Industrial and Applied Mathematics, 2017. https://doi.org/10.1137/1.9781611974782.30.","ista":"Bhattacharya S, Henzinger M, 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.","ieee":"S. Bhattacharya, M. Henzinger, and D. Nanongkai, “Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time,” in 28th Annual ACM-SIAM Symposium on Discrete Algorithms, 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.” 28th Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 0, Society for Industrial and Applied Mathematics, 2017, pp. 470–89, doi:10.1137/1.9781611974782.30.","ama":"Bhattacharya S, Henzinger M, Nanongkai D. Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time. In: 28th Annual ACM-SIAM Symposium on Discrete Algorithms. Vol 0. Society for Industrial and Applied Mathematics; 2017:470-489. doi:10.1137/1.9781611974782.30"},"author":[{"first_name":"Sayan","full_name":"Bhattacharya, Sayan","last_name":"Bhattacharya"},{"orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H"},{"full_name":"Nanongkai, Danupon","first_name":"Danupon","last_name":"Nanongkai"}],"date_updated":"2024-11-06T12:20:58Z","oa":1,"status":"public","publication_identifier":{"eisbn":["978-161197478-2"]},"scopus_import":"1","publication":"28th Annual ACM-SIAM Symposium on Discrete Algorithms","extern":"1","conference":{"end_date":"2017-01-19","start_date":"2017-01-16","location":"Barcelona, Spain","name":"SODA: Symposium on Discrete Algorithms"},"doi":"10.1137/1.9781611974782.30","day":"01","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"}],"page":"470 - 489","publication_status":"published","oa_version":"Preprint"}]