6 citations · 14 across the 10 of their papers we have counts for
Showing 2010Show all
3 papers · 1 filter
cs.DS2010
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…
cs.DM2010★ 1 cited
Tight lower bounds for the size of epsilon-nets
János Pach, Gábor Tardos
According to a well known theorem of Haussler and Welzl (1987), any range space of bounded VC-dimension admits an $\eps$-net of size $O\left(\frac{1}{\eps}\log\frac1{\eps}\right)$.…
math.CO2010
Local chromatic number of quadrangulations of surfaces
Bojan Mohar, Gábor Simonyi, Gábor Tardos
The local chromatic number of a graph was introduced by Erdős et al. [4]. In [17] a connection to topological properties of (a box complex of) the graph was established and in [18]…