research
∙
06/01/2023
Dynamic Algorithms for Matroid Submodular Maximization
Submodular maximization under matroid and cardinality constraints are cl...
share
research
∙
05/25/2023
Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements
We consider the problem of fair allocation of indivisible goods or chore...
research
∙
05/24/2023
Dynamic Constrained Submodular Optimization with Polylogarithmic Update Time
Maximizing a monotone submodular function under cardinality constraint k...
research
∙
05/18/2023
Fault-Tolerant Consensus in Quantum Networks
Fault-tolerant consensus is about reaching agreement on some of the inpu...
research
∙
05/04/2023
Delegating to Multiple Agents
We consider a multi-agent delegation mechanism without money. In our mod...
research
∙
03/08/2023
Optimal Sparse Recovery with Decision Stumps
Decision trees are widely used for their low computational cost, good pr...
research
∙
02/15/2023
Bandit Social Learning: Exploration under Myopic Behavior
We study social learning dynamics where the agents collectively follow a...
research
∙
02/08/2023
Weighted Edit Distance Computation: Strings, Trees and Dyck
Given two strings of length n over alphabet Σ, and an upper bound k on t...
research
∙
10/13/2022
Online Algorithms for the Santa Claus Problem
The Santa Claus problem is a fundamental problem in fair division: the g...
research
∙
09/15/2022
Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance
Computing the edit distance of two strings is one of the most basic prob...
research
∙
05/29/2022
Generalized Stochastic Matching
In this paper, we generalize the recently studied Stochastic Matching pr...
research
∙
05/27/2022
Generalized Reductions: Making any Hierarchical Clustering Fair and Balanced with Low Cost
Clustering is a fundamental building block of modern statistical analysi...
research
∙
05/27/2022
Adaptive Massively Parallel Algorithms for Cut Problems
We study the Weighted Min Cut problem in the Adaptive Massively Parallel...
research
∙
05/26/2022
Analysis of a Learning Based Algorithm for Budget Pacing
In this paper, we analyze a natural learning algorithm for uniform pacin...
research
∙
03/24/2022
Improved Communication Complexity of Fault-Tolerant Consensus
Consensus is one of the most thoroughly studied problems in distributed ...
research
∙
11/02/2021
Adaptive Massively Parallel Constant-round Tree Contraction
Miller and Reif's FOCS'85 classic and fundamental tree contraction algor...
research
∙
06/01/2021
Differentially Private Densest Subgraph
Given a graph, the densest subgraph problem asks for a set of vertices s...
research
∙
01/13/2021
Improved Hierarchical Clustering on Massive Datasets with Broad Guarantees
Hierarchical clustering is a stronger extension of one of today's most i...
research
∙
07/14/2020
Almost Envy-freeness, Envy-rank, and Nash Social Welfare Matchings
Envy-free up to one good (EF1) and envy-free up to any good (EFX) are tw...
research
∙
03/16/2020
Approximating LCS in Linear Time: Beating the √(n) Barrier
Longest common subsequence (LCS) is one of the most fundamental problems...
research
∙
03/08/2020
Inverse Feature Learning: Feature learning based on Representation Learning of Error
This paper proposes inverse feature learning as a novel supervised featu...
research
∙
02/27/2020
Stochastic Matching with Few Queries: (1-ε) Approximation
Suppose that we are given an arbitrary graph G=(V, E) and know that each...
research
∙
02/26/2020
Asymmetric Streaming Algorithms for Edit Distance and LCS
The edit distance (ED) and longest common subsequence (LCS) are two fund...
research
∙
02/26/2020
Streaming with Oracle: New Streaming Algorithms for Edit Distance and LCS
The edit distance (ED) and longest common subsequence (LCS) are two fund...
research
∙
12/22/2019
Approximate Maximum Matching in Random Streams
In this paper, we study the problem of finding a maximum matching in the...
research
∙
11/29/2019
Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
(see paper for full abstract) Given a vertex-weighted directed graph G...
research
∙
10/25/2019
Massively Parallel Algorithms for String Matching with Wildcards
We study distributed algorithms for string matching problem in presence ...
research
∙
10/09/2019
Prophets, Secretaries, and Maximizing the Probability of Choosing the Best
Suppose a customer is faced with a sequence of fluctuating prices, such ...
research
∙
09/08/2019
Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time
We present the first algorithm for maintaining a maximal independent set...
research
∙
09/07/2019
Computing Stackelberg Equilibria of Large General-Sum Games
We study the computational complexity of finding Stackelberg Equilibria ...
research
∙
05/20/2019
Subcubic Equivalences Between Graph Centrality Measures and Complementary Problems
Despite persistent efforts, there is no known technique for obtaining un...
research
∙
05/05/2019
MapReduce Meets Fine-Grained Complexity: MapReduce Algorithms for APSP, Matrix Multiplication, 3-SUM, and Beyond
Distributed processing frameworks, such as MapReduce, Hadoop, and Spark ...
research
∙
01/30/2019
Online Pandora's Boxes and Bandits
We consider online variations of the Pandora's box problem (Weitzman. 19...
research
∙
01/14/2019
Optimal Strategies of Blotto Games: Beyond Convexity
The Colonel Blotto game, first introduced by Borel in 1921, is a well-st...
research
∙
01/11/2019
Exponentially Faster Massively Parallel Maximal Matching
The study of graph problems in the Massively Parallel Computations (MPC)...
research
∙
11/30/2018
Fast Algorithms for Knapsack via Convolution and Prediction
The knapsack problem is a fundamental problem in combinatorial optimizat...
research
∙
11/09/2018
Polynomial-time Approximation Scheme for Minimum k-cut in Planar and Minor-free Graphs
The k-cut problem asks, given a connected graph G and a positive integer...
research
∙
11/08/2018
Stochastic Matching with Few Queries: New Algorithms and Tools
We consider the following stochastic matching problem on both weighted a...
research
∙
11/04/2018
Lower Bounds for External Memory Integer Sorting via Network Coding
Sorting extremely large datasets is a frequently occuring task in practi...
research
∙
09/11/2018
Massively Parallel Dynamic Programming on Trees
Dynamic programming is a powerful technique that is, unfortunately, ofte...
research
∙
07/17/2018
Massively Parallel Symmetry Breaking on Sparse Graphs: MIS and Maximal Matching
The success of massively parallel computation (MPC) paradigms such as Ma...
research
∙
04/11/2018
Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce
The edit distance between two strings is defined as the smallest number ...
research
∙
02/28/2018
Brief Announcement: Semi-MapReduce Meets Congested Clique
Graph problems are troublesome when it comes to MapReduce. Typically, to...
research
∙
10/30/2017
Prophet Secretary for Combinatorial Auctions and Matroids
The secretary and the prophet inequality problems are central to the fie...
research
∙
09/30/2017
On the Complexity of Chore Division
We study the proportional chore division problem where a protocol wants ...
research
∙
04/30/2012
A Game-Theoretic Model Motivated by the DARPA Network Challenge
In this paper we propose a game-theoretic model to analyze events simila...
research
∙
05/03/2011