research
∙
01/25/2023
EFX Exists for Four Agents with Three Types of Valuations
In this paper, we address the problem of determining an envy-free alloca...
share
research
∙
10/25/2021
Parameterized Convexity Testing
In this work, we develop new insights into the fundamental problem of co...
research
∙
09/17/2021
Sublinear-Time Computation in the Presence of Online Erasures
We initiate the study of sublinear-time algorithms that access their inp...
research
∙
06/09/2021
Strongly Sublinear Algorithms for Testing Pattern Freeness
Given a permutation π:[k] → [k], a function f:[n] →ℝ contains a π-appear...
research
∙
11/29/2020
Erasure-Resilient Sublinear-Time Graph Algorithms
We investigate sublinear-time algorithms that take partially erased grap...
research
∙
10/12/2020
New Sublinear Algorithms and Lower Bounds for LIS Estimation
Estimating the length of the longest increasing subsequence (LIS) in an ...
research
∙
04/05/2019
Average Sensitivity of Graph Algorithms
In modern applications of graphs algorithms, where the graphs of interes...
research
∙
05/12/2018