We are excited to announce that the 2021 TCS Women Inspirational Talk will be by Prof. Cynthia Dwork (Harvard University).

#### TCS Women Spotlight Workshop

The workshop will feature an inspirational talk by a senior researcher and short Rising Stars talks by senior graduate students and postdocs. **The workshop registration is free of charge. All are welcome to attend.**

- Date: June 22nd, 2021
- Location: Room A
- 9:00 am–11 am(EDT):
**Rising Stars Talks**- 9:00am:
Prerona Chatterjee (
**Title:**Lower Bounds in Algebraic Circuit Complexity) [VIDEO] - 9:15am: Sophie Huiberts (
**Title:**Why Can We Solve (Integer) Linear Programs?) [VIDEO] - 9:30am: Sandra Kiefer (
**Title:**Identifying Graphs by Playing with Pebbles: How Long Does It Take?) (Video coming soon) - 9:45am: Sumegha Garg (
**Title:**Tight Space Complexity of the Coin Problem) [VIDEO] - 10:00am: Audra McMillan (
**Title:**Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling ) (No Video Available) - 10:15am: Omrit Filtser (
**Title:**Proximity search in trajectory data under the Fréchet distance) [VIDEO] - 10:30am: Arpita Biswas (
**Title:**Fair Allocation under Matroid Constraints) [VIDEO] - 10:45am: 15-minute break

- 9:00am:
Prerona Chatterjee (
- 11 am–12:00 pm (EDT):
**Inspirational talk**Prof. Cynthia Dwork (**Title:**Research. Results. Rejection. Redemption!) (No video available)

**Speaker and Talk Details**

**2021 TCS Women Inspirational Talk by**

** Prof. Cynthia Dwork** (Harvard University)

**Title:** Research. Results. Rejection. Redemption!

**Abstract:**

**Bio**:

**Rising Stars** **Talk Information**

**Arpita Biswas** (Harvard University)

**Title:** Fair Allocation under Matroid Constraints

**Abstract**: Fair allocation of indivisible goods is an exciting topic since it presents challenging theoretical problems and finds applications in several real-world scenarios. A substantial body of work has focused on the unconstrained version of the fair allocation problem leaving many open questions in the constrained setting. In this talk, I’ll focus on a part of my doctoral dissertation that investigates fair allocation under matroid constraints. First, I’ll deep dive into a simple set system, called partition matroid. In this setting, the set of goods are grouped into disjoint categories and a limit (cardinality constraint) is specified on the number of goods that can be allocated from each category to any agent. The objective is to find a fair allocation in which the bundle allocated to any agent satisfies the given cardinality constraints. This problem is a generalization of the well-studied (unconstrained) fair allocation problem. The two central notions of fairness, in the context of allocation of indivisible goods, are envy freeness up to one good (EF1) and the maximin share guarantee (MMS). I’ll talk about the existence and algorithmic guarantees for these solution concepts under cardinality constraints. In particular, I’ll show that EF1 and 1/3-MMS allocations exist and can be computed in polynomial time. Furthermore, I’ll talk about the existence of fair solutions under a more general class of matroid constraints. These results provide a deep understanding of the fair allocation problem under matroid constraints.

**Bio: **Arpita Biswas is a postdoctoral fellow at the School of Engineering and Applied Sciences, Harvard University. Her research is supported by a Harvard CRCS Postdoctoral Fellowship. She is presently working on problems related to algorithmic fairness and sequential decision-making under limited resources with applications to socially impactful problems arising in healthcare and wildlife conservation domains. Before joining Harvard, she held a Visiting Researcher position at Google Research. Prior to joining Google, she received her Ph.D. at the Department of Computer Science and Automation, the Indian Institute of Science. During her Ph.D., she was a recipient of a Google Ph.D. Fellowship award (2006-2020). Her Ph.D. dissertation investigates important classes of the fair allocation problem with indivisible goods, defines appropriate fairness notions, establishes existence guarantees, and provides algorithms for obtaining fair allocations. Additionally, her thesis leverages these solution concepts to define fairness and provide solutions in diverse application domains, such as recommendation and classification.

Her primary areas of interest include Algorithmic Game Theory, Optimization, and Machine Learning—in particular, multi-agent learning, fair allocation, decision making under uncertainty, incentive mechanisms, etc. Thus far, she has worked on problems arising from real-world scenarios such as intervention planning for public health programs, resource allocation, online crowdsourcing, dynamic pricing in transportation, and ride-sharing.

**Prerona Chatterjee** (TIFR Mumbai)

**Title:** Lower Bounds in Algebraic Circuit Complexity

**Abstract:**Algebraic circuits and formulas are the standard computational models for computing multivariate polynomials. They are similar to boolean circuits and formulas except that in this case, gates are labelled by ‘+’ (addition) or ‘x’ (multiplication). Another important model is that of an algebraic branching program (ABP), which is an intermediate model between circuits and formulas in terms of computational power. I will begin the talk by defining these models of computation formally, and then survey some of the breakthrough results that have helped shape our understanding of algebraic circuits. I will then mention some of the recent projects that I have been part of.

1. Even though very strong lower bounds are known against various structured models, the best known lower bound against general algebraic circuits is barely super-linear [Str73, BS83]. This was also the best known bound against ABPs. On the other hand, against formulas, the best known lower bound was \Omega(n^2/log n) [Kal85, SY11] for multilinear polynomials (which is the interesting case). We improve the bounds for ABPs and formulas by showing a quadratic lower bound against both these models. This is joint work with Mrinal Kumar, Adrian She and Ben Lee Volk (appeared in CCC 2020).

2. As we just saw, very strong lower bounds are known against structured models but against general models, the lower bounds known are extremely weak. Therefore there has been some recent work [FSV18, GKSS17] on whether the “natural” proof techniques used to prove lower bounds against structured models can be useful against general models as well. [FSV18] gave weak evidence against them working, whereas we provide some evidence for them working. The general question of whether these natural techniques will work, however, remains open. This is joint work with Mrinal Kumar, C. Ramya, Ramprasad Saptharishi and Anamay Tengse (appeared in FOCS 2020).

3. A natural restriction that is widely studied is that of non-commutativity of multiplication. Even though stronger lower bounds are not known against circuits in this setting, exponential lower bounds are known against non-commutative (nc) ABPs and formulas [Nis91]. However, to the best of my knowledge there is no lower bound known against nc-formulas that is not a lower bound against nc-ABPs as well. Therefore a natural question is whether there is a super polynomial separation between nc-formulas and nc-ABPs. This question, asked in [Nis91] itself, remains open. However, we make some progress towards resolving it by giving a tight separation between ABPs and some structured formulas in the non-commutative setting (to appear in CCC 2021).

**Bio**: Prerona Chatterjee is a final year PhD student at TIFR Mumbai, India. Before this she obtained her Bachelor’s degree from St. Xavier’s College, Kolkata, India and then her Master’s degree from IIT Guwahati, India.

Prerona is broadly interested in the field of Complexity Theory and most of her work till now has been in the area of Algebraic Complexity Theory. She is also deeply passionate about outreach and has been part of various such initiatives and activities.

**Omrit Filtser** (Stony Brook University)

**Title:** Proximity search in trajectory data under the Fréchet distance**Abstract:** Nearest neighbor search is a fundamental and well-studied problem that has various applications in machine learning, data analysis, and classification. This important task also arises in applications where the recorded instances are trajectories or polygonal curves, modeling, for example, traffic routes, animal migration patterns, epigenetic and surgical processes, and even the response of a football player in a given situation. With recent advances in tracking technology, large collections of densely sampled trajectories became available, and require sophisticated data structures that allow efficient processing of the data. The Fréchet distance is a distance measure for curves that became very popular in the last few decades, and some variants of it were successfully applied to real data sets.

In this talk I will shortly survey the different approaches and techniques that were utilized in the last several years for the approximate near-neighbor problem under the discrete Fréchet distance. Then, I will focus on a discretization and enumeration approach that led to significantly improved bounds and can be used in other related variants of the problem.**Bio**: Omrit Filtser is a postdoctoral researcher at Stony Brook University, hosted by Prof. Joe Mitchell. She received her Ph.D. in Computer Science from Ben-Gurion University, advised by Prof. Matya Katz. Her research is in the field of computational geometry, focusing on geometric optimization problems, similarity of geometric objects, data structures and algorithms. Omrit received several awards and fellowships, including the Eric and Wendy Schmidt Postdoctoral Award for Women in Mathematical and Computing Sciences, the Israeli Council for Higher Education fellowship for postdoctoral women fellows, and the BGU scholarship for postdoctoral women fellows.

**Sumegha Garg **(Harvard University)

**Title:** Tight Space Complexity of the Coin Problem

**Abstract:** In the coin problem, we are asked to distinguish, with probability at least 2/3, between n i.i.d. coins which are heads with probability 1/2 + β from ones which are heads with probability 1/2 − β. We are interested in the space complexity of the coin problem, corresponding to the width of a read-once branching program solving the problem. The coin problem becomes more difficult as β becomes smaller.

Statistically, it can be solved whenever β = Ω(1/√n), using counting. It has been previously shown that for β = O(1/√n), counting is essentially optimal (equivalently, width poly(n) is necessary [BGW’20]). On the other hand, the coin problem only requires O(log n) width for β > 1/n^{0.306} (following low-width simulation of AND-OR tree of [Val’84]).

In this talk, we close the gap between the bounds, showing a tight threshold between the values of β = n^{−c} where O(log n) width suffices and the regime where poly(n) width is needed, with a transition at c = 1/3. This gives a complete characterization (up to constant factors) of the memory complexity of solving the coin problem, for all values of bias β.

Joint work with Mark Braverman and Or Zamir.

**Bio:** Sumegha Garg is a Rabin Postdoctoral Fellow at Harvard Theory of Computation group. She completed her PhD in Computer Science at Princeton University, advised by Mark Braverman. Before that, she received her bachelor’s degree in Computer Science and Engineering from IIT, Delhi. She is broadly interested in Complexity Theory and Algorithmic Fairness, with a focus on space complexity and theory of fair predictions

**Sophie Huiberts **(CWI)

**Title:** Why Can We Solve (Integer) Linear Programs?**Abstract:** The algorithms that are commonly used to solve (integer) linear programs work astoundingly well. From the theoretical perspective, the practical performance of these decades-old algorithms is relatively poorly understood. In this talk, I will explain some difficulties in obtaining rigorous explanations, and I will describe recent work to go beyond worst-case analysis for the simplex method for linear programming and the branch-and-bound algorithm for integer programming.**Bio:** Sophie Huiberts is a final-year PhD candidate at Centrum Wiskunde & Informatica (CWI), where she is advised by Daniel Dadush. Her research interests are in practical algorithms, polyhedra, and combinatorial optimization.

**Sandra Kiefer** (Aachen University and University of Warsaw)

**Title:** Identifying Graphs by Playing with Pebbles: How Long Does It Take?

**Abstract:** Colour Refinement, also called Naïve Vertex Classification, is a natural and well-established combinatorial method in graph isomorphism tests. In an iterative fashion, Colour Refinement computes a colouring of the vertices of its input graph. This process stabilises at some point and the final colour partition can often be used to distinguish non-isomorphic graphs.

The Colour Refinement procedure and its generalisation, the Weisfeiler-Leman algorithm, have surprising connections to numerous areas of mathematics and computer science, e.g., Linear Programming and Machine Learning. Particularly useful for an analysis of the mechanisms of the algorithm are its characterisation via logics and via an Ehrenfeucht-Fraïssé game.

In my talk, I will introduce the Colour Refinement procedure and its higher-dimensional version as well as the game view on them. I will present recent results on the number of iterations to reach the final graph colouring, which corresponds to the number of rounds played in the game.

**Bio**: Sandra Kiefer is a postdoctoral researcher in the Computer Science department at RWTH Aachen University in Germany and currently on a 1-year position as an assistant professor in Mikołaj Bojańczyk’s group at the University of Warsaw in Poland. She studied Bioinformatics and Mathematics at Goethe University Frankfurt in Germany and Universidad de Cantabria in Spain and obtained her Ph.D. in Computer Science from RWTH Aachen University under the supervision of Martin Grohe and Pascal Schweitzer in 2020. Her research visits to the Australian National University and the University of Warsaw have led to collaborations with Brendan McKay and Mikołaj Bojańczyk. She also holds an M.Ed. degree in Mathematics and Spanish.

Sandra’s research deals with algorithmic graph theory, logic in computer science, and interdisciplinary topics from mathematics, computer science, and biomedicine.

**Audra McMillan** (Apple)

**Title:** Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling

**Abstract**: In the shuffle model of differential privacy, each individual “privatizes” their own data before sending it to an aggregator called a shuffler. The shuffler then anonymizes the reports by randomly permuting them. We are then concerned with how well the output of the shuffler obscures the contribution of any single individual. Recent work has formalized the intuition that the anonymized data is substantially more “private” than the non-anonymized data. Such amplification implies substantially stronger privacy guarantees for systems in which data is contributed anonymously. In this talk, we will discuss a new result on privacy amplification by shuffling. Our result is based on a new proof strategy which is simpler than previous approaches, and naturally leads to a simple and efficient method for numerically computing state of the art privacy guarantees. Based on joint work with Kunal Talwar and Vitaly Feldman.

**Bio**: Audra McMillan is a research scientist at Apple. She received her PhD from the Department of Mathematics at the University of Michigan. Following her PhD, she was a postdoctoral researcher at Boston University and Northeastern University hosted by Adam Smith and Jon Ullman. She is interested in privacy-preserving data analysis. Specifically, her work focuses on performing fundamental statistical tasks under differential privacy, and it’s variations. Her work has applications not only to privacy but also to robust data analysis and generalization.