3 Search Results for "Sinnamon, Corwin"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.79
Analysis of Smooth Heaps and Slim Heaps

Authors: Maria Hartmann, László Kozma, Corwin Sinnamon, and Robert E. Tarjan

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
The smooth heap is a recently introduced self-adjusting heap [Kozma, Saranurak, 2018] similar to the pairing heap [Fredman, Sedgewick, Sleator, Tarjan, 1986]. The smooth heap was obtained as a heap-counterpart of Greedy BST, a binary search tree updating strategy conjectured to be instance-optimal [Lucas, 1988], [Munro, 2000]. Several adaptive properties of smooth heaps follow from this connection; moreover, the smooth heap itself has been conjectured to be instance-optimal within a certain class of heaps. Nevertheless, no general analysis of smooth heaps has existed until now, the only previous analysis showing that, when used in sorting mode (n insertions followed by n delete-min operations), smooth heaps sort n numbers in O(nlg n) time. In this paper we describe a simpler variant of the smooth heap we call the slim heap. We give a new, self-contained analysis of smooth heaps and slim heaps in unrestricted operation, obtaining amortized bounds that match the best bounds known for self-adjusting heaps. Previous experimental work has found the pairing heap to dominate other data structures in this class in various settings. Our tests show that smooth heaps and slim heaps are competitive with pairing heaps, outperforming them in some cases, while being comparably easy to implement.
Cite as

Maria Hartmann, László Kozma, Corwin Sinnamon, and Robert E. Tarjan. Analysis of Smooth Heaps and Slim Heaps. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 79:1-79:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{hartmann_et_al:LIPIcs.ICALP.2021.79,
  author =	{Hartmann, Maria and Kozma, L\'{a}szl\'{o} and Sinnamon, Corwin and Tarjan, Robert E.},
  title =	{{Analysis of Smooth Heaps and Slim Heaps}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{79:1--79:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.79},
  URN =		{urn:nbn:de:0030-drops-141482},
  doi =		{10.4230/LIPIcs.ICALP.2021.79},
  annote =	{Keywords: data structure, heap, priority queue, amortized analysis, self-adjusting}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2020.31
Space-Efficient Data Structures for Lattices

Authors: J. Ian Munro, Bryce Sandlund, and Corwin Sinnamon

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
A lattice is a partially-ordered set in which every pair of elements has a unique meet (greatest lower bound) and join (least upper bound). We present new data structures for lattices that are simple, efficient, and nearly optimal in terms of space complexity. Our first data structure can answer partial order queries in constant time and find the meet or join of two elements in O(n^{3/4}) time, where n is the number of elements in the lattice. It occupies O(n^{3/2}log n) bits of space, which is only a Θ(log n) factor from the Θ(n^{3/2})-bit lower bound for storing lattices. The preprocessing time is O(n²). This structure admits a simple space-time tradeoff so that, for any c ∈ [1/2, 1], the data structure supports meet and join queries in O(n^{1-c/2}) time, occupies O(n^{1+c}log n) bits of space, and can be constructed in O(n² + n^{1+3c/2}) time. Our second data structure uses O(n^{3/2}log n) bits of space and supports meet and join in O(d (log n)/(log d)) time, where d is the maximum degree of any element in the transitive reduction graph of the lattice. This structure is much faster for lattices with low-degree elements. This paper also identifies an error in a long-standing solution to the problem of representing lattices. We discuss the issue with this previous work.
Cite as

J. Ian Munro, Bryce Sandlund, and Corwin Sinnamon. Space-Efficient Data Structures for Lattices. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 31:1-31:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{munro_et_al:LIPIcs.SWAT.2020.31,
  author =	{Munro, J. Ian and Sandlund, Bryce and Sinnamon, Corwin},
  title =	{{Space-Efficient Data Structures for Lattices}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{31:1--31:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.31},
  URN =		{urn:nbn:de:0030-drops-122782},
  doi =		{10.4230/LIPIcs.SWAT.2020.31},
  annote =	{Keywords: Lattice, Partially-ordered set, Space-efficient data structure, Succinct data structure}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.33
Universal Communication, Universal Graphs, and Graph Labeling

Authors: Nathaniel Harms

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
We introduce a communication model called universal SMP, in which Alice and Bob receive a function f belonging to a family ℱ, and inputs x and y. Alice and Bob use shared randomness to send a message to a third party who cannot see f, x, y, or the shared randomness, and must decide f(x,y). Our main application of universal SMP is to relate communication complexity to graph labeling, where the goal is to give a short label to each vertex in a graph, so that adjacency or other functions of two vertices x and y can be determined from the labels ℓ(x), ℓ(y). We give a universal SMP protocol using O(k^2) bits of communication for deciding whether two vertices have distance at most k in distributive lattices (generalizing the k-Hamming Distance problem in communication complexity), and explain how this implies a O(k^2 log n) labeling scheme for deciding dist(x,y) ≤ k on distributive lattices with size n; in contrast, we show that a universal SMP protocol for determining dist(x,y) ≤ 2 in modular lattices (a superset of distributive lattices) has super-constant Ω(n^{1/4}) communication cost. On the other hand, we demonstrate that many graph families known to have efficient adjacency labeling schemes, such as trees, low-arboricity graphs, and planar graphs, admit constant-cost communication protocols for adjacency. Trees also have an O(k) protocol for deciding dist(x,y) ≤ k and planar graphs have an O(1) protocol for dist(x,y) ≤ 2, which implies a new O(log n) labeling scheme for the same problem on planar graphs.
Cite as

Nathaniel Harms. Universal Communication, Universal Graphs, and Graph Labeling. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 33:1-33:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{harms:LIPIcs.ITCS.2020.33,
  author =	{Harms, Nathaniel},
  title =	{{Universal Communication, Universal Graphs, and Graph Labeling}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{33:1--33:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.33},
  URN =		{urn:nbn:de:0030-drops-117182},
  doi =		{10.4230/LIPIcs.ITCS.2020.33},
  annote =	{Keywords: Universal graphs, graph labeling, distance labeling, planar graphs, lattices, hamming distance}
}
  • Refine by Author
  • 2 Sinnamon, Corwin
  • 1 Harms, Nathaniel
  • 1 Hartmann, Maria
  • 1 Kozma, László
  • 1 Munro, J. Ian
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Graph coloring
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Mathematics of computing → Trees
  • 1 Theory of computation
  • Show More...

  • Refine by Keyword
  • 1 Lattice
  • 1 Partially-ordered set
  • 1 Space-efficient data structure
  • 1 Succinct data structure
  • 1 Universal graphs
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2020
  • 1 2021

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