Soheil Behnezhad
where else to find them
no profile links on file
what they talk about
where they keep going back
no series more than once — all 3 in the filters
on a stage with
never shared a talk
who talks about the same things
nobody close enough yet
| title | conference | date |
|---|---|---|
| Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams | Managing Memory 2025 | 2025-09-29 |
Claims the pass complexity is settled: an algorithm uses log log n passes and n·polylog n space to produce a constant‑approximate matching (roundable to 1+ε)… | ||
| Recent Progress on Sublinear Time Algorithms for Maximum Matching: Upper Bounds | Dynamic Graphs and Algorithm Design (Simons Institute, 2023) | 2023-09-18 |
Recent claims: estimating maximum matching size can run sublinearly and feed fast dynamic algorithms. Concrete results include a greedy oracle that decides… | ||
| Recent Progress on Sublinear Time Algorithms for Maximum Matching: Lower Bounds | Dynamic Graphs and Algorithm Design (Simons Institute, 2023) | 2023-09-18 |
Proves a concrete hardness: any better-than-2/3 approximation to maximum matching in the adjacency‑list model requires about n^{1.2} queries by building a… | ||
| Stochastic Matching with Few Queries | Platform Markets 2019 | 2019-09-16 |
Non-adaptive algorithm draws R independent sampled realizations, takes a maximum matching from each, and queries the union; R is poly(1/p) so maximum degree… | ||
| nothing matches | ||