1 citations · 1 across the 8 of their papers we have counts for
8 papers · 1 filter
Online Tokenization with Optimal Delay in Linear Time
Mina Dalirrooyfard, Christopher Ye
Tokenization is an essential preprocessing step in almost all large language models (LLMs). One of the most popular frameworks is BPE tokenization, which consists of special token…
A Simple Average-case Analysis of Recursive Randomized Greedy MIS
Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović
We revisit the complexity analysis of the recursive version of the randomized greedy algorithm for computing a maximal independent set (MIS), originally analyzed by Yoshida, Yamamo…
Breaking the Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
Anders Aamand, Justin Y. Chen, Mina Dalirrooyfard +4
We study differentially private algorithms for graph cut sparsification, a fundamental problem in algorithms, privacy, and machine learning. While significant progress has been mad…
SPARSE-PIVOT: Dynamic correlation clustering for node insertions
Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović
We present a new Correlation Clustering algorithm for a dynamic setting where nodes are added one at a time. In this model, proposed by Cohen-Addad, Lattanzi, Maggiori, and Parotsi…
Differentially Private Gomory-Hu Trees
Anders Aamand, Justin Y. Chen, Mina Dalirrooyfard +4
Given an undirected, weighted -vertex graph , a Gomory-Hu tree is a weighted tree on such that for any pair of distinct vertices , the Min-…
Graph Partitioning With Limited Moves
Majid Behbahani, Mina Dalirrooyfard, Elaheh Fata +1
In many real world networks, there already exists a (not necessarily optimal) -partitioning of the network. Oftentimes, one aims to find a -partitioning with a smaller cut va…
Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models
Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović
Given a graph with positive and negative edge labels, the correlation clustering problem aims to cluster the nodes so to minimize the total number of between-cluster positive and w…
Nearly Tight Bounds For Differentially Private Min - and Multiway Cut
Mina Dalirrooyfard, Slobodan Mitrović, Yuriy Nevmyvaka
Finding min - cuts in graphs is a basic algorithmic tool with applications in image segmentation, community detection, reinforcement learning, and data clustering. In this pr…