14 citations · 27 across the 20 of their papers we have counts for
5 papers · 1 filter
Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots
Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan +1
We give an -space single-pass -approximation streaming algorithm for estimating the maximum directed cut size (Max-DICUT) in a directed graph on …
An Improved Lower Bound for Matroid Intersection Prophet Inequalities
Raghuvansh R. Saxena, Santhoshini Velusamy, S. Matthew Weinberg
We consider prophet inequalities subject to feasibility constraints that are the intersection of matroids. The best-known algorithms achieve a -approximation, even when r…
Streaming complexity of CSPs with randomly ordered constraints
Raghuvansh R. Saxena, Noah Singer, Madhu Sudan +1
We initiate a study of the streaming complexity of constraint satisfaction problems (CSPs) when the constraints arrive in a random order. We show that there exists a CSP, namely $\…
Sketching Approximability of (Weak) Monarchy Predicates
Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi +2
We analyze the sketching approximability of constraint satisfaction problems on Boolean domains, where the constraints are balanced linear threshold functions applied to literals.…
Fair allocation of a multiset of indivisible items
Pranay Gorantla, Kunal Marwaha, Santhoshini Velusamy
We study the problem of fairly allocating a multiset of indivisible items among agents with additive valuations. Specifically, we introduce a parameter for the numb…