--- _id: '7401' abstract: - lang: eng text: 'The genus g(G) of a graph G is the minimum g such that G has an embedding on the orientable surface M_g of genus g. A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The Z_2-genus of a graph G, denoted by g_0(G), is the minimum g such that G has an independently even drawing on M_g. By a result of Battle, Harary, Kodama and Youngs from 1962, the graph genus is additive over 2-connected blocks. In 2013, Schaefer and Stefankovic proved that the Z_2-genus of a graph is additive over 2-connected blocks as well, and asked whether this result can be extended to so-called 2-amalgamations, as an analogue of results by Decker, Glover, Huneke, and Stahl for the genus. We give the following partial answer. If G=G_1 cup G_2, G_1 and G_2 intersect in two vertices u and v, and G-u-v has k connected components (among which we count the edge uv if present), then |g_0(G)-(g_0(G_1)+g_0(G_2))|<=k+1. For complete bipartite graphs K_{m,n}, with n >= m >= 3, we prove that g_0(K_{m,n})/g(K_{m,n})=1-O(1/n). Similar results are proved also for the Euler Z_2-genus. We express the Z_2-genus of a graph using the minimum rank of partial symmetric matrices over Z_2; a problem that might be of independent interest. ' alternative_title: - LIPIcs article_number: '39' article_processing_charge: No arxiv: 1 author: - first_name: Radoslav full_name: Fulek, Radoslav id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87 last_name: Fulek orcid: 0000-0001-8485-1774 - first_name: Jan full_name: Kyncl, Jan last_name: Kyncl citation: ama: 'Fulek R, Kyncl J. Z_2-Genus of graphs and minimum rank of partial symmetric matrices. In: 35th International Symposium on Computational Geometry (SoCG 2019). Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:10.4230/LIPICS.SOCG.2019.39' apa: 'Fulek, R., & Kyncl, J. (2019). Z_2-Genus of graphs and minimum rank of partial symmetric matrices. In 35th International Symposium on Computational Geometry (SoCG 2019) (Vol. 129). Portland, OR, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.SOCG.2019.39' chicago: Fulek, Radoslav, and Jan Kyncl. “Z_2-Genus of Graphs and Minimum Rank of Partial Symmetric Matrices.” In 35th International Symposium on Computational Geometry (SoCG 2019), Vol. 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.SOCG.2019.39. ieee: R. Fulek and J. Kyncl, “Z_2-Genus of graphs and minimum rank of partial symmetric matrices,” in 35th International Symposium on Computational Geometry (SoCG 2019), Portland, OR, United States, 2019, vol. 129. ista: 'Fulek R, Kyncl J. 2019. Z_2-Genus of graphs and minimum rank of partial symmetric matrices. 35th International Symposium on Computational Geometry (SoCG 2019). SoCG: Symposium on Computational Geometry, LIPIcs, vol. 129, 39.' mla: Fulek, Radoslav, and Jan Kyncl. “Z_2-Genus of Graphs and Minimum Rank of Partial Symmetric Matrices.” 35th International Symposium on Computational Geometry (SoCG 2019), vol. 129, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, doi:10.4230/LIPICS.SOCG.2019.39. short: R. Fulek, J. Kyncl, in:, 35th International Symposium on Computational Geometry (SoCG 2019), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. conference: end_date: 2019-06-21 location: Portland, OR, United States name: 'SoCG: Symposium on Computational Geometry' start_date: 2019-06-18 date_created: 2020-01-29T16:17:05Z date_published: 2019-06-01T00:00:00Z date_updated: 2021-01-12T08:13:24Z day: '01' ddc: - '000' department: - _id: UlWa doi: 10.4230/LIPICS.SOCG.2019.39 external_id: arxiv: - '1903.08637' file: - access_level: open_access checksum: aac37b09118cc0ab58cf77129e691f8c content_type: application/pdf creator: dernst date_created: 2020-02-04T09:14:31Z date_updated: 2020-07-14T12:47:57Z file_id: '7445' file_name: 2019_LIPIcs_Fulek.pdf file_size: 628347 relation: main_file file_date_updated: 2020-07-14T12:47:57Z has_accepted_license: '1' intvolume: ' 129' language: - iso: eng month: '06' oa: 1 oa_version: Published Version project: - _id: 261FA626-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: M02281 name: Eliminating intersections in drawings of graphs publication: 35th International Symposium on Computational Geometry (SoCG 2019) publication_identifier: isbn: - 978-3-95977-104-7 issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: 1 status: public title: Z_2-Genus of graphs and minimum rank of partial symmetric matrices tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 129 year: '2019' ... --- _id: '6528' abstract: - lang: eng text: We construct a verifiable delay function (VDF) by showing how the Rivest-Shamir-Wagner time-lock puzzle can be made publicly verifiable. Concretely, we give a statistically sound public-coin protocol to prove that a tuple (N,x,T,y) satisfies y=x2T (mod N) where the prover doesn’t know the factorization of N and its running time is dominated by solving the puzzle, that is, compute x2T, which is conjectured to require T sequential squarings. To get a VDF we make this protocol non-interactive using the Fiat-Shamir heuristic.The motivation for this work comes from the Chia blockchain design, which uses a VDF as akey ingredient. For typical parameters (T≤2 40, N= 2048), our proofs are of size around 10K B, verification cost around three RSA exponentiations and computing the proof is 8000 times faster than solving the puzzle even without any parallelism. alternative_title: - LIPIcs article_number: '60' article_processing_charge: No author: - first_name: Krzysztof Z full_name: Pietrzak, Krzysztof Z id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87 last_name: Pietrzak orcid: 0000-0002-9139-1654 citation: ama: 'Pietrzak KZ. Simple verifiable delay functions. In: 10th Innovations in Theoretical Computer Science Conference. Vol 124. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:10.4230/LIPICS.ITCS.2019.60' apa: 'Pietrzak, K. Z. (2019). Simple verifiable delay functions. In 10th Innovations in Theoretical Computer Science Conference (Vol. 124). San Diego, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ITCS.2019.60' chicago: Pietrzak, Krzysztof Z. “Simple Verifiable Delay Functions.” In 10th Innovations in Theoretical Computer Science Conference, Vol. 124. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.ITCS.2019.60. ieee: K. Z. Pietrzak, “Simple verifiable delay functions,” in 10th Innovations in Theoretical Computer Science Conference, San Diego, CA, United States, 2019, vol. 124. ista: 'Pietrzak KZ. 2019. Simple verifiable delay functions. 10th Innovations in Theoretical Computer Science Conference. ITCS 2019: Innovations in Theoretical Computer Science, LIPIcs, vol. 124, 60.' mla: Pietrzak, Krzysztof Z. “Simple Verifiable Delay Functions.” 10th Innovations in Theoretical Computer Science Conference, vol. 124, 60, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, doi:10.4230/LIPICS.ITCS.2019.60. short: K.Z. Pietrzak, in:, 10th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. conference: end_date: 2019-01-12 location: San Diego, CA, United States name: 'ITCS 2019: Innovations in Theoretical Computer Science' start_date: 2019-01-10 date_created: 2019-06-06T14:12:36Z date_published: 2019-01-10T00:00:00Z date_updated: 2021-01-12T08:07:53Z day: '10' ddc: - '000' department: - _id: KrPi doi: 10.4230/LIPICS.ITCS.2019.60 ec_funded: 1 file: - access_level: open_access checksum: f0ae1bb161431d9db3dea5ace082bfb5 content_type: application/pdf creator: dernst date_created: 2019-06-06T14:22:04Z date_updated: 2020-07-14T12:47:33Z file_id: '6529' file_name: 2019_LIPIcs_Pietrzak.pdf file_size: 558770 relation: main_file file_date_updated: 2020-07-14T12:47:33Z has_accepted_license: '1' intvolume: ' 124' language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2018/627 month: '01' oa: 1 oa_version: Published Version project: - _id: 258AA5B2-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '682815' name: Teaching Old Crypto New Tricks publication: 10th Innovations in Theoretical Computer Science Conference publication_identifier: isbn: - 978-3-95977-095-8 issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: 1 status: public title: Simple verifiable delay functions tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 124 year: '2019' ... --- _id: '6556' abstract: - lang: eng text: 'Motivated by fixed-parameter tractable (FPT) problems in computational topology, we consider the treewidth tw(M) of a compact, connected 3-manifold M, defined to be the minimum treewidth of the face pairing graph of any triangulation T of M. In this setting the relationship between the topology of a 3-manifold and its treewidth is of particular interest. First, as a corollary of work of Jaco and Rubinstein, we prove that for any closed, orientable 3-manifold M the treewidth tw(M) is at most 4g(M)-2, where g(M) denotes Heegaard genus of M. In combination with our earlier work with Wagner, this yields that for non-Haken manifolds the Heegaard genus and the treewidth are within a constant factor. Second, we characterize all 3-manifolds of treewidth one: These are precisely the lens spaces and a single other Seifert fibered space. Furthermore, we show that all remaining orientable Seifert fibered spaces over the 2-sphere or a non-orientable surface have treewidth two. In particular, for every spherical 3-manifold we exhibit a triangulation of treewidth at most two. Our results further validate the parameter of treewidth (and other related parameters such as cutwidth or congestion) to be useful for topological computing, and also shed more light on the scope of existing FPT-algorithms in the field.' alternative_title: - LIPIcs article_processing_charge: No arxiv: 1 author: - first_name: Kristóf full_name: Huszár, Kristóf id: 33C26278-F248-11E8-B48F-1D18A9856A87 last_name: Huszár orcid: 0000-0002-5445-5057 - first_name: Jonathan full_name: Spreer, Jonathan last_name: Spreer citation: ama: 'Huszár K, Spreer J. 3-manifold triangulations with small treewidth. In: 35th International Symposium on Computational Geometry. Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:44:1-44:20. doi:10.4230/LIPIcs.SoCG.2019.44' apa: 'Huszár, K., & Spreer, J. (2019). 3-manifold triangulations with small treewidth. In 35th International Symposium on Computational Geometry (Vol. 129, p. 44:1-44:20). Portland, Oregon, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2019.44' chicago: Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small Treewidth.” In 35th International Symposium on Computational Geometry, 129:44:1-44:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPIcs.SoCG.2019.44. ieee: K. Huszár and J. Spreer, “3-manifold triangulations with small treewidth,” in 35th International Symposium on Computational Geometry, Portland, Oregon, United States, 2019, vol. 129, p. 44:1-44:20. ista: 'Huszár K, Spreer J. 2019. 3-manifold triangulations with small treewidth. 35th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 129, 44:1-44:20.' mla: Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small Treewidth.” 35th International Symposium on Computational Geometry, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20, doi:10.4230/LIPIcs.SoCG.2019.44. short: K. Huszár, J. Spreer, in:, 35th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20. conference: end_date: 2019-06-21 location: Portland, Oregon, United States name: 'SoCG: Symposium on Computational Geometry' start_date: 2019-06-18 date_created: 2019-06-11T20:09:57Z date_published: 2019-06-01T00:00:00Z date_updated: 2023-09-07T13:18:26Z day: '01' ddc: - '516' department: - _id: UlWa doi: 10.4230/LIPIcs.SoCG.2019.44 external_id: arxiv: - '1812.05528' file: - access_level: open_access checksum: 29d18c435368468aa85823dabb157e43 content_type: application/pdf creator: kschuh date_created: 2019-06-12T06:45:33Z date_updated: 2020-07-14T12:47:33Z file_id: '6557' file_name: 2019_LIPIcs-Huszar.pdf file_size: 905885 relation: main_file file_date_updated: 2020-07-14T12:47:33Z has_accepted_license: '1' intvolume: ' 129' keyword: - computational 3-manifold topology - fixed-parameter tractability - layered triangulations - structural graph theory - treewidth - cutwidth - Heegaard genus language: - iso: eng month: '06' oa: 1 oa_version: Published Version page: 44:1-44:20 publication: 35th International Symposium on Computational Geometry publication_identifier: isbn: - 978-3-95977-104-7 issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' related_material: record: - id: '8032' relation: part_of_dissertation status: public scopus_import: '1' status: public title: 3-manifold triangulations with small treewidth tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 129 year: '2019' ... --- _id: '6647' abstract: - lang: eng text: The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r-1)+1 points in R^d, one can find a partition X=X_1 cup ... cup X_r of X, such that the convex hulls of the X_i, i=1,...,r, all share a common point. In this paper, we prove a strengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span floor[n/3] vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Alvarez-Rebollar et al. guarantees floor[n/6] pairwise crossing triangles. Our result generalizes to a result about simplices in R^d,d >=2. alternative_title: - LIPIcs arxiv: 1 author: - first_name: Radoslav full_name: Fulek, Radoslav id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87 last_name: Fulek orcid: 0000-0001-8485-1774 - first_name: Bernd full_name: Gärtner, Bernd last_name: Gärtner - first_name: Andrey full_name: Kupavskii, Andrey last_name: Kupavskii - first_name: Pavel full_name: Valtr, Pavel last_name: Valtr - first_name: Uli full_name: Wagner, Uli id: 36690CA2-F248-11E8-B48F-1D18A9856A87 last_name: Wagner orcid: 0000-0002-1494-0568 citation: ama: 'Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg theorem. In: 35th International Symposium on Computational Geometry. Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:38:1-38:13. doi:10.4230/LIPICS.SOCG.2019.38' apa: 'Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., & Wagner, U. (2019). The crossing Tverberg theorem. In 35th International Symposium on Computational Geometry (Vol. 129, p. 38:1-38:13). Portland, OR, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.SOCG.2019.38' chicago: Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner. “The Crossing Tverberg Theorem.” In 35th International Symposium on Computational Geometry, 129:38:1-38:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.SOCG.2019.38. ieee: R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing Tverberg theorem,” in 35th International Symposium on Computational Geometry, Portland, OR, United States, 2019, vol. 129, p. 38:1-38:13. ista: 'Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2019. The crossing Tverberg theorem. 35th International Symposium on Computational Geometry. SoCG 2019: Symposium on Computational Geometry, LIPIcs, vol. 129, 38:1-38:13.' mla: Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” 35th International Symposium on Computational Geometry, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 38:1-38:13, doi:10.4230/LIPICS.SOCG.2019.38. short: R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, in:, 35th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 38:1-38:13. conference: end_date: 2019-06-21 location: Portland, OR, United States name: 'SoCG 2019: Symposium on Computational Geometry' start_date: 2019-06-18 date_created: 2019-07-17T10:35:04Z date_published: 2019-06-01T00:00:00Z date_updated: 2023-12-13T12:03:35Z day: '01' ddc: - '000' - '510' department: - _id: UlWa doi: 10.4230/LIPICS.SOCG.2019.38 external_id: arxiv: - '1812.04911' file: - access_level: open_access checksum: d6d017f8b41291b94d102294fa96ae9c content_type: application/pdf creator: dernst date_created: 2019-07-24T06:54:52Z date_updated: 2020-07-14T12:47:35Z file_id: '6667' file_name: 2019_LIPICS_Fulek.pdf file_size: 559837 relation: main_file file_date_updated: 2020-07-14T12:47:35Z has_accepted_license: '1' intvolume: ' 129' language: - iso: eng month: '06' oa: 1 oa_version: Published Version page: 38:1-38:13 project: - _id: 261FA626-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: M02281 name: Eliminating intersections in drawings of graphs publication: 35th International Symposium on Computational Geometry publication_identifier: isbn: - '9783959771047' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' related_material: record: - id: '13974' relation: later_version status: public scopus_import: 1 status: public title: The crossing Tverberg theorem tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 129 year: '2019' ... --- _id: '6725' abstract: - lang: eng text: "A Valued Constraint Satisfaction Problem (VCSP) provides a common framework that can express a wide range of discrete optimization problems. A VCSP instance is given by a finite set of variables, a finite domain of labels, and an objective function to be minimized. This function is represented as a sum of terms where each term depends on a subset of the variables. To obtain different classes of optimization problems, one can restrict all terms to come from a fixed set Γ of cost functions, called a language. \r\nRecent breakthrough results have established a complete complexity classification of such classes with respect to language Γ: if all cost functions in Γ satisfy a certain algebraic condition then all Γ-instances can be solved in polynomial time, otherwise the problem is NP-hard. Unfortunately, testing this condition for a given language Γ is known to be NP-hard. We thus study exponential algorithms for this meta-problem. We show that the tractability condition of a finite-valued language Γ can be tested in O(3‾√3|D|⋅poly(size(Γ))) time, where D is the domain of Γ and poly(⋅) is some fixed polynomial. We also obtain a matching lower bound under the Strong Exponential Time Hypothesis (SETH). More precisely, we prove that for any constant δ<1 there is no O(3‾√3δ|D|) algorithm, assuming that SETH holds." alternative_title: - LIPIcs arxiv: 1 author: - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov citation: ama: 'Kolmogorov V. Testing the complexity of a valued CSP language. In: 46th International Colloquium on Automata, Languages and Programming. Vol 132. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:77:1-77:12. doi:10.4230/LIPICS.ICALP.2019.77' apa: 'Kolmogorov, V. (2019). Testing the complexity of a valued CSP language. In 46th International Colloquium on Automata, Languages and Programming (Vol. 132, p. 77:1-77:12). Patras, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ICALP.2019.77' chicago: Kolmogorov, Vladimir. “Testing the Complexity of a Valued CSP Language.” In 46th International Colloquium on Automata, Languages and Programming, 132:77:1-77:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.ICALP.2019.77. ieee: V. Kolmogorov, “Testing the complexity of a valued CSP language,” in 46th International Colloquium on Automata, Languages and Programming, Patras, Greece, 2019, vol. 132, p. 77:1-77:12. ista: 'Kolmogorov V. 2019. Testing the complexity of a valued CSP language. 46th International Colloquium on Automata, Languages and Programming. ICALP 2019: International Colloquim on Automata, Languages and Programming, LIPIcs, vol. 132, 77:1-77:12.' mla: Kolmogorov, Vladimir. “Testing the Complexity of a Valued CSP Language.” 46th International Colloquium on Automata, Languages and Programming, vol. 132, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 77:1-77:12, doi:10.4230/LIPICS.ICALP.2019.77. short: V. Kolmogorov, in:, 46th International Colloquium on Automata, Languages and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 77:1-77:12. conference: end_date: 2019-07-12 location: Patras, Greece name: 'ICALP 2019: International Colloquim on Automata, Languages and Programming' start_date: 2019-07-08 date_created: 2019-07-29T12:23:29Z date_published: 2019-07-01T00:00:00Z date_updated: 2021-01-12T08:08:40Z day: '01' ddc: - '000' department: - _id: VlKo doi: 10.4230/LIPICS.ICALP.2019.77 ec_funded: 1 external_id: arxiv: - '1803.02289' file: - access_level: open_access checksum: f5ebee8eec6ae09e30365578ee63a492 content_type: application/pdf creator: dernst date_created: 2019-07-31T07:01:45Z date_updated: 2020-07-14T12:47:38Z file_id: '6738' file_name: 2019_LIPICS_Kolmogorov.pdf file_size: 575475 relation: main_file file_date_updated: 2020-07-14T12:47:38Z has_accepted_license: '1' intvolume: ' 132' language: - iso: eng month: '07' oa: 1 oa_version: Published Version page: 77:1-77:12 project: - _id: 25FBA906-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '616160' name: 'Discrete Optimization in Computer Vision: Theory and Practice' publication: 46th International Colloquium on Automata, Languages and Programming publication_identifier: isbn: - 978-3-95977-109-2 issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: 1 status: public title: Testing the complexity of a valued CSP language tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 132 year: '2019' ... --- _id: '11826' abstract: - lang: eng text: "The diameter, radius and eccentricities are natural graph parameters. While these problems have been studied extensively, there are no known dynamic algorithms for them beyond the ones that follow from trivial recomputation after each update or from solving dynamic All-Pairs Shortest Paths (APSP), which is very computationally intensive. This is the situation for dynamic approximation algorithms as well, and even if only edge insertions or edge deletions need to be supported.\r\nThis paper provides a comprehensive study of the dynamic approximation of Diameter, Radius and Eccentricities, providing both conditional lower bounds, and new algorithms whose bounds are optimal under popular hypotheses in fine-grained complexity. Some of the highlights include:\r\n- Under popular hardness hypotheses, there can be no significantly better fully dynamic approximation algorithms than recomputing the answer after each update, or maintaining full APSP.\r\n- Nearly optimal partially dynamic (incremental/decremental) algorithms can be achieved via efficient reductions to (incremental/decremental) maintenance of Single-Source Shortest Paths. For instance, a nearly (3/2+epsilon)-approximation to Diameter in directed or undirected n-vertex, m-edge graphs can be maintained decrementally in total time m^{1+o(1)}sqrt{n}/epsilon^2. This nearly matches the static 3/2-approximation algorithm for the problem that is known to be conditionally optimal." alternative_title: - LIPIcs article_number: '13' article_processing_charge: No arxiv: 1 author: - first_name: Bertie full_name: Ancona, Bertie last_name: Ancona - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Liam full_name: Roditty, Liam last_name: Roditty - first_name: Virginia Vassilevska full_name: Williams, Virginia Vassilevska last_name: Williams - first_name: Nicole full_name: Wein, Nicole last_name: Wein citation: ama: 'Ancona B, Henzinger MH, Roditty L, Williams VV, Wein N. Algorithms and hardness for diameter in dynamic graphs. In: 46th International Colloquium on Automata, Languages, and Programming. Vol 132. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:10.4230/LIPICS.ICALP.2019.13' apa: 'Ancona, B., Henzinger, M. H., Roditty, L., Williams, V. V., & Wein, N. (2019). Algorithms and hardness for diameter in dynamic graphs. In 46th International Colloquium on Automata, Languages, and Programming (Vol. 132). Patras, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ICALP.2019.13' chicago: Ancona, Bertie, Monika H Henzinger, Liam Roditty, Virginia Vassilevska Williams, and Nicole Wein. “Algorithms and Hardness for Diameter in Dynamic Graphs.” In 46th International Colloquium on Automata, Languages, and Programming, Vol. 132. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.ICALP.2019.13. ieee: B. Ancona, M. H. Henzinger, L. Roditty, V. V. Williams, and N. Wein, “Algorithms and hardness for diameter in dynamic graphs,” in 46th International Colloquium on Automata, Languages, and Programming, Patras, Greece, 2019, vol. 132. ista: 'Ancona B, Henzinger MH, Roditty L, Williams VV, Wein N. 2019. Algorithms and hardness for diameter in dynamic graphs. 46th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 132, 13.' mla: Ancona, Bertie, et al. “Algorithms and Hardness for Diameter in Dynamic Graphs.” 46th International Colloquium on Automata, Languages, and Programming, vol. 132, 13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, doi:10.4230/LIPICS.ICALP.2019.13. short: B. Ancona, M.H. Henzinger, L. Roditty, V.V. Williams, N. Wein, in:, 46th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. conference: end_date: 2019-07-12 location: Patras, Greece name: 'ICALP: International Colloquium on Automata, Languages, and Programming' start_date: 2019-07-09 date_created: 2022-08-12T08:14:51Z date_published: 2019-07-04T00:00:00Z date_updated: 2023-02-16T10:48:24Z day: '04' doi: 10.4230/LIPICS.ICALP.2019.13 extern: '1' external_id: arxiv: - '811.12527' intvolume: ' 132' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.4230/LIPIcs.ICALP.2019.13 month: '07' oa: 1 oa_version: Published Version publication: 46th International Colloquium on Automata, Languages, and Programming publication_identifier: isbn: - 978-3-95977-109-2 issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Algorithms and hardness for diameter in dynamic graphs type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 132 year: '2019' ... --- _id: '7407' abstract: - lang: eng text: 'Proofs of space (PoS) [Dziembowski et al., CRYPTO''15] are proof systems where a prover can convince a verifier that he "wastes" disk space. PoS were introduced as a more ecological and economical replacement for proofs of work which are currently used to secure blockchains like Bitcoin. In this work we investigate extensions of PoS which allow the prover to embed useful data into the dedicated space, which later can be recovered. Our first contribution is a security proof for the original PoS from CRYPTO''15 in the random oracle model (the original proof only applied to a restricted class of adversaries which can store a subset of the data an honest prover would store). When this PoS is instantiated with recent constructions of maximally depth robust graphs, our proof implies basically optimal security. As a second contribution we show three different extensions of this PoS where useful data can be embedded into the space required by the prover. Our security proof for the PoS extends (non-trivially) to these constructions. We discuss how some of these variants can be used as proofs of catalytic space (PoCS), a notion we put forward in this work, and which basically is a PoS where most of the space required by the prover can be used to backup useful data. Finally we discuss how one of the extensions is a candidate construction for a proof of replication (PoR), a proof system recently suggested in the Filecoin whitepaper. ' alternative_title: - LIPIcs article_processing_charge: No author: - first_name: Krzysztof Z full_name: Pietrzak, Krzysztof Z id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87 last_name: Pietrzak orcid: 0000-0002-9139-1654 citation: ama: 'Pietrzak KZ. Proofs of catalytic space. In: 10th Innovations in Theoretical Computer Science  Conference (ITCS 2019). Vol 124. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018:59:1-59:25. doi:10.4230/LIPICS.ITCS.2019.59' apa: 'Pietrzak, K. Z. (2018). Proofs of catalytic space. In 10th Innovations in Theoretical Computer Science  Conference (ITCS 2019) (Vol. 124, p. 59:1-59:25). San Diego, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ITCS.2019.59' chicago: Pietrzak, Krzysztof Z. “Proofs of Catalytic Space.” In 10th Innovations in Theoretical Computer Science  Conference (ITCS 2019), 124:59:1-59:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPICS.ITCS.2019.59. ieee: K. Z. Pietrzak, “Proofs of catalytic space,” in 10th Innovations in Theoretical Computer Science  Conference (ITCS 2019), San Diego, CA, United States, 2018, vol. 124, p. 59:1-59:25. ista: 'Pietrzak KZ. 2018. Proofs of catalytic space. 10th Innovations in Theoretical Computer Science  Conference (ITCS 2019). ITCS: Innovations in theoretical Computer Science Conference, LIPIcs, vol. 124, 59:1-59:25.' mla: Pietrzak, Krzysztof Z. “Proofs of Catalytic Space.” 10th Innovations in Theoretical Computer Science  Conference (ITCS 2019), vol. 124, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 59:1-59:25, doi:10.4230/LIPICS.ITCS.2019.59. short: K.Z. Pietrzak, in:, 10th Innovations in Theoretical Computer Science  Conference (ITCS 2019), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 59:1-59:25. conference: end_date: 2019-01-12 location: San Diego, CA, United States name: 'ITCS: Innovations in theoretical Computer Science Conference' start_date: 2019-01-10 date_created: 2020-01-30T09:16:05Z date_published: 2018-12-31T00:00:00Z date_updated: 2021-01-12T08:13:26Z day: '31' ddc: - '000' department: - _id: KrPi doi: 10.4230/LIPICS.ITCS.2019.59 ec_funded: 1 file: - access_level: open_access checksum: 5cebb7f7849a3beda898f697d755dd96 content_type: application/pdf creator: dernst date_created: 2020-02-04T08:17:52Z date_updated: 2020-07-14T12:47:57Z file_id: '7443' file_name: 2018_LIPIcs_Pietrzak.pdf file_size: 822884 relation: main_file file_date_updated: 2020-07-14T12:47:57Z has_accepted_license: '1' intvolume: ' 124' language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2018/194 month: '12' oa: 1 oa_version: Published Version page: 59:1-59:25 project: - _id: 258AA5B2-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '682815' name: Teaching Old Crypto New Tricks publication: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019) publication_identifier: isbn: - 978-3-95977-095-8 issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: 1 status: public title: Proofs of catalytic space tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 124 year: '2018' ... --- _id: '6005' abstract: - lang: eng text: Network games are widely used as a model for selfish resource-allocation problems. In the classicalmodel, each player selects a path connecting her source and target vertices. The cost of traversingan edge depends on theload; namely, number of players that traverse it. Thus, it abstracts the factthat different users may use a resource at different times and for different durations, which playsan important role in determining the costs of the users in reality. For example, when transmittingpackets in a communication network, routing traffic in a road network, or processing a task in aproduction system, actual sharing and congestion of resources crucially depends on time.In [13], we introducedtimed network games, which add a time component to network games.Each vertexvin the network is associated with a cost function, mapping the load onvto theprice that a player pays for staying invfor one time unit with this load. Each edge in thenetwork is guarded by the time intervals in which it can be traversed, which forces the players tospend time in the vertices. In this work we significantly extend the way time can be referred toin timed network games. In the model we study, the network is equipped withclocks, and, as intimed automata, edges are guarded by constraints on the values of the clocks, and their traversalmay involve a reset of some clocks. We argue that the stronger model captures many realisticnetworks. The addition of clocks breaks the techniques we developed in [13] and we developnew techniques in order to show that positive results on classic network games carry over to thestronger timed setting. alternative_title: - LIPIcs article_number: '23' article_processing_charge: No author: - first_name: Guy full_name: Avni, Guy id: 463C8BC2-F248-11E8-B48F-1D18A9856A87 last_name: Avni orcid: 0000-0001-5588-8287 - first_name: Shibashis full_name: Guha, Shibashis last_name: Guha - first_name: Orna full_name: Kupferman, Orna last_name: Kupferman citation: ama: 'Avni G, Guha S, Kupferman O. Timed network games with clocks. In: Vol 117. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPICS.MFCS.2018.23' apa: 'Avni, G., Guha, S., & Kupferman, O. (2018). Timed network games with clocks (Vol. 117). Presented at the MFCS: Mathematical Foundations of Computer Science, Liverpool, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.MFCS.2018.23' chicago: Avni, Guy, Shibashis Guha, and Orna Kupferman. “Timed Network Games with Clocks,” Vol. 117. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPICS.MFCS.2018.23. ieee: 'G. Avni, S. Guha, and O. Kupferman, “Timed network games with clocks,” presented at the MFCS: Mathematical Foundations of Computer Science, Liverpool, United Kingdom, 2018, vol. 117.' ista: 'Avni G, Guha S, Kupferman O. 2018. Timed network games with clocks. MFCS: Mathematical Foundations of Computer Science, LIPIcs, vol. 117, 23.' mla: Avni, Guy, et al. Timed Network Games with Clocks. Vol. 117, 23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:10.4230/LIPICS.MFCS.2018.23. short: G. Avni, S. Guha, O. Kupferman, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. conference: end_date: 2018-08-31 location: Liverpool, United Kingdom name: 'MFCS: Mathematical Foundations of Computer Science' start_date: 2018-08-27 date_created: 2019-02-14T14:12:09Z date_published: 2018-08-01T00:00:00Z date_updated: 2023-02-23T14:02:58Z day: '01' ddc: - '000' department: - _id: ToHe doi: 10.4230/LIPICS.MFCS.2018.23 file: - access_level: open_access checksum: 41ab2ae9b63f5eb49fa995250c0ba128 content_type: application/pdf creator: dernst date_created: 2019-02-14T14:22:04Z date_updated: 2020-07-14T12:47:15Z file_id: '6007' file_name: 2018_LIPIcs_Avni.pdf file_size: 542889 relation: main_file file_date_updated: 2020-07-14T12:47:15Z has_accepted_license: '1' intvolume: ' 117' language: - iso: eng month: '08' oa: 1 oa_version: Published Version project: - _id: 25832EC2-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S 11407_N23 name: Rigorous Systems Engineering - _id: 25F42A32-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z211 name: The Wittgenstein Prize - _id: 264B3912-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: M02369 name: Formal Methods meets Algorithmic Game Theory publication_identifier: issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' related_material: record: - id: '963' relation: earlier_version status: public scopus_import: '1' status: public title: Timed network games with clocks tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 117 year: '2018' ... --- _id: '11827' abstract: - lang: eng text: We study the metric facility location problem with client insertions and deletions. This setting differs from the classic dynamic facility location problem, where the set of clients remains the same, but the metric space can change over time. We show a deterministic algorithm that maintains a constant factor approximation to the optimal solution in worst-case time O~(2^{O(kappa^2)}) per client insertion or deletion in metric spaces while answering queries about the cost in O(1) time, where kappa denotes the doubling dimension of the metric. For metric spaces with bounded doubling dimension, the update time is polylogarithmic in the parameters of the problem. alternative_title: - LIPIcs article_number: '39' article_processing_charge: No arxiv: 1 author: - first_name: 'Gramoz ' full_name: 'Goranci, Gramoz ' last_name: Goranci - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Dariusz full_name: Leniowski, Dariusz last_name: Leniowski citation: ama: 'Goranci G, Henzinger MH, Leniowski D. A tree structure for dynamic facility location. In: 26th Annual European Symposium on Algorithms. Vol 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPICS.ESA.2018.39' apa: 'Goranci, G., Henzinger, M. H., & Leniowski, D. (2018). A tree structure for dynamic facility location. In 26th Annual European Symposium on Algorithms (Vol. 112). Helsinki, Finland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ESA.2018.39' chicago: Goranci, Gramoz , Monika H Henzinger, and Dariusz Leniowski. “A Tree Structure for Dynamic Facility Location.” In 26th Annual European Symposium on Algorithms, Vol. 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPICS.ESA.2018.39. ieee: G. Goranci, M. H. Henzinger, and D. Leniowski, “A tree structure for dynamic facility location,” in 26th Annual European Symposium on Algorithms, Helsinki, Finland, 2018, vol. 112. ista: 'Goranci G, Henzinger MH, Leniowski D. 2018. A tree structure for dynamic facility location. 26th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 112, 39.' mla: Goranci, Gramoz, et al. “A Tree Structure for Dynamic Facility Location.” 26th Annual European Symposium on Algorithms, vol. 112, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:10.4230/LIPICS.ESA.2018.39. short: G. Goranci, M.H. Henzinger, D. Leniowski, in:, 26th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. conference: end_date: 2018-08-22 location: Helsinki, Finland name: 'ESA: Annual European Symposium on Algorithms' start_date: 2018-08-20 date_created: 2022-08-12T08:20:57Z date_published: 2018-08-14T00:00:00Z date_updated: 2023-02-16T10:50:51Z day: '14' doi: 10.4230/LIPICS.ESA.2018.39 extern: '1' external_id: arxiv: - '1909.06653' intvolume: ' 112' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.4230/LIPIcs.ESA.2018.39 month: '08' oa: 1 oa_version: Published Version publication: 26th Annual European Symposium on Algorithms publication_identifier: isbn: - '9783959770811' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: A tree structure for dynamic facility location type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 112 year: '2018' ... --- _id: '11828' abstract: - lang: eng text: "We consider the problem of dynamically maintaining (approximate) all-pairs effective resistances in separable graphs, which are those that admit an n^{c}-separator theorem for some c<1. We give a fully dynamic algorithm that maintains (1+epsilon)-approximations of the all-pairs effective resistances of an n-vertex graph G undergoing edge insertions and deletions with O~(sqrt{n}/epsilon^2) worst-case update time and O~(sqrt{n}/epsilon^2) worst-case query time, if G is guaranteed to be sqrt{n}-separable (i.e., it is taken from a class satisfying a sqrt{n}-separator theorem) and its separator can be computed in O~(n) time. Our algorithm is built upon a dynamic algorithm for maintaining approximate Schur complement that approximately preserves pairwise effective resistances among a set of terminals for separable graphs, which might be of independent interest.\r\nWe complement our result by proving that for any two fixed vertices s and t, no incremental or decremental algorithm can maintain the s-t effective resistance for sqrt{n}-separable graphs with worst-case update time O(n^{1/2-delta}) and query time O(n^{1-delta}) for any delta>0, unless the Online Matrix Vector Multiplication (OMv) conjecture is false.\r\nWe further show that for general graphs, no incremental or decremental algorithm can maintain the s-t effective resistance problem with worst-case update time O(n^{1-delta}) and query-time O(n^{2-delta}) for any delta >0, unless the OMv conjecture is false." alternative_title: - LIPIcs article_number: '40' article_processing_charge: No arxiv: 1 author: - first_name: Gramoz full_name: Goranci, Gramoz last_name: Goranci - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Pan full_name: Peng, Pan last_name: Peng citation: ama: 'Goranci G, Henzinger MH, Peng P. Dynamic effective resistances and approximate schur complement on separable graphs. In: 26th Annual European Symposium on Algorithms. Vol 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPICS.ESA.2018.40' apa: 'Goranci, G., Henzinger, M. H., & Peng, P. (2018). Dynamic effective resistances and approximate schur complement on separable graphs. In 26th Annual European Symposium on Algorithms (Vol. 112). Helsinki, Finland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ESA.2018.40' chicago: Goranci, Gramoz, Monika H Henzinger, and Pan Peng. “Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs.” In 26th Annual European Symposium on Algorithms, Vol. 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPICS.ESA.2018.40. ieee: G. Goranci, M. H. Henzinger, and P. Peng, “Dynamic effective resistances and approximate schur complement on separable graphs,” in 26th Annual European Symposium on Algorithms, Helsinki, Finland, 2018, vol. 112. ista: 'Goranci G, Henzinger MH, Peng P. 2018. Dynamic effective resistances and approximate schur complement on separable graphs. 26th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 112, 40.' mla: Goranci, Gramoz, et al. “Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs.” 26th Annual European Symposium on Algorithms, vol. 112, 40, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:10.4230/LIPICS.ESA.2018.40. short: G. Goranci, M.H. Henzinger, P. Peng, in:, 26th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. conference: end_date: 2018-08-22 location: Helsinki, Finland name: 'ESA: Annual European Symposium on Algorithms' start_date: 2018-08-20 date_created: 2022-08-12T08:26:42Z date_published: 2018-08-14T00:00:00Z date_updated: 2023-02-16T11:08:08Z day: '14' doi: 10.4230/LIPICS.ESA.2018.40 extern: '1' external_id: arxiv: - '1802.09111' intvolume: ' 112' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.4230/LIPIcs.ESA.2018.40 month: '08' oa: 1 oa_version: Published Version publication: 26th Annual European Symposium on Algorithms publication_identifier: isbn: - '9783959770811' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Dynamic effective resistances and approximate schur complement on separable graphs type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 112 year: '2018' ... --- _id: '11911' abstract: - lang: eng text: It is common knowledge that there is no single best strategy for graph clustering, which justifies a plethora of existing approaches. In this paper, we present a general memetic algorithm, VieClus, to tackle the graph clustering problem. This algorithm can be adapted to optimize different objective functions. A key component of our contribution are natural recombine operators that employ ensemble clusterings as well as multi-level techniques. Lastly, we combine these techniques with a scalable communication protocol, producing a system that is able to compute high-quality solutions in a short amount of time. We instantiate our scheme with local search for modularity and show that our algorithm successfully improves or reproduces all entries of the 10th DIMACS implementation challenge under consideration using a small amount of time. alternative_title: - LIPIcs article_number: '3' article_processing_charge: No arxiv: 1 author: - first_name: Sonja full_name: Biedermann, Sonja last_name: Biedermann - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Christian full_name: Schulz, Christian last_name: Schulz - first_name: Bernhard full_name: Schuster, Bernhard last_name: Schuster citation: ama: 'Biedermann S, Henzinger MH, Schulz C, Schuster B. Memetic graph clustering. In: 17th International Symposium on Experimental Algorithms. Vol 103. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPICS.SEA.2018.3' apa: 'Biedermann, S., Henzinger, M. H., Schulz, C., & Schuster, B. (2018). Memetic graph clustering. In 17th International Symposium on Experimental Algorithms (Vol. 103). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.SEA.2018.3' chicago: Biedermann, Sonja, Monika H Henzinger, Christian Schulz, and Bernhard Schuster. “Memetic Graph Clustering.” In 17th International Symposium on Experimental Algorithms, Vol. 103. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPICS.SEA.2018.3. ieee: S. Biedermann, M. H. Henzinger, C. Schulz, and B. Schuster, “Memetic graph clustering,” in 17th International Symposium on Experimental Algorithms, L’Aquila, Italy, 2018, vol. 103. ista: 'Biedermann S, Henzinger MH, Schulz C, Schuster B. 2018. Memetic graph clustering. 17th International Symposium on Experimental Algorithms. SEA: Symposium on Experimental Algorithms, LIPIcs, vol. 103, 3.' mla: Biedermann, Sonja, et al. “Memetic Graph Clustering.” 17th International Symposium on Experimental Algorithms, vol. 103, 3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:10.4230/LIPICS.SEA.2018.3. short: S. Biedermann, M.H. Henzinger, C. Schulz, B. Schuster, in:, 17th International Symposium on Experimental Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. conference: end_date: 2018-07-29 location: L'Aquila, Italy name: 'SEA: Symposium on Experimental Algorithms' start_date: 2018-07-27 date_created: 2022-08-18T06:49:40Z date_published: 2018-07-01T00:00:00Z date_updated: 2023-02-16T11:45:14Z day: '01' doi: 10.4230/LIPICS.SEA.2018.3 extern: '1' external_id: arxiv: - '1802.07034' intvolume: ' 103' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.4230/LIPICS.SEA.2018.3 month: '07' oa: 1 oa_version: Published Version publication: 17th International Symposium on Experimental Algorithms publication_identifier: isbn: - '9783959770705' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Memetic graph clustering type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 103 year: '2018' ... --- _id: '950' abstract: - lang: eng text: "Two-player games on graphs are widely studied in formal methods as they model the interaction between a system and its environment. The game is played by moving a token throughout a graph to produce an infinite path. There are several common modes to determine how the players move the token through the graph; e.g., in turn-based games the players alternate turns in moving the token. We study the bidding mode of moving the token, which, to the best of our knowledge, has never been studied in infinite-duration games. Both players have separate budgets, which sum up to $1$. In each turn, a bidding takes place. Both players submit bids simultaneously, and a bid is legal if it does not exceed the available budget. The winner of the bidding pays his bid to the other player and moves the token. For reachability objectives, repeated bidding games have been studied and are called Richman games. There, a central question is the existence and computation of threshold budgets; namely, a value t\\in [0,1] such that if\\PO's budget exceeds $t$, he can win the game, and if\\PT's budget exceeds 1-t, he can win the game. We focus on parity games and mean-payoff games. We show the existence of threshold budgets in these games, and reduce the problem of finding them to Richman games. We also determine the strategy-complexity of an optimal strategy. Our most interesting result shows that memoryless strategies suffice for mean-payoff bidding games. \r\n" alternative_title: - LIPIcs article_number: '17' arxiv: 1 author: - first_name: Guy full_name: Avni, Guy id: 463C8BC2-F248-11E8-B48F-1D18A9856A87 last_name: Avni orcid: 0000-0001-5588-8287 - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 - first_name: Ventsislav K full_name: Chonev, Ventsislav K id: 36CBE2E6-F248-11E8-B48F-1D18A9856A87 last_name: Chonev citation: ama: 'Avni G, Henzinger TA, Chonev VK. Infinite-duration bidding games. In: Vol 85. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.CONCUR.2017.21' apa: 'Avni, G., Henzinger, T. A., & Chonev, V. K. (2017). Infinite-duration bidding games (Vol. 85). Presented at the CONCUR: Concurrency Theory, Berlin, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2017.21' chicago: Avni, Guy, Thomas A Henzinger, and Ventsislav K Chonev. “Infinite-Duration Bidding Games,” Vol. 85. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.CONCUR.2017.21. ieee: 'G. Avni, T. A. Henzinger, and V. K. Chonev, “Infinite-duration bidding games,” presented at the CONCUR: Concurrency Theory, Berlin, Germany, 2017, vol. 85.' ista: 'Avni G, Henzinger TA, Chonev VK. 2017. Infinite-duration bidding games. CONCUR: Concurrency Theory, LIPIcs, vol. 85, 17.' mla: Avni, Guy, et al. Infinite-Duration Bidding Games. Vol. 85, 17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.CONCUR.2017.21. short: G. Avni, T.A. Henzinger, V.K. Chonev, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. conference: end_date: 2017-09-07 location: Berlin, Germany name: 'CONCUR: Concurrency Theory' start_date: 2017-09-05 date_created: 2018-12-11T11:49:22Z date_published: 2017-09-01T00:00:00Z date_updated: 2023-08-29T07:02:13Z day: '01' ddc: - '000' department: - _id: ToHe - _id: KrCh doi: 10.4230/LIPIcs.CONCUR.2017.21 external_id: arxiv: - '1705.01433' file: - access_level: open_access checksum: 6d5cccf755207b91ccbef95d8275b013 content_type: application/pdf creator: system date_created: 2018-12-12T10:18:00Z date_updated: 2020-07-14T12:48:16Z file_id: '5318' file_name: IST-2017-844-v1+1_concur-cr.pdf file_size: 335170 relation: main_file file_date_updated: 2020-07-14T12:48:16Z has_accepted_license: '1' intvolume: ' 85' language: - iso: eng month: '09' oa: 1 oa_version: Published Version project: - _id: 25832EC2-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S 11407_N23 name: Rigorous Systems Engineering - _id: 25F42A32-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z211 name: The Wittgenstein Prize publication_identifier: issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik publist_id: '6466' pubrep_id: '844' quality_controlled: '1' related_material: record: - id: '6752' relation: later_version status: public scopus_import: 1 status: public title: Infinite-duration bidding games tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 85 year: '2017' ... --- _id: '11829' abstract: - lang: eng text: "In recent years it has become popular to study dynamic problems in a sensitivity setting: Instead of allowing for an arbitrary sequence of updates, the sensitivity model only allows to apply batch updates of small size to the original input data. The sensitivity model is particularly appealing since recent strong conditional lower bounds ruled out fast algorithms for many dynamic problems, such as shortest paths, reachability, or subgraph connectivity.\r\n\r\nIn this paper we prove conditional lower bounds for these and additional problems in a sensitivity setting. For example, we show that under the Boolean Matrix Multiplication (BMM) conjecture combinatorial algorithms cannot compute the (4/3-\\varepsilon)-approximate diameter of an undirected unweighted dense graph with truly subcubic preprocessing time and truly subquadratic update/query time. This result is surprising since in the static setting it is not clear whether a reduction from BMM to diameter is possible. We further show under the BMM conjecture that many problems, such as reachability or approximate shortest paths, cannot be solved faster than by recomputation from scratch even after only one or two edge insertions. We extend our reduction from BMM to Diameter to give a reduction from All Pairs Shortest Paths to Diameter under one deletion in weighted graphs. This is intriguing, as in the static setting it is a big open problem whether Diameter is as hard as APSP. We further get a nearly tight lower bound for shortest paths after two edge deletions based on the APSP conjecture. We give more lower bounds under the Strong Exponential Time Hypothesis. Many of our lower bounds also hold for static oracle data structures where no sensitivity is required.\r\n\r\nFinally, we give the first algorithm for the (1+\\varepsilon)-approximate radius, diameter, and eccentricity problems in directed or undirected unweighted graphs in case of single edges failures. The algorithm has a truly subcubic running time for graphs with a truly subquadratic number of edges; it is tight w.r.t. the conditional lower bounds we obtain." alternative_title: - LIPIcs article_number: '26' article_processing_charge: No arxiv: 1 author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Andrea full_name: Lincoln, Andrea last_name: Lincoln - first_name: Stefan full_name: Neumann, Stefan last_name: Neumann - first_name: Virginia full_name: Vassilevska Williams, Virginia last_name: Vassilevska Williams citation: 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' 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. 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. 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. conference: end_date: 2017-01-11 location: Berkley, CA, United States name: 'ITCS: Innovations in Theoretical Computer Science Conference' start_date: 2017-01-09 date_created: 2022-08-12T08:55:33Z date_published: 2017-11-28T00:00:00Z date_updated: 2023-02-16T11:49:15Z day: '28' doi: 10.4230/LIPICS.ITCS.2017.26 extern: '1' external_id: arxiv: - '1703.01638' intvolume: ' 67' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.4230/LIPICS.ITCS.2017.26 month: '11' oa: 1 oa_version: Published Version publication: 8th Innovations in Theoretical Computer Science Conference publication_identifier: isbn: - '9783959770293' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Conditional hardness for sensitivity problems type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 67 year: '2017' ... --- _id: '11831' 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." alternative_title: - LIPIcs article_number: '44' article_processing_charge: No arxiv: 1 author: - first_name: Gramoz full_name: Goranci, Gramoz last_name: Goranci - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Pan full_name: Peng, Pan last_name: Peng citation: 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' 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. 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. short: G. Goranci, M.H. Henzinger, P. Peng, in:, 25th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. conference: end_date: 2017-09-06 location: Vienna, Austria name: 'ESA: Annual European Symposium on Algorithms' start_date: 2017-09-04 date_created: 2022-08-12T09:27:11Z date_published: 2017-09-01T00:00:00Z date_updated: 2023-02-21T16:32:16Z day: '01' doi: 10.4230/LIPICS.ESA.2017.44 extern: '1' external_id: arxiv: - '1702.01136' intvolume: ' 87' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.4230/LIPIcs.ESA.2017.44 month: '09' oa: 1 oa_version: Published Version publication: 25th Annual European Symposium on Algorithms publication_identifier: isbn: - 978-3-95977-049-1 issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' related_material: record: - id: '11894' relation: later_version status: public scopus_import: '1' status: public title: Improved guarantees for vertex sparsification in planar graphs type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 87 year: '2017' ... --- _id: '11832' 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." alternative_title: - LIPIcs article_number: '48' article_processing_charge: No arxiv: 1 author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Dariusz full_name: Leniowski, Dariusz last_name: Leniowski - first_name: Claire full_name: Mathieu, Claire last_name: Mathieu citation: 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' 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' 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. 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. 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. short: M.H. Henzinger, D. Leniowski, C. Mathieu, in:, 25th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. conference: end_date: 2017-09-06 location: Vienna, Austria name: 'ESA: Annual European Symposium on Algorithms' start_date: 2017-09-04 date_created: 2022-08-12T09:58:46Z date_published: 2017-09-01T00:00:00Z date_updated: 2023-02-16T11:54:12Z day: '01' doi: 10.4230/LIPICS.ESA.2017.48 extern: '1' external_id: arxiv: - '1707.02577' intvolume: ' 87' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.4230/LIPICS.ESA.2017.48 month: '09' oa: 1 oa_version: Published Version publication: 25th Annual European Symposium on Algorithms publication_identifier: isbn: - 978-3-95977-049-1 issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Dynamic clustering to minimize the sum of radii type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 87 year: '2017' ... --- _id: '11833' 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." alternative_title: - LIPIcs article_number: '45' article_processing_charge: No arxiv: 1 author: - first_name: Gramoz full_name: Goranci, Gramoz last_name: Goranci - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Pan full_name: Peng, Pan last_name: Peng citation: 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' 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. 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.' 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. short: G. Goranci, M.H. Henzinger, P. Peng, in:, 25th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. conference: end_date: 2017-09-06 location: Vienna, Austria name: 'ESA: Annual European Symposium on Algorithms' start_date: 2017-09-04 date_created: 2022-08-12T10:46:26Z date_published: 2017-09-01T00:00:00Z date_updated: 2023-02-16T11:56:37Z day: '01' doi: 10.4230/LIPICS.ESA.2017.45 extern: '1' external_id: arxiv: - '1712.06473' intvolume: ' 87' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.4230/LIPIcs.ESA.2017.45 month: '09' oa: 1 oa_version: Published Version publication: 25th Annual European Symposium on Algorithms publication_identifier: isbn: - 978-3-95977-049-1 issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: The power of vertex sparsifiers in dynamic graph algorithms type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 87 year: '2017' ... --- _id: '11834' abstract: - lang: eng text: "We present a deterministic incremental algorithm for exactly maintaining the size of a minimum cut with ~O(1) amortized time per edge insertion and O(1) query time. This result partially answers an open question posed by Thorup [Combinatorica 2007]. It also stays in sharp contrast to a polynomial conditional lower-bound for the fully-dynamic weighted minimum cut problem. Our algorithm is obtained by combining a recent sparsification technique of Kawarabayashi and Thorup [STOC 2015] and an exact incremental algorithm of Henzinger [J. of Algorithm 1997].\r\n\r\nWe also study space-efficient incremental algorithms for the minimum cut problem. Concretely, we show that there exists an O(n log n/epsilon^2) space Monte-Carlo algorithm that can process a stream of edge insertions starting from an empty graph, and with high probability, the algorithm maintains a (1+epsilon)-approximation to the minimum cut. The algorithm has ~O(1) amortized update-time and constant query-time." alternative_title: - LIPIcs article_number: '46' article_processing_charge: No arxiv: 1 author: - first_name: Gramoz full_name: Goranci, Gramoz last_name: Goranci - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Mikkel full_name: Thorup, Mikkel last_name: Thorup citation: ama: 'Goranci G, Henzinger MH, Thorup M. Incremental exact min-cut in poly-logarithmic amortized update time. In: 24th Annual European Symposium on Algorithms. Vol 57. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:10.4230/LIPICS.ESA.2016.46' apa: 'Goranci, G., Henzinger, M. H., & Thorup, M. (2016). Incremental exact min-cut in poly-logarithmic amortized update time. In 24th Annual European Symposium on Algorithms (Vol. 57). Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ESA.2016.46' chicago: Goranci, Gramoz, Monika H Henzinger, and Mikkel Thorup. “Incremental Exact Min-Cut in Poly-Logarithmic Amortized Update Time.” In 24th Annual European Symposium on Algorithms, Vol. 57. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. https://doi.org/10.4230/LIPICS.ESA.2016.46. ieee: G. Goranci, M. H. Henzinger, and M. Thorup, “Incremental exact min-cut in poly-logarithmic amortized update time,” in 24th Annual European Symposium on Algorithms, Aarhus, Denmark, 2016, vol. 57. ista: 'Goranci G, Henzinger MH, Thorup M. 2016. Incremental exact min-cut in poly-logarithmic amortized update time. 24th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 57, 46.' mla: Goranci, Gramoz, et al. “Incremental Exact Min-Cut in Poly-Logarithmic Amortized Update Time.” 24th Annual European Symposium on Algorithms, vol. 57, 46, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, doi:10.4230/LIPICS.ESA.2016.46. short: G. Goranci, M.H. Henzinger, M. Thorup, in:, 24th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. conference: end_date: 2016-08-24 location: Aarhus, Denmark name: 'ESA: Annual European Symposium on Algorithms' start_date: 2016-08-22 date_created: 2022-08-12T10:58:32Z date_published: 2016-08-18T00:00:00Z date_updated: 2023-02-16T12:05:59Z day: '18' doi: 10.4230/LIPICS.ESA.2016.46 extern: '1' external_id: arxiv: - '1611.06500' intvolume: ' 57' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.4230/LIPIcs.ESA.2016.46 month: '08' oa: 1 oa_version: Published Version publication: 24th Annual European Symposium on Algorithms publication_identifier: isbn: - 978-3-95977-015-6 issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Incremental exact min-cut in poly-logarithmic amortized update time type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 57 year: '2016' ... --- _id: '11835' abstract: - lang: eng text: "During the last 10 years it has become popular to study dynamic graph problems in a emergency planning or sensitivity setting: Instead of considering the general fully dynamic problem, we only have to process a single batch update of size d; after the update we have to answer queries.\r\n\r\nIn this paper, we consider the dynamic subgraph connectivity problem with sensitivity d: We are given a graph of which some vertices are activated and some are deactivated. After that we get a single update in which the states of up to $d$ vertices are changed. Then we get a sequence of connectivity queries in the subgraph of activated vertices.\r\n\r\nWe present the first fully dynamic algorithm for this problem which has an update and query time only slightly worse than the best decremental algorithm. In addition, we present the first incremental algorithm which is tight with respect to the best known conditional lower bound; moreover, the algorithm is simple and we believe it is implementable and efficient in practice." alternative_title: - LIPIcs article_number: '48' article_processing_charge: No arxiv: 1 author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Stefan full_name: Neumann, Stefan last_name: Neumann citation: ama: 'Henzinger MH, Neumann S. Incremental and fully dynamic subgraph connectivity for emergency planning. In: 24th Annual European Symposium on Algorithms. Vol 57. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:10.4230/LIPICS.ESA.2016.48' apa: 'Henzinger, M. H., & Neumann, S. (2016). Incremental and fully dynamic subgraph connectivity for emergency planning. In 24th Annual European Symposium on Algorithms (Vol. 57). Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ESA.2016.48' chicago: Henzinger, Monika H, and Stefan Neumann. “Incremental and Fully Dynamic Subgraph Connectivity for Emergency Planning.” In 24th Annual European Symposium on Algorithms, Vol. 57. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. https://doi.org/10.4230/LIPICS.ESA.2016.48. ieee: M. H. Henzinger and S. Neumann, “Incremental and fully dynamic subgraph connectivity for emergency planning,” in 24th Annual European Symposium on Algorithms, Aarhus, Denmark, 2016, vol. 57. ista: 'Henzinger MH, Neumann S. 2016. Incremental and fully dynamic subgraph connectivity for emergency planning. 24th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 57, 48.' mla: Henzinger, Monika H., and Stefan Neumann. “Incremental and Fully Dynamic Subgraph Connectivity for Emergency Planning.” 24th Annual European Symposium on Algorithms, vol. 57, 48, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, doi:10.4230/LIPICS.ESA.2016.48. short: M.H. Henzinger, S. Neumann, in:, 24th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. conference: end_date: 2016-08-24 location: Aarhus, Denmark name: 'ESA: Annual European Symposium on Algorithms' start_date: 2016-08-22 date_created: 2022-08-12T11:05:41Z date_published: 2016-08-18T00:00:00Z date_updated: 2023-02-16T12:07:46Z day: '18' doi: 10.4230/LIPICS.ESA.2016.48 extern: '1' external_id: arxiv: - '1611.05248' intvolume: ' 57' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.4230/LIPIcs.ESA.2016.48 month: '08' oa: 1 oa_version: Published Version publication: 24th Annual European Symposium on Algorithms publication_identifier: isbn: - 978-3-95977-015-6 issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Incremental and fully dynamic subgraph connectivity for emergency planning type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 57 year: '2016' ... --- _id: '11836' abstract: - lang: eng text: "Given a graph where vertices are partitioned into k terminals and non-terminals, the goal is to compress the graph (i.e., reduce the number of non-terminals) using minor operations while preserving terminal distances approximately. The distortion of a compressed graph is the maximum multiplicative blow-up of distances between all pairs of terminals. We study the trade-off between the number of non-terminals and the distortion. This problem generalizes the Steiner Point Removal (SPR) problem, in which all non-terminals must be removed.\r\n\r\nWe introduce a novel black-box reduction to convert any lower bound on distortion for the SPR problem into a super-linear lower bound on the number of non-terminals, with the same distortion, for our problem. This allows us to show that there exist graphs such that every minor with distortion less than 2 / 2.5 / 3 must have Omega(k^2) / Omega(k^{5/4}) / Omega(k^{6/5}) non-terminals, plus more trade-offs in between. The black-box reduction has an interesting consequence: if the tight lower bound on distortion for the SPR problem is super-constant, then allowing any O(k) non-terminals will not help improving the lower bound to a constant.\r\n\r\nWe also build on the existing results on spanners, distance oracles and connected 0-extensions to show a number of upper bounds for general graphs, planar graphs, graphs that exclude a fixed minor and bounded treewidth graphs. Among others, we show that any graph admits a minor with O(log k) distortion and O(k^2) non-terminals, and any planar graph admits a minor with\r\n1 + epsilon distortion and ~O((k/epsilon)^2) non-terminals." alternative_title: - LIPIcs article_number: '131' article_processing_charge: No arxiv: 1 author: - first_name: Yun Kuen full_name: Cheung, Yun Kuen last_name: Cheung - first_name: Gramoz full_name: Goranci, Gramoz last_name: Goranci - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 citation: ama: 'Cheung YK, Goranci G, Henzinger MH. Graph minors for preserving terminal distances approximately - lower and upper bounds. In: 43rd International Colloquium on Automata, Languages, and Programming. Vol 55. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:10.4230/LIPICS.ICALP.2016.131' apa: 'Cheung, Y. K., Goranci, G., & Henzinger, M. H. (2016). Graph minors for preserving terminal distances approximately - lower and upper bounds. In 43rd International Colloquium on Automata, Languages, and Programming (Vol. 55). Rome, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ICALP.2016.131' chicago: Cheung, Yun Kuen, Gramoz Goranci, and Monika H Henzinger. “Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds.” In 43rd International Colloquium on Automata, Languages, and Programming, Vol. 55. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. https://doi.org/10.4230/LIPICS.ICALP.2016.131. ieee: Y. K. Cheung, G. Goranci, and M. H. Henzinger, “Graph minors for preserving terminal distances approximately - lower and upper bounds,” in 43rd International Colloquium on Automata, Languages, and Programming, Rome, Italy, 2016, vol. 55. ista: 'Cheung YK, Goranci G, Henzinger MH. 2016. Graph minors for preserving terminal distances approximately - lower and upper bounds. 43rd International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 55, 131.' mla: Cheung, Yun Kuen, et al. “Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds.” 43rd International Colloquium on Automata, Languages, and Programming, vol. 55, 131, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, doi:10.4230/LIPICS.ICALP.2016.131. short: Y.K. Cheung, G. Goranci, M.H. Henzinger, in:, 43rd International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. conference: end_date: 2016-07-15 location: Rome, Italy name: 'ICALP: International Colloquium on Automata, Languages, and Programming' start_date: 2016-07-12 date_created: 2022-08-12T11:16:01Z date_published: 2016-08-23T00:00:00Z date_updated: 2023-02-16T12:09:54Z day: '23' doi: 10.4230/LIPICS.ICALP.2016.131 extern: '1' external_id: arxiv: - '1604.08342' intvolume: ' 55' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.4230/LIPICS.ICALP.2016.131 month: '08' oa: 1 oa_version: Published Version publication: 43rd International Colloquium on Automata, Languages, and Programming publication_identifier: isbn: - 978-3-95977-013-2 issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Graph minors for preserving terminal distances approximately - lower and upper bounds type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 55 year: '2016' ... --- _id: '11837' abstract: - lang: eng 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 O(sqrt n)-approximation algorithm for general concave externality functions,\r\n(ii) an O(\\log m)-approximation algorithm for linear externality functions, and (iii) an (1-1/e)\\frac{1}{6}-approximation algorithm for 2-hop step function externalities. We also improve the result from [6] for 1-hop step function externalities by giving a (1-1/e)/2-approximation algorithm." alternative_title: - LIPIcs article_processing_charge: No author: - first_name: Sayan full_name: Bhattacharya, Sayan last_name: Bhattacharya - first_name: Wolfgang full_name: Dvorák, Wolfgang last_name: Dvorák - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: ' Martin' full_name: Starnberger, Martin last_name: Starnberger citation: ama: 'Bhattacharya S, Dvorák W, Henzinger MH, Starnberger Martin. Welfare maximization with friends-of-friends network externalities. In: 32nd International Symposium on Theoretical Aspects of Computer Science. Vol 30. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2015:90-102. doi:10.4230/LIPICS.STACS.2015.90' apa: 'Bhattacharya, S., Dvorák, W., Henzinger, M. H., & Starnberger, Martin. (2015). Welfare maximization with friends-of-friends network externalities. In 32nd International Symposium on Theoretical Aspects of Computer Science (Vol. 30, pp. 90–102). Garching, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.STACS.2015.90' chicago: Bhattacharya, Sayan, Wolfgang Dvorák, Monika H Henzinger, and Martin Starnberger. “Welfare Maximization with Friends-of-Friends Network Externalities.” In 32nd International Symposium on Theoretical Aspects of Computer Science, 30:90–102. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. https://doi.org/10.4230/LIPICS.STACS.2015.90. ieee: S. Bhattacharya, W. Dvorák, M. H. Henzinger, and Martin Starnberger, “Welfare maximization with friends-of-friends network externalities,” in 32nd International Symposium on Theoretical Aspects of Computer Science, Garching, Germany, 2015, vol. 30, pp. 90–102. ista: 'Bhattacharya S, Dvorák W, Henzinger MH, Starnberger Martin. 2015. Welfare maximization with friends-of-friends network externalities. 32nd International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 30, 90–102.' mla: Bhattacharya, Sayan, et al. “Welfare Maximization with Friends-of-Friends Network Externalities.” 32nd International Symposium on Theoretical Aspects of Computer Science, vol. 30, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 90–102, doi:10.4230/LIPICS.STACS.2015.90. short: S. Bhattacharya, W. Dvorák, M.H. Henzinger, Martin Starnberger, in:, 32nd International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 90–102. conference: end_date: 2015-03-07 location: Garching, Germany name: 'STACS: Symposium on Theoretical Aspects of Computer Science' start_date: 2015-03-04 date_created: 2022-08-12T11:39:40Z date_published: 2015-02-26T00:00:00Z date_updated: 2023-02-21T16:32:37Z day: '26' doi: 10.4230/LIPICS.STACS.2015.90 extern: '1' intvolume: ' 30' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.4230/LIPICS.STACS.2015.90 month: '02' oa: 1 oa_version: Published Version page: 90-102 publication: 32nd International Symposium on Theoretical Aspects of Computer Science publication_identifier: isbn: - 978-3-939897-78-1 issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' related_material: record: - id: '11903' relation: later_version status: public scopus_import: '1' status: public title: Welfare maximization with friends-of-friends network externalities type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 30 year: '2015' ...