Søren Fuglede Jørgensen

dblp:352/3672 · DBLP profile ↗
← Back
3ranked-venue papers
1as first author
3since 2021 · last 2025
0009-0005-9865-9771ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 2 since 2021Security and privacy · 1 · 1 first-author · 1 since 2021Applied, interdisciplinary, general and emerging computing · 1 · 1 since 2021
YearPublicationVenuePosition
2025 On Exact Sizes of Minimal CNOT Circuits
Jens Emil Christensen, Søren Fuglede Jørgensen, Andreas Pavlogiannis, Jaco van de Pol
RC2
2025 On the clique covering numbers of Johnson graphs
Søren Fuglede Jørgensen
Des. Codes Cryptogr.1
2024 Sublinear Time Shortest Path in Expander Graphs
abstract
Computing a shortest path between two nodes in an undirected unweighted graph is among the most basic algorithmic tasks. Breadth first search solves this problem in linear time, which is clearly also a lower bound in the worst case. However, several works have shown how to solve this problem in sublinear time in expectation when the input graph is drawn from one of several classes of random graphs. In this work, we extend these results by giving sublinear time shortest path (and short path) algorithms for expander graphs. We thus identify a natural deterministic property of a graph (that is satisfied by typical random regular graphs) which suffices for sublinear time shortest paths. The algorithms are very simple, involving only bidirectional breadth first search and short random walks. We also complement our new algorithms by near-matching lower bounds.
Noga Alon, Allan Grønlund Jørgensen, Søren Fuglede Jørgensen, Kasper Green Larsen
MFCS3