TCS+

A carbon-free dissemination of ideas across the globe.

TCS+ talk: Wednesday, March 20th, Aleksandar Nikolov, University of Toronto

The next TCS+ talk will take place this coming Wednesday, March 20th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 18:00 Central European Time, 17:00 UTC). Aleksandar Nikolov from University of Toronto will speak about “Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems” (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: Semidefinite programming is a powerful tool in the design and analysis of approximation algorithms for combinatorial optimization problems. In particular, the random hyperplane rounding method of Goemans and Williamson has been extensively studied for more than two decades, resulting in various extensions to the original technique and beautiful algorithms for a wide range of applications. Despite the fact that this approach yields tight approximation guarantees for some problems, like Max Cut, for many others, like Max Sat, Max DiCut, and constraint satisfaction problems with global constraints, the tight approximation ratio is still unknown. One of the main reasons for this is the fact that very few techniques for rounding semi-definite relaxations are known.

In this work, we present a new general and simple method for rounding semi-definite programs, based on Brownian motion. Our approach is inspired by recent results in algorithmic discrepancy theory. We develop and present tools for analyzing our new rounding algorithms, utilizing mathematical machinery from the theory of Brownian motion, complex analysis, and partial differential equations. Focusing on constraint satisfaction problems, we apply our method to several classical problems, including Max Cut, Max 2-Sat, and Max DiCut, and derive new algorithms that are competitive with the best known results. We further show that our algorithms can be used, together with the Sum of Squares hierarchy, to approximate constraint satisfaction problems subject to multiple global cardinality constraints.

Join work with Sepehr Abbasi-Zadeh, Nikhil Bansal, Guru Guruganesh, Roy Schwartz, and Mohit Singh

 

Advertisements

TCS+ talk: Wednesday, March 6th, Shayan Oveis Gharan, University of Washington

The next TCS+ talk will take place this coming Wednesday, March 6th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Shayan Oveis Gharan from University of Washington will speak about “Strongly log concave polynomials, high dimensional simplicial complexes, and an FPRAS for counting Bases of Matroids” (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: A matroid is an abstract combinatorial object which generalizes the notions of spanning trees, and linearly independent sets of vectors. I will talk about an efficient algorithm based on the Markov Chain Monte Carlo technique to approximately count the number of bases of any given matroid.

The proof is based on a new connections between high dimensional simplicial complexes, and a new class of multivariate polynomials called completely log-concave polynomials. In particular, we exploit a fundamental fact from our previous work that the bases generating polynomial of any given matroid is a log-concave function over the positive orthant.

Based on joint works with Nima Anari, Kuikui Liu, and Cynthia Vinzant.

 

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.

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

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

 

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.