[theory students] Theory seminar this Friday from a visitor (different time)

[Sandeep Silwal <silwal@xxxxxxxxxxx>]

Hi everyone, 

This Friday we have Tegan Wilson visiting from Northeastern. Due to time restrictions, the seminar will be 10-11am in CS 4310. If you would like to meet with her, please sign up at https://docs.google.com/spreadsheets/d/1_r5q7EebsDw0EmxSfd6eSqLLqheO07KPRCAEgFjQeXA/edit?usp=sharing. 

I am also looking for 1-2 students to take Tegan to lunch on Friday. The lunch will be covered so pls let me know if you are interested!

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/

Best,
Sandeep