Michael Kapralov
where else to find them
no profile links on file
what they talk about
where they keep going back
- ITCS2 editions2022–2023
all 5 in the filters
on a stage with
- Amulya Musipatlaonce
- Arnold Filtseronce
- David P. Woodruffonce
all 6 in the filters
who talks about the same things
- David P. Woodruff18 talks
- Samson Zhou4 talks
- Gillat Kol5 talks
- Dmitry Paramonov3 talks
- Yuval Filmus9 talks
- Mark Braverman5 talks
| title | conference | date |
|---|---|---|
| Expander Decomposition in Dynamic Streams | ITCS 2023 | 2023-01-10 |
This work shows a dynamic-stream algorithm that produces an expander decomposition reaching the optimal ε–φ tradeoff while using O(n/φ^2) memory but requiring… | ||
| Noisy Boolean Hidden Matching with Applications | ITCS 2022 | 2022-01-31 |
Defines p-noisy Boolean hidden matching where each matching edge flips independently with probability p and proves the plaintext protocol is optimal, giving… | ||
| An Optimal Space Lower Bound for Approximating MAX-CUT | Sublinear Algorithms and Nearest-Neighbor Search | 2018-11-27 |
Shows that in the single-pass streaming model any algorithm that beats a trivial factor-2 for MAX-CUT (specifically any 2−ε approximation for constant ε>0)… | ||
| The Sketching Complexity of Graph and Hypergraph Counting | Interactive Complexity 2018 | 2018-10-15 |
Counts subgraphs in bounded-degree graphs using linear sketches and a colored vertex-sampling estimator, proving space Theta(m / T^{1/μ}) where μ is the… | ||
| Data Streams I | Foundations of Data Science Boot Camp 2018 | 2018-08-27 |
Shows that classic linear sketches (distinct‑elements, AMS) are applied to the graph edge‑incidence matrix to handle dynamic edge insertions and deletions… | ||
| Data Streams II | Foundations of Data Science Boot Camp 2018 | 2018-08-27 |
CountSketch is used to turn unbiased dot‑product estimators into a practical CountSketch with B≈10·K buckets and hash repetitions T=Θ(log n): each bucket… | ||
| Streaming Lower Bounds for Approximating MAX-CUT | Information Theory in Complexity Theory and Combinatorics 2015 | 2015-04-24 |
Proves any single-pass streaming algorithm that beats a trivial 2-approximation for MAX-CUT (achieving 2−ε) requires Ω(√n) space, even when edges arrive in a… | ||
| nothing matches | ||