| Publication | Date of Publication | Type |
|---|
| Beating two-thirds for random-order streaming matching | 2026-05-12 | Paper |
Simple sublinear algorithms for (+1) vertex coloring via asymmetric palette sparsification
TheoretiCS | 2026-02-13 | Paper |
| Polynomial pass semi-streaming lower bounds for k-cores and degeneracy | 2026-01-28 | Paper |
Tight bounds for monotone minimal perfect hashing
ACM Transactions on Algorithms | 2025-11-03 | Paper |
Rounds vs. communication tradeoffs for maximal independent sets
SIAM Journal on Computing | 2025-10-24 | Paper |
A simple (1-)-approximation semi-streaming algorithm for maximum (weighted) matching
TheoretiCS | 2025-10-22 | Paper |
Improved truthful mechanisms for combinatorial auctions with submodular bidders
SIAM Journal on Computing | 2025-09-16 | Paper |
| Hidden permutations to the rescue: multi-pass streaming lower bounds for approximate matchings | 2025-08-15 | Paper |
| Rounds vs communication tradeoffs for maximal independent sets | 2025-08-15 | Paper |
| Multi-pass graph streaming lower bounds for cycle counting, MAX-CUT, matching size, and other problems | 2025-08-12 | Paper |
| Near-quadratic lower bounds for two-pass graph streaming algorithms | 2025-08-12 | Paper |
| Improved truthful mechanisms for combinatorial auctions with submodular bidders | 2025-08-12 | Paper |
| On constructing spanners from random Gaussian projections | 2025-01-14 | Paper |
| Evaluating stability in massive social networks: efficient streaming algorithms for structural balance | 2025-01-14 | Paper |
| Generalizing Greenwald-Khanna streaming quantile summaries for weighted inputs | 2024-10-08 | Paper |
| All-norm load balancing in graph streams via the multiplicative weights update method | 2024-09-25 | Paper |
| Towards a unified theory of sparsification for matching problems | 2024-08-26 | Paper |
| Asymptotically optimal bounds for estimating \(h\)-index in sublinear time with applications to subgraph counting | 2024-08-22 | Paper |
| Semi-streaming bipartite matching in fewer passes and optimal space | 2024-07-19 | Paper |
| A two-pass (conditional) lower bound for semi-streaming maximum matching | 2024-07-19 | Paper |
Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
TheoretiCS | 2024-07-03 | Paper |
| Decremental matching in general graphs | 2024-06-24 | Paper |
| A simple (1- )-approximation semi-streaming algorithm for maximum (weighted) matching | 2024-05-29 | Paper |
| Tight bounds for monotone minimal perfect hashing | 2024-05-14 | Paper |
| An auction algorithm for bipartite matching in streaming and massively parallel computation models | 2024-05-14 | Paper |
| A simple semi-streaming algorithm for global minimum cuts | 2024-05-14 | Paper |
| Tight bounds for vertex connectivity in dynamic streams | 2024-05-14 | Paper |
| On regularity lemma and barriers in streaming and dynamic matching | 2024-05-08 | Paper |
| (Noisy) gap cycle counting strikes back: random order streaming lower bounds for connected components and beyond | 2024-05-08 | Paper |
scientific article; zbMATH DE number 7829241 (Why is no real title available?)
(available as arXiv preprint) | 2024-04-09 | Paper |
scientific article; zbMATH DE number 7788378 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
Brooks’ theorem in graph streams: a single-pass semi-streaming algorithm for ∆-coloring
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
| Ruling Sets in Random Order and Adversarial Streams | 2023-12-08 | Paper |
| On the Robust Communication Complexity of Bipartite Matching | 2023-11-20 | Paper |
Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
| Improved bounds for distributed load balancing | 2023-11-02 | Paper |
Introduction to the Special Issue on ACM-SIAM Symposium on Discrete Algorithms (SODA) 2020
ACM Transactions on Algorithms | 2023-10-31 | Paper |
scientific article; zbMATH DE number 7758308 (Why is no real title available?)
(available as arXiv preprint) | 2023-10-31 | Paper |
Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach.
(available as arXiv preprint) | 2023-09-20 | Paper |
Graph connectivity and single element recovery via linear and OR queries
(available as arXiv preprint) | 2023-09-20 | Paper |
When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
(available as arXiv preprint) | 2022-07-21 | Paper |
A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
(available as arXiv preprint) | 2022-07-18 | Paper |
Separating the communication complexity of truthful and nontruthful algorithms for combinatorial auctions
SIAM Journal on Computing | 2022-04-20 | Paper |
Tight bounds for single-pass streaming complexity of the set cover problem
SIAM Journal on Computing | 2021-06-29 | Paper |
Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets
Proceedings of the 39th Symposium on Principles of Distributed Computing | 2021-03-15 | Paper |
Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing | 2021-01-20 | Paper |
Separating the communication complexity of truthful and non-truthful combinatorial auctions
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
Exploration with limited memory: streaming algorithms for coin tossing, noisy comparisons, and multi-armed bandits
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
Polynomial pass lower bounds for graph streaming algorithms
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Sublinear algorithms for ( + 1) vertex coloring
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Stochastic submodular cover with limited adaptivity
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Fully Dynamic Maximal Independent Set with Sublinear in <i>n</i> Update Time
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Fully dynamic maximal independent set with sublinear update time
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
On estimating maximum matching size in graph streams
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
| Tight bounds on the round complexity of the distributed maximum coverage problem | 2018-03-15 | Paper |
Tight bounds on the round complexity of the distributed maximum coverage problem
(available as arXiv preprint) | 2018-03-15 | Paper |
Tight bounds for single-pass streaming complexity of the set cover problem
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
On the rectangle escape problem
Theoretical Computer Science | 2017-09-07 | Paper |
Algorithms for provisioning queries and analytics
(available as arXiv preprint) | 2017-07-14 | Paper |
Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches
(available as arXiv preprint) | 2017-07-13 | Paper |
Fast convergence in the double oral auction
Web and Internet Economics | 2016-01-08 | Paper |
The minimum vulnerability problem
Algorithmica | 2015-01-19 | Paper |
The minimum vulnerability problem
Algorithms and Computation | 2013-03-21 | Paper |
