Search Mailing List Archives
[theory-seminar] Theory Lunch -- Bruce Spang
Reyna Marie Hulett
rmhulett at stanford.edu
Tue Oct 16 15:30:13 PDT 2018
P.S. Theory lunch is on Thursday, oops.
________________________________
From: theory-seminar <theory-seminar-bounces at lists.stanford.edu> on behalf of Reyna Marie Hulett <rmhulett at stanford.edu>
Sent: Tuesday, October 16, 2018 2:27:53 PM
To: theory-seminar at lists.stanford.edu; thseminar at cs.stanford.edu
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!
===========================================================
Abstract:
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.
===========================================================
Cheers,
-Reyna
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20181016/2aa83a9f/attachment-0003.html>
More information about the theory-seminar
mailing list