In memory of Luca Trevisan (1971-2024)

I will speak on the early days of Luca's research career as he entered the world stage, starting from my first meeting with him when he visited IBM as a "contractor" till his theory-world-shaking construction of "extractors". The technical part of the talk will describe his work form the interim period, joint with me and Greg Sorkin and David Williamson, on automating the construction of "gadgets" for use in NP-completeness and inapproximability proofs.

Joint work with Luca Becchetti, Francesco Pasquale, Luca Trevisan, and Isabella Ziccardi

We study expansion and information diffusion in dynamic networks, that is in networks inwhich nodes and edges are continuously created and destroyed. We consider information diffusion by flooding, the process by which, once a node is informed, it broadcasts its information to all its neighbors.

We study models in which the network is sparse, meaning that it has O(n) edges, where n is the number of nodes, and in which edges are created randomly, rather than according to a carefully designed distributed algorithm. In our models, when a node is "born", it connects to d = O(1) random other nodes. An edge remains alive as long as both its endpoints do.

If no further edge creation takes place, we show that, although the network will have Ω_d(n) isolated nodes, it is possible, with large constant probability, to inform a 1 − exp(-Ω(d)) fraction of nodes in O(log n) time. Furthermore, the graph exhibits, at any given time, a "large-set expansion" property.

We also consider models with edge regeneration, in which if an edge (v, w) chosen by v$ at birth goes down because of the death of w, the edge is replaced by a fresh random edge (v, z). In models with edge regeneration, we prove that the network is, with high probability, a vertex expander at any given time, and flooding takes O(log n) time.

The above results hold both for a simple but artificial streaming model of node churn, in which at each time step one node is born and the oldest node dies, and in a more realistic continuous-time model in which the time between births is Poisson and the lifetime of each node follows an exponential distribution.

Previous work on expansion and flooding studied models in which either the vertex set is fixed and only edges change with time or models in which edge generation occurs according to an algorithm. Our motivation for studying models with random edge generation is to go in the direction of models that may eventually capture the formation of social networks or peer-to-peer networks.

I will discuss a problem that Luca and I have worked extensively on over the past years: approximately maximizing a low-degree multivariate polynomial over the Boolean hypercube or the sphere. This is a simple testbed for nonconvex optimization that captures for example 1) a notion of multiplicative approximation for constraint satisfaction problems, and 2) the challenge of generalizing the spectral theory of graphs to hypergraphs. I will present results for both worst-case and average-case variants of this problem, along with several open questions. Based on joint works with Tim Hsieh, Chris Jones, Pravesh Kothari, and Luca Trevisan.

We address the black-box complexity of constructing pseudorandom functions (PRF) from pseudorandom generators (PRG). The celebrated GGM construction of Goldreich, Goldwasser, and Micali (Crypto 1984) provides such a construction, which (even when combined with Levin’s domain-extension trick) has super-logarithmic depth. Despite many years and much effort, this remains essentially the best construction we have to date. On the negative side, one step is provided by the work of Miles and Viola (TCC 2011), which shows that a black-box construction which just calls the PRG once and outputs one of its output bits, cannot be a PRF.

In this work, we make significant further progress: we rule out black-box constructions of PRF from PRG that follow certain structural constraints, but may call the PRG adaptively polynomially many times. In particular, we define “tree constructions” which generalize the GGM structure: they apply the PRG G along a tree path, but allow for different choices of functions to compute the children of a node on the tree and to compute the next node on the computation path down the tree. We prove that a tree construction of logarithmic depth cannot be a PRF (while GGM is a tree construction of super-logarithmic depth). We also show several other results and discuss the special case of one-call constructions.

Our main results in fact rule out even weak PRF constructions with one output bit. We use the oracle separation methodology introduced by Gertner, Malkin, and Reingold (FOCS 2001), and show that for any candidate black-box construction of F^G, there exists an oracle relative to which G is a PRG, but F^G is not a PRF.

Based on joint work with Amos Beimel and Noam Mazor, appearing in Crypto 2024.

We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable algorithms. The questions are whether there is a non-trivial FPT-approximation algorithm for the Maximum Clique (Clique) and Minimum Dominating Set (DomSet) problems parameterized by the size of the optimal solution. In particular, letting OPT be the optimum and N be the size of the input, is there an algorithm that runs in t(OPT)poly(N) time and outputs a solution of size f(OPT), for any functions t and f that are independent of N (for Clique, we want f(OPT) = ω(1))?

In recent years, there have been numerous developments with regards to these questions. In this talk, I'll give a quick survey of these results, with a focus on our paper (from FOCS 2017) which gives a negative answer to these questions, under the Gap Exponential-Time Hypothesis (Gap-ETH) assumption.

Based on joint work with Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan.

Does a random polynomial-size circuit compute a pseudorandom function? What about a one-way function? The common wisdom is that cryptographic algorithms require special structure, which is far from random. Furthermore, amplification of cryptographic strength naturally amplifies also the special structure and its distance from random. I will discuss recent efforts to show that, at least in the context of reversible circuits, random structure and random function go hand in hand. I will also discuss efforts to exploit this confluence to provide simple alternatives to various cryptographic constructions, and to further connect physical and complexity aspects of computation.

Luca has inspired me in this research in many ways: in encouraging discussions and literature pointers, in his mathematical and personal fearlessness, in his quest to simplicity, and finally in his untimely and ultimately irreversible death. For me, the study of reversible circuits brings his mathematical spirit back to life.