2 Search Results for "Molina Lovett, Antonio J."

Document
DOI: 10.4230/LIPIcs.FUN.2021.10
Computational Fun with Sturdy and Flimsy Numbers

Authors: Trevor Clokie, Thomas F. Lidbetter, Antonio J. Molina Lovett, Jeffrey Shallit, and Leon Witzman

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
Following Stolarsky, we say that a natural number n is flimsy in base b if some positive multiple of n has smaller digit sum in base b than n does; otherwise it is sturdy . We develop algorithmic methods for the study of sturdy and flimsy numbers. We provide some criteria for determining whether a number is sturdy. Focusing on the case of base b = 2, we study the computational problem of checking whether a given number is sturdy, giving several algorithms for the problem. We find two additional, previously unknown sturdy primes. We develop a method for determining which numbers with a fixed number of 0’s in binary are flimsy. Finally, we develop a method that allows us to estimate the number of k-flimsy numbers with n bits, and we provide explicit results for k = 3 and k = 5. Our results demonstrate the utility (and fun) of creating algorithms for number theory problems, based on methods of automata theory.
Cite as

Trevor Clokie, Thomas F. Lidbetter, Antonio J. Molina Lovett, Jeffrey Shallit, and Leon Witzman. Computational Fun with Sturdy and Flimsy Numbers. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{clokie_et_al:LIPIcs.FUN.2021.10,
  author =	{Clokie, Trevor and Lidbetter, Thomas F. and Molina Lovett, Antonio J. and Shallit, Jeffrey and Witzman, Leon},
  title =	{{Computational Fun with Sturdy and Flimsy Numbers}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{10:1--10:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.10},
  URN =		{urn:nbn:de:0030-drops-127715},
  doi =		{10.4230/LIPIcs.FUN.2021.10},
  annote =	{Keywords: sturdy number, flimsy number, context-free grammar, finite automaton, enumeration}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2020.12
A Simple Algorithm for Minimum Cuts in Near-Linear Time

Authors: Nalin Bhardwaj, Antonio J. Molina Lovett, and Bryce Sandlund

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

Abstract
We consider the minimum cut problem in undirected, weighted graphs. We give a simple algorithm to find a minimum cut that 2-respects (cuts two edges of) a spanning tree T of a graph G. This procedure can be used in place of the complicated subroutine given in Karger’s near-linear time minimum cut algorithm [Karger, 2000]. We give a self-contained version of Karger’s algorithm with the new procedure, which is easy to state and relatively simple to implement. It produces a minimum cut on an m-edge, n-vertex graph in O(m log³ n) time with high probability, matching the complexity of Karger’s approach.
Cite as

Nalin Bhardwaj, Antonio J. Molina Lovett, and Bryce Sandlund. A Simple Algorithm for Minimum Cuts in Near-Linear Time. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bhardwaj_et_al:LIPIcs.SWAT.2020.12,
  author =	{Bhardwaj, Nalin and Molina Lovett, Antonio J. and Sandlund, Bryce},
  title =	{{A Simple Algorithm for Minimum Cuts in Near-Linear Time}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{12:1--12:18},
  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.12},
  URN =		{urn:nbn:de:0030-drops-122594},
  doi =		{10.4230/LIPIcs.SWAT.2020.12},
  annote =	{Keywords: minimum cut, sparsification, near-linear time, packing}
}
  • Refine by Author
  • 2 Molina Lovett, Antonio J.
  • 1 Bhardwaj, Nalin
  • 1 Clokie, Trevor
  • 1 Lidbetter, Thomas F.
  • 1 Sandlund, Bryce
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Dynamic programming
  • 1 Theory of computation → Grammars and context-free languages
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 context-free grammar
  • 1 enumeration
  • 1 finite automaton
  • 1 flimsy number
  • 1 minimum cut
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 2 2020

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