TCS+ | A carbon-free dissemination of ideas across the globe.

February 14, 2019

TCS+ talk: Wednesday, February 20th, Sepehr Assadi, Princeton

The next TCS+ talk will take place this coming Wednesday, February 20th at
1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European
Time, 18:00 UTC). Sepehr Assadi from Princeton University will speak about “A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling” (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 subgraph counting problem, we are given a (large) graph $G(V, E)$ and a (small) graph $H$ (e.g., a triangle), and the goal is to estimate the number of occurrences of $H$ in $G$ . Our focus in this talk is on designing sublinear-time algorithms for approximately computing number of occurrences of $H$ in $G$ in the setting where the algorithm is given query access to $G$ . This problem has been studied in several recent work which primarily focused on specific families of graphs H such as triangles, cliques, and stars. However, not much is known about approximate counting of arbitrary graphs $H$ in the literature. This is in sharp contrast to the closely related subgraph enumeration problem in which the goal is to list all copies of the subgraph $H$ in $G$ . The AGM bound shows that the maximum number of occurrences of any arbitrary subgraph $H$ in a graph $G$ with $m$ edges is $O(m^{p(H)})$ , where $p(H)$ is the fractional edge cover number of $H$ , and enumeration algorithms with matching runtime are known for every $H$ .

In this talk, we bridge this gap between the subgraph counting and subgraph enumeration problems and present a simple sublinear-time algorithm that estimates the number of occurrences of any arbitrary graph $H$ in $G$ , denoted by $\#H$ , to within a $(1 \pm \varepsilon)$ -approximation factor with high probability in $O(m^{p(H)} /\#H)\cdot \text{poly}(\log n,1/\varepsilon)$ time. Our algorithm is allowed the standard set of queries for general graphs, namely degree queries, pair queries and neighbor queries, plus an additional edge-sample query that returns an edge chosen uniformly at random. The performance of our algorithm matches those of Eden et al. [FOCS 2015, STOC 2018] for counting triangles and cliques and extend them to all choices of subgraph $H$ under the additional assumption of edge-sample queries. Our results are also applicable to the more general problem of database join size estimation problem and for this slightly more general problem achieve optimal bounds for every choice of $H$ .

Joint work with Michael Kapralov and Sanjeev Khanna.

Leave a comment

January 28, 2019

TCS+ talk: Wednesday, February 6 — Ran Canetti, BU and TAU

The new season of TCS+ is about to start! Our first talk for Spring will take place next Wednesday, February 6th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Ran Canetti from BU and TAU will speak about “Fully Bideniable Interactive Encryption” (abstract below).

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 Sunoo Park and Oxana Poburinnaya.

Leave a comment

December 6, 2018

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

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.

Leave a comment

November 21, 2018

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

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.

Leave a comment

November 7, 2018

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

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.

Leave a comment

October 24, 2018

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

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.

Leave a comment

October 11, 2018

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

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

Leave a comment

September 26, 2018

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

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

Leave a comment

September 15, 2018

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

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:

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

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.

Leave a comment

September 5, 2018

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.

Leave a comment