Sotabase

Career

· Associate Professor, University of Waterloo2024–

Publications (119)

Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs
ACM-SIAM Symposium on Discrete Algorithms · 2017
129
cited
Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model
ACM-SIAM Symposium on Discrete Algorithms · 2016
117
cited
Sublinear Algorithms for (∆ + 1) Vertex Coloring (cid:3)
2018
113
cited
Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons
Annual Conference Computational Learning Theory · 2017
96
cited
On Estimating Maximum Matching Size in Graph Streams
ACM-SIAM Symposium on Discrete Algorithms · 2017
95
cited
A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
Information Technology Convergence and Services · 2018
76
cited
Fully dynamic maximal independent set with sublinear update time
Symposium on the Theory of Computing · 2018
71
cited
Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing · 2018
59
cited
The Stochastic Matching Problem with (Very) Few Queries
ACM Trans. Economics and Comput. · 2019
59
cited
Tight bounds for single-pass streaming complexity of the set cover problem
Symposium on the Theory of Computing · 2016
53
cited
Online Assignment of Heterogeneous Tasks in Crowdsourcing Markets
AAAI Conference on Human Computation & Crowdsourcing · 2015
51
cited
Towards a Unified Theory of Sparsification for Matching Problems
SIAM Symposium on Simplicity in Algorithms · 2018
51
cited
Randomized Composable Coresets for Matching and Vertex Cover
ACM Symposium on Parallelism in Algorithms and Architectures · 2017
50
cited
Beating Two-Thirds For Random-Order Streaming Matching
International Colloquium on Automata, Languages and Programming · 2021
42
cited
Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems
IEEE Annual Symposium on Foundations of Computer Science · 2020
42
cited
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders
IEEE Annual Symposium on Foundations of Computer Science · 2019
41
cited
Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
ACM-SIAM Symposium on Discrete Algorithms · 2018
40
cited
Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions
Information Technology Convergence and Services · 2021
37
cited
Polynomial pass lower bounds for graph streaming algorithms
Symposium on the Theory of Computing · 2019
33
cited
Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma
Symposium on the Theory of Computing · 2021
32
cited
Sotabase
Sepehr Assadi | Researcher Profile | Sotabase | Sotabase