[{"date_created":"2018-12-11T11:50:34Z","abstract":[{"lang":"eng","text":"In this article we define an algebraic vertex of a generalized polyhedron and show that the set of algebraic vertices is the smallest set of points needed to define the polyhedron. We prove that the indicator function of a generalized polytope P is a linear combination of indicator functions of simplices whose vertices are algebraic vertices of P. We also show that the indicator function of any generalized polyhedron is a linear combination, with integer coefficients, of indicator functions of cones with apices at algebraic vertices and line-cones. The concept of an algebraic vertex is closely related to the Fourier–Laplace transform. We show that a point v is an algebraic vertex of a generalized polyhedron P if and only if the tangent cone of P, at v, has non-zero Fourier–Laplace transform."}],"volume":308,"language":[{"iso":"eng"}],"isi":1,"oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1508.07594","open_access":"1"}],"date_updated":"2023-09-20T11:21:27Z","day":"21","_id":"1180","publisher":"Academic Press","citation":{"ieee":"A. Akopyan, I. Bárány, and S. Robins, “Algebraic vertices of non-convex polyhedra,” Advances in Mathematics, vol. 308. Academic Press, pp. 627–644, 2017.","chicago":"Akopyan, Arseniy, Imre Bárány, and Sinai Robins. “Algebraic Vertices of Non-Convex Polyhedra.” Advances in Mathematics. Academic Press, 2017. https://doi.org/10.1016/j.aim.2016.12.026.","mla":"Akopyan, Arseniy, et al. “Algebraic Vertices of Non-Convex Polyhedra.” Advances in Mathematics, vol. 308, Academic Press, 2017, pp. 627–44, doi:10.1016/j.aim.2016.12.026.","ista":"Akopyan A, Bárány I, Robins S. 2017. Algebraic vertices of non-convex polyhedra. Advances in Mathematics. 308, 627–644.","ama":"Akopyan A, Bárány I, Robins S. Algebraic vertices of non-convex polyhedra. Advances in Mathematics. 2017;308:627-644. doi:10.1016/j.aim.2016.12.026","apa":"Akopyan, A., Bárány, I., & Robins, S. (2017). Algebraic vertices of non-convex polyhedra. Advances in Mathematics. Academic Press. https://doi.org/10.1016/j.aim.2016.12.026","short":"A. Akopyan, I. Bárány, S. Robins, Advances in Mathematics 308 (2017) 627–644."},"department":[{"_id":"HeEd"}],"title":"Algebraic vertices of non-convex polyhedra","scopus_import":"1","publication_identifier":{"issn":["00018708"]},"status":"public","page":"627 - 644","publist_id":"6173","type":"journal_article","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","ec_funded":1,"date_published":"2017-02-21T00:00:00Z","publication":"Advances in Mathematics","external_id":{"isi":["000409292900015"]},"month":"02","author":[{"orcid":"0000-0002-2548-617X","first_name":"Arseniy","full_name":"Akopyan, Arseniy","id":"430D2C90-F248-11E8-B48F-1D18A9856A87","last_name":"Akopyan"},{"full_name":"Bárány, Imre","first_name":"Imre","last_name":"Bárány"},{"last_name":"Robins","first_name":"Sinai","full_name":"Robins, Sinai"}],"intvolume":" 308","quality_controlled":"1","year":"2017","doi":"10.1016/j.aim.2016.12.026","publication_status":"published","article_processing_charge":"No","oa_version":"Submitted Version","project":[{"name":"International IST Postdoc Fellowship Programme","grant_number":"291734","call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425"}]},{"year":"2017","doi":"10.4230/LIPICS.ITCS.2017.26","publication_status":"published","article_processing_charge":"No","oa_version":"Published Version","arxiv":1,"conference":{"location":"Berkley, CA, United States","name":"ITCS: Innovations in Theoretical Computer Science Conference","start_date":"2017-01-09","end_date":"2017-01-11"},"date_published":"2017-11-28T00:00:00Z","publication":"8th Innovations in Theoretical Computer Science Conference","external_id":{"arxiv":["1703.01638"]},"extern":"1","month":"11","author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H"},{"last_name":"Lincoln","first_name":"Andrea","full_name":"Lincoln, Andrea"},{"last_name":"Neumann","full_name":"Neumann, Stefan","first_name":"Stefan"},{"first_name":"Virginia","full_name":"Vassilevska Williams, Virginia","last_name":"Vassilevska Williams"}],"intvolume":" 67","article_number":"26","quality_controlled":"1","scopus_import":"1","title":"Conditional hardness for sensitivity problems","status":"public","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959770293"]},"type":"conference","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","volume":67,"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"}],"date_created":"2022-08-12T08:55:33Z","language":[{"iso":"eng"}],"oa":1,"main_file_link":[{"url":"https://doi.org/10.4230/LIPICS.ITCS.2017.26","open_access":"1"}],"date_updated":"2023-02-16T11:49:15Z","day":"28","_id":"11829","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"ieee":"M. H. 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 MH, Lincoln A, Neumann S, Vassilevska Williams V. 2017. Conditional hardness for sensitivity problems. 8th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science Conference, LIPIcs, vol. 67, 26.","mla":"Henzinger, Monika H., 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 H, 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.","ama":"Henzinger MH, 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","apa":"Henzinger, M. H., 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.H. Henzinger, A. Lincoln, S. Neumann, V. Vassilevska Williams, in:, 8th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017."},"alternative_title":["LIPIcs"]},{"oa_version":"Published Version","article_processing_charge":"No","publication_status":"published","doi":"10.4230/LIPICS.ESA.2017.44","year":"2017","related_material":{"record":[{"id":"11894","status":"public","relation":"later_version"}]},"quality_controlled":"1","article_number":"44","author":[{"last_name":"Goranci","first_name":"Gramoz","full_name":"Goranci, Gramoz"},{"first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"first_name":"Pan","full_name":"Peng, Pan","last_name":"Peng"}],"intvolume":" 87","month":"09","extern":"1","publication":"25th Annual European Symposium on Algorithms","external_id":{"arxiv":["1702.01136"]},"conference":{"location":"Vienna, Austria","name":"ESA: Annual European Symposium on Algorithms","start_date":"2017-09-04","end_date":"2017-09-06"},"date_published":"2017-09-01T00:00:00Z","arxiv":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","status":"public","scopus_import":"1","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-049-1"]},"title":"Improved guarantees for vertex sparsification in planar graphs","alternative_title":["LIPIcs"],"citation":{"short":"G. Goranci, M.H. Henzinger, P. Peng, in:, 25th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","ama":"Goranci G, Henzinger MH, 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","apa":"Goranci, G., Henzinger, M. H., & 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","ieee":"G. Goranci, M. H. Henzinger, and P. Peng, “Improved guarantees for vertex sparsification in planar graphs,” in 25th Annual European Symposium on Algorithms, Vienna, Austria, 2017, vol. 87.","ista":"Goranci G, Henzinger MH, Peng P. 2017. Improved guarantees for vertex sparsification in planar graphs. 25th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 87, 44.","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.","chicago":"Goranci, Gramoz, Monika H 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."},"day":"01","_id":"11831","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","main_file_link":[{"url":"https://doi.org/10.4230/LIPIcs.ESA.2017.44","open_access":"1"}],"date_updated":"2023-02-21T16:32:16Z","oa":1,"language":[{"iso":"eng"}],"volume":87,"abstract":[{"lang":"eng","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."}],"date_created":"2022-08-12T09:27:11Z"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","scopus_import":"1","status":"public","title":"Dynamic clustering to minimize the sum of radii","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-049-1"]},"citation":{"chicago":"Henzinger, Monika H, 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 MH, Leniowski D, Mathieu C. 2017. Dynamic clustering to minimize the sum of radii. 25th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 87, 48.","mla":"Henzinger, Monika H., 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.","ieee":"M. H. 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.","apa":"Henzinger, M. H., 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","ama":"Henzinger MH, 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","short":"M.H. Henzinger, D. Leniowski, C. Mathieu, in:, 25th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017."},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","_id":"11832","day":"01","alternative_title":["LIPIcs"],"language":[{"iso":"eng"}],"volume":87,"abstract":[{"lang":"eng","text":"In this paper, we study the problem of opening centers to cluster a set of clients in a metric space so as to minimize the sum of the costs of the centers and of the cluster radii, in a dynamic environment where clients arrive and depart, and the solution must be updated efficiently while remaining competitive with respect to the current optimal solution. We call this dynamic sum-of-radii clustering problem.\r\n\r\nWe present a data structure that maintains a solution whose cost is within a constant factor of the cost of an optimal solution in metric spaces with bounded doubling dimension and whose worst-case update time is logarithmic in the parameters of the problem."}],"date_created":"2022-08-12T09:58:46Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPICS.ESA.2017.48"}],"date_updated":"2023-02-16T11:54:12Z","oa":1,"article_processing_charge":"No","publication_status":"published","oa_version":"Published Version","doi":"10.4230/LIPICS.ESA.2017.48","year":"2017","author":[{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"Leniowski, Dariusz","first_name":"Dariusz","last_name":"Leniowski"},{"last_name":"Mathieu","full_name":"Mathieu, Claire","first_name":"Claire"}],"month":"09","intvolume":" 87","extern":"1","quality_controlled":"1","article_number":"48","arxiv":1,"publication":"25th Annual European Symposium on Algorithms","external_id":{"arxiv":["1707.02577"]},"date_published":"2017-09-01T00:00:00Z","conference":{"start_date":"2017-09-04","end_date":"2017-09-06","location":"Vienna, Austria","name":"ESA: Annual European Symposium on Algorithms"}},{"article_number":"45","quality_controlled":"1","extern":"1","author":[{"full_name":"Goranci, Gramoz","first_name":"Gramoz","last_name":"Goranci"},{"last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H"},{"last_name":"Peng","full_name":"Peng, Pan","first_name":"Pan"}],"intvolume":" 87","month":"09","conference":{"start_date":"2017-09-04","end_date":"2017-09-06","location":"Vienna, Austria","name":"ESA: Annual European Symposium on Algorithms"},"date_published":"2017-09-01T00:00:00Z","publication":"25th Annual European Symposium on Algorithms","external_id":{"arxiv":["1712.06473"]},"arxiv":1,"oa_version":"Published Version","publication_status":"published","article_processing_charge":"No","year":"2017","doi":"10.4230/LIPICS.ESA.2017.45","alternative_title":["LIPIcs"],"day":"01","_id":"11833","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"ieee":"G. Goranci, M. H. 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 MH, Peng P. 2017. The power of vertex sparsifiers in dynamic graph algorithms. 25th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 87, 45.","chicago":"Goranci, Gramoz, Monika H Henzinger, and Pan Peng. “The Power of Vertex Sparsifiers in Dynamic Graph Algorithms.” In 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.","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.","ama":"Goranci G, Henzinger MH, 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","apa":"Goranci, G., Henzinger, M. H., & 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.H. Henzinger, P. Peng, in:, 25th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017."},"oa":1,"main_file_link":[{"url":"https://doi.org/10.4230/LIPIcs.ESA.2017.45","open_access":"1"}],"date_updated":"2023-02-16T11:56:37Z","date_created":"2022-08-12T10:46:26Z","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."}],"volume":87,"language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"The power of vertex sparsifiers in dynamic graph algorithms","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-049-1"]},"status":"public","scopus_import":"1","type":"conference"},{"quality_controlled":"1","month":"10","intvolume":" 30","author":[{"last_name":"Kiltz","first_name":"Eike","full_name":"Kiltz, Eike"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z"},{"last_name":"Venturi","full_name":"Venturi, Daniele","first_name":"Daniele"},{"last_name":"Cash","first_name":"David","full_name":"Cash, David"},{"first_name":"Abhishek","full_name":"Jain, Abhishek","last_name":"Jain"}],"date_published":"2017-10-01T00:00:00Z","publication":"Journal of Cryptology","external_id":{"isi":["000410788600007"]},"oa_version":"Submitted Version","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks"},{"name":"Provable Security for Physical Cryptography","grant_number":"259668","call_identifier":"FP7","_id":"258C570E-B435-11E9-9278-68D0E5697425"}],"publication_status":"published","article_processing_charge":"No","year":"2017","doi":"10.1007/s00145-016-9247-3","has_accepted_license":"1","file":[{"file_size":516959,"checksum":"c647520d115b772a1682fc06fa273eb1","content_type":"application/pdf","file_id":"7843","date_updated":"2020-07-14T12:44:37Z","relation":"main_file","access_level":"open_access","file_name":"2017_JournalCrypto_Kiltz.pdf","date_created":"2020-05-14T16:30:17Z","creator":"dernst"}],"ddc":["000"],"related_material":{"record":[{"id":"3238","relation":"earlier_version","status":"public"}]},"department":[{"_id":"KrPi"}],"publisher":"Springer","_id":"1187","day":"01","citation":{"ista":"Kiltz E, Pietrzak KZ, Venturi D, Cash D, Jain A. 2017. Efficient authentication from hard learning problems. Journal of Cryptology. 30(4), 1238–1275.","chicago":"Kiltz, Eike, Krzysztof Z Pietrzak, Daniele Venturi, David Cash, and Abhishek Jain. “Efficient Authentication from Hard Learning Problems.” Journal of Cryptology. Springer, 2017. https://doi.org/10.1007/s00145-016-9247-3.","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.","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.","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","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","short":"E. Kiltz, K.Z. Pietrzak, D. Venturi, D. Cash, A. Jain, Journal of Cryptology 30 (2017) 1238–1275."},"oa":1,"isi":1,"article_type":"original","date_updated":"2023-09-20T11:20:58Z","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."}],"date_created":"2018-12-11T11:50:37Z","volume":30,"language":[{"iso":"eng"}],"issue":"4","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","ec_funded":1,"file_date_updated":"2020-07-14T12:44:37Z","page":"1238 - 1275","scopus_import":"1","title":"Efficient authentication from hard learning problems","status":"public","type":"journal_article","publist_id":"6166"},{"oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1704.01254","open_access":"1"}],"date_updated":"2023-02-21T16:32:01Z","date_created":"2022-08-16T12:20:59Z","abstract":[{"text":"We study the problem of computing a minimum cut in a simple, undirected graph and give a deterministic O(m log2 n log log2 n) time algorithm. This improves both on the best previously known deterministic running time of O(m log12 n) (Kawarabayashi and Thorup [12]) and the best previously known randomized running time of O(mlog3n) (Karger [11]) for this problem, though Karger's algorithm can be further applied to weighted graphs.\r\n\r\nOur approach is using the Kawarabayashi and Tho- rup graph compression technique, which repeatedly finds low-conductance cuts. To find these cuts they use a diffusion-based local algorithm. We use instead a flow- based local algorithm and suitably adjust their framework to work with our flow-based subroutine. Both flow and diffusion based methods have a long history of being applied to finding low conductance cuts. Diffusion algorithms have several variants that are naturally local while it is more complicated to make flow methods local. Some prior work has proven nice properties for local flow based algorithms with respect to improving or cleaning up low conductance cuts. Our flow subroutine, however, is the first that is both local and produces low conductance cuts. Thus, it may be of independent interest.","lang":"eng"}],"language":[{"iso":"eng"}],"day":"01","publisher":"Society for Industrial and Applied Mathematics","_id":"11873","citation":{"short":"M.H. Henzinger, S. Rao, D. Wang, in:, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2017, pp. 1919–1938.","ama":"Henzinger MH, Rao S, Wang D. Local flow partitioning for faster edge connectivity. In: 28th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2017:1919-1938. doi:10.1137/1.9781611974782.125","apa":"Henzinger, M. H., Rao, S., & Wang, D. (2017). Local flow partitioning for faster edge connectivity. In 28th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1919–1938). Barcelona, Spain: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611974782.125","ieee":"M. H. Henzinger, S. Rao, and D. Wang, “Local flow partitioning for faster edge connectivity,” in 28th Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 2017, pp. 1919–1938.","ista":"Henzinger MH, Rao S, Wang D. 2017. Local flow partitioning for faster edge connectivity. 28th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1919–1938.","chicago":"Henzinger, Monika H, Satish Rao, and Di Wang. “Local Flow Partitioning for Faster Edge Connectivity.” In 28th Annual ACM-SIAM Symposium on Discrete Algorithms, 1919–38. Society for Industrial and Applied Mathematics, 2017. https://doi.org/10.1137/1.9781611974782.125.","mla":"Henzinger, Monika H., et al. “Local Flow Partitioning for Faster Edge Connectivity.” 28th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2017, pp. 1919–38, doi:10.1137/1.9781611974782.125."},"status":"public","publication_identifier":{"eisbn":["978-161197478-2"]},"title":"Local flow partitioning for faster edge connectivity","scopus_import":"1","page":"1919-1938","type":"conference","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"start_date":"2017-01-16","end_date":"2017-01-19","name":"SODA: Symposium on Discrete Algorithms","location":"Barcelona, Spain"},"date_published":"2017-01-01T00:00:00Z","external_id":{"arxiv":["1704.01254"]},"publication":"28th Annual ACM-SIAM Symposium on Discrete Algorithms","arxiv":1,"quality_controlled":"1","extern":"1","month":"01","author":[{"last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H"},{"first_name":"Satish","full_name":"Rao, Satish","last_name":"Rao"},{"last_name":"Wang","first_name":"Di","full_name":"Wang, Di"}],"year":"2017","doi":"10.1137/1.9781611974782.125","related_material":{"record":[{"id":"11889","status":"public","relation":"earlier_version"}]},"oa_version":"Preprint","publication_status":"published","article_processing_charge":"No"},{"day":"01","publisher":"Society for Industrial and Applied Mathematics","_id":"11874","citation":{"chicago":"Bhattacharya, Sayan, Monika H Henzinger, and Danupon Nanongkai. “Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in o(Log3 n) Worst Case Update Time.” In 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.","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.","ista":"Bhattacharya S, Henzinger MH, Nanongkai D. 2017. Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time. 28th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 0, 470–489.","ieee":"S. Bhattacharya, M. H. Henzinger, and D. Nanongkai, “Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time,” in 28th Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 2017, vol. 0, pp. 470–489.","short":"S. Bhattacharya, M.H. Henzinger, D. Nanongkai, in:, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2017, pp. 470–489.","apa":"Bhattacharya, S., Henzinger, M. H., & 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","ama":"Bhattacharya S, Henzinger MH, Nanongkai D. Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time. In: 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"},"oa":1,"date_updated":"2023-02-17T11:54:22Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1704.02844"}],"abstract":[{"lang":"eng","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 ∊."}],"date_created":"2022-08-16T12:28:27Z","volume":"0","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","scopus_import":"1","publication_identifier":{"eisbn":["978-161197478-2"]},"title":"Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time","page":"470 - 489","type":"conference","quality_controlled":"1","extern":"1","month":"01","author":[{"last_name":"Bhattacharya","full_name":"Bhattacharya, Sayan","first_name":"Sayan"},{"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":"Nanongkai, Danupon","first_name":"Danupon","last_name":"Nanongkai"}],"conference":{"name":"SODA: Symposium on Discrete Algorithms","location":"Barcelona, Spain","start_date":"2017-01-16","end_date":"2017-01-19"},"date_published":"2017-01-01T00:00:00Z","external_id":{"arxiv":["1704.02844"]},"publication":"28th Annual ACM-SIAM Symposium on Discrete Algorithms","arxiv":1,"oa_version":"Preprint","publication_status":"published","article_processing_charge":"No","year":"2017","doi":"10.1137/1.9781611974782.30"},{"doi":"10.1007/s00224-017-9759-8","year":"2017","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"11837"}]},"oa_version":"Published Version","article_processing_charge":"No","publication_status":"published","publication":"Theory of Computing Systems","date_published":"2017-11-01T00:00:00Z","quality_controlled":"1","month":"11","intvolume":" 61","author":[{"last_name":"Bhattacharya","full_name":"Bhattacharya, Sayan","first_name":"Sayan"},{"last_name":"Dvořák","full_name":"Dvořák, Wolfgang","first_name":"Wolfgang"},{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger"},{"first_name":"Martin","full_name":"Starnberger, Martin","last_name":"Starnberger"}],"extern":"1","type":"journal_article","status":"public","publication_identifier":{"eissn":["1433-0490"],"issn":["1432-4350"]},"title":"Welfare maximization with friends-of-friends network externalities","scopus_import":"1","page":"948-986","issue":"4","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-02-21T16:29:58Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1007/s00224-017-9759-8"}],"article_type":"original","oa":1,"language":[{"iso":"eng"}],"abstract":[{"text":"Online social networks allow the collection of large amounts of data about the influence between users connected by a friendship-like relationship. When distributing items among agents forming a social network, this information allows us to exploit network externalities that each agent receives from his neighbors that get the same item. In this paper we consider Friends-of-Friends (2-hop) network externalities, i.e., externalities that not only depend on the neighbors that get the same item but also on neighbors of neighbors. For these externalities we study a setting where multiple different items are assigned to unit-demand agents. Specifically, we study the problem of welfare maximization under different types of externality functions. Let n be the number of agents and m be the number of items. Our contributions are the following: (1) We show that welfare maximization is APX-hard; we show that even for step functions with 2-hop (and also with 1-hop) externalities it is NP-hard to approximate social welfare better than (1−1/e). (2) On the positive side we present (i) an 𝑂(𝑛√)-approximation algorithm for general concave externality functions, (ii) an O(log m)-approximation algorithm for linear externality functions, and (iii) a 518(1−1/𝑒)-approximation algorithm for 2-hop step function externalities. We also improve the result from [7] for 1-hop step function externalities by giving a 12(1−1/𝑒)-approximation algorithm.","lang":"eng"}],"date_created":"2022-08-17T11:14:12Z","volume":61,"citation":{"ista":"Bhattacharya S, Dvořák W, Henzinger MH, Starnberger M. 2017. Welfare maximization with friends-of-friends network externalities. Theory of Computing Systems. 61(4), 948–986.","mla":"Bhattacharya, Sayan, et al. “Welfare Maximization with Friends-of-Friends Network Externalities.” Theory of Computing Systems, vol. 61, no. 4, Springer Nature, 2017, pp. 948–86, doi:10.1007/s00224-017-9759-8.","chicago":"Bhattacharya, Sayan, Wolfgang Dvořák, Monika H Henzinger, and Martin Starnberger. “Welfare Maximization with Friends-of-Friends Network Externalities.” Theory of Computing Systems. Springer Nature, 2017. https://doi.org/10.1007/s00224-017-9759-8.","ieee":"S. Bhattacharya, W. Dvořák, M. H. Henzinger, and M. Starnberger, “Welfare maximization with friends-of-friends network externalities,” Theory of Computing Systems, vol. 61, no. 4. Springer Nature, pp. 948–986, 2017.","apa":"Bhattacharya, S., Dvořák, W., Henzinger, M. H., & Starnberger, M. (2017). Welfare maximization with friends-of-friends network externalities. Theory of Computing Systems. Springer Nature. https://doi.org/10.1007/s00224-017-9759-8","ama":"Bhattacharya S, Dvořák W, Henzinger MH, Starnberger M. Welfare maximization with friends-of-friends network externalities. Theory of Computing Systems. 2017;61(4):948-986. doi:10.1007/s00224-017-9759-8","short":"S. Bhattacharya, W. Dvořák, M.H. Henzinger, M. Starnberger, Theory of Computing Systems 61 (2017) 948–986."},"day":"01","publisher":"Springer Nature","_id":"11903"},{"year":"2017","doi":"10.1007/s11538-016-0244-3","publication_status":"published","oa_version":"Preprint","project":[{"_id":"25B1EC9E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"618091","name":"Speed of Adaptation in Population Genetics and Evolutionary Computation"},{"name":"Limits to selection in biology and in evolutionary computation","grant_number":"250152","call_identifier":"FP7","_id":"25B07788-B435-11E9-9278-68D0E5697425"}],"acknowledgement":"We thank Nick Barton, Katarína Bod’ová, and Sr\r\n-\r\ndan Sarikas for constructive feed-\r\nback and support. Furthermore, we would like to express our deep gratitude to the anonymous referees (one\r\nof whom, Jimmy Garnier, agreed to reveal his identity) and the editor Max Souza, for very helpful and\r\ndetailed comments and suggestions that significantly helped us to improve the manuscript. This project has\r\nreceived funding from the European Union’s Seventh Framework Programme for research, technological\r\ndevelopment and demonstration under Grant Agreement 618091 Speed of Adaptation in Population Genet-\r\nics and Evolutionary Computation (SAGE) and the European Research Council (ERC) Grant No. 250152\r\n(SN), from the Scientific Grant Agency of the Slovak Republic under the Grant 1/0459/13 and by the Slovak\r\nResearch and Development Agency under the Contract No. APVV-14-0378 (RK). RK would also like to\r\nthank IST Austria for its hospitality during the work on this project.","date_published":"2017-03-01T00:00:00Z","publication":"Bulletin of Mathematical Biology","intvolume":" 79","month":"03","author":[{"full_name":"Kollár, Richard","first_name":"Richard","last_name":"Kollár"},{"id":"461468AE-F248-11E8-B48F-1D18A9856A87","last_name":"Novak","orcid":"0000-0002-2519-824X","full_name":"Novak, Sebastian","first_name":"Sebastian"}],"quality_controlled":"1","status":"public","title":"Existence of traveling waves for the generalized F–KPP equation","scopus_import":1,"page":"525-559","publist_id":"6160","type":"journal_article","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","ec_funded":1,"issue":"3","date_created":"2018-12-11T11:50:38Z","abstract":[{"lang":"eng","text":"Variation in genotypes may be responsible for differences in dispersal rates, directional biases, and growth rates of individuals. These traits may favor certain genotypes and enhance their spatiotemporal spreading into areas occupied by the less advantageous genotypes. We study how these factors influence the speed of spreading in the case of two competing genotypes under the assumption that spatial variation of the total population is small compared to the spatial variation of the frequencies of the genotypes in the population. In that case, the dynamics of the frequency of one of the genotypes is approximately described by a generalized Fisher–Kolmogorov–Petrovskii–Piskunov (F–KPP) equation. This generalized F–KPP equation with (nonlinear) frequency-dependent diffusion and advection terms admits traveling wave solutions that characterize the invasion of the dominant genotype. Our existence results generalize the classical theory for traveling waves for the F–KPP with constant coefficients. Moreover, in the particular case of the quadratic (monostable) nonlinear growth–decay rate in the generalized F–KPP we study in detail the influence of the variance in diffusion and mean displacement rates of the two genotypes on the minimal wave propagation speed."}],"volume":79,"language":[{"iso":"eng"}],"oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1607.00944","open_access":"1"}],"date_updated":"2025-05-28T11:42:46Z","day":"01","publisher":"Springer","_id":"1191","citation":{"short":"R. Kollár, S. Novak, Bulletin of Mathematical Biology 79 (2017) 525–559.","apa":"Kollár, R., & Novak, S. (2017). Existence of traveling waves for the generalized F–KPP equation. Bulletin of Mathematical Biology. Springer. https://doi.org/10.1007/s11538-016-0244-3","ama":"Kollár R, Novak S. Existence of traveling waves for the generalized F–KPP equation. Bulletin of Mathematical Biology. 2017;79(3):525-559. doi:10.1007/s11538-016-0244-3","mla":"Kollár, Richard, and Sebastian Novak. “Existence of Traveling Waves for the Generalized F–KPP Equation.” Bulletin of Mathematical Biology, vol. 79, no. 3, Springer, 2017, pp. 525–59, doi:10.1007/s11538-016-0244-3.","ista":"Kollár R, Novak S. 2017. Existence of traveling waves for the generalized F–KPP equation. Bulletin of Mathematical Biology. 79(3), 525–559.","chicago":"Kollár, Richard, and Sebastian Novak. “Existence of Traveling Waves for the Generalized F–KPP Equation.” Bulletin of Mathematical Biology. Springer, 2017. https://doi.org/10.1007/s11538-016-0244-3.","ieee":"R. Kollár and S. Novak, “Existence of traveling waves for the generalized F–KPP equation,” Bulletin of Mathematical Biology, vol. 79, no. 3. Springer, pp. 525–559, 2017."},"department":[{"_id":"NiBa"}]},{"doi":"10.1137/1.9781611974782.20","year":"2017","related_material":{"record":[{"relation":"later_version","status":"public","id":"6032"}]},"oa_version":"Submitted Version","project":[{"call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160"}],"article_processing_charge":"No","publication_status":"published","external_id":{"isi":["000426965800020"]},"conference":{"name":"SODA: Symposium on Discrete Algorithms","location":"Barcelona, Spain","end_date":"2017-01019","start_date":"2017-01-16"},"date_published":"2017-01-01T00:00:00Z","quality_controlled":"1","month":"01","author":[{"full_name":"Kazda, Alexandr","first_name":"Alexandr","last_name":"Kazda","id":"3B32BAA8-F248-11E8-B48F-1D18A9856A87"},{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","first_name":"Vladimir"},{"last_name":"Rolinek","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","full_name":"Rolinek, Michal","first_name":"Michal"}],"type":"conference","publist_id":"6159","publication_identifier":{"isbn":["978-161197478-2"]},"title":"Even delta-matroids and the complexity of planar Boolean CSPs","status":"public","page":"307 - 326","ec_funded":1,"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","date_updated":"2023-09-20T11:20:26Z","main_file_link":[{"url":"https://arxiv.org/abs/1602.03124","open_access":"1"}],"isi":1,"oa":1,"language":[{"iso":"eng"}],"date_created":"2018-12-11T11:50:38Z","abstract":[{"lang":"eng","text":"The main result of this paper is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints (we call it edge CSP) and all constraints are even Δ-matroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvorak and Kupec. Knowing that edge CSP is tractable for even Δ-matroid constraints allows us to extend the tractability result to a larger class of Δ-matroids that includes many classes that were known to be tractable before, namely co-independent, compact, local and binary."}],"department":[{"_id":"VlKo"}],"citation":{"ama":"Kazda A, Kolmogorov V, Rolinek M. Even delta-matroids and the complexity of planar Boolean CSPs. In: SIAM; 2017:307-326. doi:10.1137/1.9781611974782.20","apa":"Kazda, A., Kolmogorov, V., & Rolinek, M. (2017). Even delta-matroids and the complexity of planar Boolean CSPs (pp. 307–326). Presented at the SODA: Symposium on Discrete Algorithms, Barcelona, Spain: SIAM. https://doi.org/10.1137/1.9781611974782.20","short":"A. Kazda, V. Kolmogorov, M. Rolinek, in:, SIAM, 2017, pp. 307–326.","ieee":"A. Kazda, V. Kolmogorov, and M. Rolinek, “Even delta-matroids and the complexity of planar Boolean CSPs,” presented at the SODA: Symposium on Discrete Algorithms, Barcelona, Spain, 2017, pp. 307–326.","chicago":"Kazda, Alexandr, Vladimir Kolmogorov, and Michal Rolinek. “Even Delta-Matroids and the Complexity of Planar Boolean CSPs,” 307–26. SIAM, 2017. https://doi.org/10.1137/1.9781611974782.20.","mla":"Kazda, Alexandr, et al. Even Delta-Matroids and the Complexity of Planar Boolean CSPs. SIAM, 2017, pp. 307–26, doi:10.1137/1.9781611974782.20.","ista":"Kazda A, Kolmogorov V, Rolinek M. 2017. Even delta-matroids and the complexity of planar Boolean CSPs. SODA: Symposium on Discrete Algorithms, 307–326."},"day":"01","publisher":"SIAM","_id":"1192"},{"issue":"1","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","ec_funded":1,"page":"145 - 160","status":"public","title":"Stochastic invariants for probabilistic termination","scopus_import":"1","publication_identifier":{"issn":["07308566"]},"publist_id":"6157","type":"conference","department":[{"_id":"KrCh"}],"alternative_title":["ACM SIGPLAN Notices"],"publisher":"ACM","_id":"1194","day":"01","citation":{"ama":"Chatterjee K, Novotný P, Zikelic D. Stochastic invariants for probabilistic termination. In: Vol 52. ACM; 2017:145-160. doi:10.1145/3009837.3009873","apa":"Chatterjee, K., Novotný, P., & Zikelic, D. (2017). Stochastic invariants for probabilistic termination (Vol. 52, pp. 145–160). Presented at the POPL: Principles of Programming Languages, Paris, France: ACM. https://doi.org/10.1145/3009837.3009873","short":"K. Chatterjee, P. Novotný, D. Zikelic, in:, ACM, 2017, pp. 145–160.","ieee":"K. Chatterjee, P. Novotný, and D. Zikelic, “Stochastic invariants for probabilistic termination,” presented at the POPL: Principles of Programming Languages, Paris, France, 2017, vol. 52, no. 1, pp. 145–160.","mla":"Chatterjee, Krishnendu, et al. Stochastic Invariants for Probabilistic Termination. Vol. 52, no. 1, ACM, 2017, pp. 145–60, doi:10.1145/3009837.3009873.","ista":"Chatterjee K, Novotný P, Zikelic D. 2017. Stochastic invariants for probabilistic termination. POPL: Principles of Programming Languages, ACM SIGPLAN Notices, vol. 52, 145–160.","chicago":"Chatterjee, Krishnendu, Petr Novotný, and Djordje Zikelic. “Stochastic Invariants for Probabilistic Termination,” 52:145–60. ACM, 2017. https://doi.org/10.1145/3009837.3009873."},"oa":1,"isi":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1611.01063"}],"date_updated":"2025-07-14T09:09:58Z","abstract":[{"text":"Termination is one of the basic liveness properties, and we study the termination problem for probabilistic programs with real-valued variables. Previous works focused on the qualitative problem that asks whether an input program terminates with probability~1 (almost-sure termination). A powerful approach for this qualitative problem is the notion of ranking supermartingales with respect to a given set of invariants. The quantitative problem (probabilistic termination) asks for bounds on the termination probability. A fundamental and conceptual drawback of the existing approaches to address probabilistic termination is that even though the supermartingales consider the probabilistic behavior of the programs, the invariants are obtained completely ignoring the probabilistic aspect. In this work we address the probabilistic termination problem for linear-arithmetic probabilistic programs with nondeterminism. We define the notion of {\\em stochastic invariants}, which are constraints along with a probability bound that the constraints hold. We introduce a concept of {\\em repulsing supermartingales}. First, we show that repulsing supermartingales can be used to obtain bounds on the probability of the stochastic invariants. Second, we show the effectiveness of repulsing supermartingales in the following three ways: (1)~With a combination of ranking and repulsing supermartingales we can compute lower bounds on the probability of termination; (2)~repulsing supermartingales provide witnesses for refutation of almost-sure termination; and (3)~with a combination of ranking and repulsing supermartingales we can establish persistence properties of probabilistic programs. We also present results on related computational problems and an experimental evaluation of our approach on academic examples. ","lang":"eng"}],"volume":52,"date_created":"2018-12-11T11:50:39Z","language":[{"iso":"eng"}],"oa_version":"Submitted Version","project":[{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"name":"Moderne Concurrency Paradigms","grant_number":"S11402-N23","call_identifier":"FWF","_id":"25F5A88A-B435-11E9-9278-68D0E5697425"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"291734","name":"International IST Postdoc Fellowship Programme"}],"publication_status":"published","article_processing_charge":"No","year":"2017","doi":"10.1145/3009837.3009873","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"14539"}]},"quality_controlled":"1","month":"01","intvolume":" 52","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","first_name":"Krishnendu"},{"first_name":"Petr","full_name":"Novotny, Petr","last_name":"Novotny","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Zikelic","full_name":"Zikelic, Djordje","first_name":"Djordje"}],"date_published":"2017-01-01T00:00:00Z","conference":{"name":"POPL: Principles of Programming Languages","location":"Paris, France","end_date":"2017-01-21","start_date":"2017-01-15"},"external_id":{"isi":["000408311200013"]}},{"year":"2017","doi":"10.1556/1846.2017.00016","publication_status":"published","article_processing_charge":"No","oa_version":"Published Version","date_published":"2017-09-01T00:00:00Z","publication":"Journal of Flow Chemistry","extern":"1","month":"09","intvolume":" 7","author":[{"first_name":"Bartholomäus","full_name":"Pieber, Bartholomäus","orcid":"0000-0001-8689-388X","last_name":"Pieber","id":"93e5e5b2-0da6-11ed-8a41-af589a024726"},{"last_name":"Gilmore","first_name":"Kerry","full_name":"Gilmore, Kerry"},{"full_name":"Seeberger, Peter H.","first_name":"Peter H.","last_name":"Seeberger"}],"quality_controlled":"1","title":"Integrated flow processing - challenges in continuous multistep synthesis","status":"public","scopus_import":"1","publication_identifier":{"eissn":["2063-0212"],"issn":["2062-249X"]},"page":"129-136","type":"journal_article","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","issue":"3-4","abstract":[{"lang":"eng","text":"The way organic multistep synthesis is performed is changing due to the adoption of flow chemical techniques, which has enabled the development of improved methods to make complex molecules. The modular nature of the technique provides not only access to target molecules via linear flow approaches but also for the targeting of structural cores with single systems. This perspective article summarizes the state of the art of continuous multistep synthesis and discusses the main challenges and opportunities in this area."}],"volume":7,"date_created":"2022-08-25T10:47:51Z","language":[{"iso":"eng"}],"oa":1,"date_updated":"2023-02-21T10:10:02Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1556/1846.2017.00016"}],"article_type":"original","day":"01","publisher":"AKJournals","_id":"11976","citation":{"short":"B. Pieber, K. Gilmore, P.H. Seeberger, Journal of Flow Chemistry 7 (2017) 129–136.","ama":"Pieber B, Gilmore K, Seeberger PH. Integrated flow processing - challenges in continuous multistep synthesis. Journal of Flow Chemistry. 2017;7(3-4):129-136. doi:10.1556/1846.2017.00016","apa":"Pieber, B., Gilmore, K., & Seeberger, P. H. (2017). Integrated flow processing - challenges in continuous multistep synthesis. Journal of Flow Chemistry. AKJournals. https://doi.org/10.1556/1846.2017.00016","ieee":"B. Pieber, K. Gilmore, and P. H. Seeberger, “Integrated flow processing - challenges in continuous multistep synthesis,” Journal of Flow Chemistry, vol. 7, no. 3–4. AKJournals, pp. 129–136, 2017.","chicago":"Pieber, Bartholomäus, Kerry Gilmore, and Peter H. Seeberger. “Integrated Flow Processing - Challenges in Continuous Multistep Synthesis.” Journal of Flow Chemistry. AKJournals, 2017. https://doi.org/10.1556/1846.2017.00016.","mla":"Pieber, Bartholomäus, et al. “Integrated Flow Processing - Challenges in Continuous Multistep Synthesis.” Journal of Flow Chemistry, vol. 7, no. 3–4, AKJournals, 2017, pp. 129–36, doi:10.1556/1846.2017.00016.","ista":"Pieber B, Gilmore K, Seeberger PH. 2017. Integrated flow processing - challenges in continuous multistep synthesis. Journal of Flow Chemistry. 7(3–4), 129–136."}},{"project":[{"grant_number":"P27533_N27","name":"Structure of the Excitation Spectrum for Many-Body Quantum Systems","_id":"25C878CE-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"}],"oa_version":"Published Version","publication_status":"published","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"article_processing_charge":"Yes (via OA deal)","year":"2017","doi":"10.1007/s11005-016-0915-x","file":[{"date_updated":"2020-07-14T12:44:38Z","content_type":"application/pdf","file_id":"5296","relation":"main_file","access_level":"open_access","date_created":"2018-12-12T10:17:40Z","file_name":"IST-2016-723-v1+1_s11005-016-0915-x.pdf","creator":"system","checksum":"c0c835def162c1bc52f978fad26e3c2f","file_size":587207}],"has_accepted_license":"1","ddc":["510","539"],"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"52"}]},"quality_controlled":"1","author":[{"id":"2B5FC9A4-F248-11E8-B48F-1D18A9856A87","last_name":"Moser","first_name":"Thomas","full_name":"Moser, Thomas"},{"id":"4AFD0470-F248-11E8-B48F-1D18A9856A87","last_name":"Seiringer","orcid":"0000-0002-6781-0521","full_name":"Seiringer, Robert","first_name":"Robert"}],"intvolume":" 107","month":"03","date_published":"2017-03-01T00:00:00Z","external_id":{"isi":["000394280200007"]},"publication":"Letters in Mathematical Physics","acknowledgement":"Open access funding provided by Institute of Science and Technology (IST Austria). ","issue":"3","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","file_date_updated":"2020-07-14T12:44:38Z","page":" 533 - 552","publication_identifier":{"issn":["03779017"]},"title":"Triviality of a model of particles with point interactions in the thermodynamic limit","scopus_import":"1","status":"public","publist_id":"6152","type":"journal_article","department":[{"_id":"RoSe"}],"_id":"1198","pubrep_id":"723","publisher":"Springer","day":"01","citation":{"mla":"Moser, Thomas, and Robert Seiringer. “Triviality of a Model of Particles with Point Interactions in the Thermodynamic Limit.” Letters in Mathematical Physics, vol. 107, no. 3, Springer, 2017, pp. 533–52, doi:10.1007/s11005-016-0915-x.","ista":"Moser T, Seiringer R. 2017. Triviality of a model of particles with point interactions in the thermodynamic limit. Letters in Mathematical Physics. 107(3), 533–552.","chicago":"Moser, Thomas, and Robert Seiringer. “Triviality of a Model of Particles with Point Interactions in the Thermodynamic Limit.” Letters in Mathematical Physics. Springer, 2017. https://doi.org/10.1007/s11005-016-0915-x.","ieee":"T. Moser and R. Seiringer, “Triviality of a model of particles with point interactions in the thermodynamic limit,” Letters in Mathematical Physics, vol. 107, no. 3. Springer, pp. 533–552, 2017.","short":"T. Moser, R. Seiringer, Letters in Mathematical Physics 107 (2017) 533–552.","apa":"Moser, T., & Seiringer, R. (2017). Triviality of a model of particles with point interactions in the thermodynamic limit. Letters in Mathematical Physics. Springer. https://doi.org/10.1007/s11005-016-0915-x","ama":"Moser T, Seiringer R. Triviality of a model of particles with point interactions in the thermodynamic limit. Letters in Mathematical Physics. 2017;107(3):533-552. doi:10.1007/s11005-016-0915-x"},"oa":1,"isi":1,"date_updated":"2023-09-20T11:18:13Z","abstract":[{"text":"We consider a model of fermions interacting via point interactions, defined via a certain weighted Dirichlet form. While for two particles the interaction corresponds to infinite scattering length, the presence of further particles effectively decreases the interaction strength. We show that the model becomes trivial in the thermodynamic limit, in the sense that the free energy density at any given particle density and temperature agrees with the corresponding expression for non-interacting particles.","lang":"eng"}],"date_created":"2018-12-11T11:50:40Z","volume":107,"language":[{"iso":"eng"}]},{"date_published":"2017-01-01T00:00:00Z","external_id":{"isi":["000392229100011"]},"publication":"Heredity","author":[{"full_name":"Barton, Nicholas H","orcid":"0000-0002-8548-5240","first_name":"Nicholas H","last_name":"Barton","id":"4880FE40-F248-11E8-B48F-1D18A9856A87"}],"month":"01","intvolume":" 118","quality_controlled":"1","related_material":{"record":[{"id":"9710","relation":"research_data","status":"public"}]},"year":"2017","doi":"10.1038/hdy.2016.109","publication_status":"published","article_processing_charge":"No","project":[{"grant_number":"250152","name":"Limits to selection in biology and in evolutionary computation","_id":"25B07788-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"oa_version":"Submitted Version","date_created":"2018-12-11T11:50:40Z","volume":118,"abstract":[{"lang":"eng","text":"Much of quantitative genetics is based on the ‘infinitesimal model’, under which selection has a negligible effect on the genetic variance. This is typically justified by assuming a very large number of loci with additive effects. However, it applies even when genes interact, provided that the number of loci is large enough that selection on each of them is weak relative to random drift. In the long term, directional selection will change allele frequencies, but even then, the effects of epistasis on the ultimate change in trait mean due to selection may be modest. Stabilising selection can maintain many traits close to their optima, even when the underlying alleles are weakly selected. However, the number of traits that can be optimised is apparently limited to ~4Ne by the ‘drift load’, and this is hard to reconcile with the apparent complexity of many organisms. Just as for the mutation load, this limit can be evaded by a particular form of negative epistasis. A more robust limit is set by the variance in reproductive success. This suggests that selection accumulates information most efficiently in the infinitesimal regime, when selection on individual alleles is weak, and comparable with random drift. A review of evidence on selection strength suggests that although most variance in fitness may be because of alleles with large Nes, substantial amounts of adaptation may be because of alleles in the infinitesimal regime, in which epistasis has modest effects."}],"language":[{"iso":"eng"}],"isi":1,"oa":1,"date_updated":"2025-05-28T11:42:47Z","main_file_link":[{"open_access":"1","url":"https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5176114/"}],"day":"01","_id":"1199","publisher":"Nature Publishing Group","citation":{"mla":"Barton, Nicholas H. “How Does Epistasis Influence the Response to Selection?” Heredity, vol. 118, Nature Publishing Group, 2017, pp. 96–109, doi:10.1038/hdy.2016.109.","chicago":"Barton, Nicholas H. “How Does Epistasis Influence the Response to Selection?” Heredity. Nature Publishing Group, 2017. https://doi.org/10.1038/hdy.2016.109.","ista":"Barton NH. 2017. How does epistasis influence the response to selection? Heredity. 118, 96–109.","ieee":"N. H. Barton, “How does epistasis influence the response to selection?,” Heredity, vol. 118. Nature Publishing Group, pp. 96–109, 2017.","apa":"Barton, N. H. (2017). How does epistasis influence the response to selection? Heredity. Nature Publishing Group. https://doi.org/10.1038/hdy.2016.109","ama":"Barton NH. How does epistasis influence the response to selection? Heredity. 2017;118:96-109. doi:10.1038/hdy.2016.109","short":"N.H. Barton, Heredity 118 (2017) 96–109."},"department":[{"_id":"NiBa"}],"status":"public","title":"How does epistasis influence the response to selection?","scopus_import":"1","page":"96 - 109","type":"journal_article","publist_id":"6151","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","ec_funded":1},{"publisher":"Springer","_id":"1207","pubrep_id":"722","day":"01","citation":{"ista":"Bao Z, Erdös L, Schnelli K. 2017. Local law of addition of random matrices on optimal scale. Communications in Mathematical Physics. 349(3), 947–990.","chicago":"Bao, Zhigang, László Erdös, and Kevin Schnelli. “Local Law of Addition of Random Matrices on Optimal Scale.” Communications in Mathematical Physics. Springer, 2017. https://doi.org/10.1007/s00220-016-2805-6.","mla":"Bao, Zhigang, et al. “Local Law of Addition of Random Matrices on Optimal Scale.” Communications in Mathematical Physics, vol. 349, no. 3, Springer, 2017, pp. 947–90, doi:10.1007/s00220-016-2805-6.","ieee":"Z. Bao, L. Erdös, and K. Schnelli, “Local law of addition of random matrices on optimal scale,” Communications in Mathematical Physics, vol. 349, no. 3. Springer, pp. 947–990, 2017.","short":"Z. Bao, L. Erdös, K. Schnelli, Communications in Mathematical Physics 349 (2017) 947–990.","apa":"Bao, Z., Erdös, L., & Schnelli, K. (2017). Local law of addition of random matrices on optimal scale. Communications in Mathematical Physics. Springer. https://doi.org/10.1007/s00220-016-2805-6","ama":"Bao Z, Erdös L, Schnelli K. Local law of addition of random matrices on optimal scale. Communications in Mathematical Physics. 2017;349(3):947-990. doi:10.1007/s00220-016-2805-6"},"department":[{"_id":"LaEr"}],"date_created":"2018-12-11T11:50:43Z","abstract":[{"text":"The eigenvalue distribution of the sum of two large Hermitian matrices, when one of them is conjugated by a Haar distributed unitary matrix, is asymptotically given by the free convolution of their spectral distributions. We prove that this convergence also holds locally in the bulk of the spectrum, down to the optimal scales larger than the eigenvalue spacing. The corresponding eigenvectors are fully delocalized. Similar results hold for the sum of two real symmetric matrices, when one is conjugated by Haar orthogonal matrix.","lang":"eng"}],"volume":349,"language":[{"iso":"eng"}],"oa":1,"isi":1,"date_updated":"2023-09-20T11:16:57Z","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","file_date_updated":"2020-07-14T12:44:39Z","ec_funded":1,"issue":"3","page":"947 - 990","title":"Local law of addition of random matrices on optimal scale","publication_identifier":{"issn":["00103616"]},"scopus_import":"1","status":"public","type":"journal_article","publist_id":"6141","author":[{"id":"442E6A6C-F248-11E8-B48F-1D18A9856A87","last_name":"Bao","full_name":"Bao, Zhigang","orcid":"0000-0003-3036-1475","first_name":"Zhigang"},{"id":"4DBD5372-F248-11E8-B48F-1D18A9856A87","last_name":"Erdös","first_name":"László","full_name":"Erdös, László","orcid":"0000-0001-5366-9603"},{"full_name":"Schnelli, Kevin","orcid":"0000-0003-0954-3231","first_name":"Kevin","id":"434AD0AE-F248-11E8-B48F-1D18A9856A87","last_name":"Schnelli"}],"month":"02","intvolume":" 349","quality_controlled":"1","date_published":"2017-02-01T00:00:00Z","external_id":{"isi":["000393696700005"]},"publication":"Communications in Mathematical Physics","publication_status":"published","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"article_processing_charge":"Yes (via OA deal)","oa_version":"Published Version","project":[{"name":"Random matrices, universality and disordered quantum systems","grant_number":"338804","call_identifier":"FP7","_id":"258DCDE6-B435-11E9-9278-68D0E5697425"}],"ddc":["530"],"year":"2017","doi":"10.1007/s00220-016-2805-6","file":[{"checksum":"ddff79154c3daf27237de5383b1264a9","file_size":1033743,"access_level":"open_access","date_created":"2018-12-12T10:14:47Z","file_name":"IST-2016-722-v1+1_s00220-016-2805-6.pdf","creator":"system","date_updated":"2020-07-14T12:44:39Z","content_type":"application/pdf","file_id":"5102","relation":"main_file"}],"has_accepted_license":"1"},{"article_processing_charge":"No","publication_status":"published","project":[{"name":"Gaussian Graphical Models: Theory and Applications","grant_number":"Y 903-N35","call_identifier":"FWF","_id":"2530CA10-B435-11E9-9278-68D0E5697425"}],"oa_version":"Submitted Version","doi":"10.1111/rssb.12217","year":"2017","month":"09","author":[{"last_name":"Zwiernik","first_name":"Piotr","full_name":"Zwiernik, Piotr"},{"first_name":"Caroline","orcid":"0000-0002-7008-0216","full_name":"Uhler, Caroline","last_name":"Uhler","id":"49ADD78E-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Richards","first_name":"Donald","full_name":"Richards, Donald"}],"intvolume":" 79","quality_controlled":"1","publication":"Journal of the Royal Statistical Society. Series B: Statistical Methodology","external_id":{"isi":["000411712300012"]},"date_published":"2017-09-01T00:00:00Z","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","issue":"4","type":"journal_article","publist_id":"6142","status":"public","scopus_import":"1","publication_identifier":{"issn":["13697412"]},"title":"Maximum likelihood estimation for linear Gaussian covariance models","page":"1269 - 1292","citation":{"mla":"Zwiernik, Piotr, et al. “Maximum Likelihood Estimation for Linear Gaussian Covariance Models.” Journal of the Royal Statistical Society. Series B: Statistical Methodology, vol. 79, no. 4, Wiley-Blackwell, 2017, pp. 1269–92, doi:10.1111/rssb.12217.","chicago":"Zwiernik, Piotr, Caroline Uhler, and Donald Richards. “Maximum Likelihood Estimation for Linear Gaussian Covariance Models.” Journal of the Royal Statistical Society. Series B: Statistical Methodology. Wiley-Blackwell, 2017. https://doi.org/10.1111/rssb.12217.","ista":"Zwiernik P, Uhler C, Richards D. 2017. Maximum likelihood estimation for linear Gaussian covariance models. Journal of the Royal Statistical Society. Series B: Statistical Methodology. 79(4), 1269–1292.","ieee":"P. Zwiernik, C. Uhler, and D. Richards, “Maximum likelihood estimation for linear Gaussian covariance models,” Journal of the Royal Statistical Society. Series B: Statistical Methodology, vol. 79, no. 4. Wiley-Blackwell, pp. 1269–1292, 2017.","short":"P. Zwiernik, C. Uhler, D. Richards, Journal of the Royal Statistical Society. Series B: Statistical Methodology 79 (2017) 1269–1292.","apa":"Zwiernik, P., Uhler, C., & Richards, D. (2017). Maximum likelihood estimation for linear Gaussian covariance models. Journal of the Royal Statistical Society. Series B: Statistical Methodology. Wiley-Blackwell. https://doi.org/10.1111/rssb.12217","ama":"Zwiernik P, Uhler C, Richards D. Maximum likelihood estimation for linear Gaussian covariance models. Journal of the Royal Statistical Society Series B: Statistical Methodology. 2017;79(4):1269-1292. doi:10.1111/rssb.12217"},"day":"01","_id":"1208","publisher":"Wiley-Blackwell","department":[{"_id":"CaUh"}],"language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"We study parameter estimation in linear Gaussian covariance models, which are p-dimensional Gaussian models with linear constraints on the covariance matrix. Maximum likelihood estimation for this class of models leads to a non-convex optimization problem which typically has many local maxima. Using recent results on the asymptotic distribution of extreme eigenvalues of the Wishart distribution, we provide sufficient conditions for any hill climbing method to converge to the global maximum. Although we are primarily interested in the case in which n≫p, the proofs of our results utilize large sample asymptotic theory under the scheme n/p→γ>1. Remarkably, our numerical simulations indicate that our results remain valid for p as small as 2. An important consequence of this analysis is that, for sample sizes n≃14p, maximum likelihood estimation for linear Gaussian covariance models behaves as if it were a convex optimization problem. © 2016 The Royal Statistical Society and Blackwell Publishing Ltd."}],"volume":79,"date_created":"2018-12-11T11:50:43Z","date_updated":"2023-09-20T11:17:21Z","main_file_link":[{"url":"https://arxiv.org/abs/1408.5604","open_access":"1"}],"isi":1,"oa":1},{"oa":1,"date_updated":"2021-01-12T06:49:07Z","volume":167,"abstract":[{"text":"Systems such as fluid flows in channels and pipes or the complex Ginzburg–Landau system, defined over periodic domains, exhibit both continuous symmetries, translational and rotational, as well as discrete symmetries under spatial reflections or complex conjugation. The simplest, and very common symmetry of this type is the equivariance of the defining equations under the orthogonal group O(2). We formulate a novel symmetry reduction scheme for such systems by combining the method of slices with invariant polynomial methods, and show how it works by applying it to the Kuramoto–Sivashinsky system in one spatial dimension. As an example, we track a relative periodic orbit through a sequence of bifurcations to the onset of chaos. Within the symmetry-reduced state space we are able to compute and visualize the unstable manifolds of relative periodic orbits, their torus bifurcations, a transition to chaos via torus breakdown, and heteroclinic connections between various relative periodic orbits. It would be very hard to carry through such analysis in the full state space, without a symmetry reduction such as the one we present here.","lang":"eng"}],"date_created":"2018-12-11T11:50:44Z","language":[{"iso":"eng"}],"department":[{"_id":"BjHo"}],"day":"01","publisher":"Springer","_id":"1211","pubrep_id":"782","citation":{"ieee":"N. B. Budanur and P. Cvitanović, “Unstable manifolds of relative periodic orbits in the symmetry reduced state space of the Kuramoto–Sivashinsky system,” Journal of Statistical Physics, vol. 167, no. 3–4. Springer, pp. 636–655, 2017.","chicago":"Budanur, Nazmi B, and Predrag Cvitanović. “Unstable Manifolds of Relative Periodic Orbits in the Symmetry Reduced State Space of the Kuramoto–Sivashinsky System.” Journal of Statistical Physics. Springer, 2017. https://doi.org/10.1007/s10955-016-1672-z.","ista":"Budanur NB, Cvitanović P. 2017. Unstable manifolds of relative periodic orbits in the symmetry reduced state space of the Kuramoto–Sivashinsky system. Journal of Statistical Physics. 167(3–4), 636–655.","mla":"Budanur, Nazmi B., and Predrag Cvitanović. “Unstable Manifolds of Relative Periodic Orbits in the Symmetry Reduced State Space of the Kuramoto–Sivashinsky System.” Journal of Statistical Physics, vol. 167, no. 3–4, Springer, 2017, pp. 636–55, doi:10.1007/s10955-016-1672-z.","short":"N.B. Budanur, P. Cvitanović, Journal of Statistical Physics 167 (2017) 636–655.","ama":"Budanur NB, Cvitanović P. Unstable manifolds of relative periodic orbits in the symmetry reduced state space of the Kuramoto–Sivashinsky system. Journal of Statistical Physics. 2017;167(3-4):636-655. doi:10.1007/s10955-016-1672-z","apa":"Budanur, N. B., & Cvitanović, P. (2017). Unstable manifolds of relative periodic orbits in the symmetry reduced state space of the Kuramoto–Sivashinsky system. Journal of Statistical Physics. Springer. https://doi.org/10.1007/s10955-016-1672-z"},"status":"public","title":"Unstable manifolds of relative periodic orbits in the symmetry reduced state space of the Kuramoto–Sivashinsky system","scopus_import":1,"page":"636-655","type":"journal_article","publist_id":"6136","issue":"3-4","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:44:39Z","date_published":"2017-05-01T00:00:00Z","publication":"Journal of Statistical Physics","acknowledgement":"This work was supported by the family of late G. Robinson, Jr. and NSF Grant DMS-1211827. ","quality_controlled":"1","author":[{"full_name":"Budanur, Nazmi B","first_name":"Nazmi B","orcid":"0000-0003-0423-5010","id":"3EA1010E-F248-11E8-B48F-1D18A9856A87","last_name":"Budanur"},{"full_name":"Cvitanović, Predrag","first_name":"Predrag","last_name":"Cvitanović"}],"intvolume":" 167","month":"05","year":"2017","file":[{"date_updated":"2020-07-14T12:44:39Z","file_id":"5319","content_type":"application/pdf","relation":"main_file","access_level":"open_access","creator":"system","file_name":"IST-2017-782-v1+1_BudCvi15.pdf","date_created":"2018-12-12T10:18:01Z","checksum":"3e971d09eb167761aa0888ed415b0056","file_size":2820207}],"has_accepted_license":"1","doi":"10.1007/s10955-016-1672-z","ddc":["530"],"oa_version":"Submitted Version","publication_status":"published"},{"acknowledgement":"The authors acknowledge funding of the German Re-\r\nsearch Foundation (DFG) via the Collaborative Re-\r\nsearch Center (SFB 557) \\Control of Complex Turbu-\r\nlent Shear Flows\" and the Emmy Noether Program.\r\nFurther funding was provided by the Zuse Institute\r\nBerlin (ZIB), the DFG-CNRS research group \\Noise\r\nGeneration in Turbulent Flows\" (2003{2010), the Chaire\r\nd'Excellence 'Closed-loop control of turbulent shear ows\r\nusing reduced-order models' (TUCOROM) of the French\r\nAgence Nationale de la Recherche (ANR), and the Eu-\r\nropean Social Fund (ESF App. No. 100098251). We\r\nthank the Ambrosys Ltd. Society for Complex Sys-\r\ntems Management and the Bernd R. Noack Cybernet-\r\nics Foundation for additional support. A part of this\r\nwork was performed using HPC resources from GENCI-[CCRT/CINES/IDRIS] supported by the Grant 2011-\r\n[x2011020912","volume":68,"abstract":[{"text":"A framework fo r extracting features in 2D transient flows, based on the acceleration field to ensure Galilean invariance is proposed in this paper. The minima of the acceleration magnitude (a superset of acceleration zeros) are extracted and discriminated into vortices and saddle points, based on the spectral properties of the velocity Jacobian. The extraction of topological features is performed with purely combinatorial algorithms from discrete computational topology. The feature points are prioritized with persistence, as a physically meaningful importance measure. These feature points are tracked in time with a robust algorithm for tracking features. Thus, a space-time hierarchy of the minima is built and vortex merging events are detected. We apply the acceleration feature extraction strategy to three two-dimensional shear flows: (1) an incompressible periodic cylinder wake, (2) an incompressible planar mixing layer and (3) a weakly compressible planar jet. The vortex-like acceleration feature points are shown to be well aligned with acceleration zeros, maxima of the vorticity magnitude, minima of the pressure field and minima of λ2.","lang":"eng"}],"date_created":"2018-12-11T11:50:46Z","language":[{"iso":"eng"}],"date_published":"2016-01-01T00:00:00Z","oa":1,"main_file_link":[{"open_access":"1","url":"http://am.ippt.pan.pl/am/article/viewFile/v68p55/pdf"}],"date_updated":"2021-01-12T06:49:09Z","publication":"Archives of Mechanics","publisher":"Polish Academy of Sciences Publishing House","_id":"1216","day":"01","citation":{"ieee":"J. Kasten et al., “Acceleration feature points of unsteady shear flows,” Archives of Mechanics, vol. 68, no. 1. Polish Academy of Sciences Publishing House, pp. 55–80, 2016.","ista":"Kasten J, Reininghaus J, Hotz I, Hege H, Noack B, Daviller G, Morzyński M. 2016. Acceleration feature points of unsteady shear flows. Archives of Mechanics. 68(1), 55–80.","mla":"Kasten, Jens, et al. “Acceleration Feature Points of Unsteady Shear Flows.” Archives of Mechanics, vol. 68, no. 1, Polish Academy of Sciences Publishing House, 2016, pp. 55–80.","chicago":"Kasten, Jens, Jan Reininghaus, Ingrid Hotz, Hans Hege, Bernd Noack, Guillaume Daviller, and Marek Morzyński. “Acceleration Feature Points of Unsteady Shear Flows.” Archives of Mechanics. Polish Academy of Sciences Publishing House, 2016.","ama":"Kasten J, Reininghaus J, Hotz I, et al. Acceleration feature points of unsteady shear flows. Archives of Mechanics. 2016;68(1):55-80.","apa":"Kasten, J., Reininghaus, J., Hotz, I., Hege, H., Noack, B., Daviller, G., & Morzyński, M. (2016). Acceleration feature points of unsteady shear flows. Archives of Mechanics. Polish Academy of Sciences Publishing House.","short":"J. Kasten, J. Reininghaus, I. Hotz, H. Hege, B. Noack, G. Daviller, M. Morzyński, Archives of Mechanics 68 (2016) 55–80."},"intvolume":" 68","month":"01","author":[{"last_name":"Kasten","first_name":"Jens","full_name":"Kasten, Jens"},{"first_name":"Jan","full_name":"Reininghaus, Jan","last_name":"Reininghaus","id":"4505473A-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Hotz, Ingrid","first_name":"Ingrid","last_name":"Hotz"},{"first_name":"Hans","full_name":"Hege, Hans","last_name":"Hege"},{"full_name":"Noack, Bernd","first_name":"Bernd","last_name":"Noack"},{"last_name":"Daviller","full_name":"Daviller, Guillaume","first_name":"Guillaume"},{"first_name":"Marek","full_name":"Morzyński, Marek","last_name":"Morzyński"}],"department":[{"_id":"HeEd"}],"quality_controlled":"1","page":"55 - 80","title":"Acceleration feature points of unsteady shear flows","year":"2016","scopus_import":1,"status":"public","publist_id":"6118","type":"journal_article","publication_status":"published","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","issue":"1","oa_version":"Published Version"},{"date_published":"2016-07-01T00:00:00Z","publication":"Applied and Environmental Microbiology","acknowledgement":"Dutch Ministry of Economic Affairs, Agriculture, and Innovation through the program BioSolar CellsS. Andreas Angermayr,Pascal van Alphen, Klaas J. Hellingwerf\r\nWe thank Naira Quintana (presently at Rousselot, Belgium) for the ini-\r\ntiative at the 10th Cyanobacterial Molecular Biology Workshop\r\n(CMBW), June 2010, Lake Arrowhead, Los Angeles, CA, USA, to start the\r\ncollaborative endeavor reported here. We thank Timo Maarleveld from\r\nCWI/VU (Amsterdam) for a custom-made Python script handling the output from the NMR analysis and for evaluating and visualizing the\r\nseparate metabolites for their evaluation. We thank Rob Verpoorte from\r\nLeiden University (metabolome analysis) and Hans Aerts from the AMC\r\n(proteome analysis) for lab space and equipment. We thank Robert Leh-\r\nmann (Humboldt University Berlin) and Ilka Axmann (University of\r\nDüsseldorf) for sharing the R-code for the LOS transformation of the\r\ntranscript data. We thank Hans C. P. Matthijs from IBED for inspiring\r\ndialogues and insightful thoughts on continuous culturing of cyanobac-\r\nteria. We thank Sandra Waaijenborg for performing the transcript nor-\r\nmalization and Johan Westerhuis from BDA, Jeroen van der Steen and\r\nFilipe Branco dos Santos from MMP, and Lucas Stal from IBED/NIOZ for\r\nhelpful discussions. We thank Milou Schuurmans from MMP for help\r\nwith sampling and glycogen determination. We thank the members of the\r\nRNA Biology & Applied Bioinformatics group at SILS, in particular Selina\r\nvan Leeuwen, Elisa Hoekstra, and Martijs Jonker, for the microarray anal-\r\nysis. We thank the reviewers of this work for their insightful comments\r\nwhich improved the quality of the manuscript. This work, including the efforts of S. Andreas Angermayr, Pascal van\r\nAlphen, and Klaas J. Hellingwerf, was funded by Dutch Ministry of Eco-\r\nnomic Affairs, Agriculture, and Innovation through the program BioSolar\r\nCells.","quality_controlled":"1","month":"07","intvolume":" 82","author":[{"id":"4677C796-F248-11E8-B48F-1D18A9856A87","last_name":"Angermayr","first_name":"Andreas","orcid":"0000-0001-8619-2223","full_name":"Angermayr, Andreas"},{"last_name":"Van Alphen","first_name":"Pascal","full_name":"Van Alphen, Pascal"},{"last_name":"Hasdemir","first_name":"Dicle","full_name":"Hasdemir, Dicle"},{"first_name":"Gertjan","full_name":"Kramer, Gertjan","last_name":"Kramer"},{"full_name":"Iqbal, Muzamal","first_name":"Muzamal","last_name":"Iqbal"},{"first_name":"Wilmar","full_name":"Van Grondelle, Wilmar","last_name":"Van Grondelle"},{"full_name":"Hoefsloot, Huub","first_name":"Huub","last_name":"Hoefsloot"},{"last_name":"Choi","full_name":"Choi, Younghae","first_name":"Younghae"},{"full_name":"Hellingwerf, Klaas","first_name":"Klaas","last_name":"Hellingwerf"}],"year":"2016","doi":"10.1128/AEM.00256-16","oa_version":"Submitted Version","publication_status":"published","oa":1,"main_file_link":[{"open_access":"1","url":"https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4959195/"}],"date_updated":"2021-01-12T06:49:10Z","volume":82,"abstract":[{"text":"Investigating the physiology of cyanobacteria cultured under a diel light regime is relevant for a better understanding of the resulting growth characteristics and for specific biotechnological applications that are foreseen for these photosynthetic organisms. Here, we present the results of a multiomics study of the model cyanobacterium Synechocystis sp. strain PCC 6803, cultured in a lab-scale photobioreactor in physiological conditions relevant for large-scale culturing. The culture was sparged withN2 andCO2, leading to an anoxic environment during the dark period. Growth followed the availability of light. Metabolite analysis performed with 1Hnuclear magnetic resonance analysis showed that amino acids involved in nitrogen and sulfur assimilation showed elevated levels in the light. Most protein levels, analyzed through mass spectrometry, remained rather stable. However, several high-light-response proteins and stress-response proteins showed distinct changes at the onset of the light period. Microarray-based transcript analysis found common patterns of~56% of the transcriptome following the diel regime. These oscillating transcripts could be grouped coarsely into genes that were upregulated and downregulated in the dark period. The accumulated glycogen was degraded in the anaerobic environment in the dark. A small part was degraded gradually, reflecting basic maintenance requirements of the cells in darkness. Surprisingly, the largest part was degraded rapidly in a short time span at the end of the dark period. This degradation could allow rapid formation of metabolic intermediates at the end of the dark period, preparing the cells for the resumption of growth at the start of the light period.","lang":"eng"}],"date_created":"2018-12-11T11:50:46Z","language":[{"iso":"eng"}],"department":[{"_id":"ToBo"}],"day":"01","publisher":"American Society for Microbiology","_id":"1218","citation":{"short":"A. Angermayr, P. Van Alphen, D. Hasdemir, G. Kramer, M. Iqbal, W. Van Grondelle, H. Hoefsloot, Y. Choi, K. Hellingwerf, Applied and Environmental Microbiology 82 (2016) 4180–4189.","ama":"Angermayr A, Van Alphen P, Hasdemir D, et al. Culturing synechocystis sp. Strain pcc 6803 with N2 and CO2 in a diel regime reveals multiphase glycogen dynamics with low maintenance costs. Applied and Environmental Microbiology. 2016;82(14):4180-4189. doi:10.1128/AEM.00256-16","apa":"Angermayr, A., Van Alphen, P., Hasdemir, D., Kramer, G., Iqbal, M., Van Grondelle, W., … Hellingwerf, K. (2016). Culturing synechocystis sp. Strain pcc 6803 with N2 and CO2 in a diel regime reveals multiphase glycogen dynamics with low maintenance costs. Applied and Environmental Microbiology. American Society for Microbiology. https://doi.org/10.1128/AEM.00256-16","ieee":"A. Angermayr et al., “Culturing synechocystis sp. Strain pcc 6803 with N2 and CO2 in a diel regime reveals multiphase glycogen dynamics with low maintenance costs,” Applied and Environmental Microbiology, vol. 82, no. 14. American Society for Microbiology, pp. 4180–4189, 2016.","ista":"Angermayr A, Van Alphen P, Hasdemir D, Kramer G, Iqbal M, Van Grondelle W, Hoefsloot H, Choi Y, Hellingwerf K. 2016. Culturing synechocystis sp. Strain pcc 6803 with N2 and CO2 in a diel regime reveals multiphase glycogen dynamics with low maintenance costs. Applied and Environmental Microbiology. 82(14), 4180–4189.","mla":"Angermayr, Andreas, et al. “Culturing Synechocystis Sp. Strain Pcc 6803 with N2 and CO2 in a Diel Regime Reveals Multiphase Glycogen Dynamics with Low Maintenance Costs.” Applied and Environmental Microbiology, vol. 82, no. 14, American Society for Microbiology, 2016, pp. 4180–89, doi:10.1128/AEM.00256-16.","chicago":"Angermayr, Andreas, Pascal Van Alphen, Dicle Hasdemir, Gertjan Kramer, Muzamal Iqbal, Wilmar Van Grondelle, Huub Hoefsloot, Younghae Choi, and Klaas Hellingwerf. “Culturing Synechocystis Sp. Strain Pcc 6803 with N2 and CO2 in a Diel Regime Reveals Multiphase Glycogen Dynamics with Low Maintenance Costs.” Applied and Environmental Microbiology. American Society for Microbiology, 2016. https://doi.org/10.1128/AEM.00256-16."},"scopus_import":1,"title":"Culturing synechocystis sp. Strain pcc 6803 with N2 and CO2 in a diel regime reveals multiphase glycogen dynamics with low maintenance costs","status":"public","page":"4180 - 4189","type":"journal_article","publist_id":"6117","issue":"14","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87"}]