Schedule

Day-wise Schedule

Day 1: July 22, Monday

09:30 - 10: 00 Light Breakfast

10:00 - 10:30 Introduction

10:30 - 11:45 Session 1

Speaker: Debmalya Panigrahi

Title: New Algorithms in Network Unreliability

Abstract: The (all-terminal) network unreliability problem asks for an estimation of the probability that a given network disconnects when every edge fails independently with a given probability. In this talk, I will present some new results for this problem in graphs and extensions to hypergraphs. The talk will be partly based on joint work with Ruoxu Cen (Duke) and Jason Li (CMU) that appeared in SODA 24 and STOC 24.

Speaker: Jeremy Fineman

Title: Beating Bellman-Ford: Faster Single-Source  Shortest Paths with Negative Real Weights 

Abstract: This talk presents a new randomized algorithm for the problem of single-source shortest path on directed graphs with real (both positive and negative) edge weights. Given an input graph with n vertices and m edges, the algorithm completes in $\tilde{O}(mn^{8/9})$ time with high probability. Whereas there has been significant progress for the case of integer-weighted graphs, this result constitutes the first asymptotic improvement over the classic O(mn)-time algorithm for the case of real weights.

12:00 - 14:00 Lunch

14:00 - 15:15 Session 2

Speaker: Philip Bille

Title: Gapped String Indexing in Subquadratic Space and  Sublinear Query Time

Abstract: I’ll present and discuss the gapped string index problem. This problem is a natural data structure problem in bioinformatics and has exciting connections to the 3-sum indexing problem.

Speaker: Meng-Tsung Tsai

Title: Dependent k-Set Packing on Polynomoids 

Abstract: Polynomoids are hereditary systems in which every pair of maximal independent sets shares a bounded number of common elements. This concept encompasses several natural properties, such as collinear point subsets, star subgraphs, and highly-connected node subsets. In this talk, a unified approach to certain packing problems for all polynomoids will be presented, yielding interesting implications for natural polynomoids.

15:15 - 16:00 Coffee Break and Discussion

16:00 - 17:30 Open Problem Session

Day 2: July 23, Tuesday

09:30 - 10: 00 Light Breakfast

10:00 - 11:15 Session 3

Speaker: Michal Koucky

Title: SquareSort: a cache-oblivious sorting algorithm 

Abstract: In this talk I will present a new simple and natural cache-oblivious sorting algorithm which has asymptotically optimal IO complexity O( n/B * log_M/B n), where n is the instance size, M size of the cache and B size of a memory block. This is the same as the complexity of the best known cache-oblivious sorting algorithm FunnelSort. Joint work with Josef Matějka.

Speaker: Laszlo Kozma

Title: Finding saddlepoints faster than sorting 

Abstract: A (strict) saddlepoint of an n*n matrix is an entry that is simultaneously the (strict) maximum of its row and the (strict) minimum of its column. A 1991 algorithm by Bienstock, Chung, Fredman, Schäffer, Shor, and Suri finds the strict saddlepoint in O(nlogn) time. We show that the implicit sorting step can we avoided and the saddlepoint can be found in (optimal) O(n) time.

11:15 - 11:30 Short Break

11:30 - 12:00 Session 4

Speaker: John Lapinskas

Title: When does approximate counting have the same  running time as decision?  

Abstract: It is obvious that if one can approximately count size-k independent sets (for example) up to multiplicative error, then one can decide whether any size-k independent set exists. In many settings, there are foundational results saying that the opposite is also true, and that efficient decision algorithms for hard complexity classes would imply efficient approximate counting algorithms for those same classes; for example, a polynomial-time decision algorithm for SAT would imply an FPRAS for #SAT, and a sub-exponential time algorithm for 3-SAT would imply a sub-exponential time approximation algorithm for #3-SAT. We look at the fine-grained setting, where we care about exact running times rather than broad categories like "polynomial" or "subexponential", and ask when the same property holds (surprisingly often), when it doesn't (regrettably sometimes), and what can be done in the gaps between (an near-optimal algorithm for a common class of problems backed by matching oracle bounds).

12:00 - 14:00 Lunch

14:00 - 15:15 Session 5

Speaker: Shaofeng Jiang

Title: Dimension Reduction for Clustering Problems 

Abstract: Dimension reduction is a fundamental approach for algorithm design in high dimensional Euclidean spaces. We confider clustering problems, including facility location and k-clustering, and introduce recent advances on dimension reduction for these problems. The talk will discuss both new regimes (of parameters) as well as new methods for dimension reduction.

Speaker: Sanjana Dey

Title: Matrix Completion: Approximating the Minimum  Diameter

Abstract: In this work, we focus on the matrix completion problem and aim to minimize the diameter over an arbitrary alphabet. Given a matrix M with missing entries, our objective is to complete the matrix by filling in the missing entries in a way that minimizes the maximum (Hamming) distance between any pair of rows in the completed matrix (also known as the diameter of the matrix). It is worth noting that this problem is already known to be NP-hard. We give a polynomial time 3- approximation algorithm while proving that it is (2 − ε)-inapproximable for any ε > 0, even when considering a binary alphabet, under the assumption that P  ̸= NP.

15:15 - 16:30 Coffee Break and Discussion

16:30 - 17:00 Session 6

Speaker: Jingxun Liang

Title: Tight Cell-Probe Lower Bounds for Dynamic Succinct  Dictionaries

Abstract: The dictionary problem involves maintaining a set $S \subset [U]$ of n keys under insertions, deletions, and membership queries focusing on efficiency in both time and space. This fundamental problem has been studied extensively for six decades since 1953. Recently, a series of works has established the optimal time-space trade-off for dictionaries. In this talk, I will describe the tight lower bound result that any dictionary with an operational time $t$ must incur a redundant $\Omega(log^{(t)} n)$ bits per key in space.

Day 3: July 24, Wednesday

09:30 - 10: 00 Light Breakfast

10:00 - 11:15 Session 7

Speaker: Michael Dinitz

Title: Binary Search Tree with Distributional Predictions

Abstract: Algorithms with (machine-learned) predictions is a powerful framework for combining traditional worst-case algorithms with modern machine learning. However, the vast majority of work in this space assumes that the prediction itself is non-probabilistic, even if it is generated by some stochastic process (such as a machine learning system). This is a poor fit for modern ML, particularly modern neural networks, which naturally generate a distribution. We initiate the study of algorithms with distributional predictions, where the prediction itself is a distribution. We focus on one of the simplest yet fundamental settings: binary search trees (or searching a sorted array). We give an algorithm with query running time $O(H(p) + \log \eta)$, where $H(p)$ is the entropy of the true distribution $p$ and $\eta$ is the Earth Mover's distance between $p$ and the predicted distribution $\hat p$. We complement this with a lower bound showing that this running time is essentially optimal (up to constants).

Speaker: Sayantan Sen

Title: Distribution Learning Meets Graph Structure Sampling 

Abstract: This work establishes a novel connection between PAC-learning of high-dimensional graphical models with efficient counting and sampling of graph structures using the well-studied online learning framework. Using the exponentially weighted average (EWA) and randomized weighted majority (RWM) algorithms with the log loss function on the samples from a distribution P, we show that the average regret can bound the expected KL divergence between P and the predictions. This results in new sample complexity bounds for learning Bayes nets. Moreover, using this connection, we design the first efficient polynomial sample and time algorithm for sampling Bayes nets with a given chordal skeleton.

11:15 - 11:30 Short Break

11:30 - 12:00 Session 8

Speaker: Nicole Wein

Title: Optimal Memory Allocation: The Dos and Don'ts of  Request Fragmentation 

Abstract: I will talk about the classical problem of memory allocation, with and without request fragmentation. In the standard version (without request fragmentation), the input is an arbitrary sequence of memory requests of various sizes and frees. Upon arrival of each memory request, the algorithm must decide where to allocate it in memory. A free specifies a previous memory request, and the algorithm responds by deallocating the allocation corresponding to that request. The quality of an algorithm is measured by its memory high-water mark (largest occupied memory slot) as a function of the volume high-water mark M (largest volume of requests simultaneously allocated). The best known upper and lower bounds are the classical bounds of O(M log M) and Omega(M log M / log log M) respectively. Since logarithmic lower bounds can be prohibitive in practice, a common memory-saving strategy is to fragment requests into a small number of pieces. Despite wide proliferation of request fragmentation in practice, we are the first to study it in theory. We prove tight upper and lower bounds for the memory allocation problem both with and without fragmentation. Joint work with Michael Bender, Alexander Conway, Martin Farach-Colton, Hanna Komlos, and William Kuszmaul.

12:00 - 14:00 Lunch

14:00 - 15:15 Session 9

Speaker: Bundit Laekhanukit

Title: On Parameterized Inapproximability of k-Clique

Abstract: This talk will explore the techniques and state of the art in proving parameterized inapproximability of k-clique. After exploring several approaches that could lead to proving that k-clique is totally FPT-approximable, we will present a hardness construction derived from network coding (plus Sidon sets), which is almost combinatorial and shows a distinct picture between standard NP-hardness proof and W[1]-hardness proof.

Speaker: Yarin Shechter

Title: Faster combinatorial k-clique algorithms 

Abstract: The limitations of fast matrix multiplication algorithms have motivated research into alternative techniques for solving the k-clique problem. We present an improvement of these alternative techniques, and use them to further the state of the art for generalized settings of the k-clique problem.

15:15 - 16:30 Coffee Break and Discussion

16:30 - 17:00 Session 10

Speaker: Hanna Komlós

Title: History-Independent Dynamic Partitioning: Operation-Order Privacy in Ordered Data Structures

Abstract: A data structure is history independent if its internal representation reveals nothing about the history of operations beyond what can be determined from the current contents of the data structure. History independence is typically viewed as a security or privacy guarantee, with the intent being to minimize risks incurred by a security breach or audit. Despite widespread advances in history independence, there is an important data-structural primitive that previous work has been unable to replace with an equivalent history-independent alternative -- dynamic partitioning. In dynamic partitioning, we are given a dynamic set S of ordered elements and a size-parameter B, and the objective is to maintain a partition of S into ordered groups, each of size Θ(B). 

Dynamic partitioning is important throughout computer science, with applications to B-tree rebalancing, write-optimized dictionaries, log-structured merge trees, other external-memory indexes, geometric and spatial data structures, cache-oblivious data structures, and order-maintenance data structures. The lack of a history-independent dynamic-partitioning primitive has meant that designers of history-independent data structures have had to resort to complex alternatives. In this paper, we achieve history-independent dynamic partitioning. Our algorithm runs asymptotically optimally against an oblivious adversary, processing each insert/delete with O(1) operations in expectation and O(B log N/loglog N) with high probability in set size N.

This paper appeared at PODS 2024 and is joint work with Michael Bender, Martín Farach-Colton, and Michael Goodrich.

17:00 - 17:30 More Open Problems/ Updates on Open Problems

Day 4: July 25, Thursday

09:30 - 10: 00 Light Breakfast

10:00 - 11:15 Session 11

Speaker: William Kuszmaul

Title: Linear Probing Revisited: The Demise of Primary  Clustering 

Abstract: In this talk, we'll revisit one of the oldest data structures in computer science, the linear-probing hash table. We will overturn a 50-year old myth about the dangers of primary clustering, and we will introduce a new variation of linear probing (called graveyard hashing) that does not exhibit any clustering at all.

Speaker: Ioana-Oriana Bercea 

Title: Locally Uniform Hashing 

Abstract: Hashing is a commonly used technique for getting improved algorithms. Most analyses, however, assume access to fully-random hash functions, which is unrealistic in terms of the resources available to the algorithm. A fundamental line of work has thus been to design realistic hash functions (with small space and fast evaluation time) that make the algorithm perform almost as if it used fully-random hash functions. In this talk, we will review one such hash function, called a tornado tabulation hash function, that provides state-of-the-art randomness guarantees for several fundamental algorithms. In particular, we will define and discuss one key property that it exhibits, that of local uniformity. This is joint work with Lorenzo Beretta, Jonas Klausen, Jakob Bæk Tejs Houen, and Mikkel Thorup, appeared in FOCS 2023.

11:15 - 11:30 Short Break

11:30 - 12:00 Session 12

Speaker: Nidhi Purohit

Title: Clustering Problems: From a Viewpoint of  Parameterized Complexity 

Abstract: $k$-median is one of the classical clustering problems. It is well-known to be \classNP-hard. \emph{Parameterized complexity} is one of the algorithmic paradigms to cope with the \classNP-hardness of the problem. This talk will discuss the problem with different parameterizations.

12:00 - 14:00 Lunch

14:00 - 15:15 Session 13

Speaker: Y.C. Tay

Title: A Performance Analysis of BFT Consensus for Blockchains 

Abstract: This talk presents an analytical model that yields closed-form expressions for analyzing how protocol parameters (e.g. timer value) and network topology (Folded-Clos and Dragonfly) affect the consensus time of two BFT protocols (HotStuff and Istanbul BFT).

Speaker: Yeo Xin Yi Michelle

Title: Fully Automated Selfish Mining Analysis in  Efficient Proof Systems Blockchains

Abstract: The analysis of selfish mining in blockchains based on efficient proof systems is notoriously difficult, due to the exponential attack strategy space. In this talk I will outline the difficulties of analysing selfish mining in such systems as well as some methods to prune the strategy space. I will then present a fully automated method to compute a lower bound on the optimal selfish mining strategy and revenue.

15:15 - 16:30 Coffee Break and Discussion

16:30 - 17:45 Session 14

Speaker: Li Zeyong

Title: Simple algorithm for Range Avoidance in F\Sigma_2

Abstract: We demonstrate a single-valued F\Sigma_2 algorithm for solving Range Avoidance, using a simple perfect binary tree structure. As corollaries, we obtain strong circuit lower bounds and pseudo-deterministic constructions (with an NP oracle) for many combinatorial objects such as Ramsey graphs, rigid matrices, two-source extractors and linear codes with nearly optimal parameters.

Speaker: Renfei Zhou

Title: Dynamic "Succincter"

Abstract: We extend the seminal work "Succincter" by Mihai Pătrașcu to support dynamic operations, addressing a key challenge in dynamic succinct data structures: managing variable-size parts within a contiguous piece of memory. This has numerous applications.

Day 5: July 26, Friday

09:30 - 10: 00 Light Breakfast

10:00 - 11:15 Session 15

Speaker: Yi-Jun Chang

Title: Improved all-pairs approximate shortest paths in  congested clique 

Abstract: In this talk, I will present an O(log log log n)-round constant-approximation APSP algorithm for the Congested Clique model. Prior to this work, the best upper bounds were poly(log n) for weighted graphs and poly(log log n) for unweighted graphs. This improvement is achieved through new analyses and constructions of variants of hopsets and skeleton graphs based on the notion of k-nearest nodes.

Speaker: Muhammad Ayaz Dzulfikar

Title: Adaptive Byzantine Agreement 

Abstract: Byzantine agreement (BA) is a distributed computing problem where n nodes try to agree on a decision, and the adversary may corrupt some nodes arbitrarily. Since the 1980s, some lower bounds for BA have been proven, typically assuming the worst-case number of corrupted nodes. In this talk, I will discuss how to circumvent these lower bounds via algorithms which are adaptive towards the actual number of corrupted nodes (without knowing the actual number itself).

11:15 - 11:30 Short Break

11:30 - 12:00 Session 16

Speaker: Gopinath Mishra

Title: Streaming Graph Algorithms in the Massively Parallel Computation Model

Abstract: In this talk, we discuss graph algorithms in the streaming setting on the Massively Parallel Computation (MPC) model. Our work demonstrates that we can handle large batches of edge updates for problems such as connectivity, minimum spanning forest, and approximate matching in a constant number of rounds, with the total memory used by the algorithms essentially matching the corresponding space complexities in the standard streaming setting.

12:00 - 14:00 Lunch