4 Search Results for "Gallopoulos, Efstratios"

Document
DOI: 10.4230/LIPIcs.STACS.2026.49
2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs

Authors: Rohit Gurjar, Kilian Rothmund, and Thomas Thierauf

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Minimally rigid graphs can be decided and embedded in the plane efficiently, i.e. in polynomial time. There is also an efficient randomized parallel algorithm, i.e. in RNC. We present an NC-algorithm to decide whether one-crossing-minor-free graphs are minimally rigid. In the special case of K_{3,3}-free graphs, we also compute an infinitesimally rigid embedding in NC.
Cite as

Rohit Gurjar, Kilian Rothmund, and Thomas Thierauf. 2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 49:1-49:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gurjar_et_al:LIPIcs.STACS.2026.49,
  author =	{Gurjar, Rohit and Rothmund, Kilian and Thierauf, Thomas},
  title =	{{2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{49:1--49:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.49},
  URN =		{urn:nbn:de:0030-drops-255385},
  doi =		{10.4230/LIPIcs.STACS.2026.49},
  annote =	{Keywords: Graph Rigidity, Parallel Algorithms, Polynomial Identity Testing, Derandomization}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.131
Deterministic Complexity Analysis of Hermitian Eigenproblems

Authors: Aleksandros Sobczyk

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
In this work we revisit the arithmetic and bit complexity of Hermitian eigenproblems. Recently, [BGVKS, FOCS 2020] proved that a (non-Hermitian) matrix A can be diagonalized with a randomized algorithm in O(n^{ω}log²(n/ε)) arithmetic operations, where ω≲ 2.371 is the square matrix multiplication exponent, and [Shah, SODA 2025] significantly improved the bit complexity for the Hermitian case. Our main goal is to obtain similar deterministic complexity bounds for various Hermitian eigenproblems. In the Real RAM model, we show that a Hermitian matrix can be diagonalized deterministically in O(n^{ω}log(n)+n²polylog(n/ε)) arithmetic operations, improving the classic deterministic Õ(n³) algorithms, and derandomizing the aforementioned state-of-the-art. The main technical step is a complete, detailed analysis of a well-known divide-and-conquer tridiagonal eigensolver of Gu and Eisenstat [GE95], when accelerated with the Fast Multipole Method, asserting that it can accurately diagonalize a symmetric tridiagonal matrix in nearly-O(n²) operations. In finite precision, we show that an algorithm by Schönhage [Sch72] to reduce a Hermitian matrix to tridiagonal form is stable in the floating point model, using O(log(n/ε)) bits of precision. This leads to a deterministic algorithm to compute all the eigenvalues of a Hermitian matrix in O(n^{ω}ℱ(log(n/ε)) + n²polylog(n/ε)) bit operations, where ℱ(b) ∈ Õ(b) is the bit complexity of a single floating point operation on b bits. This improves the best known Õ(n³) deterministic and O(n^{ω}log²(n/ε)ℱ(log(n/ε))) randomized complexities. We conclude with some other useful subroutines such as computing spectral gaps, condition numbers, and spectral projectors, and with some open problems.
Cite as

Aleksandros Sobczyk. Deterministic Complexity Analysis of Hermitian Eigenproblems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 131:1-131:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{sobczyk:LIPIcs.ICALP.2025.131,
  author =	{Sobczyk, Aleksandros},
  title =	{{Deterministic Complexity Analysis of Hermitian Eigenproblems}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{131:1--131:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.131},
  URN =		{urn:nbn:de:0030-drops-235081},
  doi =		{10.4230/LIPIcs.ICALP.2025.131},
  annote =	{Keywords: Hermitian eigenproblem, eigenvalues, SVD, tridiagonal reduction, matrix multiplication time, diagonalization, bit complexity}
}
Document
DOI: 10.4230/DagSemProc.07071.6
Asynchronous Computation of PageRank computation in an interactive multithreading environment

Authors: Giorgios Kollias and Efstratios Gallopoulos

Published in: Dagstuhl Seminar Proceedings, Volume 7071, Web Information Retrieval and Linear Algebra Algorithms (2007)

Abstract
Numerical Linear Algebra has become almost indispensable in Web Information Retrieval. In this presentation we suggest that the asynchronous computation model is an attractive paradigm for organizing concurrent computations spanning data on Web scale. This suggestion is supported by experiments which highlight some interesting characteristics of this model as applied to 'page ranking' methods. After an introduction on asynchronous computing in general and 'page ranking' in particular, we present results from the asynchronous compution of PageRank using typical combinations of execution units (processes, threads) and communication mechanisms (message passing, shared memory). Sound convergence properties predicted by theory are numerically verified and interesting patterns of behavior are unveiled. Our experiments were performed on Jylab, an evolving environment enabling interactive multithreading and multiprocessing computations. This work is supported by a Pythagoras-EPEAEK-II grant and is conducted in collaboration with Daniel Szyld.
Cite as

Giorgios Kollias and Efstratios Gallopoulos. Asynchronous Computation of PageRank computation in an interactive multithreading environment. In Web Information Retrieval and Linear Algebra Algorithms. Dagstuhl Seminar Proceedings, Volume 7071, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{kollias_et_al:DagSemProc.07071.6,
  author =	{Kollias, Giorgios and Gallopoulos, Efstratios},
  title =	{{Asynchronous Computation of PageRank computation in an interactive multithreading environment}},
  booktitle =	{Web Information Retrieval and Linear Algebra Algorithms},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7071},
  editor =	{Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07071.6},
  URN =		{urn:nbn:de:0030-drops-10651},
  doi =		{10.4230/DagSemProc.07071.6},
  annote =	{Keywords: Asynchronous, pagerank, multithreading, multiprocessing}
}
Document
DOI: 10.4230/DagSemProc.07071.13
Multidamping simulation framework for link-based ranking

Authors: Giorgios Kollias and Efstratios Gallopoulos

Published in: Dagstuhl Seminar Proceedings, Volume 7071, Web Information Retrieval and Linear Algebra Algorithms (2007)

Abstract
We review methods for the approximate computation of PageRank. Standard methods are based on the eigenvector and linear system characterizations. Our starting point are recent methods based on series representation whose coefficients are damping functions, for example Linear Rank, HyperRank and TotalRank, etc. We propose a multidamping framework for interpreting PageRank and these methods. Multidamping is based on some new useful properties of Google type matrices. The approach can be generalized and could help in the exploration of new approximations for list-based ranking. This is joint work with Georgios Kollias and is supported by a Pythagoras-EPEAEK-II grant.
Cite as

Giorgios Kollias and Efstratios Gallopoulos. Multidamping simulation framework for link-based ranking. In Web Information Retrieval and Linear Algebra Algorithms. Dagstuhl Seminar Proceedings, Volume 7071, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{kollias_et_al:DagSemProc.07071.13,
  author =	{Kollias, Giorgios and Gallopoulos, Efstratios},
  title =	{{Multidamping simulation framework for link-based ranking}},
  booktitle =	{Web Information Retrieval and Linear Algebra Algorithms},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7071},
  editor =	{Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07071.13},
  URN =		{urn:nbn:de:0030-drops-10606},
  doi =		{10.4230/DagSemProc.07071.13},
  annote =	{Keywords: PageRank, Google, power method, eigenvalues, teleportation, list-based ranking, TotalRank}
}
  • Refine by Type
  • 4 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2025
  • 2 2007

  • Refine by Author
  • 2 Gallopoulos, Efstratios
  • 2 Kollias, Giorgios
  • 1 Gurjar, Rohit
  • 1 Rothmund, Kilian
  • 1 Sobczyk, Aleksandros
  • Show More...

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

  • Refine by Classification
  • 1 Theory of computation → Divide and conquer
  • 1 Theory of computation → Numeric approximation algorithms
  • 1 Theory of computation → Parallel algorithms
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 2 eigenvalues
  • 1 Asynchronous
  • 1 Derandomization
  • 1 Google
  • 1 Graph Rigidity
  • 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