Richard Hladík


Last Name

Hladík

First Name

Richard

ORCID

0000-0001-7153-3056

Organisational unit

09622 - Steurer, David / Steurer, David

Filters

2024 - 20256
Reset filters

Search Results

Publications 1 - 6 of 6
  • Universal Optimality of Dijkstra Via Beyond-Worst-Case Heaps
    Item type: Conference Paper
    Haeupler, Bernhard; Hladík, Richard; Rozhoň, Václav; et al. (2024)
    2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)
    This paper proves that Dijkstra's shortest-path algorithm is universally optimal in both its running time and number of comparisons when combined with a sufficiently efficient heap data structure. Universal optimality is a powerful beyond-worst-case performance guarantee for graph algorithms that informally states that a single algorithm performs as well as possible for every single graph topology. We give the first application of this notion to any sequential algorithm. We design a new heap data structure with a working-set property guaranteeing that the heap takes advantage of locality in heap operations. Our heap matches the optimal (worst-case) bounds of Fibonacci heaps but also provides the beyond-worst-case guarantee that the cost of extracting the minimum element is merely logarithmic in the number of elements inserted after it instead of logarithmic in the number of all elements in the heap. This makes the extraction of recently added elements cheaper. We prove that our working-set property guarantees universal optimality for the problem of ordering vertices by their distance from the source vertex: The sequence of heap operations generated by any run of Dijkstra's algorithm on a fixed graph possesses enough locality that one can couple the number of comparisons performed by any heap with our working-set bound to the minimum number of comparisons required to solve the distance ordering problem on this graph for a worst-case choice of arc lengths.
  • Fast and Simple Sorting Using Partial Information
    Item type: Conference Paper
    Haeupler, Bernhard; Hladík, Richard; Iacono, John; et al. (2025)
    Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
    We consider the problem of sorting n items, given the outcomes of m pre-existing comparisons. We present a simple and natural deterministic algorithm that runs in O(m + log T ) time and does O(log T ) comparisons, where T is the number of total orders consistent with the pre-existing comparisons. Our running time and comparison bounds are best possible up to constant factors, thus resolving a problem that has been studied intensely since 1976 (Fredman, Theoretical Computer Science). The best previous algorithm with a bound of O(log T ) on the number of comparisons has a time bound of O(n2.5) and is more complicated. Our algorithm combines three classic algorithms: topological sort, heapsort with the right kind of heap, and efficient search in a sorted list. It outputs the items in sorted order one by one. It can be modified to stop early, thereby solving the important and more general top-k sorting problem: Given k and the outcomes of some pre-existing comparisons, output the smallest k items in sorted order. The modified algorithm solves the top-k sorting problem in minimum time and comparisons, to within constant factors.
  • Smooth Sensitivity Revisited: Towards Optimality
    Item type: Conference Paper
    Hladík, Richard; Tětek, Jakub (2025)
    Leibniz International Proceedings in Informatics (LIPIcs) ~ 6th Symposium on Foundations of Responsible Computing (FORC 2025)
    Smooth sensitivity is one of the most commonly used techniques for designing practical differentially private mechanisms. In this approach, one computes the smooth sensitivity of a given query q on the given input D and releases q(D) with noise added proportional to this smooth sensitivity. One question remains: what distribution should we pick the noise from? In this paper, we give a new class of distributions suitable for the use with smooth sensitivity, which we name the PolyPlace distribution. This distribution improves upon the state-of-the-art Student’s T distribution in terms of standard deviation by arbitrarily large factors, depending on a “smoothness parameter” γ, which one has to set in the smooth sensitivity framework. Moreover, our distribution is defined for a wider range of parameter γ, which can lead to significantly better performance. Furthermore, we prove that the PolyPlace distribution converges for γ → 0 to the Laplace distribution and so does its variance. This means that the Laplace mechanism is a limit special case of the PolyPlace mechanism. This implies that our mechanism is in a certain sense optimal for γ → 0.
  • Bidirectional Dijkstra’s Algorithm is Instance-Optimal
    Item type: Conference Paper
    Haeupler, Bernhard; Hladík, Richard; Rozhoň, Václav; et al. (2025)
    Proceedings of the 2025 Symposium on Simplicity in Algorithms (SOSA)
    While Dijkstra’s algorithm has near-optimal time complexity for the problem of finding the shortest st-path, in practice, other algorithms are often superior on huge graphs. A prominent such example is the bidirectional search, which executes Dijkstra’s algorithm from both endpoints in parallel and stops when these executions meet. In this paper, we give a strong theoretical justification for the use of such bidirectional search algorithms. We prove that for weighted multigraphs, both directed and undirected, a careful implementation of bidirectional search is instance-optimal with respect to the number of edges it explores. That is, we prove that no correct algorithm can outperform our implementation of bidirectional search on any single instance by more than a constant factor. For unweighted graphs, we show that bidirectional search is instace-optimal up to a factor of O(Δ) where Δ is the maximum degree of the graph. We also show that this is the best possible.
  • Near-Universally-Optimal Differentially Private Minimum Spanning Trees
    Item type: Conference Paper
    Hladík, Richard; Tětek, Jakub (2025)
    Leibniz International Proceedings in Informatics (LIPIcs) ~ 6th Symposium on Foundations of Responsible Computing (FORC 2025)
    Devising mechanisms with good beyond-worst-case input-dependent performance has been an important focus of differential privacy, with techniques such as smooth sensitivity, propose-test-release, or inverse sensitivity mechanism being developed to achieve this goal. This makes it very natural to use the notion of universal optimality in differential privacy. Universal optimality is a strong instance-specific optimality guarantee for problems on weighted graphs, which roughly states that for any fixed underlying (unweighted) graph, the algorithm is optimal in the worst-case sense, with respect to the possible setting of the edge weights. In this paper, we give the first such result in differential privacy. Namely, we prove that a simple differentially private mechanism for approximately releasing the minimum spanning tree is near-optimal in the sense of universal optimality for the ℓ1 neighbor relation. Previously, it was only known that this mechanism is nearly optimal in the worst case. We then focus on the ℓ∞ neighbor relation, for which the described mechanism is not optimal. We show that one may implement the exponential mechanism for MST in polynomial time, and that this results in universal near-optimality for both the ℓ1 and the ℓ∞ neighbor relations.
  • Fast and Simple Sorting Using Partial Information
    Item type: Master Thesis
    Hladík, Richard (2024)
    We consider the problem of sorting n totally ordered items by doing binary comparisons, given a list of m comparisons that have already been performed. This problem has been called sorting under partial information, and it has been intensely studied since 1976. We propose a simple algorithm that solves this problem in O(log T) comparisons and O(log T + n + m) time, where T is the number of total orders consistent with the pre-existing comparisons. This is optimal up to constant factors. This problem has a long line of research, and for more than 30 years, all known solutions were either not polynomial, or relied on the ellipsoid method, which made them impractical. The best previous result achieves O(log T) comparisons in Θ(n^2.5) time and is more complicated. Our result combines two standard algorithms: topological sorting, and heapsort with the right kind of heap. Our algorithm can be obtained by a one-line modification of the topological sorting algorithm, and its analysis is short and straightforward.
Publications 1 - 6 of 6