CS Theory at Northeastern

Home Courses Seminar

Computer Science Theory at Northeastern

Click here to subscribe to our mailing list.
Click here to subscribe to our Google Calendar.

Theory Seminar

This semester the theory seminar will be held on Wednesdays 12:40 - 2:10 PM, and is being co-organized by Sushant Agarwal, Rose Silver, and John Wilkins. Write to John with suggestions for speakers!

Spring Semester, 2024

Feb 14
12:40 PM
Hastings 209
Rebecca Lin
Graph Threading
Bio: Rebecca is a PhD student at MIT CSAIL, advised by Erik Demaine. Her research spans several areas, including theoretical computer science, computer graphics, and computational fabrication, with a unifying theme of geometry. This past summer, Rebecca was a visiting researcher at the Origami Lab led by Tomohiro Tachi at the University of Tokyo. Prior to her PhD, she earned her BSc in Computer Science at the University of British Columbia, during which she was fortunate to work with Will Evans, Craig Kaplan, and Alla Sheffer.
Abstract: Inspired by artistic practices such as beadwork and himmeli, we study the problem of threading a single string through a set of tubes, so that pulling the string forms a desired graph. More precisely, given a connected graph (where edges represent tubes and vertices represent junctions where they meet), we give a polynomial-time algorithm to find a minimum-length closed walk (representing a threading of string) that induces a connected graph of string at every junction. The algorithm is based on a surprising reduction to minimum-weight perfect matching. Along the way, we give tight worst-case bounds on the length of the optimal threading and on the maximum number of times this threading can visit a single edge.
Feb 7
12:40 PM
Hastings 209
Neha Makhija
Using ILPs and Flow Algorithms as a Unified Approach for (Reverse) Data Management Problems
Jan 17
12:40 PM
Hastings 209
Antonis Skarlatos
Dynamic algorithms for k-center on graphs
Jan 10
12:30 PM
Hastings 204
Jessie Finocchiaro
Theoretical ML

Fall Semester, 2023

Spring Semester, 2023

Fall Semester, 2022

Spring Semester, 2022

Fall Semester, 2021

Spring Semester, 2020

Fall Semester, 2019

Spring Semester, 2019

Fall Semester, 2018

Spring Semester, 2018

Fall Semester, 2017

Spring Semester, 2017

Fall Semester, 2016

Spring Semester, 2016

Fall Semester, 2015

Prehistorical Theory Seminars