Maximal Independent Set (MIS) is one of the fundamental and most well-studied problems in distributed graph algorithms. Even after four decades of intensive research, the best-known (randomized) MIS algorithms have O(log n) round complexity on general graphs [Luby, STOC 1986] (where n is the number of nodes), while the best-known lower bound is Ω(√(log(n)/log(log n))) [Kuhn, Moscibroda, and Wattenhofer, JACM 2016]. Breaking past the O(log n) bound or showing stronger lower bounds have been longstanding open problems.

Energy is a premium resource in battery-powered wireless and sensor networks, and the bulk of it is used by nodes when they are awake, i.e., when they are sending, receiving, and even just listening for messages. On the other hand, when a node is sleeping, it does not perform any communication and thus spends very little energy. Several recent works have addressed the problem of designing energy-efficient distributed algorithms for various fundamental problems. These algorithms operate by minimizing the number of rounds in which any node is awake, also called the awake complexity. An intriguing question is whether one can design a distributed MIS algorithm that is significantly more energy-efficient (having very small awake complexity) compared to existing algorithms.

Our main contribution is to show that MIS can be computed in awake complexity that is exponentially better compared to the best known round complexity of O(log n) and also bypassing its fundamental Ω(√(log(n)/log(log n))) round complexity lower bound (almost) exponentially. Specifically, we show that MIS can be computed by a randomized distributed (Monte Carlo) algorithm in O(log log n) awake complexity with high probability. Since a node spends significant energy only in its awake rounds, our result shows that MIS can be computed in a highly energy-efficient way compared to the existing MIS algorithms.

In the unsplittable capacitated vehicle routing problem, we are given a metric space with a vertex called depot and a set of vertices called terminals. Each terminal is associated with a positive demand between 0 and 1. The goal is to find a minimum length collection of tours starting and ending at the depot such that the demand of each terminal is covered by a single tour (i.e., the demand cannot be split), and the total demand of the terminals in each tour does not exceed the capacity of 1.

Our main result is a polynomial-time $(2+\epsilon)$-approximation algorithm for this problem in the two-dimensional Euclidean plane, i.e., for the special case where the terminals and the depot are associated with points in the Euclidean plane and their distances are defined accordingly. This improves on recent work by Blauth, Traub, and Vygen [IPCO'21] and Friggstad, Mousavi, Rahgoshay, and Salavatipour [IPCO'22].

This is joint work with Claire Mathieu and Fabrizio Grandoni.

In this talk, I will introduce a recent work with Ashley Montanaro. I will show you that quantum computers can have exponential speedups in terms of communication complexity for some fundamental linear algebra problems. I will mainly introduce our results on solving linear regressions. The talk is based on arXiv:2210.01601.

Longest Common Substring (LCS) is an important text processing problem, which has recently been investigated in the quantum query model. The decisional version of this problem, LCS with threshold d, asks whether two length-n input strings have a common substring of length d. The two extreme cases, d = 1 and d = n, correspond respectively to Element Distinctness and Unstructured Search, two fundamental problems in quantum query complexity. However, the intermediate case 1 « d « n was not fully understood.

We show that the complexity of LCS with threshold d smoothly interpolates between the two extreme cases up to n^{o(1)} factors: LCS with threshold d has a quantum algorithm in n^{2/3 + o(1)}/d^{1/6} query complexity and time complexity, and requires at least Omega(n^{2/3}/d^{1/6}) quantum query complexity.

Our result improves upon previous upper bounds O~(min{ n/d^{1/2}, n^{2/3} }) (Le Gall and Seddighin ITCS 2022, Akmal and Jin SODA 2022), and answers an open question of Akmal and Jin.

Our main technical contribution is a quantum speed-up of the powerful String Synchronizing Set technique introduced by Kempa and Kociumaka (STOC 2019). Our quantum string synchronizing set also yields a near-optimal LCE data structure in the quantum setting, and an algorithm for the k-mismatch matching problem with k^{3/4}n^{1/2+o(1)} quantum query complexity.

Based on a SODA'23 paper joint with Jakob Nogler (ETH Zurich) and a SODA'22 paper joint with Shyan Akmal (MIT).

Obfuscation transforms a program C into a functionally equivalent program C' which hides the inner workings of C. The first formalizations of this hiding property in cryptography suffered from strong impossibility results and thus, the seemingly weak notion of indistinguishability obfuscation (iO) was formulated. It only requires that obfuscations of two circuits are indistinguishable when two circuits have equal functionality to begin with.

Although iO seems such a weak definition, it turns out surprisingly powerful (*). It allows us to transform worst-case NP problems into one-way functions, one-way functions into public-key encryption and even into fully homomorphic encryption—transformations which otherwise suffer from (black-box) separations result. In fact, iO is so strong that its existence is mutually exclusive with other assumptions which had previously been considered plausible.

At the same time, iO is also very weak; it does not even imply that P is different from NP although most cryptographic primitives (one-way functions, public-key encryption etc.) do.

In this talk, we explore the above conceptual implications. The talk is intended for a (broad) theory audience.

(*) “I must admit that I was very skeptic of the possible applicability of the notion of indistinguishable obfuscation.” Oded Goldreich when commenting on the surprising success of iO in cryptographc research.

We study the private k-median and k-means clustering problem in d dimensional Euclidean space. By leveraging tree embeddings, we give an efficient and easy to implement algorithm, that is empirically competitive with state of the art non private methods. We prove that our method computes a solution with cost at most $O(d^{3/2}\log n)\cdot OPT + O(k d^2 \log^2 n / \epsilon^2)$, where $\epsilon$ is the privacy guarantee. (The dimension term, d, can be replaced with $O(\log k)$ using standard dimension reduction techniques).

Although the worst-case guarantee is worse than that of state of the art private clustering methods, the algorithm we propose is practical, runs in near-linear, $\tilde{O}(nkd)$, time and scales to tens of millions of points. We also show that our method is amenable to parallelization in large-scale distributed computing environments. In particular we show that our private algorithms can be implemented in logarithmic number of MPC rounds in the sublinear memory regime. Finally, we complement our theoretical analysis with an empirical evaluation demonstrating the algorithm's efficiency and accuracy in comparison to other privacy clustering baselines.

Joint work with Vincent Cohen-Addad, Alessandro Epasto, Silvio Lattanzi, Vahab Mirrokni, Andres Munoz Medina, Chris Schwiegelshohn and Sergei Vassilvitskii

Sparsest cut is a fundamental graph problem, which models a general notion of balanced separator of a graph, and has uses in graph theory and divide-and-conquer approaches. In it, we are given an edge-capacitated graph, together with demands over pair of vertices, and we want to find a cut that minimizes the ratio between the capacities and demands across the cut. In other words, we aim to separate as much demand as possible using little cut capacity. For general graphs, the best known approximation factor is Õ(sqrt(log n)), and the problem is known to have no constant-approximation under the unique games conjecture.

In this talk, we focus on the simpler setting of bounded-treewidth graphs, and present new constant-factor approximation algorithms. Known algorithms in this setting are either inefficient or have large approximation factors. We will see that these algorithms can be framed as specific cases of a general algorithm with uses beyond sparsest cut, and then show how to combine the best of both approaches to obtain efficient and good approximations to the problem. As a result, we give the first constant-factor approximation algorithm running in FPT time.

Given a matrix recording pairwise distances, the Metric Violation Distance problem asks to modify the minimum number of entries of the matrix to make it into a metric. Due to its large number of applications in various data analysis and optimization tasks, this problem has been actively studied recently.

We will explain the various connections of this problem to other more well-known problems, and then present an O(log n)-approximation algorithm, exponentially improving the previous best approximation ratio of O(OPT^1/3). A major strength of this algorithm is also its simplicity and running time. We will also investigate the closely related problem of Ultrametric Violation Distance, where one aims at modifying the minimum number of entries so as to obtain an ultrametric, and present an O(1)-approximation algorithm for this problem by leveraging its close connections with a hierarchical instance of correlation clustering. If time allows, we will conclude with lower bounds for the maximization versions of both problems based on the Unique Games Conjecture.

Joint work with Vincent Cohen-Addad, Chenglin Fan and Euiwoong Lee.

Imagine facing n switches hooked up to an array of lightbulbs. Each lightbulb is connected to only a handful of switches and turns on under many, but not all, configurations of the switches to which it is connected. The satisfiability question asks whether it is possible to set the switches so that all lightbulbs are on. Naturally, whenever the answer is positive, flipping a coin for each switch will cause all lightbulbs to light up with positive probability. At the heart of the Probabilistic Method is the observation that any multiplicative underestimation of this probability, no matter how poor, suffices to prove that the answer is positive. The Lovász Local Lemma (LLL), a cornerstone of the Probabilistic Method, is a tool for establishing positive probability lower bounds in the face of conflicting correlations. In this talk, I will present a new, computational view of the LLL which leads to significant generalizations, including a passage from the setting of probabilities to that of general supermodular functions.

Deciding how to allocate the seats of a house of representatives is one of the most fundamental problems in the political organization of societies, and has been widely studied over already two centuries. The idea of proportionality is at the core of most approaches to tackle this problem, and this notion is captured by the divisor methods, such as the Jefferson/D'Hondt method. In a seminal work, Balinski and Demange extended the single-dimensional idea of divisor methods to the setting in which the seat allocation is simultaneously determined by two dimensions, and proposed the so-called biproportional apportionment method. The method, currently used in several electoral systems, is however limited to two dimensions and the question of extending it is considered to be an important problem both theoretically and in practice. In this work, we initiate the study of multidimensional proportional apportionment. We first formalize a notion of multidimensional proportionality that naturally extends that of Balinski and Demange. By means of analyzing an appropriate integer linear program we can prove that, in contrast to the two-dimensional case, the existence of multidimensional proportional apportionments is not guaranteed and deciding its existence is NP-complete. Interestingly, our main result asserts that it is possible to find approximate multidimensional proportional apportionments that deviate from the marginals by a small amount. The proof arises through the lens of discrepancy theory, mainly inspired by the celebrated Beck-Fiala Theorem. This is joint work with José Correa, Javier Cembrano and Gonzalo Diaz (PNAS 2022, EC 2021 and EAAMO 2021).

When optimizing a linear functional over a polytope P, one may prefer to pass to a linear extension whose number of facets is significantly smaller. Well-known examples of such polytopes are spanning tree polytope and permutahedron. This has motivated searching for so-called (symmetric or not) compact formulations of polytopes. Sometimes, they cannot exist [Yannakakis, Rothvoss]. While a non-negative factorization of the slack matrix of P, implicitly gives rise to a linear extension Q, one may sometimes directly describe Q, building on an algorithm which unfolds all symmetries of P. This was achieved for the permutahedron by Goemans, then his construction was generalized by Kaibel and Pashkovich. The aim of this talk is to introduce the main notions around extension complexity, and then explain the construction by Goemans, after a gentle warm up with regular n-gons in the plane.

We study a generalization of the classic Online Joint Replenishment Problem (JRP) with Delays that we call the Online Weighted Cardinality JRP with Delays. The JRP is an extensively studied inventory management problem wherein requests for different item types arrive at various points in time. A request is served by ordering its corresponding item type. The cost of serving a set of requests depends on the item types ordered. Furthermore, each request incurs a delay penalty while it is left unserved. The objective is to minimise the total service and delay costs. In the Weighted Cardinality JRP, each item type has a positive weight and the cost of ordering is a non-decreasing, concave function of the total weight of the item types ordered. This problem was first considered in the offline setting by Cheung et al.~(2015) but nothing is known in the online setting. Our main result is a deterministic, constant competitive algorithm for this problem.

With the world as connected as ever and data being created at an unprecedented rate, there has been an increasing need for algorithms that efficiently process massive graphs. Graph streaming is one such memory efficient setting where the edges of a graph are presented as a sequence of edges and an algorithm's goal is to store a sublinear number of edges needed to solve a graph problem exactly or approximately. In particular, this talk discusses the insertion-only, dynamic (or insertion-deletion) and sliding window graph streaming models of computation, highlighting the well-studied maximum matching and sister minimum vertex cover problems, and focusing on a recent space optimal (up to constant factors) algorithm for minimum vertex cover in the dynamic graph streaming model.

Quantum query model has been one of the main tools in quantum computing for understanding the complexity of problems: both in terms of designing efficient algorithms, and giving lower bounds on the complexity of the problem. In case of lower bounds, the main benefit of query model is the fact that concrete mathematical techniques exist to understand the query complexity. Our main aim in this talk is to look at this computational model and see why this model has gained so much attention in the quantum computing world.

After looking at the background and definitions for the query model, we will look at reasons why quantum query complexity is an important area of study. Not just that it is one of the simplest settings to study the complexity of functions, it naturally arises in many other areas like property testing and communication complexity.

Finally, as mentioned before, there exist many mathematical tools to study quantum query complexity. We will talk about the two main lower bound methods: adversary and polynomial. It will allow us to give a very short proof that Grover search is optimal. For the case of symmetric functions, we will see that simple arguments allow us to characterize not just the query complexity but even its lower bound techniques.

Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean function $f : \{0,1\}^n \to \{0,1\}$ and $G \in \{AND_2, XOR_2\}$, the bounded-error quantum communication complexity of the composed function ($f \circ G$) equals $O(Q(f) \log n)$, where $Q(f)$ denotes the bounded-error quantum query complexity of $f$. This is known as the BCW Simulation Theorem. This is in contrast with the classical setting, where it is easy to show that $R^{cc}(f \circ G) \leq 2R(f)$, where $R^{cc}$ and $R$ denote bounded-error communication and query complexity, respectively. We exhibited a total function for which the $\log n$ overhead in the BCW simulation is required.

We also answer several other questions related to quantum query-to-communication simulation: 1. We show that the $\log n$ overhead is not required when $f$ is symmetric (i.e., depends only on the Hamming weight of its input), generalizing a result of Aaronson and Ambainis for the Set-Disjointness function (Theory of Computing'05). 2. One may ask whether the $\log n$ overhead in the BCW Simulation Theorem can be avoided even when f is transitive, which is a weaker notion of symmetry. We show that the $\log n$ overhead is necessary for some transitive functions, even when we allow the quantum communication protocol an error probability that can be arbitrarily close to 1/2 (this corresponds to the unbounded-error model of communication). 3. We also give, among other things, a general recipe to construct functions for which the $\log n$ overhead is required in the BCW Simulation Theorem in the bounded-error communication model, even if the parties are allowed to share an arbitrary prior entangled state for free.

This talk is based on two joint works with Sourav Chakraborty, Arkadev Chattopadhyay, Peter Hoyer, Nikhil Mande, and Ronald de Wolf.

The role of symmetry in Boolean functions has been extensively studied in complexity theory. For example, Symmetric functions (functions that are invariant under all possible permutations on the input strings) are widely studied and well-understood classes of function. But there are a lot of functions with different types of symmetry which cannot be captured by the classes of symmetric functions. What happens for them? How different type of symmetry affects different complexity measures?

In this work, we study transitive functions in light of several combinatorial measures which is a natural generalization and a bigger class than symmetric functions. The question that we try to address in this paper is what are the maximum separations between various pairs of combinatorial measures for transitive functions. Such study for general Boolean functions has been going on for the past many years. The current best-known results for general Boolean functions have been nicely compiled by Aaronson et al. (STOC, 2021). But before this paper, no such systematic study has been done for the case of transitive functions.

Based on the various kinds of pointer functions, we construct new transitive functions whose complexity measures are similar to that of the original pointer functions. We have argued the barriers of Cheat Sheet techniques and also summarized the current knowledge of relations between various combinatorial measures of transitive functions in a table similar to the table compiled by Aaronson et al. (STOC, 2021) for general functions.

This is a joint work with Sourav Chakraborty and Manaswi Paraashar.

Bipartite testing has been a central problem in the area of property testing since its inception in the seminal work of Goldreich, Goldwasser and Ron [FOCS'96 and JACM'98]. Though the non-tolerant version of bipartite testing has been extensively studied in the literature, the tolerant variant is not well understood. In this paper, we consider the following version of tolerant bipartite testing: Given a parameter $\varepsilon \in (0,1)$ and access to the adjacency matrix of a graph $G$, we can decide whether $G$ is $\varepsilon$-close to being bipartite or $G$ is at least $(2+\Omega(1))\varepsilon$-far from being bipartite, by performing $\widetilde{\mathcal{O}}\left(\frac{1}{\varepsilon ^3}\right)$ queries and in $2^{\widetilde{\mathcal{O}}(1/\varepsilon)}$ time. This improves upon the state-of-the-art query and time complexities of this problem of $\widetilde{\mathcal{O}}\left(\frac{1}{\varepsilon ^6}\right)$ and  $2^{\widetilde{\mathcal{O}}(1/\varepsilon^2)}$, respectively, from the work of Alon, Fernandez de la Vega, Kannan and Karpinski (STOC'02 and JCSS'03), where $\widetilde{\mathcal{O}}(\cdot)$ hides a factor polynomial in $\log \frac{1}{\varepsilon}$.

This is a joint work with Arijit Ghosh, Gopinath Mishra, and Rahul Raychaudhury.

We introduce an explicit construction for a key distribution protocol in the Quantum Computational Timelock (QCT) security model, where one assumes that computationally secure encryption may only be broken after a time much longer than the coherence time of available quantum memories. Taking advantage of the QCT assumptions, we build a key distribution protocol called HM-QCT from the Hidden Matching problem for which there exists an exponential gap in one-way communication complexity between classical and quantum strategies. We establish that the security of HM-QCT against arbitrary attacks can be reduced to the difficulty of solving the underlying distributed problem with classical information, while legitimate users can use quantum communication. This leads to a HM-QCT key distribution scheme over n bosonic modes that can be secure with up to O(sqrt(n)/log(n)) input photons per channel use, boosting key rates by several orders of magnitude compared to QKD and allowing to operate with a non-trusted receiver.

In the 1970s, Valiant initiated the study of lower bounds for algebraic models of computation. The main question of this area, the VP vs. VNP question, is a formally simpler version of the P vs. NP question. Unlike the latter question, there are very concrete modes of attack against the VP vs. VNP question, via lower bounds for constant-depth algebraic circuits [Agrawal-Vinay 2008]. I will introduce these notions, and talk about some constant-depth circuit lower bounds that have been proved since Valiant's initial results.

We investigate fundamental barriers to fast mixing on a graph. In particular, we study the so-called Fastest Mixing Markov Chain Problem: given a graph G = (V, E), we desire the discrete-time Markov chain with smallest mixing time subject to having (1) uniform stationary distribution; (2) non-zero transition probabilities only across edges of the graph. We show that a geometric quantity, namely the vertex conductance of the graph, characterises the fastest mixing time. This characterisation can be seen as an analogue of the discrete Cheeger inequality, which characterises the mixing time of a simple random walk on a graph by its *edge* conductance. Our characterisation forbids fast mixing for graphs with small vertex conductance. To bypass this fundamental barrier, we consider Markov chains on G with equilibrium distribution which need not be uniform, but rather only ε-close to uniform in total variation. We show that another geometric quantity, the diameter of the graph, characterises such notion of “almost mixing”.

This is joint work with Sam Olesker-Taylor (arXiv:2111.05816).

There is currently a large interest in understanding the potential advantages quantum devices can offer for probabilistic modelling. In this work we investigate, within two different oracle models, the probably approximately correct (PAC) learnability of quantum circuit Born machines, i.e., the output distributions of local quantum circuits. We first show a negative result, namely, that the output distributions of super-logarithmic depth Clifford circuits are not sample-efficiently learnable in the statistical query model, i.e., when given query access to empirical expectation values of bounded functions over the sample space. This immediately implies the hardness, for both quantum and classical algorithms, of learning from statistical queries the output distributions of local quantum circuits using any gate set which includes the Clifford group. As many practical generative modelling algorithms use statistical queries – including those for training quantum circuit Born machines – our result is broadly applicable and strongly limits the possibility of a meaningful quantum advantage for learning the output distributions of local quantum circuits. As a positive result, we show that in a more powerful oracle model, namely when directly given access to samples, the output distributions of local Clifford circuits are computationally efficiently PAC learnable by a classical learner. Our results are equally applicable to the problems of learning an algorithm for generating samples from the target distribution (generative modelling) and learning an algorithm for evaluating its probabilities (density modelling). They provide the first rigorous insights into the learnability of output distributions of local quantum circuits from the probabilistic modelling perspective.

We present an algorithm solving the ROS (Random inhomogeneities in a Overdetermined Solvable system of linear equations) problem in polynomial time for $\ell > \log p$ dimensions. Our algorithm can be combined with Wagner’s attack, and leads to a sub-exponential solution for any dimension $\ell$ with best complexity known so far. When concurrent executions are allowed, our algorithm leads to practical attacks against unforgeability of blind signature schemes such as Schnorr and Okamoto–Schnorr blind signatures, threshold signatures such as GJKR and the original version of FROST, multisignatures such as CoSI and the two-round version of MuSig, partially blind signatures such as Abe–Okamoto, and conditional blind signatures such as ZGP17.

This is joint work with Fabrice Benhamouda, Tancrède Lepoint, Julian Loss and Mariana Raykova.

We investigate the connection between the complexity of nonlocal games and the arithmetical hierarchy, a classification of languages according to the complexity of arithmetical formulas defining them. It was recently shown by Ji, Natarajan, Vidick, Wright and Yuen that deciding whether the (finite-dimensional) quantum value of a nonlocal game is 1 or at most 12 is complete for the class Σ1 (i.e., RE). A result of Slofstra implies that deciding whether the commuting operator value of a nonlocal game is equal to 1 is complete for the class Π1 (i.e., coRE). We prove that deciding whether the quantum value of a two-player nonlocal game is exactly equal to 1 is complete for Π2; this class is in the second level of the arithmetical hierarchy and corresponds to formulas of the form “∀x∃yϕ(x,y)”. This shows that exactly computing the quantum value is strictly harder than approximating it, and also strictly harder than computing the commuting operator value (either exactly or approximately). We explain how results about the complexity of nonlocal games all follow in a unified manner from a technique known as compression. At the core of our Π2-completeness result is a new “gapless” compression theorem that holds for both quantum and commuting operator strategies. Our compression theorem yields as a byproduct an alternative proof of Slofstra's result that the set of quantum correlations is not closed. We also show how a “gap-preserving” compression theorem for commuting operator strategies would imply that approximating the commuting operator value is complete for Π1.

In the classical RAM, we have the following useful property. If we have an algorithm that uses M memory cells throughout its execution, and in addition is sparse, in the sense that, at any point in time, only m out of M cells will be non-zero, then we may “compress” it into another algorithm which uses only m log M memory and runs in almost the same time. We may do so by simulating the memory using either a hash table, or a self-balancing tree. We show an analogous result for quantum algorithms equipped with quantum random-access gates. If we have a quantum algorithm that runs in time T and uses M qubits, such that the state of the memory, at any time step, is supported on computational-basis vectors of Hamming weight at most m, then it can be simulated by another algorithm which uses only O(m log M) memory, and runs in time O˜(T ). We show how this theorem can be used, in a black-box way, to simplify the presentation in several papers. Broadly speaking, when there exists a need for a space-efficient history-independent quantum data-structure, it is often possible to construct a space-inefficient, yet sparse, quantum data structure, and then appeal to our main theorem. This results in simpler and shorter arguments.

Monte Carlo estimation is a well-known technique for estimating the expectation value of a random variable. For univariate random variables, taking values in the interval [-L,L], it is well-known that one classically can obtain an eps-precise estimate with O(L^2/eps^2) samples. Montanaro showed in 2015 that quantumly this can be sped up quadratically, i.e., that O(L/eps) quantum samples suffice. In this talk, we will generalize Montanaro's technique to the multivariate setting, and we show that a similar quadratic speed-up can be obtained. This result provides a useful building block as well for the more general case where we only assume that the random variable has a bounded covariance matrix. If time permits, we can also have a look at how this technique relates to Gilyén et al.'s gradient estimation algorithm.

A recent breakthrough result that fully characterizes the round complexity of secure computation.

The modern computation and information processing systems shaping our world have become massively distributed, and a fundamental understanding of distributed algorithmics has never been more important. At the same time, despite 40 years of intense study, we often do not have an adequate understanding of the fundamental barriers that rule out the existence of ultra-fast distributed algorithms. This is true even for the most well-studied problems in computer science – including the shortest path, minimum spanning tree, minimum cut, and many other well-known tasks.

In this talk, I will present a high-level overview of a sequence of papers that give a near-complete answer to the above question. Its culmination is the following pie-in-the-sky result called *universal optimality*: for all of the tasks mentioned, there exists a single distributed algorithm that, when run on any communication network G, is provably competitive with the fastest algorithm on G.

The pursuit of universal optimality has led to the development of many new connections between distributed computing and other seemingly unrelated areas of theoretical computer science. Curiously, these connections have been mutually-beneficial and have already led to many breakthroughs not only in distributed computing, but also in the theory of metric embedding, information theory, and oblivious packet routing. I will briefly explore these connections.

As the digitization of global communications accelerates, there is a growing awareness of privacy issues among large segments of society. In particular, the confidentiality of commercial transactions is under debate. In the 1980s and 1990s, Chaum, a cryptographer, developed and then deployed with his company Digicash an “anonymous” digital payment system whose guarantees were based, among other things, on mathematical proof inspired by the still nascent paradigm of “proven security”. Although his company Digicash goes bankrupt after a few years, the academic community continues to study anonymous digital payment systems, seeking to develop new functionalities, including transferability.

Our main goal was to revisit security models concerning the anonymity of payments, and then to propose a theoretically deployable payment system also based on the paradigm of proven security. During the presentation, I will talk about security models guaranteeing anonymity, as well as more fundamental questions concerning a family of cryptographic assumptions commonly used in provable security.

Certifying quantum properties with minimal assumptions is a fundamental problem in quantum information science. Self-testing is a method to infer the underlying physics of a quantum experiment only from the measured statistics. While all bipartite pure entangled states can be self-tested, little is known about how to self-test quantum states of an arbitrary number of systems. Here, we introduce a framework for network-assisted self-testing and use it to self-test any pure entangled quantum state of an arbitrary number of systems. The scheme requires the preparation of a number of singlets that scales linearly with the number of systems, and the implementation of standard projective and Bell measurements, all feasible with current technology. When all the network constraints are exploited, the obtained self-testing certification is stronger than what is achievable in any Bell-type scenario. Our work does not only solve an open question in the field but also shows how properly designed networks offer new opportunities for the certification of quantum phenomena.

We give an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with m edges and polynomially bounded integral demands, costs, and capacities in m^(1+o(1)) time. Our algorithm builds the flow through a sequence of m^(1+o(1)) approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized m^(o(1)) time using a dynamic data structure. Our framework extends to an algorithm running in m^(1+o(1)) time for computing flows that minimize general edge-separable convex functions to high accuracy. This gives an almost-linear time algorithm for several problems including entropy-regularized optimal transport, matrix scaling, p-norm flows, and isotonic regression.

At the request of the organizers, this talk will review the last years' work by (mostly others in) our group towards correcting errors in future quantum computing hardware with the so-called “cat qubits”. The basic piece of hardware is a quantum harmonic oscillator, instead of a physical two-level system, hence “bosonic” cats. In practice this is embodied by superconducting circuits, thus in an LC oscillator, or by mechanical oscillators. It is the approach currently pursued by actors like Alice&Bob startup in Paris, and Amazon quantum computing, as well as by now tens of groups around the world. The talk will be tutorial in nature. We will start by clarifying the basic physical setting and assumptions, in which cat qubits can be implemented as having almost only phase-flip errors, and no bit-flips. Then we will describe the implementation of a universal set of error-protected gates in this setting. We will conclude with some perspectives with respect to more standard code-based Quantum Error Correction methods and the more general context in which hardware-based error correction can be pursued.

In 2016, the National Institute of Standards and Technology (NIST) announced a call for standardization (also known as “NIST competition”) of post-quantum cryptographic protocols, i.e., cryptographic protocols considered to be resistant to quantum attacks. NIST was mainly interested in two types of protocols: digital signatures and encryption/key-establishment schemes. The fourth and final round of this competition is about to start, and once it is finished, the most efficient and thoroughly analyzed protocols will be standardized.

In this talk, we focus on the proposal for a digital signature. It is based upon a problem from coding theory, known as a syndrome decoding problem, and analyzed using cryptanalytic means. Namely, we analyze the time complexity of the information set decoding algorithms, widely believed to be the best algorithms for solving the syndrome decoding problem. By evaluating their complexity, both in the classical and quantum domain, we reason about the hardness of the problem. Finally, we give an example of the scheme based upon the syndrome decoding problem and analyze its security imposed by the hardness of the problem. We examine the tradeoff between signature's security and its size, which is a major challenge to be addressed in the competition.