
Does Preprocessing help in Fast Sequence Comparisons?
We study edit distance computation with preprocessing: the preprocessing...
read it

The Randomized Communication Complexity of Randomized Auctions
We study the communication complexity of incentive compatible auctionpr...
read it

BudgetSmoothed Analysis for Submodular Maximization
The greedy algorithm for submodular function maximization subject to car...
read it

Exponential Communication Separations between Notions of Selfishness
We consider the problem of implementing a fixed social choice function b...
read it

Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics
We consider the fundamental problem of selecting k out of n random varia...
read it

Settling the complexity of Nash equilibrium in congestion games
We consider (i) the problem of finding a (possibly mixed) Nash equilibri...
read it

Communication complexity of Nash equilibrium in potential games
We prove communication complexity lower bounds for (possibly mixed) Nash...
read it

The Strongish Planted Clique Hypothesis and Its Consequences
We formulate a new hardness assumption, the Strongish Planted Clique Hyp...
read it

A Simple Sublinear Algorithm for Gap Edit Distance
We study the problem of estimating the edit distance between two nchara...
read it

Smoothed Complexity of 2player Nash Equilibria
We prove that computing a Nash equilibrium of a twoplayer (n × n) game ...
read it

Asymmetric Streaming Algorithms for Edit Distance and LCS
The edit distance (ED) and longest common subsequence (LCS) are two fund...
read it

Streaming with Oracle: New Streaming Algorithms for Edit Distance and LCS
The edit distance (ED) and longest common subsequence (LCS) are two fund...
read it

Optimal SingleChoice Prophet Inequalities from Samples
We study the singlechoice Prophet Inequality problem when the gambler i...
read it

Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria
The use of monotonicity and Tarski's theorem in existence proofs of equi...
read it

Reducing approximate Longest Common Subsequence to approximate Edit Distance
Given a pair of strings, the problems of computing their Longest Common ...
read it

Constantfactor approximation of nearlinear edit distance in nearlinear time
We show that the edit distance between two strings of length n can be co...
read it

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...
read it

NearLinear Time InsertionDeletion Codes and (1+ε)Approximating Edit Distance via Indexing
We introduce fastdecodable indexing schemes for edit distance which can...
read it

NearOptimal Communication Lower Bounds for Approximate Nash Equilibria
We prove an N^2o(1) lower bound on the randomized communication complex...
read it

Finegrained Complexity Meets IP = PSPACE
In this paper we study the finegrained complexity of finding exact and ...
read it

Optimal Deterministic Mechanisms for an Additive Buyer
We study revenue maximization by deterministic mechanisms for the simple...
read it

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...
read it

Hardness of Approximate Nearest Neighbor Search
We prove conditional nearquadratic running time lower bounds for approx...
read it

99% Revenue via Enhanced Competition
A sequence of recent studies show that even in the simple setting of a s...
read it

Computing exact minimum cuts without knowing the graph
We give queryefficient algorithms for the global mincut and the st cu...
read it
Aviad Rubinstein
is this you? claim profile