# Computer Science Theory at Northeastern

## Theory Seminar

This semester the theory seminar will be every Wednesday 1:00-2:30pm at West Village H 366. If we do not have an invited speaker, we will have presentations from students or faculty. Write to Jonathan Ullman or Lydia Zakynthinou with suggestions for speakers!

## Spring Semester, 2019

 January 301:00PMWVH 366 Hugo Alves Akitaya, Tufts University Recognizing Weak Embeddings Abstract An embedding of a graph $G$ is a drawing $\varphi:G\rightarrow M$ of $G$ on a surface $M$ such that every point each vertex in $V(G)$ is mapped to distinct points and each edge in $E(G)$ to interior-disjoint Jordan arcs between the corresponding vertices. A weak embedding is a map $\varphi:G\rightarrow M$ if, for every $\epsilon>0$, there exist an embedding $\psi_\epsilon:G\rightarrow M$ so that $\|\varphi-\psi_\epsilon\|<\epsilon$, where $\|.\|$ is the uniform norm (i.e., $\sup$ norm). We say that the embedding $\psi_{\varphi}$ approximates $\varphi$. The study of weak embeddings lies at the interface of several independent lines of research in mathematics and computer science. In particular, it generalizes various graph visualization models and is a special case of the notoriously difficult cluster-planarity problem. It is also related to the foldability problem in computational origami. This talk presents several results on the algorithmic complexity of recognizing weak embeddings. February 131:00PMWVH 366 Paul Hand, Northeastern University Inverse Problems under a Learned Generative Prior Abstract Deep generative modeling has led to new and state of the art approaches for enforcing structural priors in a variety of inverse problems. In contrast to priors given by sparsity, deep models can provide direct low-dimensional parameterizations of the manifold of images or signals belonging to a particular natural class, allowing for recovery algorithms to be posed in a low-dimensional space. This dimensionality may even be lower than the sparsity level of the same signals when viewed in a fixed basis. In this talk, we will show rigorous recovery guarantees for solving inverse problems under a learned generative prior. First, we will discuss convergence guarantees for compressive sensing under random neural network priors. Then, we will show that generative priors allow for a significant advance to be made in the problem of compressive phase retrieval. To date, no known computationally efficient algorithm exists for solving phase retrieval under a sparsity prior at sample complexity proportional to the signal complexity. With generative priors, we establish a new approach for compressive phase retrieval and establish rigorous guarantees with sample complexity proportional to the signal complexity. February 201:00PMWVH 366 Ram Ramanathan, Chief Scientist, goTenna Decentralized Off-grid Wireless Mesh Networking: Tradeoffs and Protocols Abstract Decentralized infrastructure-less wireless networks can provide instantly-deployable and robust connectivity in the aftermath of natural disasters, in remote areas, and in other contexts such as the Internet-of-Things. After briefly introducing goTenna and multi-hop wireless networking, I will discuss the tradeoffs involved in designing such networks focusing in particular on connectivity properties using insights from percolation theory. I will then consider one particular problem, namely network-wide packet broadcasting, which is closely related to the Connected Dominating Set problem in graphs. I will present a fully distributed zero-control protocol for broadcasting and discuss its correctness and performance. Finally, I will touch upon some research challenges in the area such as incentivizing network growth using cryptocurrencies. February 271:00PMWVH 366 Jarosław Błasiok, Harvard University Optimal Streaming and Tracking Distinct Elements with High Probability Abstract The distinct elements problem is one of the fundamental problems in streaming algorithms --- given a stream of integers in the range $\{1,\ldots,n\}$, we wish to provide a $(1+\varepsilon)$ approximation to the number of distinct elements in the input. After a long line of research optimal solution for this problem with constant probability of success, using $\mathcal{O}(\frac{1}{\varepsilon^2}+\log n)$ bits of space, was given by Kane, Nelson and Woodruff in 2010. The standard approach used in order to achieve low failure probability $\delta$, is to take a median of $\log \delta^{-1}$ parallel repetitions of the original algorithm and report the median of computed answers. We show that such a multiplicative space blow-up is unnecessary: we provide an optimal algorithm using $\mathcal{O}(\frac{\log \delta^{-1}}{\varepsilon^2} + \log n)$ bits of space --- matching known lower bounds for this problem. That is, the $\log\delta^{-1}$ factor does not multiply the $\log n$ term. This settles completely the space complexity of the distinct elements problem with respect to all standard parameters. We consider also \emph{strong tracking} (or \emph{continuous monitoring}) variant of the distinct elements problem, where we want an algorithm which provides an approximation of the number of distinct elements seen so far, at all times of the stream. We show that this variant can be solved using $\mathcal{O}(\frac{\log \log n + \log \delta^{-1}}{\varepsilon^2} + \log n)$ bits of space, which we show to be optimal. March 271:00PMWVH 366 Christina Ilvento, Harvard University Learning Metrics for Individual Fairness Abstract There has been much discussion recently about how fairness should be measured or enforced in classification. Individual Fairness [Dwork et al. 2012], which requires that similar individuals be treated similarly, is a highly appealing definition because it gives very strong guarantees on treatment of individuals. Unfortunately, the need for a task-specific similarity metric has prevented its use in practice. In this work, we set out a framework for approximating a metric for Individual Fairness based on human judgements. Our model assumes that we have access to a human fairness arbiter, who can answer a limited set of queries concerning similarity of individuals for a particular task, is free of explicit biases and possesses sufficient domain knowledge to evaluate similarity. Our contributions include useful definitions for metric approximation relevant for Individual Fairness, constructions for approximations from a limited number of realistic queries to the arbiter on a fixed sample of individuals, and learning procedures to construct hypotheses for metric approximations which generalize to unseen samples under certain assumptions of learnability of distance threshold functions. April 101:00PMWVH 366 Oxana Poburinnaya, Boston University Fully Bideniable Interactive Encryption 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 paper 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 April 171:00PMISEC 655 Dimitris Tsipras, MIT Robust and Reliable Machine Learning: Progress and Challenges Abstract Recent progress in machine learning has made the deployment of ML systems in the real world an imminent possibility. But are our current machine learning systems really up to the task? In this talk, I will discuss the brittleness and vulnerability of the existing ML toolkit. I will then describe a conceptual framework that aims to deliver models that are more reliable, and robust to adversarial manipulation. Finally, I will outline how this framework constitutes a new learning paradigm, how it differs from the classic perspective, and what new challenges it gives rise to. April 241:00PMWVH 366 Mitali Bafna, Harvard University Thwarting Adversarial Examples: An L_0 robust Sparse Fourier Transform Abstract In the last several years, neural networks have made unprecedented achievements on computational learning tasks like image classification. Despite their remarkable success, neural networks have been shown to be brittle in the presence of adversarial noise. Many effective attacks have been proposed in the context of computer vision that reliably generate small perturbations to input images (sometimes imperceptible to humans) that drastically change the network’s classification of the image. In this work, we give a framework for improving the robustness of classifiers to adversaries with L_0 noise budgets. That is, adversaries are restricted in the number of features they can corrupt, but may corrupt each arbitrarily. Our framework is based on a new Sparse Discrete Fourier transform (DFT) that is robust to worst-case L_0 noise added in the time domain. We give a new algorithm for approximating the DFT of an approximately sparse signal that has been corrupted by worst-case L_0 noise, namely a bounded number of coordinates of the signal have been corrupted arbitrarily. Our techniques generalize to a wide range of linear transformations that are used in data analysis such as the Discrete Cosine and Sine transforms, the Hadamard transform, and their high-dimensional analogs. We use our algorithm to successfully defend against well known L_0 adversaries in the setting of image classification. We give experimental results on the Jacobian-based Saliency Map Attack (JSMA) and the Carlini Wagner (CW) L_0 attack on the MNIST and Fashion-MNIST datasets as well as the Adversarial Patch on the ImageNet dataset.