research
∙
09/09/2023
A constant factor approximation for Nash social welfare with subadditive valuations
We present a constant-factor approximation algorithm for the Nash social...
share
research
∙
05/19/2023
Practical algorithms and experimentally validated incentives for equilibrium-based fair division (A-CEEI)
Approximate Competitive Equilibrium from Equal Incomes (A-CEEI) is an eq...
research
∙
03/03/2023
Near Optimal Memory-Regret Tradeoff for Online Learning
In the experts problem, on each of T days, an agent needs to follow the ...
research
∙
01/13/2023
Sublinear Algorithms for TSP via Path Covers
We study sublinear time algorithms for the traveling salesman problem (T...
research
∙
11/29/2022
Sublinear Time Algorithms and Complexity of Approximate Maximum Matching
Sublinear time algorithms for approximating maximum matching size have l...
research
∙
11/16/2022
Beyond Worst-Case Budget-Feasible Mechanism Design
Motivated by large-market applications such as crowdsourcing, we revisit...
research
∙
11/09/2022
Fully-dynamic-to-incremental reductions with known deletion order (e.g. sliding window)
Dynamic algorithms come in three main flavors: 𝑖𝑛𝑐𝑟𝑒𝑚𝑒𝑛𝑡𝑎𝑙 (insertions-o...
research
∙
06/27/2022
Beating Greedy Matching in Sublinear Time
We study sublinear time algorithms for estimating the size of maximum ma...
research
∙
04/23/2022
Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond 1/2-Approximation
In this work we give two new algorithms that use similar techniques for ...
research
∙
11/20/2021
Approximation Algorithms for LCS and LIS with Truly Improved Running Times
Longest common subsequence (𝖫𝖢𝖲) is a classic and central problem in com...
research
∙
11/14/2021
Cardinality constrained submodular maximization for random streams
We consider the problem of maximizing submodular functions in single-pas...
research
∙
08/20/2021
Does Preprocessing help in Fast Sequence Comparisons?
We study edit distance computation with preprocessing: the preprocessing...
research
∙
04/22/2021
The Randomized Communication Complexity of Randomized Auctions
We study the communication complexity of incentive compatible auction-pr...
research
∙
02/10/2021
Budget-Smoothed Analysis for Submodular Maximization
The greedy algorithm for submodular function maximization subject to car...
research
∙
12/29/2020
Exponential Communication Separations between Notions of Selfishness
We consider the problem of implementing a fixed social choice function b...
research
∙
12/14/2020
Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics
We consider the fundamental problem of selecting k out of n random varia...
research
∙
12/08/2020
Settling the complexity of Nash equilibrium in congestion games
We consider (i) the problem of finding a (possibly mixed) Nash equilibri...
research
∙
11/12/2020
Communication complexity of Nash equilibrium in potential games
We prove communication complexity lower bounds for (possibly mixed) Nash...
research
∙
11/11/2020
The Strongish Planted Clique Hypothesis and Its Consequences
We formulate a new hardness assumption, the Strongish Planted Clique Hyp...
research
∙
07/28/2020
A Simple Sublinear Algorithm for Gap Edit Distance
We study the problem of estimating the edit distance between two n-chara...
research
∙
07/21/2020
Smoothed Complexity of 2-player Nash Equilibria
We prove that computing a Nash equilibrium of a two-player (n × n) game ...
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
∙
11/18/2019
Optimal Single-Choice Prophet Inequalities from Samples
We study the single-choice Prophet Inequality problem when the gambler i...
research
∙
09/07/2019
Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria
The use of monotonicity and Tarski's theorem in existence proofs of equi...
research
∙
04/10/2019
Reducing approximate Longest Common Subsequence to approximate Edit Distance
Given a pair of strings, the problems of computing their Longest Common ...
research
∙
04/10/2019
Constant-factor approximation of near-linear edit distance in near-linear time
We show that the edit distance between two strings of length n can be co...
research
∙
11/07/2018
An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model
In this paper we study submodular maximization under a matroid constrain...
research
∙
10/28/2018
Near-Linear Time Insertion-Deletion Codes and (1+ε)-Approximating Edit Distance via Indexing
We introduce fast-decodable indexing schemes for edit distance which can...
research
∙
05/16/2018
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
We prove an N^2-o(1) lower bound on the randomized communication complex...
research
∙
05/07/2018
Fine-grained Complexity Meets IP = PSPACE
In this paper we study the fine-grained complexity of finding exact and ...
research
∙
04/18/2018
Optimal Deterministic Mechanisms for an Additive Buyer
We study revenue maximization by deterministic mechanisms for the simple...
research
∙
04/17/2018
An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
In this paper we study the adaptivity of submodular maximization. Adapti...
research
∙
03/02/2018
Hardness of Approximate Nearest Neighbor Search
We prove conditional near-quadratic running time lower bounds for approx...
research
∙
01/09/2018
99% Revenue via Enhanced Competition
A sequence of recent studies show that even in the simple setting of a s...
research
∙
11/08/2017