A carbon-free dissemination of ideas across the globe.

### TCS+ talk: Wednesday, December 12 — Julia Chuzhoy, TTIC

The next TCS+ talk will take place this coming Wednesday, December 12th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Julia Chuzhoy from TTIC will speak about “Almost Polynomial Hardness of Node-Disjoint Paths in Grids” (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: In the classical Node-Disjoint Paths (NDP) problem, we are given an n-vertex graph G, and a collection of pairs of its vertices, called demand pairs. The goal is to route as many of the demand pairs as possible, where to route a pair we need to select a path connecting it, so that all selected paths are disjoint in their vertices.

The best current algorithm for NDP achieves an $O(\sqrt{n})$-approximation, while, until recently, the best negative result was a roughly $\Omega(\sqrt{\log n})$-hardness of approximation. Recently, an improved $2^{\Omega(\sqrt{\log n})}$-hardness of approximation for NDP was shown, even if the underlying graph is a subgraph of a grid graph, and all source vertices lie on the boundary of the grid. Unfortunately, this result does not extend to grid graphs.

The approximability of NDP in grids has remained a tantalizing open question, with the best upper bound of $\tilde{O}(n^{1/4})$, and the best lower bound of APX-hardness. In this talk we come close to resolving this question, by showing an almost polynomial hardness of approximation for NDP in grid graphs.

Our hardness proof performs a reduction from the 3COL(5) problem to NDP, using a new graph partitioning problem as a proxy. Unlike the more standard approach of employing Karp reductions to prove hardness of approximation, our proof is a Cook-type reduction, where, given an input instance of 3COL(5), we produce a large number of instances of NDP, and apply an approximation algorithm for NDP to each of them. The construction of each new instance of NDP crucially depends on the solutions to the previous instances that were found by the approximation algorithm.

Joint work with David H.K. Kim and Rachit Nimavat.

### TCS+ talk: Wednesday, November 28 — Eric Balkanski, Harvard University

The next TCS+ talk will take place this coming Wednesday, November 28th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Eric Balkanski from Harvard University will speak about “The Adaptive Complexity of Maximizing a Submodular Function” (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 introduce the study of submodular optimization in the adaptive complexity model to quantify the information theoretic complexity of black-box optimization in a parallel computation model. Informally, the adaptivity of an algorithm is the number of sequential rounds it makes when each round can execute polynomially-many function evaluations in parallel. Since submodular optimization is regularly applied on large datasets we seek algorithms with low adaptivity to enable speedups via parallelization. For the canonical problem of maximizing a monotone submodular function under a cardinality constraint, all that was known until recently is that the adaptivity needed to obtain a constant approximation is between 1 and $\Omega(n)$. Our main result is a tight characterization showing that the adaptivity needed is, up to lower order terms, $\Theta(\log n)$:

• We describe an algorithm which requires $O(\log n)$ sequential rounds and achieves an approximation that is arbitrarily close to 1/3;
• We show that no algorithm can achieve an approximation better than $O(1/\log n)$ with fewer than $O(\log n/\log\log n)$ rounds.
Thus, when allowing for parallelization, our algorithm achieves a constant factor approximation exponentially faster than any previous algorithm for submodular maximization. I will conclude the talk by surveying very recent results on submodular optimization in the adaptive complexity model.

Joint work with Yaron Singer.

### 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.