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 -- Bruce Spang

Reyna Marie Hulett rmhulett at
Tue Oct 16 15:30:13 PDT 2018

P.S. Theory lunch is on Thursday, oops.

From: theory-seminar <theory-seminar-bounces at> on behalf of Reyna Marie Hulett <rmhulett at>
Sent: Tuesday, October 16, 2018 2:27:53 PM
To: theory-seminar at; thseminar at
Subject: [theory-seminar] Theory Lunch -- Bruce Spang

Hi all,

This week in theory lunch, Bruce will talk to us about "Unconstraining Graph-Constrained Group Testing." As always, please join us from noon to 1 pm in Gates 463A!

In network tomography, one goal is to find a small set of failed links in a network by sending a few packets through the network and seeing which reach their destination. This can be seen as a variant of combinatorial group testing, which has been studied before under the moniker "graph-constrained group testing."

I will discuss some of our recent work on this problem, in which we show that for many graphs, the “constraints” imposed by the underlying graph are no constraint at all. That is, for many graphs it is possible to identify the failed links in the “graph-constrained” group testing problem with a number of tests which is near-optimal even for the group testing problem with no graph constraints.

Based on joint work with Mary Wootters.


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

More information about the theory-seminar mailing list