TCS for All Meeting 2024 Program

Monday, June 24, 2024

12:30 pm – 1:30 pm PDT: Inspirational Talk by Luca Trevisan (Bocconi University)

1:30 pm – 2 pm PDT: Ask Me Anything Panel

4:15 pm- 5:30 pm PDT: Rising Stars Talks

4:15 pm: Mitali Bafna (MIT)

4:40 pm: Shunhua Jiang (Columbia University)

5:05 pm: Dhara Thakkar (IIT Gandhinagar)

Talks and speakers info:

Inspirational Talk

Luca Trevisan (Bocconi University)

Bio: Luca Trevisan was an Italian professor of computer science at Bocconi University in Milan. Trevisan received his PhD from La Sapienza University in Rome. He held assistant professor positions at Columbia University, the University of California, Berkeley, and Stanford University before joining the Department of Decision Sciences at Bocconi University.

Luca’s research focused on theoretical computer science, particularly computational complexity, algorithm analysis, the foundations of cryptography, and intersections between theoretical computer science and pure mathematics. He was a Fellow of the ACM and a member of the Accademia Nazionale delle Scienze Detta dei XL, the Italian National Academy of Science. Among his many accolades, he received the Oberwolfach Prize in 2000, the Sloan Fellowship in 2000, and the NSF CAREER Award. He was also an invited speaker at the 2006 International Congress of Mathematicians and received an ERC Advanced Grant in 2019.

Rising Stars

Mitali Bafna

Title: High Dimensional Expansion and Applications to Direct Product Testing

Abstract: The study of high-dimensional expanders (HDX) in recent years has found many applications in TCS, particularly in the areas of approximate sampling and coding theory. In this talk, we will discuss one such application to the direct product testing problem, which intersects various areas such as PCPs, hardness amplification, and property testing.

Given a set system S, containing various k-sized subsets of [n], the direct product (DP) encoding of a function f: [n] \to {0,1} using S, is the function DP(f): S \to {0,1}^k which, for every set s in S, gives the restriction of f to the set s. The local testing question for a given set system then asks whether one can locally test whether a given function table F: S -> {0,1}^k is close to DP(f) for some f.

A particularly interesting regime of parameters is when |S| = O(n) (the “sparse regime”), where the test is only allowed to query the function F in two places, and the probability of the test accepting is low (the “low soundness regime”). Using tools from HDX, we show that there is a sparse set system S supporting a direct product test in the low soundness regime, resolving a conjecture by Dinur and Kaufman.

In this talk, I will discuss high-dimensional expanders, and their application to the direct product testing problem, and conclude with their relevance to PCPs.

Bio: Mitali Bafna is a postdoc at MIT Math. Before this, she was a postdoc at CMU hosted by Prof. Aayush Jain and Prof. Pravesh Kothari. She graduated from Harvard advised by Prof. Madhu Sudan and was an undergrad at IIT Madras. Her research focuses on complexity theory and algorithms, particularly the complexity of combinatorial optimization problems, the sum of squares algorithms, and high-dimensional expanders.

Shunhua Jiang

Abstract: The latest progress in optimization relies on exploiting dynamic data structures to reduce the cost-per-iteration of iterative algorithms. This new framework has already led to algorithmic breakthroughs on many decade-old optimization problems, from maxflow and matching to semidefinite programming (SDP). 

In this talk, we will discuss some of the recent developments for speeding up Interior Point Methods (IPMs) for linear programming (LP). These results almost match the time required to solve a single linear system.

Bio: Shunhua Jiang is a PhD student in the theoretical computer science group at Columbia University under the supervision of Prof. Omri Weinstein and Prof. Alexandr Andoni. Previously she obtained her bachelor’s degree from Yao class at Tsinghua University. Her main research interests are optimization and data structures, while she is also broadly interested in other problems in theory and machine learning.

Dhara Thakkar

Title: On Computing Optimal Representations of Finite Groups

Abstract: There are several ways to represent a group as an input to an algorithm, including the generator-relator representation, the matrix group representation, the black box group representation, the Cayley table representation, and the permutation group representation. While studying algorithms for group theoretical problems, it is natural to study efficient representations of groups. 

In this talk, I will discuss three optimal representations of finite groups. More specifically, 1. I will present a constant query-time data structure that can store any finite group using only O(n) words, where n denotes the order of the group. 2. I will also present a polynomial time algorithm to find a minimum generating set of a group.

Bio: Dhara Thakkar is a final year Ph.D student at the Indian Institute of Technology Gandhinagar. Prior to this, she completed her M.Phil and master’s degree in mathematics. Her research interests include algebraic computations, algebraic complexity theory, algebraic combinatorics, graph theory, and parameterized complexity. Dhara will soon join Nagoya University as a postdoctoral researcher under the mentorship of Prof. François Le Gall.