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
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.

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 (

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list