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 stanford.edu
Tue Oct 16 14:27:53 PDT 2018


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/e73e4158/attachment-0003.html>


More information about the theory-seminar mailing list