[theory students] Theory seminar today! 10-11am in CS 4310 (special time)

[Sandeep Silwal <silwal@xxxxxxxxxxx>]

Hi everyone, 

Today we have Tegan Wilson visiting from Northeastern. Due to time restrictions, the seminar will be 10-11am in CS 4310.

Title: Breaking the VLB Barrier for Oblivious Reconfigurable Networks

Abstract: 
Valiant Load Balancing (VLB) has a long history in both the theory and practice of oblivious routing. Even after forty years, VLB continues to take center stage as a widely used â and in some settings, provably optimal â way to balance load in the network obliviously to the traffic demands. However, the ability of the network to rapidly reconfigure its interconnection topology gives rise to new possibilities.

In this work we revisit the question of whether VLB remains optimal in the novel setting of reconfigurable networks. Prior work [AWSWKAâ22] showed that VLB achieves the optimal tradeoff between latency and guaranteed throughput. In this work, we show that a strictly superior latency-throughput tradeoff is achievable when the throughput bound is relaxed to hold with high probability. Our results are enabled by a novel oblivious routing scheme that improves VLB by stretching routing paths the minimum possible amount â an additive stretch of 1 rather than a multiplicative stretch of 2 â yet still manages to balance load with high probability when either the traffic demand matrix or the networkâs interconnection schedule are shuffled by a uniformly random permutation.
 
This talk is based on joint work with Daniel Amir, Nitika Saran, Robert Kleinberg, Vishal Shrivastav, and Hakim Weatherspoon. 
 
Bio: Tegan is a Distinguished Postdoc at Northeastern working under Rajmohan Rajaraman. She received her PhD from Cornell University and was advised by Robert Kleinberg. Her recent work has focused on network and routing design for reconfigurable datacenter networks. Her website is here: https://teganwilson.github.io/

See you there!

Sandeep