Sepehr Assadi
where else to find them
what they talk about
where they keep going back
- ITCS2 editions2022–2023
all 6 in the filters
on a stage with
- Aaron Bernsteinonce
- Chen Wangonce
- Vihan Shahonce
all 4 in the filters
who talks about the same things
- Amin Saberi6 talks
- Shay Solomon3 talks
- Makrand Sinha5 talks
- Anindya De3 talks
- Ryan Williams18 talks
- Robert Krauthgamer3 talks
| title | conference | date |
|---|---|---|
| O(log log n) Passes is Optimal for Semi-Streaming Maximal Independent Set | Workshop on Local Algorithms (WoLA) 2024 | 2024-08-05 |
Shows an unconditional lower bound that any semi‑streaming algorithm that finds a maximal independent set with constant success probability requires Ω(log log… | ||
| Sublinear Insights: A Faster (Classical) Algorithm for Edge Coloring | Extroverted Sublinear Algorithms 2024 | 2024-06-17 |
Presents a randomized algorithm that outputs a Delta+O(log n) coloring in O(m log Delta) expected time, using ideas from McGregor (streaming) and… | ||
| Graph Coloring Through the Sublinear Lens | Sublinear Algorithms Boot Camp 2024 | 2024-05-21 |
Shows that sampling O(log n) colors per vertex from the Δ+1 palette suffices so the graph is list-colorable from those lists (called palette sparsification)… | ||
| New Advances on Multi-Pass Graph Streaming Lower Bounds | Sublinear Algorithms Boot Camp 2024 | 2024-05-21 |
Proves that semi‑streaming MIS needs Theta(log log n) passes by reducing bounded‑round communication to streaming, using round‑elimination on a matrix of… | ||
| A Simple (1−eps)-Approximation Adaptive Sketching Algorithm for Maximum (Weighted) Matching | Sketching and Algorithm Design 2023 | 2023-10-09 |
Presents a concrete algorithm that achieves a (1−ε)-approximation for weighted matching in general (non‑bipartite) graphs using O(log n / ε) rounds of adaptive… | ||
| All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method | ITCS 2023 | 2023-01-10 |
Algorithm gives a semi-streaming (O~(n) space) method that uses the multiplicative weights update method to reduce all-norm load balancing to an oracle solved… | ||
| Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions | ITCS 2022 | 2022-01-31 |
A constant-factor correlation clustering algorithm appears with only adjacency list of positive subgraph access: randomized algorithm runs in O(n log^2 n) time… | ||
| An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams | ITCS 2022 | 2022-01-31 |
An algorithm gives an alpha-approximate maximum matching in dynamic graph streams using n^2/alpha^3 bits of space (optimal up to constants) and works for alpha… | ||
| Sublinear Algorithms for (Delta + 1) Vertex Coloring | Sublinear Algorithms and Nearest-Neighbor Search | 2018-11-27 |
Claim: sampling O(log n) random colors per vertex (a palette sparsification) suffices, with high probability, to retain a Delta+1 coloring. Tools: use the HSS… | ||
| nothing matches | ||