Quantum annealing (QA) holds promise for optimization problems in quantum computing, especially for combinatorial optimization. This analog framework attracts attention for its potential to address complex problems. Its gate-based homologous, QAOA with proven performance, has brought lots of attention to the NISQ era. Several numerical benchmarks try to classify these two metaheuristics however, classical computational power highly limits the performance insights. In this work, we introduce a new parametrized version of QA enabling a precise 1-local analysis of the algorithm. We develop a tight Lieb-Robinson bound for regular graphs, achieving the best-known numerical value to analyze QA locally. Studying MaxCut over cubic graph as a benchmark optimization problem, we show that a linear-schedule QA with a 1-local analysis achieves an approximation ratio over 0.7020, outperforming any known 1-local algorithms.

A quantum system of n interacting particles at thermal equilibrium can be described using a polynomial number of parameters, which correspond to the strengths of the forces between particles. A natural open question has been whether these parameters can be estimated efficiently by running experiments on the system. We resolve this question by giving the first polynomial-time algorithm for this task. This improves over prior work, which uses polynomially many samples from the system, but requires exponential time. In this talk, I will introduce the problem and describe some of the key ideas behind our algorithm.

Based on joint work with Allen Liu, Ankur Moitra and Ewin Tang.

Maintaining spectral information quickly with changing data matrix is essential in several applications. In this talk I would give an overview of what is known in this area and present a simple yet novel algorithm and analysis of maintaining an approximate maximum eigenvalue and eigenvector of a positive semi-definite matrix quickly, that undergoes decremental updates. Our algorithms also hint towards a separation between oblivious and adaptive adversaries in the dynamic setting, which has not yet been resolved.

This is based on a very recent work with Thatchaphol Sararunak.

In the LOCAL model of distributed computing, n processors are connected together through a graph. They communicate with their neighbours in a synchronised way a limited number of times (through infinite bandwith communication channels), and then produce an output. Their goal is to find a strategy solving some information processing task, e.g. to obtain a proper coloring of the graph. To answer this question, the considered physical theory of information matters: for instance, Quantum Information Theory (QIT) can in principle allow for strategies solving the task quicker.

Finding lower bounds on the maximal speed at which QIT can solve a task is tricky. To circumvent this difficulty, several proofs based on the No-Signalling (NS) Principle (which states that an event A can influence an event B only if some signal can physically be sent from A to B) were proposed and a new NS-LOCAL model of distributed computing was proposed.

I’ll re-interpret this NS-LOCAL model based on the theoretical physics formalism of light cones in circuits. I will justify that the NS-LOCAL model is the “largest reasonable model with a pre-shared resource between the nodes”. Then, I’ll introduce a weaker Causal-LOCAL model, the “largest reasonable model without pre-shared resource between the nodes”.

All this will be illustrated with easy to understand examples. I was recently told by Vaclav Rozhon: We computer scientists are very scared of the word “quantum”. Note that I’ll almost not talk about quantum theory, hence no need to be scared.

In Bell scenarios with two outcomes per party, we algorithmically consider the two sides of the membership problem for the local polytope: constructing local models and deriving separating hyperplanes, that is, Bell inequalities. We take advantage of the recent developments in so-called Frank-Wolfe algorithms to significantly increase the convergence rate of existing methods. As an application, we study the threshold value for the nonlocality of two-qubit Werner states under projective measurements. Here, we improve on both the upper and lower bounds present in the literature. Importantly, our bounds are entirely analytical; moreover, they yield refined bounds on the value of the Grothendieck constant of order three: 1.4367 ≤ KG(3) ≤ 1.4546. We also demonstrate the efficiency of our approach in multipartite Bell scenarios, and present the first local models for all projective measurements with visibilities noticeably higher than the entanglement threshold.

We will present a very simple streaming algorithm on F0 estimation that also caught the eye of Donald E. Knuth. In a recent article, Donald E. Knuth started with the following two paragraphs:

“Sourav Chakraborty, N. V. Vinodchandran, and Kuldeep S. Meel have recently proposed an interesting algorithm for the following problem: A stream of elements (a1, a2,…,am) is input, one at a time, and we want to know how many of them are distinct. In other words, if A = {a1, a2,…,am} is the set of elements in the stream, with multiplicities ignored, we want to know |A|, the size of that set. But we don’t have much memory; in fact, |A| is probably a lot larger than the number of elements that we can hold in memory at any one time. What is a good strategy for computing an unbiased estimate of |A|?

Their algorithm is not only interesting, it is extremely simple. Furthermore, it’s wonderfully suited to teaching students who are learning the basics of computer science. (Indeed, ever since I saw it, a few days ago, I’ve been unable to resist trying to explain the ideas to just about everybody I meet.) Therefore I’m pretty sure that something like this will eventually become a standard textbook topic. This note is an initial approximation to what I might write about it if I were preparing a textbook about data streams.”

This simple algorithm comes out of the first ever “efficient” streaming algorithm (from PODS 21) for the Klee's Measure problem, which was a big open problem in the world of streaming for many years.

This work is based on joint works with N. V. Vinodchandran, and Kuldeep S. Meel across multiple articles, notable the following: Estimating the Size of Union of Sets in Streaming Models. PODS 2021; Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size. PODS 2022; Distinct Elements in Streams: An Algorithm for the (Text) Book. ESA 2022.

Several fundamental objects in quantum mechanics are described by linear operations that transform quantum states. For example, measurements are operations that transform quantum states into probability distributions, while quantum channels transform quantum states into other quantum states. The formalism of higher-order operations then concerns itself with the question of how to transform these quantum operations, e.g., how a quantum channel can be transformed into another quantum channel or into a probability distribution. Hence, higher-order operations are built on the idea of studying “functions of functions” from a quantum-information perspective.

In this talk, we will discuss the basics of the formalism of higher-order operations, and how their often simple mathematical characterization can be exploited to efficiently optimize over quantum strategies for different information-theoretic tasks. We will discuss its applications to channel discrimination, quantum circuit optimization, and its connection to indefinite causal order—a phenomenon that naturally emerges from the higher-order formalism. In particular, we will discuss potential advantages of indefinite causal order, and the cost, in terms of the necessary number of calls of an arbitrary quantum operation, of simulating it with standard quantum circuits.

How can one test the correctness of a program that is supposed to output an element from a large universe according to a certain distribution? These kinds of programs are heavily used in real life but are rarely tested for correctness.

This problem can be framed as a problem in property testing. Property testing is a subject that deals with these challenges. It tries to design sub-linear algorithms for testing various properties of inputs. The key lies in the way the data is accessed by the algorithm.

One of the central problems in property testing and many other related subjects is testing if a distribution has a certain property - say whether a distribution on a finite set is uniform. The conventional way of accessing the distributions is by drawing samples according to the distributions. Unfortunately, in this setting the number of samples that are necessary for testing properties of distribution (for most natural properties) is polynomial in the size of support of the distribution. Thus when the support is relatively big the algorithms become impractical in real life applications.

We introduced a new way of accessing the distribution using ``conditional-sampling oracle“. This oracle can be used to design much faster algorithms for testing properties of distribution and thus makes the algorithm useful in practical scenarios.

We show that the conditional oracle can be implemented in many real life problems and we have been able to show the usefulness of this model and our algorithms in practical purposes and in other areas of research - like testing of probabilistic verification. This model also throws a number of interesting theoretical questions.

The talk will be based on the following works: On the Power of Conditional Samples in Distribution Testing with Eldar Fischer, Arie MAtsliah and Yonatan Goldhrish (SICOMP 2016); Property Testing of Joint Distributions using Conditional Samples with Rishiraj Bhattacharyya (ToCT 2018); On Testing of Uniform Samplers with Kuldeep Meel (AAAI2019); On Testing of Samplers with Kuldeep Meel and Yash Pote (NeuRIPS 2020); Designing Samplers is Easy: The Boon of Testers with Kuldeep Meel, Priyanka Golia and Mate Soos (FMCAD22); On Quantitative Testing of Samplers with Kuldeep Meel, Priyanka Golia and Mate Soos (CP22); Testing of Horn Samplers with Ansuman Banerjee, Shayak Chakraborty, Sayantan Sen, Uddalok Sarkar and Kuldeep Meel (AISTAT 2023); Tight Lower Bound on Equivalence Testing in Conditional Sampling Model with Diptarka Chakraborty and Gunjan Kumar (SODA 2024).

We initiate a systematic study of the time complexity of quantum divide and conquer algorithms for classical problems. We establish generic conditions under which search and minimization problems with classical divide and conquer algorithms are amenable to quantum speedup, and apply these theorems to an array of problems involving strings, integers, and geometric objects. They include LONGEST DISTINCT SUBSTRING, KLEE’S COVERAGE, several optimization problems on stock transactions and k-INCREASING SUBSEQUENCE. For most of these results our quantum time upper bound matches the quantum query lower bound for the problem, up to polylogarithmic factors.

In this talk I will discuss recent advances in the fundamental robust optimization problem of minimizing the maximum of a finite number of convex loss functions. In particular, I will show how to develop stochastic methods for approximately solving this problem with a near-optimal number of gradient queries. Along the way, I will cover several optimization techniques of broader utility, including accelerated methods for using ball-optimization oracles and stochastic bias-reduced gradient methods.

This talk will include joint work with Hilal Asi, Yair Carmon, Arun Jambulapati, and Yujia Jin including https://arxiv.org/abs/2105.01778 and https://arxiv.org/abs/2106.09481.

We consider general prepare-and-measure scenarios in which Alice can transmit qubit states to Bob, who can perform general measurements in the form of positive operator-valued measures (POVMs). We show that the statistics obtained in any such quantum protocol can be simulated by the purely classical means of shared randomness and two bits of communication. Furthermore, we prove that two bits of communication is the minimal cost of a perfect classical simulation.

Then, we apply our methods to Bell scenarios, which extends the well-known Toner and Bacon protocol. In particular, two bits of communication are enough to simulate all quantum correlations associated to arbitrary local POVMs applied to any entangled two-qubit state. For the case of projective measurements, we provide explicit protocols that simulate perfectly the statistics of all local projective measurements on any pair of entangled qubits by communicating one classical trit. If the state is weakly entangled, already a single bit is sufficient and the expected amount of communication approaches zero in the limit where the degree of entanglement approaches zero.

This talk is mainly based on https://arxiv.org/abs/2207.02244 and will also discuss some results from https://arxiv.org/abs/2207.12457.

One of the key challenges of the quantum machine learning field is identifying learning problems where quantum learning algorithms can achieve a provable exponential advantage over classical learning algorithms. Proofs of separation for learning mostly work by reductions to plausible complexity theoretic assumptions of various types. Previously known examples of advantages are all contrived, and all rely on cryptographic methods to make learning hard for a classical learner. However, the broadly shared intuition is that learning separations should be most apparent when the learning task involves data from genuinely quantum sources (but still classical, i.e., measured out), which are very different from cryptographic problems. In this talk I will discuss this apparent discrepancy by providing a fine-grained analysis of existing learning separations and present new results showing how various types of advantages can be obtained, which will include advantages stemming from a large class of complex quantum physical systems.

We introduce and study elastic SNARKs, a class of proofs where the prover can select different time and memory tradeoffs, depending on the execution environment and the proved statement. The output proof is independent of the chosen configuration.

We construct an elastic SNARK for rank-1 constraint satisfiability (R1CS). In a time-efficient configuration, the prover uses a linear number of cryptographic operations and a linear amount of memory. In a space-efficient configuration, the prover uses streaming algorithms and a quasilinear number of cryptographic operations with a logarithmic amount of memory. A key component of our construction is an elastic probabilistic proof. Along the way, we also formulate a streaming framework for R1CS that we deem of independent interest.

We additionally contribute Gemini, a Rust implementation of our protocol. Our benchmarks show that Gemini, on a single machine, supports R1CS instances with tens of billions of constraints.

Joint work with Jonathan Bootle (IBM Zurich), Alessandro Chiesa (EPFL), and Yuncong Hu (Shanghai Jiao Tong University).

Article link: https://ia.cr/2022/420

The Local Hamiltonian problem for stoquastic local Hamiltonians (those that avoid the sign problem) is shown to be StoqMA-complete when the interactions are algebraically local. Moreover, the problem becomes MA-complete if the Hamiltonian is also frustration-free. In this work, we extend these results, proving the hardness of the problem for Hamiltonians that are geometrically local on 1D and 2D lattices, with only nearest neighbour interactions between qudits.

We study a variant of the widely popular, fast, and often used family of community detection procedures referred to as label propagation algorithms. These mechanisms also exhibit many parallels with models of opinion exchange dynamics and consensus mechanisms in distributed computing.

Initially, given a network, each vertex starts with a random label in the interval [0,1]. Then, in each round of the algorithm, every vertex switches its label to the majority label in its neighborhood (including its own label). At the first round, ties are broken towards smaller labels, while at each of the next rounds, ties are broken uniformly at random.

We investigate the performance of this algorithm on the binomial random graph G(n,p). Via a technically delicate analysis, we show that for np>n^(5/8+epsilon), the algorithm terminates with a single label a.a.s. Moreover, we show that if np = omega(n^(2/3)), a.a.s., this label is the smallest one, whereas if n^(5/8+epsilon) < np = o(n^(2/3)), the surviving label is, a.a.s., not the smallest one.

Joint work with Lyuben Lichev (Univ. Jean Monnet), Dieter Mitsche (Univ. Jean Monnet & Pontifícia Univ. Católica de Chile), and Pawel Pralat (Toronto Metropolitan Univ.).

We show that n-bit integers can be factorized by independently running a quantum circuit with $\tilde{O}(n^{3/2})$ gates for $\sqrt{n}+4$ times, and then using polynomial-time classical post-processing. In contrast, Shor's algorithm requires circuits with $\tilde{O}(n^2)$ gates. The correctness of our algorithm relies on a number-theoretic heuristic assumption reminiscent of those used in subexponential classical factorization algorithms. It is currently not clear if the algorithm can lead to improved physical implementations in practice.

No background in quantum computation will be assumed.

Based on the recent arXiv preprint: https://arxiv.org/abs/2308.06572

Hierarchical clustering is a popular technique for organizing data as a rooted tree structure that simultaneously clusters data at multiple levels of granularity. A well-studied recent objective function views the input as a weighted graph with edges indicating similarity between the data points, and focuses on finding a tree that minimizes the cost of hierarchical partitioning. The resulting optimization problem is NP-hard, and previous algorithms for approximating this objective require at least linear time/space. In this talk, we will consider algorithms for hierarchical clustering that use sublinear resources (space, time, and communication). 

Specifically, we will present sublinear algorithms for hierarchical clustering in the streaming model (space), in the query model (time), and in the MPC model (communication). At the core of our algorithmic results is a connection between hierarchical clustering and a suitably relaxed notion of cut sparsifiers of graphs that lends itself to efficient sublinear algorithms. We complement our algorithmic results by establishing nearly matching lower bounds that rule out algorithms with better performance guarantees in each of these models.

This is joint work with Arpit Agarwal, Huan Li, and Prathamesh Patil.

Extremely Lossy Functions (ELFs) are families of functions that, depending on the choice during key generation, either operate in injective mode or instead have only a polynomial image size. The choice of the mode is indistinguishable to an outsider. ELFs were introduced by Zhandry (Crypto 2016) and have been shown to be very useful in replacing random oracles in a number of applications.

One open question is to determine the minimal assumption needed to instantiate ELFs. While all constructions of ELFs depend on some form of exponentially-secure public-key primitive, it was conjectured that exponentially-secure secret-key primitives, such as one-way functions, hash functions or one-way product functions, might be sufficient to build ELFs.

In this talk I will present our result which answers this conjecture mostly negatively: We show that no primitive, which can be derived from a random oracle (which includes all secret-key primitives mentioned above), is enough to construct even moderately lossy functions in a black-box manner. However, we also show that (extremely) lossy functions themselves do not imply public-key cryptography, leaving open the option to build ELFs from some intermediate primitive between the classical categories of secret-key and public-key cryptography.

Consider the following basic problem in sparse linear regression – an algorithm gets labeled samples of the form (x, <w.x> + \eps) where w is an unknown n-dimensional vector, x is drawn from a background distribution D and \eps is some independent noise. Given the promise that w is k-sparse, the breakthrough work of Candes, Rhomberg and Tao (2005) shows that w can be recovered with samples and time which scales as O(k log n). This should be contrasted with general linear regression where O(n) samples are information theoretically necessary.

In this talk, we look at this question from the vantage point of property testing and study the decision variant of the following question – namely, what is the complexity of deciding if the unknown vector w is k-sparse (or at least say 0.01 far from k-sparse in \ell_2 distance). We show that the decision version of the problem can be solved with samples which are independent of n as long as the background distribution D is i.i.d. and the components are not Gaussian. We further show that weakening any of the conditions in this result necessarily makes the complexity scale as log n (thus showing our results are tight).

Private Information Retrieval (PIR) allows a client to query a server holding a database $D$ (or a set of non-colluding servers holding the same database) for the value of the database at index $i$ (i.e., $D[i]$). Security warrants that the servers must not learn anything about $i$. Much research has focused on the concrete efficiency of PIR schemes; however, no scheme guarantees that the client will indeed receive $D[i]$ when some threshold number of servers can be malicious.

In this talk, I will describe the construction of the first 3-server PIR scheme where the client is guaranteed to obtain the output even in the presence of 1 malicious server. The protocol is concretely efficient and enjoys several attractive properties: 1) The client performs no cryptographic operations; 2) All cryptographic operations performed by the servers can be done in an offline pre-processing phase without the involvement of the client; 3) It is based on symmetric key cryptographic primitives. I will further talk about where this fits in the PIR landscape and its immediate applications.

Periodicity is a fundamental combinatorial property of strings. We say that p is a period of a string s[1..n] if s[i]=s[i+p] for every i such that both s[i] and s[i+p] are defined. While this notion seems interesting on its own, it can be often used as a tool for designing efficient algorithms. At a high level, many of such algorithms operate differently depending on whether a given string does or does not have a small period, where small usually means smaller than half of its length (or, say, quarter). In other words, we design an algorithm that is efficient if the given string is repetitive, and another algorithm that is efficient if the given string is non-repetitive, in every case carefully exploiting either the periodicity or the fact that input looks “random”, and then run the appropriate algorithm. Of course, in some cases, one needs to proceed in a more complex manner, and instead of classifying the whole string look at its substrings and process each of them differently depending on its structure. I will survey some of such results, including the recent generalization of periodicity that can be applied in approximate pattern matching.

For any Boolean functions $f$ and $g$, the question whether $R(f\circ g) = \tilde{\Theta}(R(f) \cdot R(g))$, is known as the composition question for the randomized query complexity. This question is one of the important and well-studied problems in the field of analysis of Boolean functions, and yet we are far from answering it satisfactorily.

It is known that the measure composes if one assumes various properties of the outer function (or inner function). In this talk we extend the class of outer functions for which randomized query composes. Specifically, we show that when the randomized query complexity of outer function is its arity (full), composition holds true for any inner function. Such a result was known for approximate degree composition but not for randomized query complexity.

The subset cover problem for $k \geq 1$ hash functions, which can be seen as an extension of the collision problem, was introduced in 2002 by Reyzin and Reyzin to analyse the security of their hash-function based signature scheme HORS. The security of many hash-based signature schemes relies on this problem or a variant of this problem (e.g. HORS, SPHINCS, SPHINCS+, $\dots$).

Recently, Yuan, Tibouchi and Abe (2022) introduced a variant to the subset cover problem, called restricted subset cover, and proposed a quantum algorithm for this problem. In this work, we prove that any quantum algorithm needs to make $\Omega\left((k+1)^{-\frac{2^{k}}{2^{k+1}-1}}\cdot N^{\frac{2^{k}-1}{2^{k+1}-1}}\right)$ queries to the underlying hash functions with codomain size $N$ to solve the restricted subset cover problem, which essentially matches the query complexity of the algorithm proposed by Yuan, Tibouchi and Abe.

We also analyze the security of the general $(r,k)$–subset cover problem, which is the underlying problem that implies the unforgeability of HORS under a $r$-chosen message attack (for $r \geq 1$). We prove that a generic quantum algorithm needs to make $\Omega\left(N^{k/5}\right)$ queries to the underlying hash functions to find a $(1,k)$–subset cover. We also propose a quantum algorithm that finds a $(r,k)$–subset cover making $O\left(N^{k/(2+2r)}\right)$ queries to the $k$ hash functions.

We study the computational complexity of finding a solution in straight-cut and square-cut pizza sharing, where the objective is to fairly divide 2-dimensional resources. We show that, for both the discrete and continuous versions of the problems, finding an approximate solution is PPA-complete even for very large constant additive approximation, while finding an exact solution for the square-cut problem is FIXP-hard and in BU. We also study the corresponding decision variants of the problems and their complexity. All our hardness results for the continuous versions apply even when the input is very simple, namely, a union of unweighted squares or triangles.

Joint work with Argyrios Deligkas and John Fearnley.

The problem of undirected st-connectivity is important both for its applications in network problems, and for its theoretical connections with logspace complexity. Classically, a long line of work led to a time-space tradeoff of T=Õ(n^2/S) for any S such that S=Ω(log(n)) and S=O(n^2/m), where T is the running time and S is the used space. In this talk, I will present a surprising result that quantumly there is no nontrivial time-space tradeoff: there is a quantum algorithm that achieves both optimal time Õ(n) and optimal space O(log(n)) simultaneously. This improves on previous results, which required either O(log(n)) space and Õ(n^1.5) time, or Õ(n) space and time. To complement this, we show that there is a nontrivial time-space tradeoff when given a lower bound on the spectral gap of a corresponding random walk.

I will talk about a random process that computes a maximal independent set (MIS) on a general n-vertex graph. Despite its simplicity, this process has hardly received attention in the literature. It is easy to prove that the process is fast on certain graph families, such cliques and trees. However, analyzing the process on graphs beyond these simple cases seems challenging. I will present a result stating that the process is fast also on G(n,p) random graphs, for 0 ≤ p ≤ poly(log n) ・n^(-1/2) and p ≥ 1/ poly(log n). I will also present an extension of this process which is fast on all G(n,p). Both processes readily translate into distributed MIS algorithms, which are self-stabilizing, use constant space, constant random bits per round, and work in distributed models with restricted communication capabilities.

The Generic Group Model (GGM) has been used to make analyses of many cryptographic assumptions and protocols. However, it is well known that the GGM should be used with caution, as there are protocols that are secure in this model that are not secure in practice. This motivates the study of standard model notions formalizing the fact that a real-world group “looks generic” in some sense.

We introduce a standard model definition called pseudo-generic group (PGG). The definition we obtain generalizes the Uber assumptions. Our other results focus on applications of PGGs. We first show that PGGs are a generalization of Uber, and then present a number of applications. Some of our implications use a new type of hash function, which we call linear dependency destroyers (LDDs) and which we use to relate PGGs to UCE hash functions (which are the analog of PGGs for hash functions).

Two of the most important questions in the theory of computer science are: - Is verifying the solution to a computational problem easier than deciding if one exists? - Can quantum computers solve problems their classical counterparts cannot? Indeed, their formalisations in the model of poly-time computation yield the fundamental P vs. NP (or BPP vs. MA) and BPP vs. BQP problems. Closely related is the “quantum P vs. quantum NP” question: - Is verification easier than decision *for quantum computers*?

In the property-testing setting, which models super-efficient algorithms that only probe a minuscule portion of their input, decision/verification and quantum/classical separations exist: positive answers to the first two questions have been known for some time. However, the property-testing analogue of QMA (“quantum NP”) has not heretofore been systematically explored. Our paper fills this gap by initiating its study: we formalise super-efficient quantum verifiers and study their power and limitations. Among other results, we prove all of the possible separations among QMA, MA and BQP in the property-testing setting.

Joint work with Tom Gur, Subhayan Roy Moulik and Justin Thaler.

Private Set Intersection (PSI) is a cryptographic primitive that allows parties to jointly compute the set of all common elements between their datasets, without leaking any value outside the intersection. It is a special case of secure multi-party computation (MPC). In this talk, we will introduce PSI and its state of the art. We also propose new protocols for private set intersection (PSI), building upon recent constructions of pseudorandom correlation generators, such as vector-OLE and ring-OLE. Our new constructions improve over the state of the art on several aspects and perform especially well in the setting where the parties have databases with small entries.

This joint work with Geoffroy Couteau was published at PKC 2023. Available here: ia.cr/2022/334

Increasing data sizes necessitate fast and efficient algorithms for analyzing them. Regression is one such essential tool that is used widely in computer science. In this talk, I will focus on the “p-​norm regression problem”, which is a generalization of the standard “linear regression problem”, and captures several important problems including the maximum flow problem on graphs. Historically, obtaining fast, high-​accuracy algorithms for this problem has been challenging due to the lack of smoothness and strong convexity of the function, however, recent breakthroughs have been able to get around these issues. I will present an overview of how these algorithms work and discuss some generalizations of these techniques to other regression problems.

Interior-point methods offer a highly versatile framework for convex optimization that is effective in theory and practice. A key notion in their theory is that of a self-concordant barrier. We give a suitable generalization of self-concordance to Riemannian manifolds and show that it gives the same structural results and guarantees as in the Euclidean setting, in particular local quadratic convergence of Newton's method. We analyze a path-following method for optimizing compatible objectives over a convex domain for which one has a self-concordant barrier, and obtain the standard complexity guarantees as in the Euclidean setting. We provide general constructions of barriers, and show that on the space of positive-definite matrices and other symmetric spaces, the squared distance to a point is self-concordant. To demonstrate the versatility of our framework, we give algorithms with state-of-the-art complexity guarantees for the general class of scaling and non-commutative optimization problems, which have been of much recent interest, and we provide the first algorithms for efficiently finding high-precision solutions for computing minimal enclosing balls and geometric medians in nonpositive curvature.

Joint work with Hiroshi Hirai and Michael Walter, based on https://arxiv.org/abs/2212.10981 and https://arxiv.org/abs/2303.04771.

We consider the traditional goals of cryptography, including secure communication and secure computation, when allowing only one-way communication over noisy channels: - Can Alice transmit a message to Bob without Eve learning this message? - Can Alice transmit exactly one of two messages to Bob without Alice learning which message was received?

We show how to circumvent information-theoretic impossibility results by settling for computational security and using the power of cryptographic obfuscation. In particular, under plausible assumptions, we obtain a positive answer to the first question whenever Alice's channel to Bob is not a degradation of the channel to Eve, and a positive answer to the second question over simple channels such as a binary symmetric channel or a binary erasure channel.

The first part of the talk is based on joint work with Alexis Korb, Paul Lou, and Amit Sahai. The second part is based on joint work with Shweta Agrawal, Eyal Kushilevitz, Varun Narayanan, Manoj Prabhakaran, Vinod M. Prabhakaran, and Alon Rosen.

Self-stabilization is a suitable paradigm for distributed systems, particularly prone to transient faults. Errors such as memory or messages corruption, break of a communication link, can put the system in an inconsistent state. A protocol is self-stabilizing if, whatever the initial state of the system, it guarantees that it will return a normal behavior in finite time. Several constraints concern algorithms designed for distributed systems. Asynchrony is one emblematic example. With the development of networks of connected, autonomous devices, it also becomes crucial to design algorithms with a low energy consumption, and not requiring much in terms of resources.

One way to address these problems is to aim at reducing the size of the messages exchanged between the nodes of the network. This thesis focuses on the memory optimization of the communication for self-stabilizing distributed algorithms. We will present a negative results, proving the impossibility to solve some problems under a certain limit on the size of the exchanged messages, and a particularly efficient algorithms in terms of memory for one fundamental problem in distributed systems: the token circulation.

The experimental violation of Bell inequalities has supported the rejection of classical mechanics in favour of quantum mechanics. But will we one day replace quantum mechanics by a more complete, *future* physical theory? In this work, we extend Bell's theorem to multipartite scenarios where the parties are constrained by the structure of a network. More precisely, we define and investigate the concept of genuinely multipartite nonlocality (GMNL), which is a property exhibited by some quantum correlations that can be obtained from quantum operations on N-partite quantum states but cannot be explained by convex combinations of local processes on (N-1)-partite states coming from any such *future* theories. We conclude by reporting some recent investigations of GMNL in graph states.

In this presentation we will dive in the core of Randomized Numerical Linear Algebra and present out recent results (Sobczyk and Luisier, NeurIPS 2022) related to the Johnson-Lindenstrauss (JL) lemma and its applications. We revisit a key problem: how to approximate the Euclidean lengths (or distances) of a set of high-dimensional vectors. Can we do better than JL? Based on techniques which are inspired by the recently published Hutch++ algorithm for trace estimation, we proposed algorithms which can (provably) improve the standard JL bounds, both in theory and in practice. We will describe all these algorithms and sketch the proof techniques. These improvements can ultimately lead to more practical and efficient randomized algorithms for scientific computing, especially when high accuracy is required, which is a known shortcoming of JL-based random projections. We will also discuss how these results can be applied to other problems, namely to compute Euclidean distances between high-dimensional data points, to estimate the statistical leverage scores of a matrix, and to approximate the charge densities in a quantum mechanical system. The talk will be concluded with open problems.

Chosen-ciphertext game-based security (CCA) definitions capture confidentiality by asking an adversary to distinguish between honestly computed encryptions of chosen plaintexts. In the context of voting systems, such guarantees have been shown to be sufficient to prove ballot privacy (Asiacrypt'12). In this presentation, we will see that they fall short when one seeks to obtain receipt-freeness, that is, when corrupted voters who submit chosen ciphertexts encrypting their vote must be prevented from proving how they voted to a third party. Since no known encryption security notion can lead to a receipt-free ballot submission process, we address this challenge by proposing a novel publicly verifiable encryption primitive coined Traceable Receipt-free Encryption (TREnc) and a new notion of traceable CCA security filling the definitional gap underlined above. TREnc is the first primitive allowing to generically realize a non-interactive receipt-free e-voting system in a flexible plug-and-play model. In addition to this sufficient condition, TREnc is mild enough to design the most efficient e-voting scheme among those achieving similar goals. In other words, modeling TREnc provides a better understanding of the cryptographic techniques that help reach receipt-freeness more easily.

Work published at Asiacrypt'22. Available here: https://ia.cr/2022/822.

Short Bio: Thomas Peters is a Professor and an FNRS research associate at UCLouvain, Belgium. He got a Master degree in pure mathematics and a Ph.D. in cryptography before joining ENS as a postdoc. His interests range from modeling security and building cryptographic primitives to the design of efficient public- and secret-key encryption schemes as well as advanced signature schemes with privacy-preserving features, and to zero-knowledge proofs.

Modern cryptography does not only enable to protect your personal data on the Internet, or to authenticate for certain services, but also evaluate a function on private inputs of multiple parties, without anyone being able to learn something about these inputs. Cryptographic protocols of this type are called “secure multiparty computation” and are suitable for a broad spectrum of applications, such as for voting or auctions, where the vote or bid should remain private. To prove security of such protocols, one needs assumptions that are often complexity-theoretic in nature – for example that it is difficult to factorize sufficiently large numbers. Security assumptions that are based on *physical principles* exhibit quite some advantages when compared to complexity-theoretic assumptions: the protocols are often conceptually simpler, the security is independent of the computational power of an attacker, and the functioning and security is often more transparent to humans. The talk highlights cryptographic protocols for secure multiparty computation that is executed with the help of a deck of *physical playing cards*. The security assumption is that the cards have indistinguishable backs and that certain shuffling actions can be performed securely. One application of these protocols is a didactic method to illustrate cryptography and to allow for secure multiparty computation that can be performed completely without any computer involved.

In this area of cryptography, researchers aim to construct protocols using a minimal number of cards – and to prove them optimal in this sense. Depending on the requirements posed to running time (finite vs. finite only in expectation) and to the practicability of the used shuffles, one can derive different lower bounds for the necessary number of cards. For the necessary structural insights to these lower bound results, I will present “state diagrams”, a graph-based representation of all possible protocol runs, which allow for direct reading of correctness and security from the diagram. With this method, proofs of lower bounds with respect to the number of cards become proofs that certain protocol states are not reachable in the associated combinatorial graph structure. Using this, one can even formalize the respective notions of card-based cryptography as a C program and prove the run-minimality of a card-minimal AND protocol using a Software Bounded Model Checking approach. If there is time, I will also briefly cover the case of secure multiparty computation that additionally protects the *function to be computed* for Turing machines.

The talk is meant as an accessible overview talk on the topic.

Studying embeddings of metric spaces has been demonstrated to be an extremely useful tool with several applications in computer science, most prominently for approximation algorithms. The goal is to embed a “difficult” metric space into another simpler metric space (such as Euclidean space), in a way that approximately preserves distances.

In this talk, I will consider embeddings of flat tori R^n/L, where L is an n-dimensional lattice. I will show how the least distortion embedding of a flat torus can be computed by an infinite-dimensional semidefinite program. Analysing the semidefinite program, I will derive some interesting results about the structure of least distortion embeddings. Additionally, I will discuss (potential) approaches to tackle the closest vector problem, by making use of the embedding of the torus R^n/L.

Based on joint work with Moritz Lücke, Frank Vallentin and Marc Zimmermann.

The Max-Cut problem is the meeting ground for two beautiful results in theoretical computer science: On the one hand we have the Tsirelson’s theorem for XOR games from quantum information and on the other hand we have the Goemans-Williamson’s hyperplane rounding algorithm, a celebrated result in combinatorial optimization. Making this connection explicit allows us to reinterpret the Goemans-Williamson algorithm in terms of operators rather than hyperplanes. We draw a few lessons from this reinterpretation and we see how one might extend this story to other problems in combinatorial optimization. The hope here is to obtain better approximation ratios for combinatorial optimization problems. We also see how one can tell this story purely in terms of non-local games. In the language of non-local games the question we are trying to answer is: Is there a good classical strategy hidden somewhere inside every quantum strategy of a nonlocal game?

We introduce a new bilinear operation, which we call Polyform, for fast approximate matrix multiplication, through sums of carefully weighted sparse polynomial multiplications. This algorithmic framework leads to several (parametrized) improvements over known worst-case speed-vs-accuracy tradeoffs for approximate matrix multiplication. It also yields a cheap practical alternative to matrix multiplication in deep neural networks (DNNs), which is the main bottleneck in large-scale training and inference.

This algorithm involves unexpected connections to additive combinatorics, sparse Fourier transforms, and spherical harmonics. In particular, optimizing the polynomial's coefficients leads to a (non-convex) low-rank SDP problem generalizing Spherical Codes. Meanwhile, our experiments demonstrate that, when using SGD to optimize these coefficients in DNNs, Polyform provides a major speedup on state-of-art DL models with minor accuracy loss. This suggests replacing matrix multiplication with (variants of) polynomial multiplication in large-scale deep neural networks.

Penguin A, who studies machine learning, has come up with an amazing circuit, that takes as input some parameters, such as how thick your feathers are, and outputs whether you have heightened risk of cold sensitivity or fish allergy.
 Penguin B would like to use the circuit, but does not want to reveal their sensitive medical data to A.
 On the other hand, the circuit contains sensitive medical information of a few other penguins, so A cannot simply publish the algorithm either.

Garbling to the rescue!

Garbling is a cryptographic technique that allows B to compute the output of A's circuit using B's data, without B learning anything about the circuit (other than the output) and without A learning B's data. In this talk, I show how A can “encrypt” each gate in the circuit and thus obtain a garbled circuit that B can evaluate, without learning what the gates are.

Additionally, I talk about the limitations on what types of circuits we can garble, in particular, what kind of security you can achieve, if you want to garble cryptographic circuits.

In the LOCAL model of distributed computing, where in a single round of communication each node can send to each of its neighbors a message of an arbitrary size, it is know that, classically, the round complexity of 3-coloring an n-node ring is Theta(log^∗ n). In the case where the communication is quantum, only trivial bounds were previously known: at least some communication must take place.

In a recent joint work with François Le Gall, we showed the first non-trivial quantum lower bound for 3-coloring by using the observation that the probabilistic output of the network must be non-signaling, thus effectively sidestepping the difficulty of characterizing the power of quantum entanglement.

In this talk, I will present our results, observations that led to them, and potential directions for future work.

In this talk, we introduce two complete equational theories: one for linear optical circuits and one for quantum circuits. More precisely, in both cases we introduce a set of circuit equations that we prove to be sound and complete: two circuits represent the same quantum evolution if and only if they can be transformed one into the other using the equations.

We shall first present our proposed equational theory for linear optical circuits. We shall then discuss how the semantics of both kind of circuits differ, and how to relate them using controlled-gates. The discussion will drive is to the completeness result for quantum circuits, based on the one for linear optical circuits.

Informally, obfuscation aims to compile programmes into unintelligible ones while preserving functionality. As a first approximation, this can be seen as trying to convert a programme to a “black-box representation”, which cannot be used for anything beyond obtaining its input/output behaviour. Learning, on the other hand, aims to generate the representation of a function given oracle access to it. In this talk, we will investigate new links between the two fields.

No specialised knowledge of cryptography or computational complexity is required, and the talk is aimed at a general TCS audience. For completeness however, we provide below a more technical description of our results.

Most recent works on cryptographic obfuscation focus on the high-end regime of obfuscating general circuits while guaranteeing computational indistinguishability between functionally equivalent circuits. Motivated by the goals of simplicity and efficiency, we initiate a systematic study of “low-end” obfuscation, focusing on simpler representation models and information-theoretic notions of security. We obtain the following results. 1) Positive results via “white-box” learning. We present a general technique for obtaining perfect indistinguishability obfuscation from exact learning algorithms that are given restricted access to the representation of the input function. We demonstrate the usefulness of this approach by obtaining simple obfuscation for decision trees and multilinear read-k arithmetic formulas. 2) Negative results via PAC learning. A proper obfuscation scheme obfuscates programs from a class C by programs from the same class. Assuming the existence of one-way functions, we show that there is no proper indistinguishability obfuscation scheme for k-CNF formulas for any constant k ≥ 3; in fact, even obfuscating 3-CNF by k-CNF is impossible. This result applies even to computationally secure obfuscation, and makes an unexpected use of PAC learning in the context of negative results for obfuscation. 3) Separations. We study the relations between different information-theoretic notions of indistinguishability obfuscation, giving cryptographic evidence for separations between them.

This is joint work with Elette Boyle, Yuval Ishai, Robert Robere, and Gal Yehuda, which was presented at ITCS 2023.

Correlation clustering is a classic model for clustering with several applications in data mining and unsupervised machine learning. In this problem, we are given a complete graph where each edge is labeled + or -; and the goal is to find a partition of the vertex set so as to minimize the number of + edges across the parts of the partition plus the number of – edges within the parts of the partition.

We will first present a new result showing that a constant number of rounds of the Sherali-Adams hierarchy yields a strict improvement over the natural LP: we present the first better-than-two approximation for the problem, improving upon the previous approximation of 2.06 of Chawla, Makarychev, Schramm, Yaroslavtsev based on rounding the natural LP (which is known to have an integrality gap of 2). We will then review several recent ideas which have led to practical constant factor approximations to Correlation Clustering in various setups: distributed and parallel environments, differentially-private algorithms, dynamic algorithms, or sublinear time algorithms.

This is a combination of joint works with Euiwoong Lee, Alantha Newman, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski, Chenglin Fan and Andreas Maggiori.

We propose a class of randomized quantum algorithms for the task of sampling from matrix functions, without the use of quantum block encodings or any other coherent oracle access to the matrix elements. As such, our use of qubits is purely algorithmic, and no additional qubits are required for quantum data structures. For NxN matrices, the space cost is log(N)+2 qubits and depending on the structure of the matrices, the gate complexity can be comparable to state-of-the-art methods that use quantum data structures of up to size O(N^2), when considering equivalent end-to-end problems. Within our framework, we present a quantum linear system solver that allows one to sample properties of the solution vector, as well as an algorithm for sampling properties of ground states of Hamiltonians. As a concrete application, we combine these two sub-routines to present a scheme for calculating Green's functions of quantum many-body systems.

Query complexity is a model computing that allows to understand algorithms, both quantum and classical. In this setting, we can prove rigorous upper and lower bounds, so we can make comparisons between the quantum and classical world. We will focus on the case of Boolean functions, $f: S\subseteq \{-1,1\}^n \to \{-1,1\}$. If f is total ($S=\{-1,1\}^n$), it is known that the quantum query complexity and the classical one are polynomially related. It is also known that for very structured problems (partial functions, with $|S|<<2^n$) these two quantities can be exponentially separated (see for instance period finding). A folklore conjecture dating from the 90's asserts that a lot of structure is indeed needed to attain these superpolynomial quantum advantages. Aaronson and Ambainis suggested a way of explaining that believe in 2009, when they conjectured that every bounded polynomial of bounded degree has a very influential variable. This, alongside the fact that quantum query algorithms output bounded polynomials of bounded degree, would imply that quantum query algorithms could be approximated by classical ones almost everywhere with only a polynomial overhead in the query complexity. The community has made a few attempts to prove this conjecture, but it is still open and it is only known to be true for some particular cases.

Nevertheless, it might not be necessary to prove the exact statement proposed by Aaronson and Ambainis to show that quantum speedups need structure. This is because in 2017 Arunachalam, Briet and Palazuelos showed that the output of quantum query algorithms are not only bounded, but also completely bounded. Given that being completely bounded is much more restrictive than being bounded, it might be easier to prove the Aaronson and Ambainis conjecture for this smaller family of polynomials. We explore this line of research and prove a new particular case of the Aaronson and Ambainis conjecture. To do show, we use the technique used by Varopoulos to rule out a trilinear von Neumann's inequality.

In this talk, we introduce Certificate Game complexity, a new measure of complexity based on the probability of winning a game in which two players are given inputs with different function values and are asked to output some index i where their inputs differ, in a zero-communication setting. We study four variants of it, namely those with private coin, public coin, shared entanglement and non-signaling strategies, and place them in the landscape of known complexity measures.

We show that the public coin model is bounded above by randomized query and certificate complexities, while the non-signaling model, which is the weakest model we consider, is bounded below by fractional certificate complexity. The quantum measure highlights an interesting and surprising difference between classical and quantum query models. While public coin certificate game complexity is bounded above by randomized query complexity, quantum certificate game complexity can be quadratically larger than quantum query complexity.

This is a joint work with Sourav Chakraborty, Anna Gal, Sophie Laplante and Rajat Mittal.

While quantum walk frameworks make it easy to design quantum algorithms, as evidenced by their wide application across domains, the major drawback is that they can achieve at most a quadratic speedup over the best classical algorithm.

In this work, we generalise the electric network framework – the most general of quantum walk frameworks, into a new framework that we call the multidimensional quantum walk framework, which no longer suffers from the aforementioned drawback, while still maintaining the original classical walk intuition. We then apply this framework to the k-distinctness problem, to obtain a time complexity that matches the currently best known query complexity by Belovs(2012), as well as to the welded trees problem, where we can solve the problem in a linear number of queries.

This talk will focus on the application to welded trees.

Joint work with Stacey Jeffery (2208.13492)

Classical computations are inherently “many-time”: given a device that performs a computation on a provided input, we can always (at least in principle) run the computation on many different inputs by rewinding the device, returning it to its initial state. This principle does not apply to quantum computations: a quantum computation can irreversibly lose information, and so cannot in general be rewound. This causes serious problems for the analysis of interactive cryptographic protocols in the quantum setting: the classical security reduction typically relies on the ability to rewind the adversary in order to record its responses across different interactions.

In this talk, I will present a new, general quantum rewinding technique that transforms a “one-time” quantum computation into a “many-time” computation. This opens the door to quantum security for many tasks. One key application is to prove that Kilian’s four-message succinct argument system for NP is secure against quantum attack (assuming the post-quantum hardness of the Learning with Errors problem).

Based on joint work with Alessandro Chiesa, Fermi Ma, Alex Lombardi, and Mark Zhandry.

The interplay between the properties of graphs and the eigenvalues of their adjacency matrices is well-studied. Important graph invariants, such as diameter and chromatic number, can be understood using these eigenvalue techniques. In this talk, we bring these classical techniques in algebraic graph theory to the study of quantum walks.

A system of interacting quantum qubits can be modelled by a quantum process on an underlying graph and is, in some sense, a quantum analogue of random walk. This gives rise to a rich connection between graph theory, linear algebra and quantum computing. In this talk, I will give an overview of applications of algebraic graph theory in quantum walks, as well as various recent results.

In a recent paper with V. Schmeits, we show that the evolution of a general discrete-time quantum walk that consists of two reflections satisfies a Chebyshev recurrence, under a projection. We apply this to a model of discrete-time quantum walk proposed by H. Zhan [J. Algebraic Combin. 53(4):1187-1213, 2020], whose transition matrix is given by two reflections, using the face and vertex incidence relations of a graph embedded in an orientable surface. For the vertex-face walk, we prove theorems about perfect state transfer and periodicity and give infinite families of examples where these occur.

We tackle the long-standing question of the computational complexity of determining homology groups of simplicial complexes, a fundamental task in computational topology, posed by Kaibel and Pfetsch 20 years ago. We show that this decision problem is QMA1-hard. Moreover, we show that a version of the problem satisfying a suitable promise and certain constraints is contained in QMA. This suggests that the seemingly classical problem may in fact be quantum mechanical. In fact, we are able to significantly strengthen this by showing that the problem remains QMA1-hard in the case of clique complexes, a family of simplicial complexes specified by a graph which is relevant to the problem of topological data analysis. The proof combines a number of techniques from Hamiltonian complexity and homological algebra. We discuss potential implications for the problem of quantum advantage in topological data analysis.

In this talk we investigate the relation between Collision Resistant Hash Functions and their distributional relaxation. Loosely speaking a shrinking function is called collision resistant if no probabilistic polynomial time adversary can produce two inputs that map to the same value, while it is (only) distributional collision resistant if such efficient adversaries cannot provide uniform such values.

While hash functions are commonly considered to be part of symmetric cryptography, their existence cannot be based on one-way functions in a black box manner (Simon'98), a result that directly extends to the distributional relaxation. Yet, we are able to show that distributional collision resistance cannot be boosted to (full) collision resistance. Formally, we show the existence of an oracle relative to which distributional collision resistant hash functions exist but (full) collision resistant hash functions do not.

Function Secret Sharing (FSS) allows a dealer to share a function f with two or more evaluators. Given secret shares of a function f, the evaluators can locally compute secret shares of f(x) on an input x, without learning information about f.

In this talk, I will present a model and constructions for access control in FSS. We consider a setting where evaluators need to ensure that the dealer is authorized to share the provided function. We show how, for a function family F and an access control list defined over the family, the evaluators receiving the shares of f (from the family F) can efficiently check that the dealer knows the corresponding access key in the access control list.

We show that this model enables new applications of FSS, such as: – anonymous authentication in a multi-party setting, – access control in private databases, and – authentication and spam prevention in anonymous communication systems.

Our definitions and constructions abstract and improve the concrete efficiency of several recent systems that implement ad-hoc mechanisms for access control over FSS.

Speaker bio: Sacha is a 4th year PhD student at MIT CSAIL working on privacy-preserving systems and applied cryptography.