TCS Women 2020 Program

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: Thursday, June 25th, 2020
  • 1:00 pm–3:00 pm (EST): Rising Stars Talks
  • 3:00 pm–4:00 pm (EST): Inspirational talk Shafi Goldwasser (UC Berkeley & Simons Institute for Theory of Computing).
  • Rising Stars Talks

Speaker and Talk Details:

2020 TCS Women Inspirational Talk by

Prof. Shafi Goldwasser (UC Berkeley & Simons Institute for Theory of Computing).

Title: From Basic Research to Impact

Abstract: 

This talk will describe how modeling and some basic research questions  in the realm of theory of computing translate — in the past, present and more interestingly in the future –to impact on modern day computing and other fields such as the law and  biomedical research.

Bio:

Shafi Goldwasser is the Director of the Simons Institute for the Theory of Computing, and the C. Lester Hogan Professor in Electrical Engineering and Computer Sciences at UC Berkeley. She is also the RSA Professor of Electrical Engineering and Computer Science at MIT, and a professor of Computer Science and applied mathematics at the Weizmann Institute of Science in Israel. Goldwasser received a BS in applied mathematics from Carnegie Mellon University in 1979, and MS and PhD in computer science from UC Berkeley in 1984.

Goldwasser was the recipient of ACM Turing Award for 2012. She was also the recipient of the Gödel Prize in 1993 and another in 2001 for her work on interactive proofs and connections to approximation, and was awarded the ACM Grace Murray Hopper Award (1996), the RSA award in mathematics (1998), the ACM Athena award for women in computer science (2008), the Benjamin Franklin Medal in Computer and Cognitive Science (2010), the IEEE Emanuel R. Piore Award (2011), the Barnard College Medal of Distinction (2016), and the Suffrage Science Award (2016). She is a member of the AAAS, ACM, NAE, NAS, Israeli Academy of Science, London Mathematical Society, and Russian Academy of Science.

Rising Stars Talk Information

Sepideh Mahabadi (TTIC)

Title: Composable Core-sets for the Determinant Maximization Problem
Abstract:
Given a data set, a “core-set” is a subset of the data that is sufficient for approximating the solution of a given task. A “composable core-set” is a core-set with the composability property: given a collection of data sets, the union of the core-sets for all data sets in the collection, should be a core-set for the union of the data sets. Using composable core-sets one can obtain efficient solutions to a wide variety of massive data processing applications, such as streaming and map-reduce models of computation.

For large data sets, a common task is to summarize the data by choosing a small set of representatives while maximizing the “diversity”. In this talk, I will briefly mention several measures for capturing the notion of diversity, and then focus on the Determinant Maximization problem, which is a prominent geometric model that has recently gained a lot of interest in modeling diversity. I will present tight algorithms for efficient construction of composable core-sets for the determinant maximization problem.

Bio:
Sepideh Mahabadi is a research assistant professor at Toyota Technological Institute at Chicago (TTIC). She received her PhD from MIT, where she was advised by Piotr Indyk. For a year, she was a Postdoctoral Research Scientist at Simons Collaboration on Algorithms and Geometry based at Columbia University. She received her B.Sc. from Sharif University of Technology, Iran.

Her research lies in theoretical aspects of big data, and in particular designing algorithms for massive data problems. Her research interests include high dimensional computational geometry, streaming algorithms, sketching, sub-linear time algorithms, metric embeddings, and graph algorithms. More broadly, she is interested in problems that are interesting from the theoretical point of view and at the same time have real world applications.

Talya Eden (MIT)

Title: Apprximately Counting and Sampling Subgraphs in Sublinear-Time

Abstract: In this talk I will shortly survey the recent develpoments in approximate subgraph counting and sampling in sublinear-time. One of the most important tools in understanding the basic structure of graphs is the study of graph motifs. Graph motifs are recurrent and statistically significant small subgraphs that represent basic interaction patterns in the graph. There is a plethora of algorithms concerning the problem of motif counting, both from a theoretical perspective, and from a practical one. What is common to all is that they read the entire graph. However,  in many practical scenarios the input graphs  are huge, and at times hard to access, so that even going through all the input once is infeasible.
Therefore, we design sublinear-time algorithms for the problems of counting, sampling and detecting subgraphs.

Bio: Talya Eden is a postdoctoral fellow at the MIT Institute for Foundations of Data Science (MIFODS) hosted by Prof. Piotr Indyk and Prof. Ronitt Rubinfeld.
 Her work is also supported by a Rothschild Postdoctoral Fellowship and a Schmidt Postdoctoral Award. Her research focus is on sublinear time algorithms and property testing and in particular sublinear time estimation of graph parameters. Prior to that, she was a PhD student in the School of Electrical Engineering at Tel Aviv University under the advisement of Prof. Dana Ron, where her research was supported by the Weinstein Award for Graduate Studies, Sephora Berrebi Scholarship for Women in Advanced Computer Science, and Azrieli Fellows Scholarship.

Mahsa Derakhshan (University of Maryland)

Title: Computing Optimal Strategies of Blotto games
Abstract: The Colonel Blotto game, first introduced by Borel in 1921, is a well-studied game theory classic. Two colonels each have a pool of troops that they divide simultaneously among a set of battlefields. The winner of each battlefield is the colonel who puts more troops in it, and the overall utility of each colonel is the sum of weights of the battlefields that she wins. Over the past century, the Colonel Blotto game has found applications in many different forms of competition, from advertisements to politics to sports. In the literature, the main objective that is considered for this game is maximizing the guaranteed expected payoff. This corresponds to the conventional utility maximization. We further propose another natural objective, which is to maximize the probability of obtaining a minimum payoff. This concerns scenarios such as elections where the candidates’ goal is to maximize the probability of getting at least half of the votes (rather than the expected number of votes). In this talk, we will consider both of these objectives and discuss how it is possible to obtain (almost) optimal solutions in both cases.

Bio: Mahsa is a Ph.D. student at the University of Maryland. Before that, she earned her bachelor’s degree in software engineering from the Sharif University of Technology in Iran.

Mahsa is broadly interested in the design and analysis of algorithms in the areas of graph theory and algorithmic game theory.  Some of her recent projects are about the kidney exchange problem (e.g., stochastic matching), optimization problems in online platforms (e.g., reserve price optimization and product ranking), and finding optimal strategies in two-player games (e.g., Colonel Blotto and Security Games). Mahsa’s research is supported by Ann G. Wylie Dissertation Fellowship and Google Ph.D. Fellowship.

Kira Goldner (Columbia University)

Title: Interdimensional Mechanism Design

Abstract: What is the best mechanism a seller can use to maximize their revenue?  This is one of the fundamental questions of mechanism design, yet it is only fully resolved for single-dimensional settings (e.g. with one item or many identical items).  Characterizing optimal mechanisms in settings where buyers have multiple parameters has remained a core open problem.  In “multi-dimensional” settings (e.g. with many heterogeneous items, where buyers have unit-demand or additive valuations), optimal mechanisms are often intractable and elude characterization.  We identify a class of “interdimensional” problems containing many natural settings for which we can provide characterizations.  It sits fundamentally in between the two extremes of single-dimensional and multi-dimensional with respect to the optimal mechanism’s complexity of characterization, menu complexity, and more
Joint work with (1) Amos Fiat, Anna Karlin, and Elias Koutsoupias and (2) Nikhil Devanur, Raghuvansh Saxena, Ariel Schvartzman, and Matt Weinberg.

Bio: Kira Goldner is a postdoctoral researcher at Columbia University hosted by Tim Roughgarden in the Computer Science department.  Specifically, she is an NSF Mathematical Sciences Postdoctoral Research Fellow and a Data Science Institute Postdoctoral Fellow.  Her research is in algorithmic mechanism design, with work ranging from relaxing traditional behavioral and informational assumptions, maximizing revenue in settings motivated by practice, and applying mechanism design to social good.  Kira also co-founded Mechanism Design for Social Good (MD4SG), an interdisciplinary initiative working to improve access to opportunity for historically disadvantaged communities.  She received her PhD in computer science and engineering from the University of Washington under the advisement of Anna Karlin, during which she was supported by a 2017-19 Microsoft Research PhD Fellowship and a 2016-17 Google Anita Borg Scholarship.

Nicole Wein (MIT)

Title: Algorithms and Hardness for Approximating Distance Parameters in Graphs

Abstract: Among the most important graph parameters are the graph’s diameter, radius, and the eccentricities of its vertices. The eccentricity of a vertex v is defined as the maximum over all vertices u of d(v, u), and the diameter and radius are the largest and smallest eccentricities over all vertices in the graph, respectively. One can compute all of these parameters by running an all-pairs shortest paths algorithm in time O(mn) (ignoring log factors). Furthermore, conditional lower bounds show that no polynomially faster algorithms exist (under the strong exponential time hypothesis and the hitting set hypothesis). For large graphs, this running time can be prohibitively slow, so we turn to approximation algorithms. I will talk about algorithms and conditional lower bounds for approximating diameter, radius, eccentricities, and variants of these problems.

Bio: Nicole Wein is a final-year PhD student at MIT advised by Virginia Vassilevska Williams. Her research interests are mainly in graph algorithms including dynamic algorithms, parameterized algorithms, data structures, and fine-grained complexity.

Akanksha Agrawal (Ben-Gurion University)

Title: Parameterized Guarding of Polygons via CSP

Abstract: Several frameworks have been designed to cope with NP-hardness. One such framework is Parameterized Complexity, where in addition to the input size, one studies how a secondary measure affects the computational complexity of the problem. A parameterized problem is obtained by coupling the classical instance of the problem with an integer, called the parameter. A typical goal in Parameterized Complexity is to design an algorithm (called an FPT algorithm) for the parameterized problem that runs in time O(f(k) n^{O(1)}), where n is the input size, k is the parameter, and f is some (computable) function.

In this talk, we will look at the parameterized complexity of a fundamental visibility problem in Computational Geometry, called the Art Gallery problem. The input consists of a simple polygon P, (possibly infinite) sets X and Y of points within P, and an integer k, and the objective is to decide whether at most k guards can be placed on points in X so that every point in Y is visible to at least one guard. In the classic formulation of Art Gallery, X and Y consist of all the points within P. Other well-known variants restrict X and Y to consist either of all the points on the boundary of P or of all the vertices of P. All the above mentioned variants of Art Gallery are known not to admit FPT algorithms under standard complexity theoretic assumptions, when parameterized by the solution size, k [Bonnet and Miltzow, ESA’16]. Given the above result, the following question was posed by Giannopoulos [Lorentz Center Workshop, 2016].

“Is Art Gallery FPT with respect to the number of reflex vertices?”

We will obtain a positive answer to the above question, for some variants of the Art Gallery problem. By utilising the structural properties of “almost convex polygons”, we design a two-stage reduction from (Vertex,Vertex)-Art Gallery to a new CSP problem where constraints have arity two and involve monotone functions. For the above special version of CSP, we obtain a polynomial time algorithm. Combining these results, we obtain an FPT algorithm for (Vertex,Vertex)-Art Gallery, when parameterized by the number of reflex vertices. We note that our approach also extends to (Vertex,Boundary)-Art Gallery and (Boundary,Vertex)-Art Gallery.

Bio: Akanksha Agrawal is currently a postdoctoral researcher at Ben-Gurion University of the Negev, Israel. She obtained her Ph.D. from University of Bergen, Norway, where she was advised by Prof. Saket Saurabh and Prof. Daniel Lokshtanov. She is mainly interested in studying problems in the framework of Parameterized Complexity, particularly, problems in computational geometry and graph modification.

Susanna F. de Rezende (Czech Academy of Sciences)

Title: Finding Algebraic Proofs is NP-Hard


Abstract: In this talk we will address the proof search problem: How hard is it to find a proof? More formally, we say a proof system S is automatable if there is an algorithm that takes as input an unsatisfiable CNF formula F and outputs a proof of unsatisfiability of F (in the proof system S) in time polynomial in the size of the shortest such proof. In a recent breakthrough result, Atserias and Müller (FOCS 2019) established that it is NP-hard to automate the resolution proof system. We will outline a simpler version of their proof and explain how it can be extended to hold also for three algebraic proof systems: Nullstellensatz, Polynomial Calculus, and Sherali–Adams. This talk is based on joint work with Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere and Dmitry Sokolov.


Bio: Susanna is a postdoc at the Institute of Mathematics of the Czech Academy of Sciences. Prior to that she was a PhD student of Prof. Jakob Nordström at KTH Royal Institute of Technology, where she defended her thesis in June 2019. She was a research fellow at the Simons Institute, Berkeley in 2018 and will be again in 2021. She currently works on computational complexity, with primary focus on proof complexity. Susanna’s research is funded by a postdoctoral grant from the Knuth and Alice Wallenberg Foundation.