Search Mailing List Archives


Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[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