23 citations · 60 across the 19 of their papers we have counts for
23 papers
Humanity's Last Exam
Long Phan, Alice Gatti, Ziwen Han +1168
Benchmarks are important tools for tracking the rapid advancements in large language model (LLM) capabilities. However, benchmarks are not keeping pace in difficulty: LLMs now achi…
Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances
Václav Rozhoň, Bernhard Haeupler, Anders Martinsson +2
We introduce stronger notions for approximate single-source shortest-path distances, show how to efficiently compute them from weaker standard notions, and demonstrate the algorith…
A Simple Deterministic Distributed Low-Diameter Clustering
Václav Rozhoň, Bernhard Haeupler, Christoph Grunau
We give a simple, local process for nodes in an undirected graph to form non-adjacent clusters that (1) have at most a polylogarithmic diameter and (2) contain at least half of all…
Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization
Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler +2
This paper presents significantly improved deterministic algorithms for some of the key problems in the area of distributed graph algorithms, including network decomposition, hitti…
Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond
Salwa Faour, Mohsen Ghaffari, Christoph Grunau +2
We develop a general deterministic distributed method for locally rounding fractional solutions of graph problems for which the analysis can be broken down into analyzing pairs of…
A Nearly Tight Analysis of Greedy k-means++
Christoph Grunau, Ahmet Alper Özüdoğru, Václav Rozhoň +1
The famous -means++ algorithm of Arthur and Vassilvitskii [SODA 2007] is the most popular way of solving the -means problem in practice. The algorithm is very simple: it samp…
Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates
Marcel Bezdrighin, Michael Elkin, Mohsen Ghaffari +4
This paper presents efficient distributed algorithms for a number of fundamental problems in the area of graph sparsification: We provide the first deterministic distributed algori…
Deterministic Distributed Algorithms and Measurable Combinatorics on -Regular Forests
Sebastian Brandt, Yi-Jun Chang, Jan Grebík +3
We investigate the connections between the fields of distributed computing and measurable combinatorics by considering complexity classes of locally checkable labeling problems on…
Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications
Václav Rozhoň, Michael Elkin, Christoph Grunau +1
This paper presents new deterministic and distributed low-diameter decomposition algorithms for weighted graphs. In particular, we show that if one can efficiently compute approxim…
Measurable tilings by abelian group actions
Jan Grebík, Rachel Greenfeld, Václav Rozhoň +1
Let be a measure space with a measure-preserving action of an abelian group . We consider the problem of understanding the structure of measurable…
On Homomorphism Graphs
Sebastian Brandt, Yi-Jun Chang, Jan Grebík +3
We introduce a new type of examples of bounded degree acyclic Borel graphs and study their combinatorial properties in the context of descriptive combinatorics, using a generalizat…
Classification of Local Problems on Paths from the Perspective of Descriptive Combinatorics
Jan Grebík, Václav Rozhoň
We classify which local problems with inputs on oriented paths have so-called Borel solution and show that this class of problems remains the same if we instead require a measurabl…
The randomized local computation complexity of the Lovász local lemma
Sebastian Brandt, Christoph Grunau, Václav Rozhoň
The Local Computation Algorithm (LCA) model is a popular model in the field of sublinear-time algorithms that measures the complexity of an algorithm by the number of probes the al…
Local Problems on Grids from the Perspective of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics
Jan Grebík, Václav Rozhoň
We present an intimate connection among the following fields: (a) distributed local algorithms: coming from the area of computer science, (b) finitary factors of iid processes: com…
Improved Deterministic Network Decomposition
Mohsen Ghaffari, Christoph Grunau, Václav Rozhoň
Network decomposition is a central tool in distributed graph algorithms. We present two improvements on the state of the art for network decomposition, which thus lead to improveme…
Adapting -means algorithms for outliers
Christoph Grunau, Václav Rozhoň
This paper shows how to adapt several simple and classical sampling-based algorithms for the -means problem to the setting with outliers. Recently, Bhaskara et al. (NeurIPS 2019…
Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma
Sebastian Brandt, Christoph Grunau, Václav Rozhoň
Recently, Brandt, Maus and Uitto [PODC'19] showed that, in a restricted setting, the dependency of the complexity of the distributed Lovász Local Lemma (LLL) on the chosen LLL crit…
Simple and sharp analysis of k-means||
Václav Rozhoň
We present a simple analysis of k-means|| (Bahmani et al., PVLDB 2012) -- a distributed variant of the k-means++ algorithm (Arthur and Vassilvitskii, SODA 2007). Moreover, the boun…
k-means++: few more steps yield constant approximation
Davin Choo, Christoph Grunau, Julian Portmann +1
The k-means++ algorithm of Arthur and Vassilvitskii (SODA 2007) is a state-of-the-art algorithm for solving the k-means clustering problem and is known to give an O(log k)-approxim…
Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization
Václav Rozhoň, Mohsen Ghaffari
We present a simple polylogarithmic-time deterministic distributed algorithm for network decomposition. This improves on a celebrated -time algorithm of Panco…
Cut distance identifying graphon parameters over weak* limits
Martin Doležal, Jan Grebík, Jan Hladký +2
The theory of graphons comes with the so-called cut norm and the derived cut distance. The cut norm is finer than the weak* topology (when considering the predual of -functi…
Relating the cut distance and the weak* topology for graphons
Martin Doležal, Jan Grebík, Jan Hladký +2
The theory of graphons is ultimately connected with the so-called cut norm. In this paper, we approach the cut norm topology via the weak* topology (when considering a predual of $…
A local approach to the Erdős-Sós conjecture
Václav Rozhoň
A famous conjecture of Erdős and Sós states that every graph with average degree more than contains all trees with edges as subgraphs. We prove that the Erdős-Sós conje…