Program of the Workshop on High-Dimensional and Complex Data Algorithms (Venice 2025)

The schedule is provisional and it should be expected that further changes will take place.

09:30 - 09:40 Coffee and Welcome
09:40 - 10:30 Talk by Ola Svensson
- A (2+ε)-Approximation Algorithm for Metric k-Median
10:30 - 11:00 Research discussions
11:00 - 11:30 Coffee break
11:30 - 12:30 Talk by Seth Pettie
- Moment Estimation, Sampling, and the Levy-Khintchine Representation Theorem
13:00 - 14:30 Lunch at OKE Zattere
- Address: Sestiere Dorsoduro, 1414, 30123 Venezia VE, Italy
14:45 - 15:45 Talk by Omri Weinstein
- Faster Combinatorial Matrix-Multiplication
15:45 - 16:30 Coffee break
16:30 - 17:30 Short talks
- Erik Waingarten: Streaming the Diameter in General Metrics
- Pavel Veselý: Streaming Diameter of High-Dimensional Points
- Michal Koucký: Almost Linear Size Sketches for Edit Distance
- Omri Ben Eliezer: Approximate Counting and Birgé Decomposition
- Pan Peng: Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts
17:30 - 18:30 Research discussions
19:00 - 23:55 Dinner at Ristorante Al Giardinetto da Severino
- Address: Salizada Zorzi, 4928, 30122 Venezia VE, Italy

09:30 - 10:20 Talk by Vera Traub
- The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2
10:20 - 11:00 Research discussions
11:00 - 11:30 Coffee break
11:30 - 12:30 Short talks
- Seffi Naor: Non Linear Paging
- Yasamin Nazari: Dynamic Algorithms with Predictions
- Ali Vakilian: Learning-Augmented Streaming Algorithms for Approximating Max-Cut
- Santoshini Velusamy: Constant-round Distributed Algorithms for Max-k-AND and Implications in Streaming
- Rajesh Jayaram: Approximating High-Dimensional Earth Mover’s Distance as Fast as Closest Pair
13:00 - 14:30 Lunch at Ristorante San Trovaso
- Address: Calle Larga Nani, 967, 30100 Venezia VE, Italy
14:45 - 15:45 Talk by Yang Liu
- Improved Algorithms for Estimating the Spanning Tree Count
15:45 - 16:30 Coffee break
16:30 - 17:30 Talk by Piotr Indyk
- Towards Overcoming the Reranking Bottleneck
17:30 - 18:30 Research discussions + Open Problems session
18:00 - 19:00 Reception

09:30 - 10:30 Short talks
- Pierre Fraigniaud: Distributed Cycle Detection
- Marcin Pilipczuk: Bounding ε-scatter Dimension via Metric Sparsity
- Arnab Bhattacharyya: Computing Distances between High-dimensional Distributions
- Krzysztof Onak: Robust Data Structures for Searching under Adaptive Queries
10:30 - 11:00 Research discussions
11:00 - 11:30 Coffee break
11:30 - 12:30 Talk by Michael Kapralov
- Spectral Clustering in Birthday Paradox Time
13:00 - 14:30 Lunch at OKE Zattere
- Address: Sestiere Dorsoduro, 1414, 30123 Venezia VE, Italy
14:45 - 15:45 Talk by Alexandr Andoni
- Data Dependent Frameworks for High-Dimensional Problems
15:45 - 16:30 Coffee break
16:30 - 17:15 Talk by Anupam Gupta
- The Price of Explainability for Clustering
17:15 - 18:30 Research discussions
19:00 - 23:55 Dinner at Ristorante Vecia Cavana
- Address: Via Tera Santi Apostoli, 4624, 30121 Venezia VE, Italy

The workshop is by invitation only

May 12 - 15, 2025

Palazzo Giustinian Lolin, Calle Giustinian, 2893, 30124 Venezia, Italy

Centre for Discrete Mathematics and its Applications