2 Search Results for "Gurunathan, Vijaykrishna"

Document
DOI: 10.4230/LIPIcs.ITCS.2024.96
Matrix Multiplication in Quadratic Time and Energy? Towards a Fine-Grained Energy-Centric Church-Turing Thesis

Authors: Gregory Valiant

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We describe two algorithms for multiplying n × n matrices using time and energy Õ(n²) under basic models of classical physics. The first algorithm is for multiplying integer-valued matrices, and the second, quite different algorithm, is for Boolean matrix multiplication. We hope this work inspires a deeper consideration of physically plausible/realizable models of computing that might allow for algorithms which improve upon the runtimes and energy usages suggested by the parallel RAM model in which each operation requires one unit of time and one unit of energy.
Cite as

Gregory Valiant. Matrix Multiplication in Quadratic Time and Energy? Towards a Fine-Grained Energy-Centric Church-Turing Thesis. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 96:1-96:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{valiant:LIPIcs.ITCS.2024.96,
  author =	{Valiant, Gregory},
  title =	{{Matrix Multiplication in Quadratic Time and Energy? Towards a Fine-Grained Energy-Centric Church-Turing Thesis}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{96:1--96:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.96},
  URN =		{urn:nbn:de:0030-drops-196248},
  doi =		{10.4230/LIPIcs.ITCS.2024.96},
  annote =	{Keywords: Physics based computing, matrix multiplication, low-energy computing}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.36
Packing Squares into a Disk with Optimal Worst-Case Density

Authors: Sándor P. Fekete, Vijaykrishna Gurunathan, Kushagra Juneja, Phillip Keldenich, Linda Kleist, and Christian Scheffer

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

Abstract
We provide a tight result for a fundamental problem arising from packing squares into a circular container: The critical density of packing squares into a disk is δ = 8/(5π)≈ 0.509. This implies that any set of (not necessarily equal) squares of total area A ≤ 8/5 can always be packed into a disk with radius 1; in contrast, for any ε > 0 there are sets of squares of total area 8/5+ε that cannot be packed, even if squares may be rotated. This settles the last (and arguably, most elusive) case of packing circular or square objects into a circular or square container: The critical densities for squares in a square (1/2), circles in a square (π/(3+2√2) ≈ 0.539) and circles in a circle (1/2) have already been established, making use of recursive subdivisions of a square container into pieces bounded by straight lines, or the ability to use recursive arguments based on similarity of objects and container; neither of these approaches can be applied when packing squares into a circular container. Our proof uses a careful manual analysis, complemented by a computer-assisted part that is based on interval arithmetic. Beyond the basic mathematical importance, our result is also useful as a blackbox lemma for the analysis of recursive packing algorithms. At the same time, our approach showcases the power of a general framework for computer-assisted proofs, based on interval arithmetic.
Cite as

Sándor P. Fekete, Vijaykrishna Gurunathan, Kushagra Juneja, Phillip Keldenich, Linda Kleist, and Christian Scheffer. Packing Squares into a Disk with Optimal Worst-Case Density. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SoCG.2021.36,
  author =	{Fekete, S\'{a}ndor P. and Gurunathan, Vijaykrishna and Juneja, Kushagra and Keldenich, Phillip and Kleist, Linda and Scheffer, Christian},
  title =	{{Packing Squares into a Disk with Optimal Worst-Case Density}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{36:1--36: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.36},
  URN =		{urn:nbn:de:0030-drops-138356},
  doi =		{10.4230/LIPIcs.SoCG.2021.36},
  annote =	{Keywords: Square packing, packing density, tight worst-case bound, interval arithmetic, approximation}
}
  • Refine by Author
  • 1 Fekete, Sándor P.
  • 1 Gurunathan, Vijaykrishna
  • 1 Juneja, Kushagra
  • 1 Keldenich, Phillip
  • 1 Kleist, Linda
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Models of computation
  • 1 Theory of computation → Packing and covering problems

  • Refine by Keyword
  • 1 Physics based computing
  • 1 Square packing
  • 1 approximation
  • 1 interval arithmetic
  • 1 low-energy computing
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2021
  • 1 2024

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