TCS+

A carbon-free dissemination of ideas across the globe.

TCS+ talk: Wednesday, October 21 — Aayush Jain, UCLA

The next TCS+ talk will take place this coming Wednesday, October 21th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Aayush Jain from UCLA will speak about “Indistinguishability Obfuscation from Well-Founded Assumptions” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Due to security concerns, registration is required to attend the interactive talk. (The link to the YouTube livestream will also be posted on our website on the day of the talk, so people who did not sign up will still be able to watch the talk live.) 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 a construction of an indistinguishability obfuscation scheme, whose security rests on the subexponential hardness of four well-founded assumptions. We show the existence of an indistinguishability Obfuscation scheme for all circuits assuming sub-exponential security of the following assumptions:

  • The Learning with Errors (LWE) assumption with arbitrarily small subexponential modulus-to-noise ratio,
  • The SXDH assumption with respect to bilinear groups of prime order p,
  • Existence of a Boolean Pseudorandom Generator (PRG) in \mathsf{NC}^0 with arbitrary polynomial stretch, that is, mapping n bits to n^{1+\tau} bits, for any constant \tau>0.
  • The Learning Parity with Noise (LPN) assumption over \mathbb{Z}_p with error-rate \ell^{-\delta}, where \ell is the dimension of the secret and \delta>0 is an arbitrarily small constant.
    Further, assuming only polynomial security of these assumptions, there exists a compact public-key functional encryption scheme for all circuits.

The main technical novelty is the introduction and construction of a cryptographic pseudorandom generator that we call a Structured-Seed PRG (sPRG), assuming LPN over \mathbb{Z}_p and PRGs in \mathsf{NC}^0. During the talk, I will discuss how structured seed PRGs have evolved from different notions of novel pseudorandom generators proposed in the past few years, and how an interplay between different areas of theoretical computer science played a major role in providing valuable insights leading to this work. Time permitting, I will go into the details of how to construct sPRGs.

Joint work with Huijia (Rachel) Lin and Amit Sahai

TCS+ talk: Wednesday, October 14 — Jayadev Acharya, Cornell University

The next TCS+ talk will take place this coming Wednesday, October 14th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Jayadev Acharya from Cornell University will speak about “Distributed Statistical Inference under Local Information Constraints ” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Due to security concerns, registration is required to attend the interactive talk. (The link to the YouTube livestream will also be posted on our website on the day of the talk, so people who did not sign up will still be able to watch the talk live.) 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 consider statistical inference tasks in a distributed setting where access to data samples is subjected to strict “local constraints,” through a unified framework that captures communication limitations and (local) privacy constraints as special cases. We study estimation (learning) and goodness-of-fit (testing) for both discrete and high-dimensional distributions. Our goal is to understand how the sample complexity increases under the information constraints.

In this talk we will provide an overview of this field and a sample of some of our results. We will discuss the role of (public) randomness and interactivity in information-constrained inference, and make a case for thinking about randomness and interactivity as resources.

The work is part of a long-term ongoing collaboration with Clément Canonne (IBM Research) and Himanshu Tyagi (IISc), and includes works done with Cody Freitag (Cornell), Yanjun Han (Stanford), Yuhan Liu (Cornell), and Ziteng Sun (Cornell).

TCS+ talk: Wednesday, October 7 — Susanna F. de Rezende, Mathematical Institute of the Czech Academy of Sciences

The next TCS+ talk will take place this coming Wednesday, October 7th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Susanna F. de Rezende from Mathematical Institute of the Czech Academy of Sciences will speak about “Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Due to security concerns, registration is required to attend the interactive talk. (The link to the YouTube livestream will also be posted on our website on the day of the talk, so people who did not sign up will still be able to watch the talk live.) 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: Lifting theorems in complexity theory are a method of transferring lower bounds in a weak computational model into lower bounds for a more powerful computational model, via function composition. There has been an explosion of lifting theorems in the last ten years, essentially reducing communication lower bounds to query complexity lower bounds. These theorems only hold for composition with very specific “gadgets” such as indexing and inner product.

In this talk, we will present a generalization of the theorem lifting Nullstellensatz degree to monotone span program size by Pitassi and Robere (2018) so that it works for any gadget with high enough rank, in particular, for useful gadgets such as equality and greater-than. We will then explain how to apply our generalized theorem to solve three open problems:
– We present the first result that demonstrates a separation in proof power for cutting planes with unbounded versus polynomially bounded coefficients. Specifically, we exhibit CNF formulas that can be refuted in quadratic length and constant line space in cutting planes with unbounded coefficients, but for which there are no refutations in subexponential length and subpolynomial line space if coefficients are restricted to be of polynomial magnitude.
– We give the strongest separation to-date between monotone Boolean formulas and monotone Boolean circuits. Namely, we show that the classical GEN problem, which has polynomial-size monotone Boolean circuits, requires monotone Boolean formulas of size 2^{\Omega(n / \textrm{polylog} n)}.
– We give the first explicit separation between monotone Boolean formulas and monotone real formulas. Namely, we give an explicit family of functions that can be computed with monotone real formulas of nearly linear size but require monotone Boolean formulas of exponential size. Previously only a non-explicit separation was known.

This talk is based on joint work with Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, and Marc Vinyals, available at https://arxiv.org/abs/2001.02144

TCS+ talk: Wednesday, September 30 — Alex Wein, NYU

The next TCS+ talk will take place this coming Wednesday, September 30th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Alex Wein from NYU will speak about “Low-Degree Hardness of Random Optimization Problems” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Due to security concerns, registration is required to attend the interactive talk. (The link to the YouTube livestream will also be posted on our website on the day of the talk, so people who did not sign up will still be able to watch the talk live.) 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 high-dimensional statistical problems (including planted clique, sparse PCA, community detection, etc.), the class of “low-degree polynomial algorithms” captures many leading algorithmic paradigms such as spectral methods, approximate message passing, and local algorithms on sparse graphs. As such, lower bounds against low-degree algorithms constitute concrete evidence for average-case hardness of statistical problems. This method has been widely successful at explaining and predicting statistical-to-computational gaps in these settings.
While prior work has understood the power of low-degree algorithms for problems with a “planted” signal, we consider here the setting of “random optimization problems” (with no planted signal), including the problem of finding a large independent set in a random graph, as well as the problem of optimizing the Hamiltonian of mean-field spin glass models. I will define low-degree algorithms in this setting, argue that they capture the best known algorithms, and explain new proof techniques for giving lower bounds against low-degree algorithms in this setting. The proof involves a variant of the so-called “overlap gap property”, which is a structural property of the solution space.

Based on joint work with David Gamarnik and Aukosh Jagannath, available at arXiv:2004.12063.

TCS+ talk: Wednesday, September 23 — Fotis Iliopoulos, Princeton and IAS

The next TCS+ talk will take place this coming Wednesday, September 23th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Fotis Iliopoulos from Princeton and IAS will speak about “Stochastic Local Search and the Lovász Local Lemma” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Due to security concerns, registration is required to attend the interactive talk. (The link to the YouTube livestream will also be posted on our website on the day of the talk, so people who did not sign up will still be able to watch the talk live.) 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 Lovasz Local Lemma (LLL) is a powerful tool in probabilistic combinatorics which can be used to establish the existence of objects that satisfy certain properties. The breakthrough of Moser and Tardos (who recently received the Godel Prize for their work) and follow-up works revealed that the LLL has intimate connections with a class of stochastic local search algorithms for finding such desirable objects.

In this talk, I will survey this line of work through the perspective of recent unifying results, and also talk about recent applications to solving pseudo-random constraint satisfaction problems.

TCS+ talk: Thursday, September 17 — Richard Peng, Georgia Tech

The next TCS+ talk will take place this coming Thursday, September 17th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Richard Peng from Georgia Tech will speak about “Solving Sparse Linear Systems Faster than Matrix Multiplication” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Due to security concerns, registration is required to attend the interactive talk. (The link to the YouTube livestream will also be posted on our website on the day of the talk, so people who did not sign up will still be able to watch the talk live.) 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: Can linear systems be solved faster than matrix multiplication? While there has been remarkable progress for the special cases of graph structured linear systems, in the general setting, the bit complexity of solving an n-by-n linear system Ax=b is n^\omega, where \omega < 2.372864 is the matrix multiplication exponent. Improving on this has been an open problem even for sparse linear systems with \text{poly}(n) condition number.

We present an algorithm that solves linear systems in sparse matrices asymptotically faster than matrix multiplication for any \omega>2. This speedup holds for any input matrix A with o(n^{\omega-1}/\log(\kappa(A))) non-zeros, where \kappa(A) is the condition number of A. For \text{poly}(n)-conditioned matrices with O(n) nonzeros, and the current value of \omega, the bit complexity of our algorithm to solve to within any 1/\text{poly}(n) error is O(n^{2.331645}).

Our algorithm can be viewed as an efficient randomized implementation of the block Krylov method via recursive low displacement rank factorizations. It is inspired by the algorithm of [Eberly-Giesbrecht-Giorgi-Storjohann-Villard ISSAC 0607] for inverting matrices over finite fields. In our analysis of numerical stability, we develop matrix anti-concentration techniques to bound the smallest eigenvalue and the smallest gap in eigenvalues of semi-random matrices.

Joint work with Santosh Vempala, manuscript at https://arxiv.org/abs/2007.10254.

TCS+ talk: Wednesday, June 10 — Cliff Stein, Columbia University

In solidarity with the current protests in the United States (https://www.shutdownstem.com/), our speaker asked that the talk this coming Wednesday be postponed.

Cliff’s talk has been rescheduled to Thursday, June 18th; we will keep you updated in case of any further change. We would also take this opportunity to call the TCS community for feedback, and for suggestions and comments. As a small team organizing this virtual seminar, we are continuously trying to improve and welcome your input.

The next TCS+ talk (and the last of the season!) will take place this coming Wednesday, June 10th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Cliff Stein from Columbia University will speak about “Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Due to security concerns, registration is required to attend the interactive talk. (The link to the YouTube livestream will also be posted on our
website
on the day of the talk, so people who did not sign up will still be able to watch the talk live.) 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: Although sequential algorithms with (nearly) optimal running time for finding shortest paths in undirected graphs with non-negative edge weights have been known for several decades, near-optimal parallel algorithms have turned out to be a much tougher challenge. In this talk, we present a (1+\varepsilon)-approximate parallel algorithm for computing shortest paths in undirected graphs, achieving polylog depth and near-linear work. All prior (1+\varepsilon)-algorithms with polylog depth perform at least superlinear work. Improving this long-standing upper bound obtained by Cohen (STOC’94) has been open for 25 years.

Our algorithm uses several new tools. Prior work uses hopsets to introduce shortcuts in the graph. We introduce a new notion that we call low hop emulators. We also introduce compressible preconditioners, which we use in conjunction with Serman’s framework (SODA ’17) for the uncapacitated minimum cost flow problem.

Joint work with Alex Andoni and Peilin Zhong.

TCS+ talk: Wednesday, June 3 — Michael P. Kim, Stanford University

The next TCS+ talk (and penultimate of the season!) will take place this coming Wednesday, June 3th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Michael Kim from Stanford University will speak about “Learning from Outcomes:  Evidence-Based Rankings” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Due to security concerns, registration is required to attend the interactive talk. (The link to the YouTube livestream will also be posted on our
website
on the day of the talk, so people who did not sign up will still be able to watch the talk live.) 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 this work, we address the task of ranking members of a population according to their qualifications based on a training set of binary outcome data. A natural approach for ranking is to reduce to prediction: first learn to predict individuals’ “probability” of success; then rank individuals in the order specified by the predictions. A concern with this approach is that such rankings may be vulnerable to manipulation. The rank of an individual depends not only on their own qualification but also on every other individuals’ qualifications, so small inaccuracies in prediction may result in a highly inaccurate and unfair induced ranking. We show how to obtain rankings that satisfy a number of desirable accuracy and fairness criteria, despite the coarseness of binary outcome data.
We develop two parallel definitions of evidence-based rankings. First, we study a semantic notion of domination-compatibility: if the training data suggest that members of a set S are on-average more qualified than the members of T, then a ranking that favors T over S (i.e., where T dominates S) is blatantly inconsistent with the data, and likely to be discriminatory. Our definition asks for domination-compatibility, not just for a pair of sets (e.g., majority and minority populations), but rather for every pair of sets from a rich collection \mathcal{C} of subpopulations. The second notion—evidence-consistency—aims at precluding even more general forms of discrimination: the ranking must be justified on the basis of consistency with the expectations for every set in the collection \mathcal{C}. Somewhat surprisingly, while evidence-consistency is a strictly stronger notion than domination-compatibility when the collection \mathcal{C} is predefined, the two notions are equivalent when the collection \mathcal{C} may depend on the ranking itself. Finally, we show a tight connection between evidence-based rankings and multi-calibrated predictors [HKRR’18]. This connection establishes a way to reduce the task of ranking to prediction that ensures strong guarantees of fairness in the resulting ranking.
Joint work with Cynthia Dwork, Omer Reingold, Guy N. Rothblum, and Gal Yona. Appeared at FOCS 2019.

 

TCS+ talk: Wednesday, May 27 — Rahul Ilango, MIT

The next TCS+ talk will take place this coming Wednesday, May 27th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Rahul Ilango from MIT will speak about “Is it (NP) hard to distinguish order from chaos?” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Due to security concerns, registration is required to attend the interactive talk. (The link to the YouTube livestream will also be posted on our
website
on the day of the talk, so people who did not sign up will still be able to watch the talk live.) 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 Minimum Circuit Size Problem (MCSP) roughly asks what the “complexity” of a given string is. Informally, one can think of this as determining the degree of “computational order” a string has.

In the past several years, there has been a resurgence of interest in MCSP. A series of exciting results have begun unraveling what looks to be a fascinating story. This story already reveals deep connections between MCSP and a growing list of fields, including cryptography, learning theory, structural complexity theory, average-case complexity, and circuit complexity. As an example, Santhanam recently proved a conditional equivalence between the complexity of MCSP and the existence of one-way functions.

This talk is split into two parts. The first part is a broad introduction to MCSP, answering the following questions: What is this problem? Why is it interesting? What do we know so far, and where might the story go next? The second part discusses recent joint work with Bruno Loff and Igor Oliveira showing that the “multi-output version” of MCSP is NP-hard.

 

TCS+ talk: Wednesday, May 20 — Mark Bun, Boston University

The next TCS+ talk will take place this coming Wednesday, May 20th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Mark Bun from Boston University will speak about “An Equivalence between Private Classification and Online Predictability” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Due to security concerns, registration is required to attend the interactive talk. (The link to the YouTube livestream will also be posted on our website on the day of the talk, so people who did not sign up will still be able to watch the talk live.) 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 prove that every concept class with finite Littlestone dimension can be learned by an (approximate) differentially-private algorithm. The converse direction was shown in recent work of Alon, Livni, Malliaris, and Moran, STOC ’19. Together these two results show that a class of functions is privately learnable if and only if it is learnable in the mistake-bound model of online learning. To establish our result, we introduce “global stability,” a new notion of algorithmic stability for learning algorithms that we show can always be satisfied when learning classes of finite Littlestone dimension.