The TOC Student Seminar offers the opportunity for students to hear about the work of their peers, to learn about recent developments in theory and to practice their presentational skills. Plus there is free lunch. E-mail this term's organizer (Chris Peikert) with questions, to volunteer to provide food (you will be reimbursed), or to present a talk. Lunch will be served at 11:45; talks start at 12:00. Please do not eat lunch unless you plan on staying.
(You may also be interested in the previous term's seminar.)
Proposed Formats Include:
| Date | Subject | Speaker | Lunch Provided by |
| Feb. 9 | Random Subgraphs, Spanning Trees, and Reliability | Jan Vondrak | Chris and Grant |
| Feb. 16 | TBA | Alon Rosen, Adam Smith | Nicole and Taghi |
Jan Vondrak
Suppose that your network is prone to random failures, and every edge has a given cost. Every node can fail with probability $p$ (or alternatively, every edge can fail with probability $p$). Assume further that it is important for you to have the minimum spanning tree (MST) in the remaining subgraph. Can you find a small set of edges $Q$ which contains this MST with high probability? We find the asymptotically optimal size of set $Q$, and answer all possibly related questions. No open problems remain (except some difficult ones).
Alon Rosen, Adam Smith
Abstracts TBA