3 Search Results for "Knudsen, Jakob Bæk Tejs"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.76
A Sparse Johnson-Lindenstrauss Transform Using Fast Hashing

Authors: Jakob Bæk Tejs Houen and Mikkel Thorup

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
The Sparse Johnson-Lindenstrauss Transform of Kane and Nelson (SODA 2012) provides a linear dimensionality-reducing map A ∈ ℝ^{m × u} in 𝓁₂ that preserves distances up to distortion of 1 + ε with probability 1 - δ, where m = O(ε^{-2} log 1/δ) and each column of A has O(ε m) non-zero entries. The previous analyses of the Sparse Johnson-Lindenstrauss Transform all assumed access to a Ω(log 1/δ)-wise independent hash function. The main contribution of this paper is a more general analysis of the Sparse Johnson-Lindenstrauss Transform with less assumptions on the hash function. We also show that the Mixed Tabulation hash function of Dahlgaard, Knudsen, Rotenberg, and Thorup (FOCS 2015) satisfies the conditions of our analysis, thus giving us the first analysis of a Sparse Johnson-Lindenstrauss Transform that works with a practical hash function.
Cite as

Jakob Bæk Tejs Houen and Mikkel Thorup. A Sparse Johnson-Lindenstrauss Transform Using Fast Hashing. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 76:1-76:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{houen_et_al:LIPIcs.ICALP.2023.76,
  author =	{Houen, Jakob B{\ae}k Tejs and Thorup, Mikkel},
  title =	{{A Sparse Johnson-Lindenstrauss Transform Using Fast Hashing}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{76:1--76:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.76},
  URN =		{urn:nbn:de:0030-drops-181281},
  doi =		{10.4230/LIPIcs.ICALP.2023.76},
  annote =	{Keywords: dimensionality reduction, hashing, concentration bounds, moment bounds}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.3
Classifying Convex Bodies by Their Contact and Intersection Graphs

Authors: Anders Aamand, Mikkel Abrahamsen, Jakob Bæk Tejs Knudsen, and Peter Michael Reichstein Rasmussen

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
Let A be a convex body in the plane and A₁,…,A_n be translates of A. Such translates give rise to an intersection graph of A, G = (V,E), with vertices V = {1,… ,n} and edges E = {uv∣ A_u ∩ A_v ≠ ∅}. The subgraph G' = (V, E') satisfying that E' ⊂ E is the set of edges uv for which the interiors of A_u and A_v are disjoint is a unit distance graph of A. If furthermore G' = G, i.e., if the interiors of A_u and A_v are disjoint whenever u≠ v, then G is a contact graph of A. In this paper, we study which pairs of convex bodies have the same contact, unit distance, or intersection graphs. We say that two convex bodies A and B are equivalent if there exists a linear transformation B' of B such that for any slope, the longest line segments with that slope contained in A and B', respectively, are equally long. For a broad class of convex bodies, including all strictly convex bodies and linear transformations of regular polygons, we show that the contact graphs of A and B are the same if and only if A and B are equivalent. We prove the same statement for unit distance and intersection graphs.
Cite as

Anders Aamand, Mikkel Abrahamsen, Jakob Bæk Tejs Knudsen, and Peter Michael Reichstein Rasmussen. Classifying Convex Bodies by Their Contact and Intersection Graphs. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{aamand_et_al:LIPIcs.SoCG.2021.3,
  author =	{Aamand, Anders and Abrahamsen, Mikkel and Knudsen, Jakob B{\ae}k Tejs and Rasmussen, Peter Michael Reichstein},
  title =	{{Classifying Convex Bodies by Their Contact and Intersection Graphs}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.3},
  URN =		{urn:nbn:de:0030-drops-138024},
  doi =		{10.4230/LIPIcs.SoCG.2021.3},
  annote =	{Keywords: convex body, contact graph, intersection graph}
}
Document
DOI: 10.4230/LIPIcs.ITC.2020.6
Expander Graphs Are Non-Malleable Codes

Authors: Peter Michael Reichstein Rasmussen and Amit Sahai

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
Any d-regular graph on n vertices with spectral expansion λ satisfying n = Ω(d³log(d)/λ) yields a O((λ^{3/2})/d)-non-malleable code for single-bit messages in the split-state model.
Cite as

Peter Michael Reichstein Rasmussen and Amit Sahai. Expander Graphs Are Non-Malleable Codes. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 6:1-6:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{rasmussen_et_al:LIPIcs.ITC.2020.6,
  author =	{Rasmussen, Peter Michael Reichstein and Sahai, Amit},
  title =	{{Expander Graphs Are Non-Malleable Codes}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{6:1--6:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.6},
  URN =		{urn:nbn:de:0030-drops-121114},
  doi =		{10.4230/LIPIcs.ITC.2020.6},
  annote =	{Keywords: Non-Malleable Code, Expander Graph, Mixing Lemma}
}
  • Refine by Author
  • 2 Rasmussen, Peter Michael Reichstein
  • 1 Aamand, Anders
  • 1 Abrahamsen, Mikkel
  • 1 Houen, Jakob Bæk Tejs
  • 1 Knudsen, Jakob Bæk Tejs
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Mathematics of computing → Graph theory
  • 1 Mathematics of computing → Spectra of graphs
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Cryptographic primitives
  • Show More...

  • Refine by Keyword
  • 1 Expander Graph
  • 1 Mixing Lemma
  • 1 Non-Malleable Code
  • 1 concentration bounds
  • 1 contact graph
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2020
  • 1 2021
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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