2 citations · 5 across the 16 of their papers we have counts for
7 papers · 1 filter
Secretary, Prophet, and Stochastic Probing via Big-Decisions-First
Aviad Rubinstein, Sahil Singla
We revisit three fundamental problems in algorithms under uncertainty: the Secretary Problem, Prophet Inequality, and Stochastic Probing, each subject to general downward-closed co…
Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
Xiao Mao, Aviad Rubinstein
We present novel randomized approximation schemes for the Edit Distance (ED) problem and the Longest Common Subsequence (LCS) problem that, for any constant , compute a $(1+ε)…
Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani +1
How many adjacency matrix queries (also known as pair queries) are required to estimate the size of a maximum matching in an -vertex graph ? We study this fundamental questio…
Parallel Sampling via Counting
Nima Anari, Ruiquan Gao, Aviad Rubinstein
We show how to use parallelization to speed up sampling from an arbitrary distribution on a product space , given oracle access to counting queries: $\mathbb{P}_{X\sim μ…
Approximating Maximum Matching Requires Almost Quadratic Time
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
We study algorithms for estimating the size of maximum matching. This problem has been subject to extensive research. For -vertex graphs, Bhattacharya, Kiss, and Saranurak [FOCS…
Local Computation Algorithms for Maximum Matching: New Lower Bounds
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
We study local computation algorithms (LCA) for maximum matching. An LCA does not return its output entirely, but reveals parts of it upon query. For matchings, each query is a ver…
Approximate Earth Mover's Distance in Truly-Subquadratic Time
Lorenzo Beretta, Aviad Rubinstein
We design an additive approximation scheme for estimating the cost of the min-weight bipartite matching problem: given a bipartite graph with non-negative edge costs and $\varepsil…