Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Space Efficient Approximation to Maximum Matching Size from Uniform Edge
  Samples   Given a source of iid samples of edges of an input graph $G$ with $n$
vertices and $m$ edges, how many samples does one need to compute a constant
factor approximation to the maximum matching size in $G$? Moreover, is it
possible to obtain such an estimate in a small amount of space? We show that,
on the one hand, this problem cannot be solved using a nontrivially sublinear
(in $m$) number of samples: $m^{1-o(1)}$ samples are needed. On the other hand,
a surprisingly space efficient algorithm for processing the samples exists:
$O(\log^2 n)$ bits of space suffice to compute an estimate.
  Our main technical tool is a new peeling type algorithm for matching that we
simulate using a recursive sampling process that crucially ensures that local
neighborhood information from `dense' regions of the graph is provided at
appropriately higher sampling rates. We show that a delicate balance between
exploration depth and sampling rate allows our simulation to not lose precision
over a logarithmic number of levels of recursion and achieve a constant factor
approximation. The previous best result on matching size estimation from random
samples was a $\log^{O(1)} n$ approximation [Kapralov et al'14].
  Our algorithm also yields a constant factor approximate local computation
algorithm (LCA) for matching with $O(d\log n)$ exploration starting from any
vertex. Previous approaches were based on local simulations of randomized
greedy, which take $O(d)$ time {\em in expectation over the starting vertex or
edge} (Yoshida et al'09, Onak et al'12), and could not achieve a better than
$d^2$ runtime. Interestingly, we also show that unlike our algorithm, the local
simulation of randomized greedy that is the basis of the most efficient prior
results does take $\wt{\Omega}(d^2)\gg O(d\log n)$ time for a worst case edge
even for $d=\exp(\Theta(\sqrt{\log n}))$.

10
The categories of this paper are: q-bio
24
The categories of this paper are: dg-ga
22
The categories of this paper are: chao-dyn
6
The categories of this paper are: astro-ph
21
The categories of this paper are: adap-org
7
The categories of this paper are: hep-th
34
The categories of this paper are: chem-ph
36
The categories of this paper are: cmp-lg
0
The categories of this paper are: hep-ph
9
The categories of this paper are: nlin
13
The categories of this paper are: quant-ph
29
The categories of this paper are: funct-an
4
The categories of this paper are: cond-mat
26
The categories of this paper are: bayes-an
28
The categories of this paper are: alg-geom
32
The categories of this paper are: atom-ph