Search Mailing List Archives
[theory-seminar] Theory Lunch -- Bruce Spang
Reyna Marie Hulett
rmhulett at stanford.edu
Tue Oct 16 14:27:53 PDT 2018
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...
More information about the theory-seminar