Search Mailing List Archives
[theory-seminar] [theory-lunch] Cyrus Rashtchian on Edge Estimation with Independent Set Oracles
Hongyang Zhang
hongyang at cs.stanford.edu
Mon Mar 19 09:50:19 PDT 2018
Hi Everyone
This Thursday, Cyrus Rashtchian, who is visiting from UW, will tell us
about *Edge Estimation with Independent Set Oracles*. See abstract below.
As before, we meet from noon to 1pm at Gates 463a.
-----------------------------------------------------------------
Abstract:
I will explain recent results on estimating the number of edges in a graph
with access to only an independent set oracle. Independent set queries draw
motivation from group testing and have applications to the complexity of
decision versus counting problems. I will describe two algorithms to
estimate the number of edges in an n-vertex graph: one that uses only
polylog(n) bipartite independent set queries, and another one that uses
n^{2/3}polylog(n) independent set queries. There are many nice, accessible
open questions, such as estimating the number of triangles in a graph.
Joint work with Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan
Ramamoorthy, and Makrand Sinha
,
ITCS 2018 (https://arxiv.org/abs/1711.07567)
-----------------------------------------------------------------
Best,
Hongyang
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20180319/07fa2fa2/attachment-0001.html>
More information about the theory-seminar
mailing list