7 papers
Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds
Deeparnab Chakrabarty, Aditi Dudeja, David Saulpic
We study the round complexity of learning a hidden partition of an -element universe using PAIR queries: PAIR() tells us whether and belong to the sam…
Distributed Stochastic Graph Algorithms
Keren Censor-Hillel, Aditi Dudeja, George Giakkoupis
We study stochastic graph optimization problems in a novel distributed setting. As in the standard centralized setting, a random subgraph of a known base graph is realize…
Frontier Space-Time Algorithms Using Only Full Memory
Petr Chmel, Aditi Dudeja, Michal Koucký +2
We develop catalytic algorithms for fundamental problems in algorithm design that run in polynomial time, use only workspace, and use sublinear catalytic spa…
The Careless Coupon Collector's Problem
Emilio Cruciani, Aditi Dudeja
We initiate the study of the Careless Coupon Collector's Problem (CCCP), a novel variation of the classical coupon collector, that we envision as a model for information systems su…
A Weighted-to-Unweighted Reduction for Matroid Intersection
Aditi Dudeja, Mara Grilnberger
Given two matroids and over the same ground set, the matroid intersection problem is to find the maximum cardinality common independent set. In the…
Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs
Aditi Dudeja, Rashmika Goswami, Michael Saks
Vizing's theorem states that any graph of maximum degree can be properly edge colored with at most colors. In the online setting, it has been a matter of interest to fi…