Spring 2022 — Theory Thursdays

Location: Soda 606 (usually)

Time: Thursdays 17:00 - 18:00 (usually)

Theory Thursdays are stand-alone talks on interesting topics in TCS. If you’re interested in giving one, let an officer know!

Date	Topic	Resources
3/17	Siqi Liu: Finding planar drawings for planar graphs Abstract: In this short talk I will introduce the notion of graph Laplacian and show an algorithm that uses graph Laplacians to find planar drawings for planar graphs.	This talk is based on these notes by Dan Spielman
4/6	Nate Young: VLSI lower bounds Abstract: With the end of single-processor performance scaling and enormous popularity of very-high-compute applications like those in deep learning, there is more interest than ever in parallel computation and application-specific parallel hardware. Although parallel models like PRAMs are sometimes studied by theoreticians, these theoretical models fail to capture not only important constant factors but even some very important asymptotic costs incurred by real parallel computation. In this talk, I will give an introduction to a line of work that attempts to close this gap using theoretical models of integrated-circuit chips, and I will present a few asymptotic lower bounds on computation time and chip area using this much more realistic model.

Date

Topic

Resources

3/17

Siqi Liu: Finding planar drawings for planar graphs

Abstract: In this short talk I will introduce the notion of graph Laplacian and show an algorithm that uses graph Laplacians to find planar drawings for planar graphs.

This talk is based on these notes by Dan Spielman

4/6

Nate Young: VLSI lower bounds

Abstract: With the end of single-processor performance scaling and enormous popularity of very-high-compute applications like those in deep learning, there is more interest than ever in parallel computation and application-specific parallel hardware. Although parallel models like PRAMs are sometimes studied by theoreticians, these theoretical models fail to capture not only important constant factors but even some very important asymptotic costs incurred by real parallel computation. In this talk, I will give an introduction to a line of work that attempts to close this gap using theoretical models of integrated-circuit chips, and I will present a few asymptotic lower bounds on computation time and chip area using this much more realistic model.