A carbon-free dissemination of ideas across the globe.

### TCS+ talk: Wednesday, November 14 — Urmila Mahadev, UC Berkeley

The next TCS+ talk will take place this coming Wednesday, November 14th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Urmila Mahadev from UC Berkeley will speak about “Classical Homomorphic Encryption for Quantum Circuits” (abstract below).

Please make sure you reserve a spot for your group to join us live by signing up on the online form. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: We present the first leveled fully homomorphic encryption scheme for quantum circuits with classical keys. The scheme allows a classical client to blindly delegate a quantum computation to a quantum server: an honest server is able to run the computation while a malicious server is unable to learn any information about the computation. We show that it is possible to construct such a scheme directly from a quantum secure classical homomorphic encryption scheme with certain properties. Finally, we show that a classical homomorphic encryption scheme with the required properties can be constructed from the learning with errors problem.

### TCS+ talk: Wednesday, October 31 — Michal Koucky, Charles University

The next TCS+ talk will take place this coming Wednesday, October 31th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 18:00 Central European Time, 17:00 UTC). Michal Koucky from Charles University will speak about “Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time ” (abstract below).

Please make sure you reserve a spot for your group to join us live by signing up on the online form. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

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. The edit distance can be computed exactly using a dynamic programming algorithm that runs in quadratic time. Andoni, Krauthgamer and Onak (2010) gave a nearly linear time algorithm that approximates edit distance within approximation factor $\mathrm{poly}(\log n)$. In this talk I will present an algorithm with running time $O(n^{2-2/7})$ that approximates the edit distance within a constant factor.

Joint work with Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, and Mike Saks.

### TCS+ talk: Wednesday, October 17 — C. Seshadhri, UC Santa Cruz

The next TCS+ talk will take place this coming Wednesday, October 17th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). C. Seshadhri from UC Santa Cruz will speak about “Finding forbidden minors through random walks: (almost) $n^{1/2}$-query one-sided testers for minor closed properties” (abstract below).

Please make sure you reserve a spot for your group to join us live by signing up on the online form. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: Let $G$ be an undirected, bounded degree graph with $n$ vertices. Fix a finite graph $H$, and suppose one must remove $\varepsilon n$ edges from $G$ to make it $H$-minor free (for some small constant $\varepsilon>0$). We give a nearly $n^{1/2}$ time algorithm that, with high probability, finds an $H$-minor in such a graph.

As an application, consider a graph $G$ that requires $\varepsilon n$ edge removals to make it planar. This result implies an algorithm, with the same running time, that produces a $K_{3,3}$ or $K_5$ minor in $G$. No prior sublinear time bound was known for this problem. By the graph minor theorem, we get an analogous result for any minor-closed property.

Up to $n^{o(1)}$ factors, this result resolves a conjecture of Benjamini-Schramm-Shapira (STOC 2008) on the existence of one-sided property testers for minor-closed properties. Furthermore, our algorithm is nearly optimal, by lower bounds of Czumaj et al (RSA 2014).

Joint work with Akash Kumar and Andrew Stolman

### TCS+ talk: Wednesday, October 3 — Alex Andoni, Columbia University

The next TCS+ talk will take place this coming Wednesday, October 3th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Alex Andoni from Columbia University will speak about “Parallel Graph Connectivity in Log Diameter Rounds” (abstract below).

Please make sure you reserve a spot for your group to join us live by signing up on the online form. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: The MPC model has emerged as a compelling model for modern parallel systems, such as MapReduce, Hadoop and Spark, capturing well coarse-grained computation on large data. Here, data is distributed to processors, each of which has a sublinear (in the input data) amount of memory and we alternate between rounds of computation and rounds of communication, where each machine can communicate an amount of data as large as the size of its memory. This model is stronger than the classical PRAM model, and the recent research program has been to design algorithms whose running time is smaller than in the PRAM model.

One now-classic challenge is the graph connectivity problem. On an undirected graph with $n$ nodes and $m$ edges, $O(\log n)$ round connectivity algorithms have been known for over 35 years. However, no algorithms with better complexity bounds are known for MPC (in fact even impossible for some restricted algorithms).

We give a faster algorithms for the connectivity problem when parameterizing the time complexity as a function of the diameter of the graph. Our main result is a $O(\log D \cdot \log\log_{m/n} n)$ time connectivity algorithm for  diameter-$D$ graphs, using $O(m)$ total memory.

Joint work with Zhao Song, Cliff Stein, Zhengyu Wang, Peilin Zhong (to appear in FOCS’18).

### TCS+ talk: Wednesday, September 19 — Avishay Tal, Simons Institute

The next TCS+ talk will take place this coming Wednesday, September 19th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Avishay Tal from the Simons Institute will speak about an “Oracle Separation of BQP and the Polynomial Hierarchy” (abstract below).

Please make sure you reserve a spot for your group to join us live by signing up on the online form. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: We present an oracle, $A$, relative to which $\mathsf{BQP}^{A}$ is not contained in $\mathsf{PH}^{A}$.

Following the approach of Aaronson [STOC, 2010], our result is obtained by finding a distribution $D$ over Boolean strings of length $N$ such that:

1. There exists a quantum algorithm that runs in time${\rm polylog}(N)$ and distinguishes between$D$ and the uniform distribution over Boolean strings of length$N$.
2. No Boolean circuit of quasi-polynomial size and constant depth can
distinguish between $D$ and the uniform distribution with advantage better than ${\rm polylog}(N)/\sqrt{N}$.

Joint work with Ran Raz.

### Fall is Coming

Summer is over, and Fall is upon us. Trees changing color, pumpkins invading the Starbucks’ iced chai lattes, and a new exciting season of TCS+!

The focus here is the latter, and specifically to remind you to (1) block your calendar, (2) book a room on a fortnightly fashion, and (3) sit back with your favorite talk-watching snack and prepare for a treat: as customary, the TCS+ seminars will take place every other Wednesday, starting exactly two weeks from now (Wed. 19th September), at the by-now-standard time of 1pm EST (10am PST).

The first speakers lined up for the Fall are:

• Sept. 19th: Avishay Tal (Simons Institute)
• Oct. 3rd: (TBD)
• Oct. 17th: C. Seshadri (UC Santa Cruz)
• Oct. 31st: (TBD)
• Nov. 14th: Urmila Mahadev (UC Berkeley)

An up-to-date calendar will always appear on our webpage, where you can also subscribe to our mailing-list and suggest talks.

As always, TCS+ welcomes feedback, be it on the technical or scientific aspects. Please help us continue the success of our seminars by attending, suggesting speakers, and spreading the word to those universities worldwide that would most benefit from watching our seminars.

Best wishes for the new academic year,
The organizers.

### TCS+ talk: Wednesday, May 30th — Michael Kearns, UPenn

The next and last TCS+ talk for the Spring will take place this coming Wednesday, May 30th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Michael Kearns from UPenn will speak about “Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness” (abstract below).

Please make sure you reserve a spot for your group to join us live by signing up on the online form. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: The most prevalent notions of fairness in machine learning are statistical definitions: they fix a small collection of pre-defined groups, and then ask for parity of some statistic of the classifier across these groups. Constraints of this form are susceptible to intentional or inadvertent “fairness gerrymandering”, in which a classifier appears to be fair on each individual group, but badly violates the fairness constraint on one or more structured subgroups defined over the protected attributes. We propose instead to demand statistical notions of fairness across exponentially (or infinitely) many subgroups, defined by a structured class of functions over the protected attributes. This interpolates between statistical definitions of fairness and recently proposed individual notions of fairness, but raises several computational challenges. It is no longer clear how to audit a fixed classifier to see if it satisfies such a strong definition of fairness.

We prove that the computational problem of auditing subgroup fairness for both equality of false positive rates and statistical parity is equivalent to the problem of weak agnostic learning, which means it is computationally hard in the worst case, even for simple structured subclasses. But it also raises the possibility of applying empirically successful machine learning methods to the problem.

We then derive two algorithms that provably converge to the best fair classifier, given access to oracles which can solve the agnostic learning problem. The algorithms are based on a formulation of subgroup fairness as a two-player zero-sum game between a Learner and an Auditor. Our first algorithm provably converges in a polynomial number of steps. Our second algorithm enjoys only provably asymptotic convergence, but has the merit of simplicity and faster per-step computation. We implement the simpler algorithm using linear regression as a heuristic oracle, and show that we can effectively both audit and learn fair classifiers on real datasets.

Joint work with Seth Neel, Aaron Roth, and Zhiwei Steven Wu.