Resource-Competitive Broadcast

Posted on Sep 25, 2014

Date: Thursday, September 25, 2014
Time: 11:00 – 12:15 PM
Place: Dane Smith Hall 125

Maxwell Young,
Department of Computing
Drexel University

We consider the problem of broadcasting a message from a sender to n >= 1 receivers in a time-slotted, single-hop, wireless network with a single communication channel. Sending and listening dominate the energy usage of small wireless devices and this is abstracted as a unit cost per time slot. A jamming adversary exists who can disrupt the channel at unit cost per time slot, and aims to prevent the transmission of the message. Let T be the number of slots jammed by the adversary. Our goal is to design algorithms whose cost is resource-competitive, that is, whose per-device cost is a function, preferably o(T), of the adversary’s cost. Devices must work without knowledge of n,T, or the adversary’s jamming strategy.

Short Bio:
Maxwell Young is an Assistant Professor in the Department of Computing at Drexel University. Before moving to Philadelphia, he held postdoctoral positions at the University of Michigan and at the National University of Singapore, and he earned his Ph.D. in computer science at the University of Waterloo, Canada. His research interests include security and distributed computing.

Watch Colloquium: 

Read More

Phase Transitions In Approximate Counting

Posted on Sep 22, 2014

Date: Thursday, September 18, 2014
Time: 11:00 — 12:15 PM
Place: Dane Smith Hall 125

Eric Vigoda,
College of Computing,
Georgia Tech

This talk will give an overview of recent results establishing connections between the complexity of approximate counting problems and phase transitions in statistical physics. I will focus on recent work (with A. Galanis and D. Stefankovic in STOC ’14) showing hardness results for approximately counting colorings. The key tool is a simplified approach for the analysis of spin systems on random regular graphs.

Eric Vigoda is a Professor of Computer Science at the Georgia Institute of Technology. He received his PhD from UC Berkeley in 1999. He was a faculty member at the University of Chicago from 2002-2004, and then moved to Georgia Tech in 2004. He was awarded a Fulkerson prize in 2006 (with A. Sinclair and M. Jerrum) for their work on approximating the permanent of a non-negative matrix.

Watch Colloquium:


Read More