Building Community Among Early-Career Researchers in Theoretical Computer Science

Early-career researchers in theoretical computer science presented novel algorithms, techniques, and data structures at the annual Junior Theorists Workshop, co-hosted by the Northwestern CS Theory Group and Toyota Technological Institute at Chicago (TTIC) on November 30 and December 1.

“As in past years, we had tomorrow's stars here to talk about some of the best work happening in theoretical computer science today,” said Samir Khuller, Peter and Adrienne Barris Chair of Computer Science at Northwestern Engineering. “We were delighted to co-host this event and have so many excellent speakers and visitors come and see what Northwestern and TTIC offer by way of research opportunities and collaboration opportunities.”

Dmitrii Avdiukhin, a postdoctoral scholar in computer science at the McCormick School of Engineering, and Santhoshini Velusamy, a research assistant professor at TTIC, organized the two-day workshop.

“This was a great workshop covering a large range of topics, including graph algorithms, learning theory, game theory, and machine learning,” Avdiukhin said. “It was a nice opportunity to communicate with excellent junior researchers, and I'm grateful to the speakers for their great talks.”

Launched by Northwestern CS in 2018, the annual Junior Theorists Workshop expanded two years ago with the partnership of TTIC. The event is held at Northwestern one day, and on the TTIC the next, providing an opportunity for researchers to visit and meet with faculty and students at both campuses.

"The event has been a great venue for junior researchers in theoretical computer science to showcase their wonderful research, said Aravindan Vijayaraghavan, an associate professor of computer science and (by courtesy) industrial engineering and management sciences at Northwestern Engineering.

Vijayaraghavan is Northwestern’s IDEAL site director.

"In addition to the excellent talks, the Junior Theorists Workshop is an opportunity for this cohort of top young researchers to get to know each other and to meet faculty at Northwestern and TTIC," said Avrim Blum, professor and chief academic officer at TTIC. "It is also a great excuse for those of us at TTIC and Northwestern to get together with each other."

Day 1 presenters:

• Bailey Flanigan (Carnegie Mellon University) – “The Power of Public Spirit in Voting”
• Max Hopkins (University of California, San Diego) – “Realizable Learning is All You Need”
• Lunjia Hu (Stanford University) – “A Unifying Theory of Distance from Calibration”
• Arun Jambulapati (Simons Institute) – “New Techniques in Accelerated Methods”
• Allen Liu (MIT) – “Learning Quantum Hamiltonians at Any Temperature in Polynomial Time”
• Georgy Noarov (University of Pennsylvania) – “High-Dimensional Prediction for Sequential Decision Making”
• Zihan Tan (Rutgers University) – “On (1+ε)-Approximate Flow Sparsifiers”
• Tegan Wilson (Cornell University) – “Optimal Oblivious Reconfigurable Networks”

Avdiukhin investigates convex and nonconvex optimization, machine learning, hierarchical clustering, and approximation algorithms. He is advised by Konstantin Makarychev, professor of computer science at Northwestern Engineering. Avdiukhin earned a PhD in computer science from Indiana University in 2023.

During a local researcher talk, Avdiukhin discussed “Optimal Sample Complexity of Contrastive Learning,” or the minimum number of labeled tuples — sequence data types — sufficient for getting high generalization accuracy. In joint work with Noga Alon (Princeton University), Dor Elboim (Institute for Advanced Study), Orr Fischer (Tel Aviv University), and Grigory Yaroslavtsev (George Mason University), Avdiukhin demonstrated that the theoretical bounds on sample complexity obtained via the Vapnik-Chervonenkis/Natarajan dimension can have strong predictive power for experimental results.

Day 2 presenters:

• Shyan Akmal (MIT) – “MAJORITY-3SAT (and Related Problems) in Polynomial Time”
• Linda Cai (Princeton University) – “Pandora’s Problem with Nonobligatory Inspection: Optimal Structure and a PTAS”
• Kate Donahue (Cornell University) – “Stability, Optimality, and Fairness in Federated Learning”
• He Jia (Georgia Institute of Technology) – “Robustly Learning Affine Transformations with Asymptotically Optimal Error”
• Han Shao (TTIC) – “Trustworthy Machine Learning under Social and Adversarial Data Sources”
• Shashank Srivastava (TTIC) – “List Decoding of Tanner Codes from Distance Certificates”
• Arsen Vasilyan (MIT) – “Testing Distributional Assumptions of Learning Algorithms”
• Thuy-Duong Vuong (Stanford University) – “Optimal sampling algorithms using entropic independence”
• Yinzhan Xu (MIT) – “Fredman’s Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More”

Santhoshini also presented her research in the local “Research at TTIC” talk. Her research focuses on the design and the analysis of algorithms in the streaming setting. She presented her work on the streaming approximability of constraint satisfaction problems, an infinite class of optimization problems which includes problems such as Max-CUT, Max-k-SAT, Unique Games, and several other problems of interest in computer science.

“One of the primary goals of the workshop was to encourage conversations and foster collaborations between researchers at Northwestern, TTIC, and junior researchers across the country who have been doing excellent research in recent years," Santhoshini said. "I’m very grateful that I had the opportunity to engage in illuminating discussions with many of our speakers and participants during the workshop."