Showcasing Early-Career Researchers in Theoretical Computer Science

The Northwestern CS Theory Group and Toyota Technological Institute at Chicago co-hosted the Junior Theorists Workshop on January 5-6

Building community among early-career researchers in theoretical computer science, postdoctoral researchers and PhD students presented novel algorithms, techniques, and data structures at the annual Junior Theorists Workshop on January 5-6, co-hosted by the Northwestern CS Theory Group and Toyota Technological Institute at Chicago (TTIC).

Samir Khuller“The Junior Theorists Workshop has become an amazing showcase event to see tomorrow's super star postdocs and graduate students today,” said Samir Khuller, Peter and Adrienne Barris Chair of Computer Science at Northwestern Engineering. “The selection of talks, overall organization and selection of topics gave a broad-spectrum view of cutting-edge results from the next generation of researchers in theoretical computer science.”

Local researcher talks

Sami Davies and Quanquan Liu, postdoctoral fellows in theoretical computer science at the McCormick School of Engineering; Liren Shan, a fifth-year PhD student in the Northwestern CS Theory Group; and Yiding Feng (CS PhD ’21), a postdoctoral researcher at Microsoft Research – New England, presented local researcher talks.

Davies, a CIFellow advised by Khuller, discussed the application of learning-augmented algorithms to the maximum flow problem. Davies and collaborators Benjamin Moseley (Carnegie Mellon University), Sergei Vassilvitskii (Google), and Yuyan Wang (Google Brain), improved the performance of the widely used Ford-Fulkerson algorithm for computing maximum flows by seeding Ford-Fulkerson with predicted flows.

Liu, also advised by Khuller, studies algorithms for large data, graph algorithms, algorithms and data structures, and parallel/high performance computing. She presented joint work on differential privacy with collaborators Laxman Dhulipala (University of Maryland, College Park and Google Research); Sofya Raskhodnikova (Boston University); and Jessica Shi, Julian Shun, and Shangdi Yu (MIT). Liu discussed local edge differentially private algorithms for k-core decomposition, low out-degree ordering, and densest subgraph.

Shan studies approximation algorithms, graph theory, and algorithmic game theory.
He demonstrated his proof of a new generalization of the higher-order Cheeger inequality for partitioning with buffers — research Shan conducted with adviser Konstantin Makarychev, professor of computer science at Northwestern Engineering; Yury Makarychev, professor at TTIC; and Aravindan Vijayaraghavan, associate professor of computer science and (by courtesy) industrial engineering and management sciences at Northwestern Engineering. The team’s inequality is constructive and avoids the “square-root loss” that is present in the standard Cheeger inequalities. They also propose a complementary lower bound.

Feng, who was advised by Jason Hartline, professor of computer science at Northwestern Engineering, studies online decision making, online resource allocation, online learning, mechanism and information design, and optimization. He discussed joint work with Rad Niazadeh (University of Chicago) on the optimal trade-off between batching and inefficiency in the context of designing robust online allocations. The team is developing algorithmic tools to vary the trade-off between greediness and hedging of the matching algorithm across stages.

Aravindan Vijayaraghavan“The Junior Theorists Workshop was started four years ago because there weren't many venues for junior researchers to showcase their wonderful research,” Vijayaraghavan said. “It is great to see the workshop expand and grow in strength under the joint organization of Northwestern, TTIC and IDEAL.”

Showcasing perspectives in theoretical CS

Suprovat Ghoshal, a joint postdoctoral researcher advised by Konstantin and Yury Makarychev, and Ali Vakilian, a research assistant professor at TTIC and a former postdoc with the Institute for Data, Econometrics, Algorithms, and Learning (IDEAL), organized the workshop.

“The workshop was a wonderful opportunity to interact and network with up-and-coming researchers in TCS,” Ghoshal said. “As an organizer, I also got a chance to understand the various steps that need to come together in these workshops. All-in-all, it was a great learning experience.”

Hartline and Avrim Blum, professor and chief academic officer at TTIC, managed the speaker selection process.

“The Chicago Junior Theorists Workshop, which we organized jointly with Northwestern, was a fantastic opportunity to see presentations on cutting-edge research in theoretical computer science from some of today's top young stars in the field,” Blum said. “From core questions about the nature of computation, to tools and frameworks for advancing social issues in computing, these researchers showed some of the latest questions being investigated and gave a glimpse at the exciting future this field has to offer.”

Additional workshop presenters included:

Jason Hartline“This was a really excellent workshop highlighting the research of an incredibly strong batch of junior computer science theorists,” Hartline said. “It was great to get a taste for what is happening at the forefront of many diverse subareas of theoretical computer science and also get to meet the rising stars of the field. Ali and Suprovat did a great job with the program and the administrative team Mary and Xiaolin made both days run seamlessly.”

McCormick News Article