5 Search Results for "Blömer, Johannes"

Document
DOI: 10.4230/LIPIcs.WADS.2025.45
Fast Kd-Trees for the Kullback-Leibler Divergence and Other Decomposable Bregman Divergences

Authors: Tuyen Pham and Hubert Wagner

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
The contributions of the paper span theoretical and implementational results. First, we prove that Kd-trees can be extended to ℝ^d with the distance measured by an arbitrary Bregman divergence. Perhaps surprisingly, this shows that the triangle inequality is not necessary for correct pruning in Kd-trees. Second, we offer an efficient algorithm and C++ implementation for nearest neighbour search for decomposable Bregman divergences. The implementation supports the Kullback-Leibler divergence (relative entropy) which is a popular distance between probability vectors and is commonly used in statistics and machine learning. This is a step toward broadening the usage of computational geometry algorithms. Our benchmarks show that our implementation efficiently handles both exact and approximate nearest neighbour queries. Compared to a linear search, we achieve two orders of magnitude speedup for practical scenarios in dimension up to 100. Our solution is simpler and more efficient than competing methods.
Cite as

Tuyen Pham and Hubert Wagner. Fast Kd-Trees for the Kullback-Leibler Divergence and Other Decomposable Bregman Divergences. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pham_et_al:LIPIcs.WADS.2025.45,
  author =	{Pham, Tuyen and Wagner, Hubert},
  title =	{{Fast Kd-Trees for the Kullback-Leibler Divergence and Other Decomposable Bregman Divergences}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{45:1--45:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.45},
  URN =		{urn:nbn:de:0030-drops-242766},
  doi =		{10.4230/LIPIcs.WADS.2025.45},
  annote =	{Keywords: Kd-tree, k-d tree, nearest neighbour search, Bregman divergence, decomposable Bregman divergence, KL divergence, relative entropy, cross entropy, Shannon’s entropy}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.48
Exact Algorithms for Minimum Dilation Triangulation

Authors: Sándor P. Fekete, Phillip Keldenich, and Michael Perk

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We provide a spectrum of new theoretical insights and practical results for finding a Minimum Dilation Triangulation (MDT), a natural geometric optimization problem of considerable previous attention: Given a set P of n points in the plane, find a triangulation T, such that a shortest Euclidean path in T between any pair of points increases by the smallest possible factor compared to their straight-line distance. No polynomial-time algorithm is known for the problem; moreover, evaluating the objective function involves computing the sum of (possibly many) square roots. On the other hand, the problem is not known to be NP-hard. (1) We provide practically robust methods and implementations for computing an MDT for benchmark sets with up to 30,000 points in reasonable time on commodity hardware, based on new geometric insights into the structure of optimal edge sets. Previous methods only achieved results for up to 200 points, so we extend the range of optimally solvable instances by a factor of 150. (2) We develop scalable techniques for accurately evaluating many shortest-path queries that arise as large-scale sums of square roots, allowing us to certify exact optimal solutions, with previous work relying on (possibly inaccurate) floating-point computations. (3) We resolve an open problem by establishing a lower bound of 1.44116 on the dilation of the regular 84-gon (and thus for arbitrary point sets), improving the previous worst-case lower bound of 1.4308 and greatly reducing the remaining gap to the upper bound of 1.4482 from the literature. In the process, we provide optimal solutions for regular n-gons up to n = 100.
Cite as

Sándor P. Fekete, Phillip Keldenich, and Michael Perk. Exact Algorithms for Minimum Dilation Triangulation. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 48:1-48:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SoCG.2025.48,
  author =	{Fekete, S\'{a}ndor P. and Keldenich, Phillip and Perk, Michael},
  title =	{{Exact Algorithms for Minimum Dilation Triangulation}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{48:1--48:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.48},
  URN =		{urn:nbn:de:0030-drops-232006},
  doi =		{10.4230/LIPIcs.SoCG.2025.48},
  annote =	{Keywords: dilation, minimum dilation triangulation, exact algorithms, algorithm engineering, experimental evaluation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.46
Coresets for Fuzzy K-Means with Applications

Authors: Johannes Blömer, Sascha Brauer, and Kathrin Bujna

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
The fuzzy K-means problem is a popular generalization of the well-known K-means problem to soft clusterings. We present the first coresets for fuzzy K-means with size linear in the dimension, polynomial in the number of clusters, and poly-logarithmic in the number of points. We show that these coresets can be employed in the computation of a (1+epsilon)-approximation for fuzzy K-means, improving previously presented results. We further show that our coresets can be maintained in an insertion-only streaming setting, where data points arrive one-by-one.
Cite as

Johannes Blömer, Sascha Brauer, and Kathrin Bujna. Coresets for Fuzzy K-Means with Applications. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 46:1-46:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{blomer_et_al:LIPIcs.ISAAC.2018.46,
  author =	{Bl\"{o}mer, Johannes and Brauer, Sascha and Bujna, Kathrin},
  title =	{{Coresets for Fuzzy K-Means with Applications}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{46:1--46:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.46},
  URN =		{urn:nbn:de:0030-drops-99942},
  doi =		{10.4230/LIPIcs.ISAAC.2018.46},
  annote =	{Keywords: clustering, fuzzy k-means, coresets, approximation algorithms, streaming}
}
Document
DOI: 10.4230/DagSemProc.07381.1
07381 Abstracts Collection – Cryptography

Authors: Johannes Blömer, Dan Boneh, Ronald Cramer, and Ueli Maurer

Published in: Dagstuhl Seminar Proceedings, Volume 7381, Cryptography (2008)

Abstract
From 16.09.2007 to 21.09.2007 the Dagstuhl Seminar 07381 ``Cryptography'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Johannes Blömer, Dan Boneh, Ronald Cramer, and Ueli Maurer. 07381 Abstracts Collection – Cryptography. In Cryptography. Dagstuhl Seminar Proceedings, Volume 7381, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{blomer_et_al:DagSemProc.07381.1,
  author =	{Bl\"{o}mer, Johannes and Boneh, Dan and Cramer, Ronald and Maurer, Ueli},
  title =	{{07381 Abstracts Collection – Cryptography}},
  booktitle =	{Cryptography},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7381},
  editor =	{Johannes Bl\"{o}mer and Dan Boneh and Ronald Cramer and Ueli Maurer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07381.1},
  URN =		{urn:nbn:de:0030-drops-12935},
  doi =		{10.4230/DagSemProc.07381.1},
  annote =	{Keywords: Cryptography, information security, public-key cryptography, cryptographic protocols, security proofs}
}
Document
DOI: 10.4230/DagSemProc.07381.2
07381 Executive Summary - Cryptography

Authors: Johannes Blömer, Dan Boneh, Ronald Cramer, and Ueli Maurer

Published in: Dagstuhl Seminar Proceedings, Volume 7381, Cryptography (2008)

Abstract
The topics covered in the seminar spanned most areas of cryptography, in one way or another, both in terms of the types of schemes (public-key cryptography, symmetric cryptography, hash functions and other cryptographic functions, multi-party protocols, etc.) and in terms of the mathematical methods and techniques used (algebra, number theory, elliptic curves, probability theory, information theory, combinatorics, quantum theory, etc.). The range of applications addressed in the various talks was broad, ranging from secure communication, key management, authentication, digital signatures and payment systems to e-voting and Internet security. While the initial plan had been to focus more exclusively on public-key cryptography, it turned out that this sub-topic branches out into many other areas of cryptography and therefore the organizers decided to expand the scope, emphasizing quality rather than close adherence to public-key cryptography. This decision turned out to be a wise one. What was common to almost all the talks is that rigorous mathematical proofs for the security of the presented schemes were given. In fact, a central topic of many of the talks were proof methodologies for various contexts.
Cite as

Johannes Blömer, Dan Boneh, Ronald Cramer, and Ueli Maurer. 07381 Executive Summary - Cryptography. In Cryptography. Dagstuhl Seminar Proceedings, Volume 7381, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{blomer_et_al:DagSemProc.07381.2,
  author =	{Bl\"{o}mer, Johannes and Boneh, Dan and Cramer, Ronald and Maurer, Ueli},
  title =	{{07381 Executive Summary - Cryptography}},
  booktitle =	{Cryptography},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7381},
  editor =	{Johannes Bl\"{o}mer and Dan Boneh and Ronald Cramer and Ueli Maurer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07381.2},
  URN =		{urn:nbn:de:0030-drops-12928},
  doi =		{10.4230/DagSemProc.07381.2},
  annote =	{Keywords: Cryptography, information security, public-key cryptography, cryptographic protocols, security proofs}
}
  • Refine by Type
  • 5 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2018
  • 2 2008

  • Refine by Author
  • 3 Blömer, Johannes
  • 2 Boneh, Dan
  • 2 Cramer, Ronald
  • 2 Maurer, Ueli
  • 1 Brauer, Sascha
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs
  • 2 DagSemProc

  • Refine by Classification
  • 2 Theory of computation → Computational geometry
  • 1 General and reference → Experimentation
  • 1 Information systems → Data structures
  • 1 Mathematics of computing → Arbitrary-precision arithmetic
  • 1 Mathematics of computing → Combinatorial algorithms
  • Show More...

  • Refine by Keyword
  • 2 Cryptography
  • 2 cryptographic protocols
  • 2 information security
  • 2 public-key cryptography
  • 2 security proofs
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact