TCS Women 2019 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 is open to all.

Speaker and Talk Details:

Prof. Ronitt Rubinfeld,
MIT & Tel Aviv University

Title: A Comedy of Errors
(2019 Inspirational Talk)

Abstract: In the late 1980s, a new model of “Program Checking” was put forth by Blum and Kannan in order to prevail over errors in programs. With that as a starting point, several lines of research developed — including one that eventually morphed into the area of sublinear time algorithms.  Along the way, errors were made and others were detected.  We will recount the arbitrary nature of this process and place it in historical context. 

Bio: Ronitt Rubinfeld  is a professor of Electrical Engineering and Computer Science at MIT and a professor of Computer Science at Tel-Aviv University. Her research interests include randomized algorithms and computational complexity. She works in the fields of Property Testing and Sub-linear Time Algorithms, which provide the foundations for measuring the performance of algorithms that analyze data without looking at all of it. Ronitt Rubinfeld was an invited speaker at the International Congress of Mathematicians in 2006 and is an ACM Fellow.

Rising Stars:

  • Naama Ben-David
    CMU
  • Debarati Das
    Charles University
  • Andrea Lincoln
    MIT
  • Oxana
    Poburinnaya
    Boston University

Talk Abstracts & Speaker Bios

TCS Women Panel & Lunch

  • Date: Monday, June 24th
  • Time: STOC Lunch Break

All Women participants of FCRC are invited!

Panelists:

  • Shuchi Chawla, University of Wisconsin Madison
  • Julia Chuzhoy, TTIC
  • Edith Cohen, Google
  • Faith Ellen,
    University of Toronto
  • Huijia (Rachel) Lin
    University of Washington
  • Nutan Limaye
    Indian Institute of Technology, Mumbai

TCS Women Poster Session

The TCS Women Poster Session will be held together with the STOC poster session on Monday, June 24th. All are welcome!

Poster Presentations:

Maryam Bahrani, Princeton University, “Matroid Secretary in Limited Computational Models”

Nitya Mani, Stanford University, “Sidorenko’s Conjecture and Quasirandomness in Directed Networks”

Meryem Essaidi, Princeton University, “When to Limit Market Entry under Mandatory Purchase”

Lydia Zakynthinou, Northeastern University, “Efficient Private Algorithms for Learning Halfspaces”

Yifan Wu, Peking University, “Decentralized Crowdsourcing Data Market”

Oxana Poburinnaya, Boston University, “Fully Bideniable Interactive Encryption”

Tamalika Mukherjee, Purdue University, “Large Gaps in Martingales and Their Applications”

Sarah Scheffler, Boston University, “Post-processing Calibrated Classifiers”

Drishti Wali, Cornell University, “Graph regret bounds for Thompson sampling and UCB”

Naama Ben-David, Carnegie Mellon University, “Fault Tolerance in Message-and-Memory Networks”

Anna Melnichenko, Hasso Plattner Institute, University of Potsdam, Geometric Network Creation Games

Shir Peleg, Tel-Aviv University, Sylvester-Gallai Type THeorems for Quadratic Polynomials

Rupei Xu, University of Texas at Dallas, Robertson-Seymour Theorem–the Mathematical Foundation of 5G Network Protocol

Maryam Negahbani, Dartmouth College, Fair Algorithms for Clustering

Rising Stars Talks:

————–

Title: Theoretical Foundations for Distributed Systems
Speaker: Naama Ben-David (CMU)

Abstract: Many large-scale computations are nowadays done using several processors, whether on a single multithreaded machine, or distributed over many machines. With this rise in popularity, it is now more important than ever to understand distributed computation, and to make the best use of what such technology has to offer. In this talk, I will cover two ways in which a solid theoretical foundation of distributed computing can help guide the way we use it in practice.
First, I will discuss exponential backoff in shared memory. Exponential backoff has long been used to improve performance in many settings in which communication is contended. While we have a theoretical understanding of its advantages in synchronous settings, no theoretical model has been successful in explaining why backoff helps in asynchronous shared memory. I will present the first theoretical model to capture shared memory backoff, and explain how it relates to previous literature.
In the second part of the talk, I will discuss RDMA, a communication primitive that can replace message passing in distributed data centers. Many recent papers in the systems community have shown large performance benefits gained by replacing standard messaging technology with RDMA-based versions. However, it has so far been unclear whether these speedups are due to a fundamental difference between RDMA and previous hardware generations, or are simply a side-effect of more cleverly-written software.
I will present the first theoretical model that captures RDMA’s power, and formally prove that RDMA is fundamentally stronger than previous message-passing technology.

Bio: Naama Ben-David is a final-year PhD student at Carnegie Mellon University. Her primary research interests are in the intersection of theory and practice in distributed computing. More specifically, Naama strives to theoretically explain phenomena seen in modern concurrent machines, and to use this insight to design and analyze practical algorithms for concurrent settings. Naama’s research is supported by an NSERC postgraduate scholarship and a Microsoft Research PhD Fellowship.

————–

Title:  Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time
Speaker: Debarati Das (Charles University)

Abstract:  Edit distance is a measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. This distance measure finds applications in fields such as computational biology, pattern recognition, text processing, and information retrieval. The edit distance can be computed exactly using a dynamic programming algorithm that runs in quadratic time, which is also known to be almost optimal under SETH assumption [Backurs, Indyk 2015]. Andoni, Krauthgamer and Onak (2010) gave a nearly linear time (randomized) algorithm that approximates edit distance within poly-log(n) approximation factor. In this talk we discuss a randomized algorithm with running time O(n^(2-2/7)) that approximates the edit distance within a constant factor. (Joint work with Chakraborty, Goldenberg, Koucky and Saks)

Bio: Debarati Das has recently finished her Ph.D. studies from Computer Science Institute of Charles University, Prague, Czech Republic. She completed her M.Tech. from Indian Institute of Technology Kanpur in 2014. Her primary research interests include lower bounds, data structures, graph algorithms, streaming algorithms and fine grained complexity. She is currently working on problems related to edit distance. She will join the Basic Algorithms Research, Copenhagen as a Postdoc. 

————–

Title: Fully Bideniable Interactive Encryption
Speaker: Oxana Poburinnaya (Boston University)

Abstract: While standard encryption guarantees secrecy of the encrypted plaintext only against an attacker that has no knowledge of the communicating parties’ keys and randomness of encryption, deniable encryption [Canetti et al., Crypto’96] provides the additional guarantee that the plaintext remains secret even in face of entities that attempt to coerce (or bribe) the communicating parties to expose their internal states, including the plaintexts, keys and randomness. To achieve this guarantee, deniable encryption equips the parties with faking algorithms which allow them to generate fake keys and randomness that make the ciphertext appear consistent with any plaintext of the parties’ choice. To date, however, only partial results were known: Either deniability against coercing only the sender, or against coercing only the receiver [Sahai-Waters, STOC ‘14] or schemes satisfying weaker notions of deniability [O’Neil et al., Crypto ‘11].
In this talk we present the first fully bideniable interactive encryption scheme, thus resolving the 20-years-old open problem. Our scheme also provides an additional and new guarantee: Even if the sender claims that one plaintext was used and the receiver claims a different one, the adversary has no way of figuring out who is lying – the sender, the receiver, or both. This property, which we call off-the-record deniability, is useful when the parties don’t have means to agree on what fake plaintext to claim, or when one party defects against the other. Our protocol has three messages, which is optimal [Bendlin et al., Asiacrypt’11], and needs a globally available reference string. We assume subexponential indistinguishability obfuscation (IO) and one-way functions.
Joint work with Ran Canetti and Sunoo Park

Bio: Oxana is a 6th year PhD student at Boston University, working in theoretical cryptography with Professor Ran Canetti. Prior to joining BU, she studied mathematics at Moscow State University.

————–

Title: Faster Random k-CNF Satisfiability
Speaker: Andrea Lincoln (MIT)

Abstract: We describe an algorithm to solve the problem of Boolean CNF-Satisfiability when the input formula is chosen randomly.
We build upon the algorithms of [Schöning 1999] and [Dantsin et al. 2002]. The Schöning algorithm works by trying many possible random assignments, and for each one searching systematically in the neighborhood of that assignment for a satisfying solution. Previous algorithms for this problem run in time O(2^{n (1- \Omega(1)/k)}).
Our improvement is simple: we count how many clauses are satisfied by each randomly sampled assignment, and only search in the neighborhoods of assignments with abnormally many satisfied clauses. We show that assignments like these are significantly more likely to be near a satisfying assignment. This improvement saves a factor of 2^{n \Omega(\lg^2 k)/k}, resulting in an overall runtime of O(2^{n (1- \Omega(\lg^2 k)/k)}) for random k-SAT.

Bio: Andrea Lincoln is a PhD student at MIT. She is advised by Virginia Vassilevska Williams. She studies Fine-Grained Complexity and applies it to new areas. Andrea’s projects have included deterministic space/time trade offs for 3-SUM, generating tight mn^{1-o(1)} lower bounds for sparse APSP, and average-case fine-grained complexity. Her most recent focus has been on building either fine-grained cryptography or faster algorithms for average-case fine-grained problems.