1 citations · 1 across the 4 of their papers we have counts for
4 papers · 1 filter
An Estimator for Matching Size in Low Arboricity Graphs with Two Applications
Hossein Jowhari
In this paper, we present a new simple degree-based estimator for the size of maximum matching in bounded arboricity graphs. When the arboricity of the graph is bounded by , the…
The Sparse Awakens: Streaming Algorithms for Matching Size Estimation in Sparse Graphs
Graham Cormode, Hossein Jowhari, Morteza Monemizadeh +1
Estimating the size of the maximum matching is a canonical problem in graph algorithms, and one that has attracted extensive study over a range of different computational models. W…
A Second Look at Counting Triangles in Graph Streams (revised)
Graham Cormode, Hossein Jowhari
In this paper we present improved results on the problem of counting triangles in edge streamed graphs. For graphs with edges and at least triangles, we show that an extra…
Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems
Hossein Jowhari, Mert Sağlam, Gábor Tardos
In this paper, we present near-optimal space bounds for Lp-samplers. Given a stream of updates (additions and subtraction) to the coordinates of an underlying vector x \in R^n, a p…