## Algorithms and complexity

#### Day, hour and place

Tuesday / Wednesday at 11am, room 3052

The calendar of events (iCal format).

In order to add the event calendar to your favorite agenda, subscribe to the calendar by using this link.

#### Contact(s)

The live broadcasts are on Zoom.

The video recordings are on Youtube.

### Next talks

Algorithms and complexity

Monday June 24, 2024, 2PM, Salle 3052

**Chandrima Kayal** (ISI Kolkata) *To be announced.*

Algorithms and complexity

Tuesday June 25, 2024, 2PM, Salle 3052

**Atsuya Hasegawa** (The University of Tokyo) *On the Power of Quantum Distributed Proofs*

First, we give a more efficient dQMA protocol for the equality problem with a simpler analysis. We also show a quantum advantage for the equality problem on path networks still persists even when the network size is large, by considering “relay points” between extreme nodes. Second, we show that even in a general network, there exist efficient dQMA protocols for the ranking verification problem, the Hamming distance problem, and more problems that derive from efficient quantum one-way communication protocols. Third, in a line network, we construct an efficient dQMA protocol for a problem that has an efficient two-party QMA communication protocol. Finally, we obtain the first lower bounds on the proof and communication cost of dQMA protocols.

Based on joint work with Srijita Kundu and Harumichi Nishimura (https://arxiv.org/abs/2403.14108)

### Previous talks

#### Year 2024

Algorithms and complexity

Tuesday June 18, 2024, 11AM, Salle 3052

**Sebastian Zur** (QuSoft, University of Amsterdam) *Multidimensional Electrical Networks and their Application to Exponential Speedups for Graph Problems*

We first use this framework to find a marked vertex in one-dimensional random hierarchical graphs as defined by Balasubramanian, Li, and Harrow [arXiv ’23]. In this work, they generalised the well known exponential quantum-classical separation of the welded tree problem by Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman [STOC ’03] to random hierarchical graphs. Our result partially recovers their results with an arguably simpler analysis. Furthermore, by constructing a 3-regular graph based on welded trees, this framework also allows us to show an exponential speedup for the pathfinding problem. This solves one of the open problems by Li [arXiv ’23], where they construct a non-regular graph and use the degree information to achieve a similar speedup.

In analogy to the connection between the (edge-vertex) incidence matrix of a graph and Kirchhoff’s Law and Ohm’s Law in an electrical network, we also rebuild the connection between the alternative incidence matrix and Kirchhoff’s Alternative Law and Ohm’s Alternative Law. By establishing this connection, we expect that the multidimensional electrical network could have more applications beyond quantum walks.

Algorithms and complexity

Monday June 17, 2024, 11AM, Salle 3052

**Gopal Pandurangan** (University of Houston) *Energy-Efficient Distributed Algorithms*

In this talk we present results on energy-efficient distributed algorithms for various distributed computing problems. These results show that fundamental problems such as Maximal Independent Set (MIS), Leader Election, Spanning Tree, and Minimum Spanning tree (MST) and several other problems can be solved in a small awake complexity, which can be significantly better than the traditional round complexity (which counts both sleeping and awake rounds).

In particular, a main result that we will present is that the fundamental MIS problem can be solved in (expected) $O(1)$ rounds node-averaged awake complexity, which measures the average number of rounds a node is awake during the algorithm. In particular, we present a randomized distributed algorithm for MIS that has expected $O(1)$-rounds node-averaged awake complexity and, with high probability has $O(\log{n})$-rounds worst-case awake complexity and $O(\log^{3.41}n)$-rounds worst-case complexity.

We will also discuss a subsequent result that shows that MIS can be computed in $O(\log \log n)$ (worst-case) awake complexity that is exponentially better compared to the best known round complexity of $O(\log n)$ and also bypassing its fundamental $\Omega(\sqrt{\log n/\log \log n})$ round complexity lower bound exponentially.

Algorithms and complexity

Tuesday June 11, 2024, 11AM, Salle 3052

**Divyarthi Mohan** (Tel-Aviv University) *Optimal Stopping with Interdependent Values*

We study online selection problems in both the prophet and secretary settings, when arriving agents have interdependent values. In the interdependent values model, introduced in the seminal work of Milgrom and Weber [1982], each agent has a private signal and the value of an agent is a function of the signals held by all agents. Results in online selection crucially rely on some degree of independence of values, which is conceptually at odds with the interdependent values model. For prophet and secretary models under the standard independent values assumption, prior works provide constant factor approximations to the welfare. On the other hand, when agents have interdependent values, prior works in Economics and Computer Science provide truthful mechanisms that obtain optimal and approximately optimal welfare under certain assumptions on the valuation functions. We bring together these two important lines of work and provide the first constant factor approximations for prophet and secretary problems with interdependent values. We consider both the algorithmic setting, where agents are non-strategic (but have interdependent values), and the mechanism design setting with strategic agents. All our results are constructive and use simple stopping rules.

Joint work with Simon Mauras and Rebecca Reiffenhäuser.

Algorithms and complexity

Wednesday June 5, 2024, 11AM, Salle 4052 (PCQC)

**Marin Costes** (Université Paris-Saclay) *Space-time deterministic graph rewriting*

Algorithms and complexity

Tuesday June 4, 2024, 11AM, Salle 3052

**Kuo-Chin Chen** (Foxconn Research) *Quantum Walks on Simplicial Complexes and Harmonic Homology: Application to Topological Data Analysis with Superpolynomial Speedups*

Crucially, the walk operates on a state space encompassing both positively and negatively oriented simplices, effectively doubling its size compared to unoriented approaches. Through coherent interference of these paired simplices, we are able to successfully encode the combinatorial Laplacian, which would otherwise be impossible. This observation constitutes our major technical contribution. We also extend the framework by constructing variant quantum walks. These variants enable us to: (1) estimate the normalized persistent Betti numbers, capturing topological information throughout a deformation process, and (2) verify a specific QMA1-hard problem, showcasing potential applications in computational complexity theory.

Online talk

Algorithms and complexity

Wednesday May 29, 2024, 2PM, Salle 3052

**Leo Zhou** (Caltech) *Local Minima in Quantum Systems*

Algorithms and complexity

Tuesday May 28, 2024, 11AM, Salle 3052

**Nikolas Melissaris** (Aarhus University) *Cheater Identification on a Budget: MPC with Identifiable Abort from Pairwise MACs*

Cheater identification in MPC allows the honest parties to agree upon the identity of a cheating party, in case the protocol aborts. In the context of a dishonest majority, this becomes especially critical, as it serves to thwart denial-of-service attacks and mitigate known impossibility results on ensuring fairness and guaranteed output delivery.

In this work, we present a new, lightweight approach to achieving identifiable abort in dishonest majority MPC. We avoid all of the heavy machinery used in previous works, instead relying on a careful combination of lightweight detection mechanisms and techniques from state-of-the-art protocols secure with (non-identifiable) abort.

At the core of our construction is a homomorphic, multi-receiver commitment scheme secure with identifiable abort. This commitment scheme can be constructed from cheap vector oblivious linear evaluation protocols based on learning parity with noise. To support cheater identification, we design a general compilation technique, similar to a compiler of Ishai et al. (Crypto 2014), but avoid its requirement for adaptive security of the underlying protocol. Instead, we rely on a different (and seemingly easier to achieve) property we call online extractability, which may be of independent interest. Our MPC protocol can be viewed as a version of the BDOZ MPC scheme (Bendlin et al., Eurocrypt 2011) based on pairwise information-theoretic MACs, enhanced to support cheater identification and a highly efficient preprocessing phase, essentially as efficient as the non-identifiable protocol of Le Mans (Rachuri & Scholl, Crypto 2022).

Algorithms and complexity

Tuesday May 28, 2024, 3PM, Salle 4052 (PCQC)

**Galina Pass** (QuSoft, University of Amsterdam) *Multidimensional Quantum Walks, Recursion, and Quantum Divide & Conquer*

Algorithms and complexity

Tuesday May 21, 2024, 3PM, Salle 4052 (PCQC)

**Xiaodi Wu** (University of Maryland) *Hamiltonian-oriented Quantum Algorithm Design and Programming*

We propose to use quantum Hamiltonian evolution as the central object in end-to-end quantum application design, i.e. the so-called Hamiltonian-oriented paradigm, based on the observation that Hamiltonian evolution is a native abstraction for both low-level hardware control and high-level quantum applications. We illustrate that the Hamiltonian-oriented design not only allows more efficient implementation of existing quantum algorithms but also inspires novel quantum algorithms, especially in optimization and scientific computing, which are hard to perceive in the circuit model. We also develop a programming infrastructure called SIMUQ (SIMUlation language for Quantum) for easy implementation of Hamiltonian-based quantum applications for domain experts on heterogeneous quantum devices.

Algorithms and complexity

Tuesday May 21, 2024, 2PM, Salle 3052

**Lawrence Roy** (Aarhus University) *VOLE-in-the-Head and Post-Quantum Signatures*

Algorithms and complexity

Tuesday April 30, 2024, 11AM, Salle 3052

**André Chailloux** (INRIA Paris) *The Quantum Decoding Problem*

The purpose of this paper is to introduce and to lay a firm foundation for QDP. We first show QDP is likely to be easier than classical decoding, by proving that it can be solved in quantum polynomial time in a large regime of noise whereas no non-exponential quantum algorithm is known for the classical decoding problem. Then, we show that QDP can even be solved (albeit not necessarily efficiently) beyond the information theoretic Shannon limit for classical decoding. We give precisely the largest noise level where we can solve QDP giving the information theoretic limit for this new problem. Finally, we study how QDP can be used in the DRT reduction. First, we show that our algorithms can be properly used in the DRT reduction showing that our quantum algorithms for QDP beyond Shannon capacity can be used to find minimal weight codewords in a random code. On the negative side, we show that the DRT reduction cannot be, in all generality, a reduction between finding small codewords and QDP by exhibiting quantum algorithms for QDP where this reduction entirely fails. Our proof techniques include the use of specific quantum measurements, such as q-ary unambiguous state discrimination and pretty good measurements as well as strong concentration bounds on weight distribution of random shifted dual codes, which we relate using quantum Fourier analysis.

Algorithms and complexity

Tuesday April 23, 2024, 11AM, Salle 3052

**Team Event** *AlgoComp lightning talks ⚡️*

Algorithms and complexity

Tuesday April 16, 2024, 10AM, Salle 3052

**Zvi Lotker** (Bar-Ilan University) *Narratives: Shaping the Evolution of Social Networks and the Concept of Time (Part 2 of a mini-course of two sessions, 2 hours each)*

In the first lecture, we will cover chapters 11, 12, and 13. In the second lecture, we will cover chapters 14, 15, and 16.

Chapter 11 studies the perception of time in narrative. We model the narrative of a reader's experience of time as an evolving social network. This chapter takes the function analysis approach, which uses functions as the principal mathematical object. Therefore, the evolving social network is a function of time.

Chapter 12 introduces the notion of subjective and objective clocks. We model subjective time in narrative, and introduce a the subjective clock to allow machines to measure subjective time. We define clocks as an increasing monotonic function. This definition deviates from the traditional definition of clocks as oscillators. The advantage of the monotonic definition is that it is inclusive of both psychological/subjective clocks and objective clocks.

Chapter 13 explains how to compare clocks. Following the stochastic process definition of Martingales, the basic idea is to remove all Euclidean symmetries (such as translation and rotation) from the two clocks. This is equivalent to removing the linear part of those clocks. We introduce the $M$ diagram, which allows for representation of the two clocks as a function of each other after cancelling the Euclidean symmetry. We compare clocks by finding the point at which clocks begin to deviate from one another.

Chapter 14 uses the relationships between clocks to identify critical events in the evolution of a social network. We use the drift between the weighted clock and the event clock to identify critical events in weighted social networks. Chapter 14 defines the law of two clocks, which we can implement in narrative processing.

Chapter 15 provides techniques to transform evolving social networks into a real function. This helps us simplify the analysis of social networks. We use these techniques in narrative processing.

Chapter 16 defines higher orders of social networks and gives some explanation of evolving social network surfaces. We related social network surfaces to sub-stories within a larger overarching narrative.

Algorithms and complexity

Monday April 15, 2024, 10AM, Salle 3052

**Zvi Lotker** (Bar-Ilan University) *Narratives: Shaping the Evolution of Social Networks and the Concept of Time (Part 1 of a mini-course of two sessions, 2 hours each)*

In the first lecture, we will cover chapters 11, 12, and 13. In the second lecture, we will cover chapters 14, 15, and 16.

Chapter 11 studies the perception of time in narrative. We model the narrative of a reader's experience of time as an evolving social network. This chapter takes the function analysis approach, which uses functions as the principal mathematical object. Therefore, the evolving social network is a function of time.

Chapter 12 introduces the notion of subjective and objective clocks. We model subjective time in narrative, and introduce a the subjective clock to allow machines to measure subjective time. We define clocks as an increasing monotonic function. This definition deviates from the traditional definition of clocks as oscillators. The advantage of the monotonic definition is that it is inclusive of both psychological/subjective clocks and objective clocks.

Chapter 13 explains how to compare clocks. Following the stochastic process definition of Martingales, the basic idea is to remove all Euclidean symmetries (such as translation and rotation) from the two clocks. This is equivalent to removing the linear part of those clocks. We introduce the $M$ diagram, which allows for representation of the two clocks as a function of each other after cancelling the Euclidean symmetry. We compare clocks by finding the point at which clocks begin to deviate from one another.

Chapter 14 uses the relationships between clocks to identify critical events in the evolution of a social network. We use the drift between the weighted clock and the event clock to identify critical events in weighted social networks. Chapter 14 defines the law of two clocks, which we can implement in narrative processing.

Chapter 15 provides techniques to transform evolving social networks into a real function. This helps us simplify the analysis of social networks. We use these techniques in narrative processing.

Chapter 16 defines higher orders of social networks and gives some explanation of evolving social network surfaces. We related social network surfaces to sub-stories within a larger overarching narrative.

Algorithms and complexity

Tuesday April 9, 2024, 11AM, Salle 3052

**Christoph Egger** (IRIF) *On Fine-Grained Key-Agreement*

One can require the adversary to *find* a key or alternatively just require it to *distinguish* between the produced key and a random key. The two notions are equivalent given *classical* access to a random function oracle; however, they are different when parties have superposition access to said oracle – the best bound for the classical transformation uses semi-classical one-way-to-hiding due to Ambainis et al. (Crypto'19) which incurs a security degradation. Consequently, the key-agreement protocol by Brassard et al. (JCryptology'19) does not *directly* provide distinguishing security.

In the talk, I will present a key-agreement protocol relative to a random function oracle with superposition access, which directly provides distinguishing security, and discuss semi-classical one-way-to-hiding, which is a core building block of this work.

In a different direction, one can also base key agreement on space hardness: An adversary that has less *memory* than some (polynomial) bound fails to break the security. I will mention some preliminary results in this setting.

Algorithms and complexity

Friday April 5, 2024, 11AM, Salle 3052

**Yanlin Chen** (CWI Amsterdam) *A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix*

Our first algorithm used block-encoding techniques to compute the matrix-vector product as a quantum state, from which we obtain a classical description by a new time-efficient unbiased pure-state tomography algorithm that has essentially optimal sample complexity O(d log(d)/ε^2) and that comes with improved statistical properties compared to earlier pure-state tomography algorithms. Our second algorithm estimated the matrix-vector product one entry at a time, using a new “Gaussian phase estimation” procedure. We also develop a time-efficient process- tomography algorithm for reflections around bounded-rank subspaces, providing the basis for our top-eigensubspace estimation application.

This is the joint work with Ronald de Wolf and András Gilyén.

Algorithms and complexity

Tuesday April 2, 2024, 11AM, Salle 3071

**Michael Klooß** (Aalto University) *Adaptive Special Soundness: Improved Knowledge Extraction by Adaptive Useful Challenge Sampling*

However, special soundness fails to adequately capture guarantees provided by simple “probabilistic tests”, e.g., short random linear combinations as used in many lattice-based proof systems. In this talk, I will introduce (adaptive) special soundness, which captures many scenarios and discuss the rewinding-based knowledge extraction. Moreover, I will point out current limitations and open problems with regard to (adaptive) special soundness.

This talk is based on join work with Thomas Attema, Russell W. F. Lai, and Pavlo Yatsyna.

Algorithms and complexity

Tuesday March 26, 2024, 11AM, Salle 3052

**Willy Quach** (Weizmann Institute of Science) *How (not) to prove cryptographic security against quantum attacks*

In this talk, I will focus on the following basic question: how do we prove that a cryptographic construction is secure against quantum attacks? I will highlight a perhaps surprising distinction between the security of cryptographic constructions against quantum attacks, and the quantum hardness of the underlying problems that are used to reason about security. Doing so will highlight a natural connection to cryptographic proofs of quantumness.

Based on joint work with Alex Lombardi, Ethan Mook, and Daniel Wichs.

Algorithms and complexity

Tuesday March 19, 2024, 11AM, Salle 3052

**Joon Lee** (EPFL) *The Sparse Parity Matrix*

Algorithms and complexity

Tuesday March 12, 2024, 11AM, Salle 3052

**Christina Boura** (UVSQ) *New results in differential cryptanalysis*

Algorithms and complexity

Tuesday March 5, 2024, 11AM, Salle 3052

**Julian Wechs** (Université Libre de Bruxelles) *Subsystem decompositions of quantum circuits and processes with indefinite causal order*

Algorithms and complexity

Tuesday February 27, 2024, 11AM, Salle 3052

**Sophie Huiberts** (LIMOS, Clermont-Ferrand) *Open problems about the simplex method*

Algorithms and complexity

Tuesday February 27, 2024, 2PM, Salle 3052

**Christian Konrad** (University of Bristol) *An Unconditional Lower Bound for Two-Pass Streaming Algorithms for Maximum Matching Approximation*

We will focus on the two-pass setting, and we show that every randomized two-pass streaming algorithm that computes a better than 8/9-approximation to Maximum Matching requires strictly more than semi-streaming space.

Prior to our work, only a conditional two-pass lower bound by Assadi [SODA'22] was known that relates the quality of their lower bound to the maximum density of Ruzsa-Szemeredi graphs (RS-graphs) with matchings of linear sizes. In the best case, i.e., if very dense RS-graphs with linear-sized matchings exist, their lower bound rules out approximation ratios above 0.98, however, with current knowledge, only approximation factors of 1 − o(1) are ruled out.

Our lower bound makes use of the information cost trade-off of the Index problem in the two-party communication setting established by Jain et al. [JACM’09]. To the best of our knowledge, our work is the first that exploits this trade-off result in the context of lower bounds for multi-pass graph streaming algorithms.

Algorithms and complexity

Tuesday January 9, 2024, 4PM, Salle 3052

**Gabriel Senno** (Quside) *Quantifying the intrinsic randomness of quantum measurements*

#### Year 2023

Algorithms and complexity

Tuesday December 19, 2023, 11AM, Salle 3052

**Arthur Braida** (Atos) *Tight Lieb-Robinson Bound for approximation ratio in Quantum Annealing*

Algorithms and complexity

Wednesday December 13, 2023, 4PM, Salle 3052

**Ainesh Bakshi** (MIT) *Learning quantum Hamiltonians at any temperature in polynomial time*

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

online talk

Algorithms and complexity

Tuesday December 12, 2023, 11AM, Salle 3052

**Deeksha Adil** (ETH Zurich) *Dynamically Computing Approximate Eigenvectors*

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

Algorithms and complexity

Tuesday December 5, 2023, 11AM, Salle 3052

**Marc-Olivier Renou** (INRIA Saclay) *Causal and No Signalling-LOCAL models as the largest generalization of synchronous quantum distributed computing*

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.

Algorithms and complexity

Wednesday November 22, 2023, 11AM, Salle 4052 (PCQC)

**Sébastien Designolle** (Zuse Institut Berlin) *Frank-Wolfe algorithms for Bell nonlocality*

Algorithms and complexity

Wednesday November 22, 2023, 3PM, Salle 3052

**Sourav Chakraborty** (ISI Kolkata) *Distinct Elements in Streams and the Klee's Measure Problem*

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

Algorithms and complexity

Tuesday November 21, 2023, 11AM, Salle 3052

**Jessica Bavaresco** (University of Geneva) *Quantum information processing from the approach of higher-order operations*

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.

Algorithms and complexity

Tuesday November 21, 2023, 3PM, Salle 4052 (PCQC)

**Sourav Chakraborty** (ISI Kolkata) *Testing correctness of samplers using property testing: from theory to practice and back again*

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

Algorithms and complexity

Wednesday November 15, 2023, 11AM, Salle 1007

**Jinge Bao** (CQT, Singapore) *On the quantum time complexity of divide and conquer*

Algorithms and complexity

Tuesday November 14, 2023, 11AM, Salle 3052

**Aaron Sidford** (Stanford University) *Efficiently Minimizing the Maximum Loss*

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.

Algorithms and complexity

Wednesday November 8, 2023, 2PM, Salle 3052

**Marco Túlio Quintino** (LIP6) *Simulating qubit correlations with classical communication*

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.

Algorithms and complexity

Tuesday November 7, 2023, 2PM, Salle 4052 (PCQC)

**Casper Gyurik** (Leiden University) *On provable learning separations between classical and quantum learners*

Algorithms and complexity

Tuesday October 24, 2023, 11AM, Salle 3052

**Michele Orrù** (LIP6) *Elastic SNARKs for Diverse Environments*

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

Algorithms and complexity

Tuesday October 10, 2023, 11AM, Salle 3052

**Asad Raza** (LIP6) *MA-hardness of Geometrically Local Stoquastic Hamiltonians*

Algorithms and complexity

Tuesday October 3, 2023, 11AM, Salle 3052

**Marcos Kiwi** (Universidad de Chile) *Label propagation on binomial random graphs*

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

Joint seminar with Distributed

Algorithms and complexity

Wednesday September 27, 2023, 11AM, Salle 3052

**Oded Regev** (NYU Courant) *An Efficient Quantum Factoring Algorithm*

No background in quantum computation will be assumed.

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

Algorithms and complexity

Wednesday September 13, 2023, 11AM, Salle 147 (Olympe de Gouges)

**Sanjeev Khanna** (University of Pennsylvania) *Sublinear Algorithms for Hierarchical Clustering*

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.

Algorithms and complexity

Tuesday September 5, 2023, 11AM, Salle 147 (Olympe de Gouges)

**Felix Rohrbach** (Technische Universität Darmstadt) *Searching for ELFs in the Cryptographic Forest*

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.

Algorithms and complexity

Wednesday July 12, 2023, 11AM, Salle 147 (Olympe de Gouges)

**Anindya De** (University of Pennsylvania) *Testing Noisy Linear Equations for Sparsity*

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

Algorithms and complexity

Tuesday July 11, 2023, 11AM, Salle 147 (Olympe de Gouges)

**Naman Kumar** (IRIF) *Private Information Retrieval with Guaranteed Output*

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.

Algorithms and complexity

Tuesday July 4, 2023, 11AM, Salle 165 (Olympe de Gouges)

**Pawel Gawrychowski** (University of Wrocław) *How to exploit periodicity*

Algorithms and complexity

Tuesday June 27, 2023, 11AM, Salle 147 (Olympe de Gouges)

**Rajat Mittal** (IIT Kanpur) *Composition of randomized query for outer functions with full complexity*

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.

Algorithms and complexity

Tuesday June 20, 2023, 2PM, Salle 147 (Olympe de Gouges)

**Samuel Bouaziz-Ermann** (LIP6) *Quantum Security of Subset Cover Problems*

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.

Algorithms and complexity

Monday June 12, 2023, 11AM, Salle 147 (Olympe de Gouges)

**Themistoklis Melissourgos** (University of Essex) *Strong Inapproximability Results on Pizza-Sharing*

Joint work with Argyrios Deligkas and John Fearnley.

Joint seminar with Verification

Algorithms and complexity

Tuesday June 6, 2023, 11AM, Salle 147 (Olympe de Gouges)

**Galina Pass** (QuSoft, University of Amsterdam) *(No) Quantum space-time tradeoff for USTCON*

Algorithms and complexity

Tuesday May 16, 2023, 11AM, Salle 146 (Olympe de Gouges)

**Isabella Ziccardi** (University of L'Aquila) *Distributed Self-Stabilizing MIS with Few States and Weak Communication*

Algorithms and complexity

Wednesday May 3, 2023, 11AM, Salle 147 (Olympe de Gouges)

**Balthazar Bauer** (IRIF) *Beyond Uber: Instantiating Generic Groups via PGGs*

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

Algorithms and complexity

Tuesday April 25, 2023, 11AM, Salle 3052

**Marcel Dall'Agnol** (University of Warwick) *Complexity separations in quantum property testing*

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.

Algorithms and complexity

Tuesday April 18, 2023, 11AM, Salle 3052

**Dung Bui** (IRIF) *Private Set Intersection (PSI) and its Applications*

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

Algorithms and complexity

Tuesday April 18, 2023, 2PM, Salle 3052

**Deeksha Adil** (ETH Zurich) *Fast Algorithms for Regression Problems*

Algorithms and complexity

Wednesday April 12, 2023, 11AM, Salle 3052

**Harold Nieuwboer** (University of Amsterdam and Ruhr University Bochum) *Interior-point methods on manifolds: theory and applications*

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

Algorithms and complexity

Thursday April 6, 2023, 11AM, Salle 3052

**Yuval Ishai** (Technion) *Cryptography from One-Way Noisy Communication*

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.

Algorithms and complexity

Monday April 3, 2023, 2PM, Salle 3052

**Gabriel Le Bouder** (LIP6) *Memory-Optimization for Self-Stabilizing Distributed Algorithms*

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.

Joint seminar with Distributed

Algorithms and complexity

Tuesday March 21, 2023, 11AM, Salle 3052

**Xavier Coiteux-Roy** (TUM) *Any physical theory of nature must be boundlessly multipartite nonlocal*

Algorithms and complexity

Tuesday March 14, 2023, 11AM, Salle 3052

**Aleksandros Sobczyk** (IBM Research Zurich) *Approximate Euclidean lengths and distances beyond Johnson-Lindenstrauss*

Algorithms and complexity

Tuesday March 14, 2023, 2PM, Salle 3052

**Thomas Peters** (UCLouvain) *Traceable Receipt-Free Encryption*

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.

Algorithms and complexity

Wednesday March 8, 2023, 11AM, Salle 3052

**Alexander Koch** (IRIF) *An Introduction to Card-Based Cryptography*

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.

Algorithms and complexity

Tuesday February 28, 2023, 11AM, Salle 3052

**Arne Heimendahl** (University of Cologne) *Low distortion embeddings of flat tori*

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.

Algorithms and complexity

Tuesday February 28, 2023, 10AM, Salle 3052

**Hamoon Mousavi** (Columbia University) *Non-commutativity for combinatorial optimization*

Algorithms and complexity

Wednesday February 22, 2023, 11AM, Salle 3052

**Omri Weinstein** (Columbia University) *Approximate Matrix Multiplication via Spherical Convolutions*

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.

Algorithms and complexity

Tuesday February 21, 2023, 11AM, Salle 3052

**Pihla Karanko** (Aalto University) *Introduction to garbling (with penguin illustrations!)*

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.

Algorithms and complexity

Wednesday February 15, 2023, 11AM, Salle 3052

**Ansis Rosmanis** (Nagoya University) *Non-trivial quantum lower bound for 3-coloring the ring using non-signaling arguments*

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.

Algorithms and complexity

Tuesday February 14, 2023, 11AM, Salle 3052

**Benoît Valiron** (LMF, CentraleSupélec) *Complete Equational Theories for Linear Optical and Quantum Circuits*

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.

Joint seminar with PPS

Algorithms and complexity

Tuesday February 7, 2023, 11AM, Salle 3052

**Pierre Meyer** (IRIF / Reichman University) *On Low-End Obfuscation and Learning*

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.

Algorithms and complexity

Wednesday February 1, 2023, 2PM, Salle 3052

**Vincent Cohen-Addad** (Google Research) *Recent Progress on Correlation Clustering: The Power of Sherali-Adams and New Practical insights*

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.

Algorithms and complexity

Monday January 30, 2023, 11AM, Salle 3052

**Samson Wang** (Imperial College London) *Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra*

Algorithms and complexity

Wednesday January 25, 2023, 10AM, Salle 3052

**Francisco Escudero Gutiérrez** (CWI, Amsterdam) *Aaronson and Ambainis conjecture: a route towards the need for structure in quantum speedups*

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.

Algorithms and complexity

Wednesday January 25, 2023, 11AM, Salle 3052

**Anupa Sunny** (IRIF) *Certificate Games*

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.

Algorithms and complexity

Tuesday January 24, 2023, 11AM, Salle 3052

**Sebastian Zur** (CWI, Amsterdam) *Multidimensional Quantum Walks*

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)

Algorithms and complexity

Wednesday January 18, 2023, 11AM, Salle 3052

**Nicholas Spooner** (University of Warwick) *How to Rewind a Quantum Computer*

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.

online talk

Algorithms and complexity

Tuesday January 17, 2023, 2PM, Salle 3052

**Krystal Guo** (KdVI, University of Amsterdam) *Algebraic graph theory and 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.

Joint seminar with Graphs

Algorithms and complexity

Tuesday January 17, 2023, 11AM, Salle 3052

**Tamara Kohler** (mathQI, Universidad Complutense de Madrid) *Clique Homology is QMA1-hard*

Algorithms and complexity

Tuesday January 10, 2023, 11AM, Salle 3052

**Christoph Egger** (IRIF) *Separating Distributional Collision Resistance from (Plain) Collision Resistance*

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.

Algorithms and complexity

Tuesday January 10, 2023, 10AM, Salle 3052

**Sacha Servan-Schreiber** (MIT) *Private Access Control for Function Secret Sharing*

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.

#### Year 2022

Algorithms and complexity

Wednesday December 14, 2022, 11AM, Salle 3052

**Fabien Dufoulon** (University of Houston) *Sleeping is Superefficient: MIS in Exponentially Better Awake Complexity*

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.

Joint seminar with Distributed

Algorithms and complexity

Wednesday December 14, 2022, 2PM, Salle 3052

**Hang Zhou** (École Polytechnique) *Unsplittable Euclidean Capacitated Vehicle Routing*

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.

Algorithms and complexity

Tuesday December 6, 2022, 11AM, Salle 1004

**Changpeng Shao** (University of Bristol) *Quantum communication complexity of linear regression*

online talk

Algorithms and complexity

Wednesday November 30, 2022, 4PM, Salle 3052

**Ce Jin** (MIT) *Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and k-mismatch Matching*

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

online talk

Algorithms and complexity

Wednesday November 30, 2022, 11AM, Salle 3052

**Chris Brzuska** (Aalto University) *Obfuscation: Implications in Complexity and Cryptography*

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.

Algorithms and complexity

Tuesday November 22, 2022, 11AM, Salle 3052

**David Saulpic** (University of Vienna) *Embedding Euclidean Spaces into Trees for Clustering: Scalable Differentially Private Clustering*

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

Algorithms and complexity

Wednesday November 16, 2022, 2PM, Salle 3052

**Daniel Vaz** (DIENS/IRIF) *Good and Efficient Approximation for the Sparsest Cut Problem in Bounded-Treewidth Graphs*

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.

Algorithms and complexity

Tuesday November 15, 2022, 11AM, Salle 3052

**Arnaud De Mesmay** (LIGM) *Fitting Metrics and Ultrametrics with Minimum Disagreements*

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.

Algorithms and complexity

Tuesday November 8, 2022, 11AM, Salle 2017

**Dimitris Achlioptas** (University of Athens) *The Lovász Local Lemma as Approximate Dynamic Programming*

Algorithms and complexity

Wednesday October 5, 2022, 4:30PM, Salle 3052

**Daniel Szilagyi & Brandon Augustino** *Seminar Paris-Lehigh on Quantum Interior Point Methods*

Algorithms and complexity

Friday September 30, 2022, 2PM, Salle 1007

**Victor Verdugo** (Universidad de O'Higgins, Chile) *Multidimensional Apportionment Through Discrepancy Theory*

Algorithms and complexity

Wednesday July 20, 2022, 11AM, Salle 3052

**Maud Szusterman** (IRIF) *Compact formulations: how to deduce a linear extension from an algorithm?*

Algorithms and complexity

Tuesday July 12, 2022, 10AM, Salle 3052

**Seeun William Umboh** (The University of Sydney) *Online Weighted Cardinality Joint Replenishment Problem with Delay*

Algorithms and complexity

Tuesday July 12, 2022, 11AM, Salle 3052

**Kheeran Naidu** (University of Bristol) *Space Optimal Vertex Cover in Dynamic Streams (with an overview of graph streaming)*

Algorithms and complexity

Tuesday June 28, 2022, 11AM, Salle 3052

**Rajat Mittal** (IIT Kanpur) *Quantum query complexity (what, why and how)*

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.

Algorithms and complexity

Tuesday June 28, 2022, 3PM, Salle 3052

**Manaswi Paraashar** (Aarhus University) *Quantum weirdness in query-to-communication simulation and the role of symmetry*

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.

Algorithms and complexity

Tuesday June 21, 2022, 11AM, Salle 3052

**Chandrima Kayal** (ISI Kolkata) *Separations between Combinatorial Measures for Transitive Functions*

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.

Algorithms and complexity

Tuesday June 21, 2022, 3PM, Salle 3052

**Sayantan Sen** (ISI Kolkata) *Tolerant Bipartiteness Testing in Dense Graphs*

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

Algorithms and complexity

Tuesday June 7, 2022, 11AM, Salle 3052

**Francesco Mazzoncini** (Télécom Paris) *Hybrid Quantum Cryptography from One-way Quantum Communication Complexity Separation*

Algorithms and complexity

Tuesday June 7, 2022, 4PM, Salle 3052

**Srikanth Srinivasan** (IIT Bombay) *Some Recent (and Some Old) Advances in Algebraic Complexity Theory*

Algorithms and complexity

Tuesday May 17, 2022, 11AM, Salle 3052

**Luca Zanetti** (University of Bath) *How fast can you mix on a graph?*

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

Algorithms and complexity

Wednesday May 11, 2022, 11AM, Salle 3052

**Marios Ioannou** (Freie Universität Berlin) *Learnability of the output distributions of local quantum circuits*

Algorithms and complexity

Tuesday May 10, 2022, 5PM, Salle 3052

**Michele Orrù** (UC Berkeley) *On the (in)security of ROS*

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

Online talk

Algorithms and complexity

Wednesday April 27, 2022, 4PM, Salle 3052

**Hamoon Mousavi** (Columbia University) *Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy*

online talk

Algorithms and complexity

Wednesday April 20, 2022, 2PM, Salle 3052

**Subhasree Patro** (CWI Amsterdam) *Memory Compression with Quantum Random-Access Gates*

Algorithms and complexity

Wednesday April 20, 2022, 3PM, Salle 3052

**Arjan Cornelissen** (CWI Amsterdam) *Multivariate quantum Monte Carlo Estimation*

Algorithms and complexity

Wednesday April 20, 2022, 5PM, Salle 3052

**Pierre Meyer** (IDC Herzliya / IRIF) *Two-Round MPC from Minimal Assumptions*

Algorithms and complexity

Tuesday April 12, 2022, 11AM, Salle 3052

**Goran Žužić** (ETH Zurich) *Universal optimality in distributed computing and its connections to diverse areas of theoretical computer science*

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.

Algorithms and complexity

Tuesday April 12, 2022, 3PM, Salle 3052

**Balthazar Bauer** (IRIF) *Transferable E-cash: An analysis in the algebraic group model*

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.

Algorithms and complexity

Tuesday April 5, 2022, 2PM, LIP6, Tower 26, corridor 25/26, room 105

**Ivan Supic** (LIP6, Sorbonne University) *Quantum networks self-test all entangled states*

Algorithms and complexity

Tuesday March 29, 2022, 4PM, Salle 3052

**Sushant Sachdeva** (University of Toronto) *Maximum Flow and Minimum-Cost Flow in Almost-Linear Time*

The speaker will give the talk online.

Algorithms and complexity

Tuesday February 22, 2022, 2PM, Salle 3052

**Alain Sarlette** (QUANTIC lab, INRIA Paris) *Building a fault-tolerant quantum computer with bosonic cat-codes*

A Zoom link will be distributed via the qinfo-paris mailing list. If you would like to receive the link (or join the mailing list), please contact gribling@irif.fr

Algorithms and complexity

Tuesday January 25, 2022, 2PM, 3052

**Simona Etinski** (INRIA / IRIF) *Latest challenges in post-quantum cryptography*

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.

#### Year 2021

Algorithms and complexity

Wednesday December 15, 2021, 10AM, Salle 1007

**Serge Massar** (Laboratoire d’Information Quantique CP224, Université libre de Bruxelles) *Characterizing the intersection of QMA and coQMA*

Algorithms and complexity

Tuesday December 7, 2021, 11AM, Salle 1007

**Bruce Kapron** (Computer Science Department, University of Victoria) *Type-two feasibility via bounded query revision*

Recently, we have provided several such characterizations. The underlying idea is to bound run time in terms of an ordinary polynomial in the largest answer returned by an oracle, while imposing a constant upper bound on the number of times an oracle query (answer) may exceed all previous ones in size. The resulting classes are contained in Mehlhorn's class, and when closed under composition are in fact equivalent.

In this talk we will present these recent results and follow-up work involving new scheme-based characterizations of Mehlhorn's class, as well as a recent characterization using a tier-based type system for a simple imperative programming language with oracle calls.

(Joint work with F. Steinberg, and with E. Hainry, J.-Y. Marion, and R. Pechoux.)

Algorithms and complexity

Tuesday December 7, 2021, 2PM, 3052

**Daniel Szilagyi** *Introduction to convexity - optimization and sampling*

Quantum info Paris

Algorithms and complexity

Wednesday November 17, 2021, 11AM, Salle 1007

**Spyros Angelopoulos** (LIP6) *Competitive Sequencing with Noisy Advice*

We study such competitive sequencing problems in a setting in which the online algorithm has some (potentially) erroneous information, expressed as a k-bit advice string, for some given k. For concreteness, we follow the formulation of contract scheduling as case study. We first consider the untrusted advice setting in which the objective is to obtain a Pareto-optimal schedule, considering the two extremes: either the advice is error-free, or it is generated by a (malicious) adversary. Here, we show a Pareto-optimal schedule, using a new approach for applying the functional-based lower-bound technique due to [Gal, Israel J. Math. 1972]. Next, we introduce and study a new noisy advice setting, in which a number of the advice bits may be erroneous; the exact error is unknown to the online algorithm, which only has access to a pessimistic estimation (i.e., an upper bound on this error). We give the first upper and lower bounds on the competitive ratio of an online problem in this setting. To this end, we combine ideas from robust query-based search in arrays (such as Rényi-Ulam types of games) and fault-tolerant contract scheduling. The presentation will also discuss the applicability of these approaches in more general online problems.

Joint work with Diogo Arsénio and Shahin Kamali.

Algorithms and complexity

Tuesday October 19, 2021, 2PM, Salle 3052

**Stephen Piddock** (School of Mathematics, University of Bristol) *Quantum analogue simulation: universality and complexity*

Based on https://arxiv.org/abs/2003.13753 and https://arxiv.org/abs/2101.12319

Algorithms and complexity

Tuesday October 12, 2021, 11AM, Salle 1007

**Pierre Meyer** (IRIF, IDC Herzliya) *Breaking the Circuit Size Barrier for Secure Computation under Quasi-Polynomial LPN*

Our main application, and the motivation behind this work, is a generic two-party secure computation protocol for every layered (boolean or arithmetic) circuit of size $s$ with total communication $O(s/\log\log s)$ and polynomial computation, assuming the super-polynomial hardness of the standard learning parity with noise assumption (a circuit is layered if its nodes can be partitioned in layers, such that any wire connects adjacent layers). This expands the set of assumptions under which the `circuit-size barrier' can be broken, for a large class of circuits. The strength of the underlying assumption is tied to the sublinearity factor: we achieve communication $O(s/k(s))$ under the $s^{2^{k(s)}}$-hardness of LPN, for any $k(s) \leq (\log\log s) / 4$.

Previously, the set of assumptions known to imply a PCG for correlations of degree $\omega(1)$ or generic secure computation protocols with sublinear communication was restricted to LWE, DDH, and a circularly secure variant of DCR.

Algorithms and complexity

Tuesday June 22, 2021, 11AM, Salle 3052 + Zoom

**Subhasree Patro** (CWI) *Quantum Fine-Grained Complexity*

The situation in the quantum regime is no better; almost all known lower bounds for quantum algorithms are defined in terms of query complexity, which doesn’t help much for problems for which the best-known algorithms take superlinear time. Therefore, employing fine-grained reductions in the quantum setting seems a natural way forward. However, translating the classical fine-grained reductions directly into the quantum regime is not always possible for various reasons. In this talk, I will present some recent results in which we circumvent these challenges and prove quantum time lower bounds for some problems in BQP conditioned on the conjectured quantum hardness of SAT (and its variants) and the 3SUM problem.

Algorithms and complexity

Wednesday June 9, 2021, 10AM, Collège de France

**Frédéric Magniez - Elham Kashefi** (IRIF - CNRS, University of Edinburgh) *Derniers développements pour l’internet et intelligence artificielle quantique*

Algorithms and complexity

Tuesday June 8, 2021, 4PM, Online

**Kyriakos Axiotis** (MIT) *Decomposable Submodular Function Minimization via Maximum Flow*

Algorithms and complexity

Wednesday June 2, 2021, 10AM, Collège de France

**Frédéric Magniez - André Chailloux** (IRIF - INRIA) *Limites et impact du calcul quantique*

Algorithms and complexity

Wednesday May 26, 2021, 10AM, Collège de France

**Frédéric Magniez - Iordanis Kerenidis** (IRIF - CNRS) *Transformée de Fourier quantique II*

Algorithms and complexity

Wednesday May 19, 2021, 10AM, Collège de France

**Frédéric Magniez - Stacey Jeffery** (IRIF - CWI) *Optimisation quantique*

Algorithms and complexity

Wednesday May 12, 2021, 10AM, Collège de France

**Frédéric Magniez - Miklos Santha** (IRIF - CNRS, CQT) *Transformée de Fourier quantique I*

Algorithms and complexity

Wednesday May 5, 2021, 10AM, Collège de France

**Frédéric Magniez - Simon Perdrix** (IRIF - CNRS) *Circuits quantiques, premiers algorithmes*

Algorithms and complexity

Tuesday May 4, 2021, 11AM, Online

**Paweł Gawrychowski** (University of Wrocław) *Distance oracles and labeling schemes for planar graphs*

Algorithms and complexity

Wednesday April 14, 2021, 10AM, Collège de France

**Frédéric Magniez - Thomas Vidick** (IRIF - California Institute of Technology) *Cryptographie et communication quantiques*

Algorithms and complexity

Wednesday April 7, 2021, 10AM, Collège de France

**Frédéric Magniez - Eleni Diamanti** (IRIF - CNRS) *Information quantique, premières utilisations calculatoires*

Algorithms and complexity

Thursday April 1, 2021, 6PM, Collège de France

**Frédéric Magniez** (IRIF, Collège de France) *Algorithmes quantiques : quand la physique quantique défie la thèse de Church-Turing*

Lien de diffusion : https://www.youtube.com/watch?v=JqNvAN05R04

Algorithms and complexity

Tuesday March 30, 2021, 11AM, Zoom

**David Saulpic** (LIP6) *A New Coreset Framework for Clustering*

https://u-paris.zoom.us/j/88942335626?pwd=R25JRVhJWGU4dnNEUFYxZ1RKbDRPQT09

Algorithms and complexity

Tuesday March 16, 2021, 11AM, Room 3052 & Online

**Federico Centrone** (IRIF) *Experimental demonstration of quantum advantage for NP verification with limited information*

https://u-paris.zoom.us/j/88942335626?pwd=R25JRVhJWGU4dnNEUFYxZ1RKbDRPQT09

Algorithms and complexity

Tuesday March 2, 2021, 4PM, Zoom

**Soheil Behnezhad** (Department of Computer Science, University of Maryland) *Beating Two-Thirds For Random-Order Streaming Matching*

We prove that for an absolute constant $\epsilon_0 > 0$, one can find a $(2/3 + \epsilon_0)$-approximate maximum matching of $G$ using $O(n \log n)$ space with high probability. This breaks the natural boundary of $2/3$ for this problem prevalent in the prior work and resolves an open problem of Bernstein~[ICALP'20] on whether a $(2/3 + \Omega(1))$-approximation is achievable.

https://u-paris.zoom.us/j/88942335626?pwd=R25JRVhJWGU4dnNEUFYxZ1RKbDRPQT09

Algorithms and complexity

Tuesday February 9, 2021, 11AM, Online

**Xavier Waintal** (Univ. Grenoble Alpes, CEA) *What Limits the Simulation of Quantum Computers?*

Algorithms and complexity

Tuesday January 19, 2021, 11AM, Online

**Christian Konrad** (University of Bristol) *Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams*

This work appeared at CCC'20. Joint work with Jacques Dark.

Algorithms and complexity

Tuesday January 5, 2021, 11AM, Online

**Benny Applebaum** (Tel-Aviv University) *The Round Complexity of Perfectly-Secure Multiparty Computation*

I will survey a recent line of works that settles the round complexity of perfect-MPC with optimal security threshold for general functions. In particular, we show that 2 rounds are sufficient and necessary in the passive setting and 4 rounds are sufficient and necessary in the active setting.

Based on joint works with Zvika Brakerski, Eliran Kachlon, Arpita Ptra, and Rotem Tsabary.

BBB link: https://bbb-front.math.univ-paris-diderot.fr/recherche/yas-vbs-c25-ogj

#### Year 2020

Algorithms and complexity

Tuesday December 15, 2020, 2PM, Online

**Paul Fermé** (ENS Lyon) *Tight Approximation Guarantees for Concave Coverage Problems*

Based on joint work with Siddharth Barman and Omar Fawzi.

Algorithms and complexity

Wednesday December 2, 2020, 2PM, Online

**Claire Mathieu** (IRIF) *Competitive Data-Structure Dynamization*

Algorithms and complexity

Wednesday October 28, 2020, 11AM, Salle 3052 & En ligne

**Simon Mauras** (IRIF) *Assessment of Covid-19 containment strategies in primary schools and workplaces using contact graphs*

Algorithms and complexity

Wednesday October 21, 2020, 11AM, Salle 3052 & En ligne

**Geoffroy Couteau** (IRIF) *Contact Tracing*

Algorithms and complexity

Wednesday October 7, 2020, 11AM, Salle 3052

**Adrian Vladu** (IRIF) *Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs*

Our algorithm relies on developing an interior point method–based framework which acts on the space of circulations in the underlying graph. From the combinatorial point of view, this framework can be viewed as iteratively improving the cost of a suboptimal solution by pushing flow around some carefully chosen circulations.

This talk will be self-contained and will assume no prior background in optimization. Based on https://arxiv.org/abs/2003.04863, appears in FOCS 2020.

Algorithms and complexity

Thursday October 1, 2020, 2PM, Salle 3052

**Vera Traub** (University of Bonn) *An improved approximation algorithm for ATSP*

Svensson, Tarnawski, and Végh perform several steps of reducing ATSP to more and more structured instances. We avoid one of their reduction steps (to irreducible instances) and thus obtain a simpler and much better reduction to vertebrate pairs. Moreover, we show that a slight variant of their algorithm for vertebrate pairs has a much smaller approximation ratio.

Overall we improve the approximation ratio from 506 to 22 + ε for any ε > 0. We also improve the upper bound on the integrality ratio of the standard LP relaxation from 319 to 22.

This is joint work with Jens Vygen.

Live webcast of IGAFIT Algorithmic Colloquium

Algorithms and complexity

Friday September 25, 2020, 11AM, Salle 3052

**Makrand Sinha** (CWI) *k-Forrelation Optimally Separates Quantum and Classical Query Complexity*

Live webcast of CWI/QuSoft seminar

Algorithms and complexity

Friday September 18, 2020, 11AM, Salle 3052

**Arjan Cornelissen** (QuSoft, U of Amsterdam) *A self-contained, simplified analysis of span programs algorithms*

Live webcast of CWI/QuSoft seminar

Algorithms and complexity

Tuesday June 30, 2020, 7PM, Online

**Amos Korman** (IRIF) *SIROCCO Prize for Innovation in Distributed Computing*

Algorithms and complexity

Tuesday June 9, 2020, 2:30PM, Online

**Francesco D'amore** (INRIA) *On the Search Efficiency of Parallel Lévy Walks in ${\mathbb Z}^2$*

In this setting, we provide a comprehensive analysis of the efficiency of Lévy walks for the complete range of the exponent $\alpha$. For any choice of $\alpha$, we observe that the total work until the target is visited, i.e., the product $k \cdot h_{k,\ell}$, is at least $\Omega(\ell^2)$ with constant probability. Our main result is that the right choice for $\alpha$ to get optimal work varies between $1$ and $3$, as a function of the number $k$ of available agents. For instance, when $k = \tilde \Theta(\ell^{1-\epsilon})$, for some positive constant $\epsilon < 1$, then the unique optimal setting for $\alpha$ lies in the super-diffusive regime $(2,3)$, namely, $\alpha = 2+\epsilon$. Our results should be contrasted with various previous works in the continuous time-space setting showing that the exponent $\alpha = 2$ is optimal for a wide range of related search problems on the plane.

The online reference is here https://hal.archives-ouvertes.fr/hal-02530253

Algorithms and complexity

Tuesday June 2, 2020, 11AM, Online

**Weiqiang Wen** (IRISA) *Learning With Errors and Extrapolated Dihedral Cosets*

Algorithms and complexity

Tuesday May 26, 2020, 11AM, Online

**Édouard Bonnet** (ENS Lyon) *Twin-width*

Joint work with Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant

Algorithms and complexity

Tuesday May 19, 2020, 11AM, Online

**Vincent Cohen-Addad** (Google Zürich) *On the Parameterized Complexity of Clustering*

For many applications, finding efficient fixed-parameter algorithms is a very natural approach. Popular choices of parameters are either parameters of the problem itself (e.g. the number of clusters) or on the underlying structure of the input (e.g. the dimension in the metric case). We will focus on classic metric clustering objectives such as k-median and k-means and review recent results on the fixed parameter complexity of these problems, and the most important open problems.

Algorithms and complexity

Tuesday April 21, 2020, 11AM, Online

**Yihui Quek** (Stanford) *Robust Quantum Minimum Finding with an Application to Hypothesis Selection*

Algorithms and complexity

Friday April 10, 2020, 3PM, Online

**André Schrottenloher, Yixin Shen** (INRIA, IRIF) *Improved Classical and Quantum Algorithms for Subset-Sum*

Joint work with Xavier Bonnetain and Rémi Bricout.

Algorithms and complexity

Tuesday March 31, 2020, 2:30PM, Online

**Vincent Jugé** (LIGM) *Adaptive ShiversSort - A new sorting algorithm*

Algorithms and complexity

Thursday February 20, 2020, 10AM, Salle 3052

**Alantha Newman** (Université Grenoble Alpes) *Approximation algorithms based on LP and SDP rounding (Lecture 4/4)*

Additional information: https://pagesperso.g-scop.grenoble-inp.fr/~newmana/AlgsGTMiniCourse2020/

Algorithms and complexity

Tuesday February 18, 2020, 10AM, Salle 3052

**Alantha Newman** (Université Grenoble Alpes) *Approximation algorithms based on LP and SDP rounding (Lecture 3/4)*

Additional information: https://pagesperso.g-scop.grenoble-inp.fr/~newmana/AlgsGTMiniCourse2020/

Algorithms and complexity

Friday February 14, 2020, 10AM, Salle 3052

**Alantha Newman** (Université Grenoble Alpes) *Approximation algorithms based on LP and SDP rounding (Lecture 2/4)*

Additional information: https://pagesperso.g-scop.grenoble-inp.fr/~newmana/AlgsGTMiniCourse2020/

Algorithms and complexity

Thursday February 13, 2020, 10AM, Salle 3052

**Alantha Newman** (Université Grenoble Alpes) *Approximation algorithms based on LP and SDP rounding (Lecture 1/4)*

Additional information: https://pagesperso.g-scop.grenoble-inp.fr/~newmana/AlgsGTMiniCourse2020/

Algorithms and complexity

Tuesday February 11, 2020, 11AM, Salle 1007

**Simon Apers** (CWI) *Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving*

In this work we show that quantum algorithms allow to speed up spectral sparsification, and thereby many of the derived algorithms. To this end we build on a string of existing results, most notably sparsification algorithms by Spielman and Srivastava (STOC'08) and Koutis and Xu (TOPC'16), a spanner construction by Thorup and Zwick (STOC'01), a single-source shortest-paths quantum algorithm by Dürr et al. (ICALP'04) and an efficient k-wise independent hash construction by Christiani, Pagh and Thorup (STOC'15). Combining our sparsification algorithm with existing classical algorithms yields the first quantum speedup for approximating the max cut, min cut, min st-cut, sparsest cut and balanced separator of a graph. Combining our algorithm with a classical Laplacian solver, we demonstrate a similar speedup for Laplacian solving, for approximating effective resistances, cover times and eigenvalues of the Laplacian, and for spectral clustering.

This is joint work with Ronald de Wolf.

Algorithms and complexity

Tuesday February 4, 2020, 11AM, Salle 1007

**Jacques Dark** (University of Warwick) *Two-Party Lower Bounds for Graph Streaming Problems*

This is a very powerful tool which immediately transformed every sketching lower bound into a turnstile streaming lower bound - such as the tight bound for approximate maximum matching of [Assadi, Khanna, Li, Yaroslavtsev 2016]. However, there are many interesting input constraints we can consider which are not compatible with the sketching reduction. What happens if we enforce that the input graph must always be simple (contains no repeat edges)? What happens when we bound the number of deletions?

In this talk, I will present work towards answering these questions. We introduce a new elementary communication problem - finding a hidden bit in a partially revealed matrix - and show how tight two-party communication bounds for the maximum matching and minimum vertex cover problems can be achieved by surprisingly simple reductions from this problem. In particular, this gives us tight turnstile streaming bounds even for always-simple inputs or streams of bounded-length n^2. I will conclude with a conjecture for the bounded-deletions case and a discussion of the remaining challenges.

Joint work with Christian Konrad.

Algorithms and complexity

Tuesday January 28, 2020, 11AM, Salle 1007

**Spyros Angelopoulos** (LIP6) *Online Computation with Untrusted Advice*

Joint work with Christoph Dürr, Shendan Jin, Shahin Kamali and Marc Renault.

Algorithms and complexity

Thursday January 23, 2020, 11AM, Salle 1007

**Moni Naor** (Weizmann Institute) *Instance Complexity and Unlabeled Certificates in the Decision Tree Model*

In this talk I will discuss labeled and unlabeled certificates, in particular in the context of ``instance optimality“. This is a measure of goodness of an algorithm in which the performance of one algorithm is compared to others per input. This is in sharp contrast to worst-case and average-case complexity measures, where the performance is compared either on the worst input or on an average one, respectively.

Joint work with Tomer Grossman and Ilan Komargodski

Algorithms and complexity

Tuesday January 21, 2020, 11AM, Salle 1007

**Tatiana Starikovskaya** (ENS) *Sliding window property testing for regular languages*

In this work, we make an important step forward and combine the sliding window model with the property testing setting, which results in ultra-efficient algorithms for all regular languages. Informally, a sliding window property tester must accept the active window if it belongs to the language and reject it if it is far from the language. We consider deterministic and randomized sliding window property testers with one-sided and two-sided errors. In particular, we show that for any regular language, there is a deterministic sliding window property tester that uses logarithmic space and a randomized sliding window property tester with two-sided error that uses constant space.

The talk is based on a joint work with Ganardi, Hucke, and Lohrey published in ISAAC 2019.

Algorithms and complexity

Tuesday January 14, 2020, 11AM, Salle 1007

**Olivier Tercieux** (Paris School of Economics) *Unpaired Kidney Exchange: Overcoming Double Coincidence of Wants without Money*

Most of the talk is based on https://drive.google.com/file/d/1ZxPC3sc9HvrlG7JUtqCdyZ_BSHttkGhN/view. I'll also mention https://www.ipp.eu/publication/juin-2019-perspectives-sur-le-programme-de-dons-croises-de-reins-en-france/.

#### Year 2019

Algorithms and complexity

Tuesday December 17, 2019, 11AM, Salle 1007

**Clément Canonne** (IBM Research) *Uniformity Testing for High-Dimensional Distributions: Subcube Conditioning, Random Restrictions, and Mean Testing*

This is the “subcube conditional sampling model”, first considered in Bhattacharyya and Chakraborty (2018). We provide a nearly optimal ~O(sqrt{d})-algorithm for testing uniformity in this model. The key component of our proof is a natural notion of random restriction for distributions on {-1,1}^d, and a quantitative analysis of how such a restriction affects the mean vector of the distribution. Along the way, we provide a /very/ nearly tight upper bound on the (standard) sample complexity of a natural problem, “mean testing.”

Joint work with Xi Chen, Gautam Kamath, Amit Levi, and Erik Waingarten.

Algorithms and complexity

Monday December 16, 2019, 12:30AM, Amphi Turing

**M. Teillaud, T. Starikovskaya, M. Bonamy, C. Mathieu** *Autour des algorithmes*

Programme :

12h30-13h15 : Accueil et café

13h15-13h30 : Ouverture

13h30-14h15 : Exposé de Monique Teillaud, Autour des triangulations de Delaunay

14h15-15h : Exposé de Tatiana Starikovskaya, Streaming algorithms for string processing

15h-15h45 : Exposé de Marthe Bonamy, Complexity of graph coloring

15h45-16h15 : goûter

16h15-17h : Exposé de Claire Mathieu, Rank Aggregation

17h-18h : Table ronde “Prospectives de l'algorithmique en France” animée par Claire Mathieu. Participantes : Anne Boyer, Ioana Manolescu et Camille Terrier.

Algorithms and complexity

Tuesday December 3, 2019, 11AM, Salle 1007

**Shahrzad Haddadan** (Max Planck) *Algorithms for top-k Lists and Social Networks*

In the first part, we discuss algorithms on permutations as well as prefixes of permutations also known as top-k lists. The study of later particularly arises in big data scenarios when analysis of the entire permutation is costly or not interesting. We start by discussing random walks on the set of full rankings or permutations of n objects, a set whose size is n!. Since 1990s to today, various versions of this problem have been studied, each for different motivation.

The second part of the talk is devoted to property testing in social networks: given a graph, an algorithm seeks to approximate several parameters of a graph just by accessing the graph by means of oracles and while querying these oracles as few times as possible. We introduce a new oracle access model which is applicable to social networks, and assess the complexity of estimating parameters such as number of users (vertices) in this model.

In the third part of the talk, we introduce a new dynamic graph model which is based on triadic closure: a friendship is more likely to be formed between a pair of users with a larger number of mutual friends. We find upper bounds for the rate of graph evolution in this model and using such bounds we devise algorithms discovering communities. I will finish this talk by proposing new directions and presenting related open problems.

Algorithms and complexity

Wednesday November 27, 2019, 2PM, Salle 3052

**Adrian Vladu** (Boston University) *Submodular Maximization with Matroid and Packing Constraints in Parallel*

Our results are as follows:

* For a matroid constraint, in O(log^2 n/ε^3) adaptive rounds, we obtain a 1−1/e−ε approximation for monotone functions, and a 1/e−ε approximation for non-monotone functions. This offers an exponential speedup over the previously existing algorithms.

* For m packing constraints, up to polylogarithmic factors in n, m and 1/ε, we require Õ(1/ε^2) adaptive rounds to obtain a 1/e−ε approximation for non-monotone functions, and 1-1/e-ε approximation for monotone functions. This matches the iteration complexity of the fastest currently known parallel algorithm for solving packing linear programs [Young ’01, Mahoney et al, ’16].

Our results apply more generally to the problem of maximizing a diminishing returns submodular (DR-submodular) function.

Algorithms and complexity

Tuesday October 15, 2019, 11AM, Salle 1007

**Zvi Lotker** (Ben Gurion University) *Variation on preferential-attachment*

Algorithms and complexity

Tuesday September 10, 2019, 11AM, Salle 1007

**David Saulpic** (ENS) *Fast Approximation Schemes for Clustering in Doubling Metrics*

Algorithms and complexity

Tuesday July 2, 2019, 11AM, Salle 1007

**Andrei Romashchenko** (LIRMM) *An Operational Characterization of Mutual Information in Algorithmic Information Theory*

Algorithms and complexity

Monday June 24, 2019, 11AM, Salle 3052

**Carola Doerr** (CNRS, LIP6 Sorbonne University) *Evolutionary Algorithms – From Theory to Practice and Back*

In the last 15 years, the theory of randomized black-box optimization has advanced considerably, and has contributed to efficient optimization by providing insights into the working principles of black-box optimization which are hard or impossible to obtain by empirical means. On the other hand, empirically-guided benchmarking has opened up new research directions for theoretical investigations.

In this presentation we will discuss the state of the art in the theory of randomized black-box optimization algorithms. As part of this critical survey we will also mention a number of open questions and connections to other fields of Computer Science.

Algorithms and complexity

Thursday June 6, 2019, 2PM, Salle 3052

**Baruch Schieber** (NJIT) *Constrained Submodular Maximization via Greedy Local Search*

This is joint work with Kanthi Sarpatwar and Hadas Shachnai

Algorithms and complexity

Tuesday May 28, 2019, 11AM, Salle 1007

**Simon Apers** (INRIA) *Quantum Fast-Forwarding: Markov Chains and Graph Property Testing*

This tool leads to speedups on random walk algorithms in a very natural way. Specifically I will consider random walk algorithms for testing the graph expansion and clusterability, and show that QFF allows to quadratically improve the dependency of the classical property testers on the random walk runtime. Moreover, this new quantum algorithm exponentially improves the space complexity of the classical tester to logarithmic. As a subroutine of independent interest, I use QFF to determine whether a given pair of nodes lies in the same cluster or in separate clusters. This solves a robust version of s-t connectivity, relevant in a learning context for classifying objects among a set of examples. The different algorithms crucially rely on the quantum speedup of the transient behavior of random walks.

Algorithms and complexity

Tuesday May 21, 2019, 11AM, Salle 1007

**Miklos Santha** (IRIF, CQT) *Discrete logarithm and Diffie-Hellman problems in identity black-box groups*

Joint work with Gabor Ivanyos and Antoine Joux.

Algorithms and complexity

Tuesday May 7, 2019, 11AM, Salle 1007

**Benjamin Smith** (INRIA, LIX) *Pre- and post-quantum Diffie-Hellman from groups, actions, and isogenies*

Algorithms and complexity

Tuesday April 16, 2019, 11AM, Salle 1007

**Clément Canonne** (Stanford University) *Statistical Inference Under Local Information Constraints*

We propose a general formulation for inference problems in this distributed setting, and instantiate it to two fundamental inference questions, learning and uniformity testing. We study the role of randomness for those questions, and obtain striking separations between public- and private-coin protocols for the latter, while showing the two settings are equally powerful for the former. (Put differently, sharing with your neighbors does help a lot for the test, but not really for the learning.)

Based on joint works with Jayadev Acharya (Cornell University), Cody Freitag (Cornell University), and Himanshu Tyagi (IISc Bangalore).

Algorithms and complexity

Tuesday March 26, 2019, 11AM, Salle 1007

**Alexander Knop** (UC San Diego) *On proof systems based on branching programs*

Algorithms and complexity

Tuesday March 5, 2019, 11AM, Salle 1007

**Valia Mitsou** (IRIF) *Limitations of treewidth for problems beyond NP*

Algorithms and complexity

Friday March 1, 2019, 3PM, Salle 1007

**Jacob Leshno** (Chicago Booth) *Facilitating Student Information Acquisition in Matching Markets*

Algorithms and complexity

Tuesday February 26, 2019, 11AM, Salle 1007

**Uri Zwick** (Tel Aviv University) *Faster k-SAT algorithms using biased-PPSZ*

Joint work with Thomas Dueholm Hansen, Haim Kaplan and Or Zamir

Algorithms and complexity

Tuesday February 19, 2019, 11AM, Salle 3052

**Danupon Nanongkai** (KTH) *Distributed Shortest Paths, Exactly*

Algorithms and complexity

Tuesday January 29, 2019, 11AM, Salle 1007

**Balthazar Bauer** (ENS) *An application of communication complexity to cryptography*

#### Year 2018

Algorithms and complexity

Tuesday December 4, 2018, 11AM, Salle 1007

**Geoffroy Couteau** (KIT) *Compressing Vector OLE*

Oblivious linear-function evaluation (OLE) is a secure two-party protocol allowing a receiver to learn any linear combination of a pair of field elements held by a sender. OLE serves as a common building block for secure computation of arithmetic circuits, analogously to the role of oblivious transfer (OT) for boolean circuits. A useful extension of OLE is vector OLE (VOLE), allowing the receiver to learn any linear combination of two vectors held by the sender. In several applications of OLE, one can replace a large number of instances of OLE by a smaller number of long instances of VOLE. This motivates the goal of amortizing the cost of generating long instances of VOLE.

I will present a new approach for generating pseudo-random instances of VOLE via a deterministic local expansion of a pair of short correlated seeds and no interaction. This provides the first example of compressing a non-trivial and cryptographically useful correlation with good concrete efficiency. This result enjoys several applications; I will discuss in particular an application to the construction of non-interactive zero-knowledge proofs with reusable preprocessing.

Our VOLE generators are based on a novel combination of function secret sharing (FSS) for multi-point functions and linear codes in which decoding is intractable. Their security can be based on variants of the learning parity with noise (LPN) assumption over large fields that resist known attacks. I will also discuss recent exciting developments toward the 'dream goal' of compressing arbitrary pseudorandom bilinear correlations.

Algorithms and complexity

Tuesday November 27, 2018, 11AM, Salle 1007

**Sagnik Mukhopadhyay** (Computer Science Institute of Charles University) *Lifting theorems for Equality*

In this talk, I will talk about simulations or lifting theorems in general from a previous work of Chattopadhyay et al., and lifting theorem for Equality in particular—especially why the general recipe of Chattopadhyay et al. does not work for Equality. I will also mention an application of this technique to prove tight communication lower bound for Gap-Equality problem. This is a joint work with Bruno Loff.

Algorithms and complexity

Thursday November 22, 2018, 2PM, Salle 1007

**Aviad Rubinstein** (Stanford) *Distributed PCP Theorems for Hardness of Approximation in P*

Using our new framework, we obtain, for the first time, PCP-like hardness of approximation results for problems in P.

Based on joint works with Amir Abboud, Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy Rothblum, and Ryan Williams.

Algorithms and complexity

Tuesday October 16, 2018, 11:30AM, Salle 1007

**Suryajith Chillara** (IIT Bombay) *A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas*

Arithmetic formulas are directed trees where the leaves are labelled by variables and elements of the field, and internal vertices are labelled by + or x. Every internal vertex computes a polynomial by operating on its inputs. It is easy to see that they are a natural model of computation of polynomials, syntactically (symbolically). The size of the arithmetic formulas refers to the number of + and x operations needed to compute the polynomial.

Rephrasing the question in the algebraic setting we ask the following: for any s, \varepsilon >0, are there polynomial computations that can be efficiently computed by arithmetic formulas of size s but not by any arithmetic formula of size s^{1-\varepsilon}?

In this talk, we will restrict ourselves to arithmetic formulas where computation at every vertex is a multilinear polynomial and here we show explicit separations between the expressive powers of multilinear formulas of small-depth and all polynomial sizes. The multilinear restriction is a reasonable one since most polynomials of interest are indeed multilinear.

Formally, we will show that for any s = poly(n) and \delta > 0, we show that there are explicit polynomial families that have multilinear formulas of size at most s but no 'small'-depth multilinear formulas of size less than s^{0.5 - \delta}. Our proof can be viewed as a derandomization of a lower bound technique of Raz (JACM 2009) using \epsilon-biased spaces.

(Joint work with Nutan Limaye and Srikanth Srinivasan. Appeared in the proceedings of ICALP 2018.)

Algorithms and complexity

Tuesday September 4, 2018, 11AM, Salle 1007

**Kavitha Telikepalli** (Tata Institute of Fundamental Research) *Popular Matchings: A Tale of Two Classes*

Interestingly, all tractability results in popular matchings seem to reduce the popular matching problem to an appropriate question in either stable matchings or dominant matchings. Dominant matchings always exist in G and form a subclass of max-size popular matchings while stable matchings form a subclass of min-size popular matchings. We recently showed that deciding if G admits a popular matching that is neither stable nor dominant is NP-hard. This implies a tight 1/2-factor approximation for the max-weight popular matching problem in G and the hardness of finding a popular matching in a non-bipartite graph.

[Joint work with Agnes Cseh, Yuri Faenza, Chien-Chung Huang, Vladlena Powers, and Xingyu Zhang.]

Algorithms and complexity

Tuesday June 19, 2018, 11AM, Salle 1007

**Leonard Wossnig** (University College London) *Sketching as tool for faster quantum simulation*

Algorithms and complexity

Tuesday June 5, 2018, 11AM, Salle 1007

**Andrea Rocchetto** (Oxford - UCL) *Learnability and quantum computation*

Algorithms and complexity

Tuesday May 29, 2018, 11AM, Salle 1007

**Steve Alpern** (University of Wariwick, UK) *Shortest Paths in Networks with Unreliable Directions*

Algorithms and complexity

Tuesday May 22, 2018, 11AM, Salle 1007

**Anupam Prakash** (IRIF) *Improved quantum linear system solvers and applications to machine learning*

Algorithms and complexity

Wednesday April 11, 2018, 2PM, Salle 1007

**Libor Caha** (RCQI Bratislava) *The Feynman-Kitaev computer's clock: bias, gaps, idling and pulse tuning*

Joint work with Zeph Landau and Daniel Nagaj

Algorithms and complexity

Tuesday April 10, 2018, 11AM, Salle 1007

**Pierre Aboulker** (Université Grenoble-Alpes, Labo G-SCOP) *Distributed coloring of graphs with fewer colors*

This is a joint work with Bousquet, Bonamy, and Esperet.

Algorithms and complexity

Tuesday March 27, 2018, 11AM, Salle 1007

**Kamil Khadiev** (University of Latvia) *Quantum online algorithms with restricted memory*

We consider streaming algorithms and two-way automata as models for online algorithms. We compare quantum and classical models in case of logarithmic memory and sublogarithmic memory.

We get the following results for online streaming algorithms: - a quantum online streaming algorithm with 1 qubit of memory and 1 advice bit can be better than a classical online streaming algorithm with $o(\log n)$ bits of memory and $o(\log n)$ advice bits. - Quantum online streaming algorithm with a constant size of memory and $t$ advice bits can be better than deterministic online streaming algorithms with $t$ advice bits and unlimited computational power. - In a case of a polylogarithmic size of memory, quantum online streaming algorithms can be better than classical ones even if they have advice bits.

We get the following results for two way automata as an online algorithm for solving online minimization problems: - a two way automata with quantum and classical states for online minimization problems with a constant size of memory can be better than classical ones even if they have advice bits.

Algorithms and complexity

Tuesday March 20, 2018, 11AM, Salle 1007

**Valia Mitsou** (IRIF) *On the complexity of defective coloring.*

Defective coloring, like proper coloring, has many applications, for example in scheduling (assign jobs to machines which can work on up to Δ* jobs in parallel), or in radio networks (assign frequencies to antennas with some slack, that is, an antenna can be assigned the same frequency with up to Δ* other antennas within its range without a signal conflict).

We will present some algorithmic and complexity results on this problem in classes of graphs where proper coloring is easy: on the one hand, we will consider subclasses of perfect graphs, namely cographs and chordal graphs; on the other hand we will talk about structural parameterizations, such as treewidth and feedback vertex set.

Joint work with Rémy Belmonte (University of Electro-Communications, Tokyo) and Michael Lampis (Lamsade, Université Paris Dauphine) that appeared in WG '17 and in STACS '18.

Algorithms and complexity

Tuesday February 13, 2018, 11AM, Salle 1007

**Antoine Grospellier** (INRIA) *Efficient decoding of random errors for quantum expander codes*

Algorithms and complexity

Monday February 12, 2018, 2PM, Salle 3052

**Nabil Mustafa** (ESIEE) *Local Search for Geometric Optimization Problems.*

Algorithms and complexity

Tuesday February 6, 2018, 11AM, Salle 1007

**Shendan Jin** (LIP6) *Online Maximum Matching with Recourse*

In the first part of this paper, we consider the edge arrival model, in which an arriving edge never disappears from the graph. Here, we first show an improved analysis on the performance of the algorithm given in [AMP, 2013], by exploiting the structure of the specific problem. In addition, we extend the result of [Boyar et al., 2017] and show that the greedy algorithm has ratio 3/2 for every even positive k and ratio 2 for every odd k. Moreover, we present and analyze L-Greedy — an improvement of the greedy algorithm — which for small values of k outperforms the algorithm of [AMP, 2013]. In terms of lower bounds, we show that no deterministic algorithm better than 1+1/(k−1) exists, improving upon the lower bound of 1+1/k shown in [AMP, 2013].

The second part of the paper is devoted to the edge arrival/departure model, which is the fully dynamic variant of the online matching problem with recourse. The analysis of L-Greedy carries through in this model; moreover we show a general lower bound of (k2−3k+3)/(k2−4k+5) for all even k≥4 and provide the stronger bound of 10/7 for k=4. For k∈{2,3}, the competitive ratio is 3/2.

Joint work with Spyros Angelopoulos and Christoph Dürr.

Algorithms and complexity

Monday February 5, 2018, 2PM, Salle 2018

**Charles Bennett** *Do-It-Yourself randomness over Device-Independent randomness*

Algorithms and complexity

Tuesday January 30, 2018, 10AM, Collège de France, Amphithéâtre Maurice Halbwachs - Marcelin Berthelot

**Claire Mathieu - Allison Bishop** (DI ENS, IRIF - IEX and Columbia University) *On Algorithms Operating in Adversarial Conditions*

Additional information: http://www.college-de-france.fr/site/claire-mathieu/course-2018-01-30-10h00.htm

Algorithms and complexity

Tuesday January 23, 2018, 10AM, Collège de France, Amphithéâtre Maurice Halbwachs - Marcelin Berthelot

**Claire Mathieu - Tim Roughgarden** (DI ENS, IRIF - Stanford University) *On Game Theory Through the Computational Lens*

Additional information: http://www.college-de-france.fr/site/claire-mathieu/course-2018-01-23-10h00.htm

Algorithms and complexity

Wednesday January 17, 2018, 11AM, Salle 2015

**Philip Lazos** (Oxford) *The Infinite Server Problem*

Algorithms and complexity

Tuesday January 16, 2018, 10AM, Collège de France, Amphithéâtre Maurice Halbwachs - Marcelin Berthelot

**Claire Mathieu - Jon Kleinberg** (DI ENS, IRIF - Cornell University) *On Algorithms and Fairness*

Additional information: http://www.college-de-france.fr/site/claire-mathieu/course-2018-01-16-10h00.htm

Algorithms and complexity

Tuesday January 16, 2018, 2:30PM, Salle 3014

**Nicolas Thiery** (Université Paris Sud) *Computing huge subspaces of diagonal harmonic polynomials: symmetries to the rescue!*

To fuel his ongoing studies François needed to compute the structure of H(5,6). This is a space of dimension 6.10^5 made of polynomials in 30 variables of degree up to 15, each having thousands of terms.

In this talk, I'll explain how the calculation can now be completed in 45 minutes with a dozen cores and ~15Go of memory. This exploits a combination of strategies (symmetries, representation theory of the symmetric and general linear group, …), each of which reduces the complexity in time and memory by one or two orders of magnitude.

There will be little prerequisites and it's my hope that some strategies (and maybe the code!) could be used in other contexts.

Algorithms and complexity

Tuesday January 9, 2018, 10AM, Collège de France, Amphithéâtre Maurice Halbwachs - Marcelin Berthelot

**Claire Mathieu - Mark Jerrum** (DI ENS, IRIF - Queen Mary, University of London) *On Sampling and Approximate Counting*

Additional information: http://www.college-de-france.fr/site/claire-mathieu/course-2018-01-09-10h00.htm

#### Year 2017

Algorithms and complexity

Tuesday December 19, 2017, 10AM, Collège de France, Amphithéâtre Maurice Halbwachs - Marcelin Berthelot

**Claire Mathieu - Bruno Salvy** (DI ENS, IRIF - INRIA) *On Analytic Combinatorics*

Additional information: http://www.college-de-france.fr/site/claire-mathieu/course-2017-12-19-10h00.htm

Algorithms and complexity

Thursday December 14, 2017, 2:30PM, Salle 1016

**Emanuele Natale** (Max Planck Institute for Informatics) *Computing through Dynamics: Principles for Distributed Coordination*

Algorithms and complexity

Tuesday December 12, 2017, 10AM, Collège de France, Amphithéâtre Maurice Halbwachs - Marcelin Berthelot

**Claire Mathieu - Amos Fiat** (DI ENS, IRIF - University of Tel-Aviv) *On Static and Dynamic Pricing*

Additional information: http://www.college-de-france.fr/site/claire-mathieu/course-2017-12-12-10h00.htm

Algorithms and complexity

Tuesday December 12, 2017, 2PM, Salle 3052

**Jean Krivine** (IRIF) *Incremental Update for Graph Rewriting*

Reference: Boutillier P., Ehrhard T., Krivine J. (2017) Incremental Update for Graph Rewriting. In: Yang H. (eds) Programming Languages and Systems. ESOP 2017. Lecture Notes in Computer Science, vol 10201. Springer, Berlin, Heidelberg

Séminaire commun du pole Algorithmes et Structures Discrètes

Algorithms and complexity

Tuesday December 5, 2017, 10AM, Collège de France, Amphithéâtre Maurice Halbwachs - Marcelin Berthelot

**Claire Mathieu - Laurent Massoulié** (DI ENS, IRIF - INRIA) *Community Detection*

Additional information: http://www.college-de-france.fr/site/claire-mathieu/course-2017-12-05-10h00.htm

Algorithms and complexity

Tuesday November 28, 2017, 10AM, Collège de France, Amphithéâtre Maurice Halbwachs - Marcelin Berthelot

**Claire Mathieu - Pierre Fraigniaud** (DI ENS, IRIF - IRIF, CNRS) *On Distributed Algorithms*

Additional information: http://www.college-de-france.fr/site/claire-mathieu/course-2017-11-28-10h00.htm

Algorithms and complexity

Tuesday November 21, 2017, 11AM, Salle 1007

**André Chailloux** (INRIA Paris) *A tight security reduction in the quantum random oracle model for code-based signature schemes*

Joint work with Thomas Debris-Alazard

Algorithms and complexity

Thursday November 16, 2017, 2PM, Salle 3052

**Elena Kirshanova** (ENS Lyon) *Connections between the Dihedral Coset Problem and LWE*

Algorithms and complexity

Tuesday November 14, 2017, 2PM, 3052

**Laurent Massoulié** (MSR-Inria) *Rapid Mixing of Local Graph Dynamics*

This is joint work with Rémi Varloot.

Algorithms and complexity

Friday November 10, 2017, 3PM, Salle 3052

**Simon Apers** (Ghent University) *Mixing and quantum sampling with quantum walks: some results and questions*

Algorithms and complexity

Tuesday October 31, 2017, 11AM, Salle 1007

**Ami Paz** (IRIF) *A (2+\epsilon)-Approximation for Maximum Weight Matching in the Semi-Streaming Model*

We will start by discussing the local-ratio technique, a simple, sequential approximation paradigm we use in our algorithm. Then, we will consider the variations needed in order to adjust this technique to the semi-streaming model.

Based on a joint work with Gregory Schwartzman.

Algorithms and complexity

Tuesday October 17, 2017, 2PM, Salle 3052

**Claire Mathieu** (DI - ENS) *Online k-compaction*

This is joint work with Carl Staelin, Neal E. Young, and Arman Yousefi.

Algorithms and complexity

Tuesday October 10, 2017, 11AM, Salle 1007

**Victor Verdugo** (ENS - Universidad de Chile) *How Large is Your Graph?*

Algorithms and complexity

Tuesday October 3, 2017, 11AM, Salle 1007

**Giuseppe Italiano** (Universita di Roma Tor Vergata) *Decremental Single-Source Reachability and Strongly Connected Components in O(m \sqrt{n log n}) Total Update Time*

Joint work with Shiri Chechik, Thomas Dueholm Hansen, Jakub Łącki and Nikos Parotsidis.

Algorithms and complexity

Tuesday September 26, 2017, 11AM, Salle 1007

**Vianney Perchet** (CMLA, Ens Paris-Saclay) *Online Search Problems*

We also consider the non-bayesian case with a variant of regret minimization. We provide and analyze several algorithms with fast rates of convergence and/or guaranteed efficiency.

Algorithms and complexity

Tuesday September 19, 2017, 11AM, Salle 1007

**Vincent Viallat Cohen-Addad** *Hierarchical Clustering: Objective Functions and Algorithms*

We take an axiomatic approach to defining `good' objective functions for both similarity and dissimilarity-based hierarchical clustering. We characterize a set of “admissible” objective functions (that includes Dasgupta's one) that have the property that when the input admits a `natural' hierarchical clustering, it has an optimal value.

Equipped with a suitable objective function, we analyze the performance of practical algorithms, as well as develop better algorithms. For similarity-based hierarchical clustering, Dasgupta showed that the divisive sparsest-cut approach achieves an O(log^{3/2} n)-approximation. We give a refined analysis of the algorithm and show that it in fact achieves an O(\sqrt{log n})-approx. (Charikar and Chatziafratis independently proved that it is a O(\sqrt{log n})-approx.). This improves upon the LP-based O(logn)-approx. of Roy and Pokutta. For dissimilarity-based hierarchical clustering, we show that the classic average-linkage algorithm gives a factor 2 approx., and provide a simple and better algorithm that gives a factor 3/2 approx..

Finally, we consider `beyond-worst-case' scenario through a generalisation of the stochastic block model for hierarchical clustering. We show that Dasgupta's cost function has desirable properties for these inputs and we provide a simple 1 + o(1)-approximation in this setting.

Joint work with Varun Kanade, Frederik Mallmann-Trenn, and Claire Mathieu.

Algorithms and complexity

Tuesday July 11, 2017, 11AM, Salle 1007

**Oded Regev** (Courant Institute of Mathematical Sciences, NYU) *A Reverse Minkowski Theorem*

I will present a proof of a reverse form of Minkowski's theorem, conjectured by Daniel Dadush in 2012, showing that locally dense lattices are also globally dense (in the appropriate sense).

The talk will be self contained and I will not assume any familiarity with lattices.

Based on joint papers with Daniel Dadush and Noah Stephens-Davidowitz.

Algorithms and complexity

Thursday July 6, 2017, 11AM, Salle 3052

**Joel Friedman** (University of British Columbia) *Inner Rank and Lower Bounds for Matrix Multiplication*

We call the tool we use “inner rank,” which seems to have gone unnoticed in the literature (at least in the way we use it). While our bounds are not competitive with the best bounds to date over the complex numubers, we argue that “inner rank” may lead to improved results and merits further study.

Algorithms and complexity

Tuesday June 20, 2017, 11AM, Salle 1007

**Laurent Bulteau** (CNRS, Laboratoire d'Informatique Gaspard Monge, Marne-la-Vallée, France.) *Beyond Adjacency Maximization: Scaffold Filling for New String Distances*

Algorithms and complexity

Tuesday June 13, 2017, 11AM, Salle 1007

**Abel Molina** *The Optimality of Projections for Quantum State Exclusion*

Algorithms and complexity

Tuesday June 6, 2017, 4PM, 3052

**Thomas Vidick** (California Institute of Technology) *Entanglement Tests from Group Representations.*

(i) The first family of self-tests (or, two-player entangled games) for arbitrarily high-dimensional entanglement that is robust to a constant fraction of noise. (Joint work with Natarajan, arXiv:1610.03574.)

(ii) The first finite self-test such that for any eps>0, entangled states of dimension poly(1/eps) are both necessary and sufficient to achieve success probability 1-eps. (Joint work with Slofstra, in preparation.)

Algorithms and complexity

Tuesday May 2, 2017, 11AM, Salle 1007

**Pierre Senellart** (DI/ENS) *Tree decompositions for probabilistic data management*

In this talk, we review recent work on the problem of efficiently querying probabilistic databases, i.e., compact representations of probability distributions over databases, by exploiting the structure of the data. In the deterministic setting, a celebrated result by Courcelle shows that any monadic second-order query can be evaluated in linear-time on instances of bounded treewidth. We show that this result generalizes to probabilistic instances through the use of provenance. In the probabilistic setting, we show that a bound on the treewidth is necessary for query evaluation to be tractable, in sharp contrast with the deterministic setting. This leads us to studying which real-world databases actually have low treewidth, and to propose practical algorithms for query evaluation in databases that can be partially decomposed in a low-treewidth part and a high-treewidth core.

Pierre Senellart is a Professor in the Computer Science Department at the École normale supérieure in Paris, France, and the head of the Valda team of Inria Paris. He is an alumnus of ENS and obtained his M.Sc. (2003) and Ph.D. (2007) in computer science from Université Paris-Sud, studying under the supervision of Serge Abiteboul. He was awarded an Habilitation à diriger les recherches in 2012 from Université Pierre et Marie Curie. Before joining ENS, he was an Associate Professor (2008–2013) then a Professor (2013–2016) at Télécom ParisTech. He also held secondary appointments as Lecturer at the University of Hong Kong in 2012–2013, and as Senior Research Fellow at the National University of Singapore from 2014 to 2016. His research interests focus around practical and theoretical aspects of Web data management, including Web crawling and archiving, Web information extraction, uncertainty management, Web mining, and intensional data management.

Algorithms and complexity

Tuesday April 25, 2017, 11AM, Salle 1007

**Nicolas Flammarion** (DI/ENS) *Optimal rates for Least-Squares Regression through stochastic gradient descent.*

Algorithms and complexity

Tuesday April 18, 2017, 11AM, Salle 1007

**Adrian Kosowski** (Inria, IRIF Université Paris 7) *Protocols for Detecting a Signal*

We describe two population protocols which solve the considered problem efficiently, converging to a correct output state on a (1-epsilon)-fraction of a population of n agents within a polylogarithmic number of steps, starting from any initial configuration of the system, w.h.p. under a fair uniformly random scheduler. One of the proposed protocols requires O(log n) states and has certain desirable robustness properties, while the other uses only a constant number of states.

Algorithms and complexity

Thursday April 13, 2017, 2PM, Salle 3052

**Przemyslaw Uznanski** (ETH Zürich, Switzerland) *All-Pairs 2-reachability in O(n^ω log n) Time*

Moreover, our algorithm produces a witness (i.e., a separating edge or a separating vertex) for all pair of vertices where 2-reachability does not hold. By processing these witnesses, we can compute all the edge- and vertex-dominator trees of G in O(n^2) additional time, which in turn enables us to answer various connectivity queries in O(1) time. For instance, we can test in constant time if there is a path from u to v avoiding an edge e, for any pair of query vertices u and v, and any query edge e, or if there is a path from u to v avoiding a vertex w, for any query vertices u, v, and w.

This is a joint work with Loukas Georgiadis (University of Ioannina), Daniel Graf (ETH Zurich), Giuseppe Italiano and Nikos Parotsidis (University of Rome, Tor Vergata).

Link to the paper: https://arxiv.org/abs/1612.08075

Algorithms and complexity

Tuesday March 21, 2017, 11AM, Salle 1007

**Emanuele Natale** *Friend or Foe? Population Protocols can perform Community Detection*

More precisely, upon running the protocol, every node assigns itself a binary label of $m = \Theta(\log n)$ bits, so that with high probability, for all but a small number of outliers, nodes within the same community are assigned labels with Hamming distance $o(m)$, while nodes belonging to different communities receive labels with Hamming distance at least $m/2 - o(m)$. We refer to such an outcome as a “community sensitive labeling” of the graph.

Our algorithm uses $\Theta(\log^2 n)$ local memory and computes the community sensitive labeling after each node performs $\Theta(\log^2 n)$ steps of local work. Our algorithm and its analysis work in the “(random) population protocol” model, in which anonymous nodes do not share any global clock (the model is asynchronous) and communication occurs over one single (random) edge per round. We believe, this is the first provably-effective protocol for community detection that works in this model.

Joint work with Luca Becchetti, Andrea Clementi, Francesco Pasquale, Prasad Raghavendra, and Luca Trevisan.

Link to the arxiv version: https://arxiv.org/abs/1703.05045

Algorithms and complexity

Tuesday February 21, 2017, 11AM, Salle 1007

**Zvi Lotker** *Literature Networks and Time in Social Networks.*

Algorithms and complexity

Tuesday February 7, 2017, 11AM, Salle 1007

**Charles Paperman** *Streaming and circuit complexity*

Algorithms and complexity

Tuesday January 31, 2017, 11AM, Salle 1007

**Chien-Chung Huang** (CNRS, ENS Paris) *Popularity, Mixed Matchings, and Self-duality*

Motivated by the fact that a popular mixed matching could have a much higher utility than all popular matchings, we study the popular fractional matching polytope {\cal P}_G. Our main result is that this polytope is half-integral (and in the special case where a stable matching is a perfect matching, this polytope is integral), implying that there is always a max-utility popular mixed matching \Pi such that \Pi = {(M_0,\frac{1}{2}),(M_1,\frac{1}{2})} and \Pi can be computed in polynomial time. An immediate consequence is that in order to implement a max-utility popular mixed matching in $G$, we need just one single random bit.

We analyze {\cal P}_G whose description may have exponentially many constraints via an extended formulation in m+n dimensions with O(m+n) constraints. The linear program that gives rise to this formulation has an unusual property: self-duality. In other words, this linear program is exactly identical to its dual program. This is a rare case where an LP of a natural problem has such a property. The self-duality of the LP plays a crucial role in our proof of the half-integrality of {\cal P}_G.

We also show that our result carries over to the roommates problem, where the given graph G may not be bipartite. The polytope of popular fractional matchings is still half-integral here and thus we can compute a max-utility popular half-integral matching in G in polynomial time. To complement this result, we also show that the problem of computing a max-utility popular (integral) matching in a roommates instance G is NP-hard.

Algorithms and complexity

Tuesday January 10, 2017, 11AM, Salle 1007

**Vincent Jugé** (LSV, CNRS & ENS Cachan, Univ. Paris-Saclay) *Dynamic Complexity of Parity Games with Bounded Tree-Width*

In this talk, we will consider a specific class for dynamic complexity, called DynFO. A dynamic problem belongs to this class if updates can be performed by applying first-order formulas. We will show that a dynamic variant of Courcelle's theorem belongs to DynFO, and we will apply this result to computing optimal strategies in 2-player reachability or parity games.

This talk is based on joint a work with Patricia Bouyer-Decitre and Nicolas Markey.

#### Year 2016

Algorithms and complexity

Tuesday December 13, 2016, 11AM, Salle 1007

**Amos Korman** (CNRS, IRIF) *From Ants to Query Complexity*

This talk is based on joint works with biologists: Ofer Feinerman, Udi Fonio, Yael Heyman and Aviram Gelblum, and CS co-authors: Lucas Boczkowski, Adrian Kosowski and Yoav Rodeh.

Algorithms and complexity

Tuesday December 6, 2016, 11AM, Salle 1007

**Omar Fawzi** *Algorithmic aspects of optimal channel coding*

Based on joint work with Siddharth Barman. arXiv:1508.04095

Algorithms and complexity

Friday December 2, 2016, 11AM, Salle 1007

**Luc Sanselme** *Determinism and Computational Power of Real Measurement-based Quantum Computation*

We explore the consequences of this result for real MBQC and its applications. Real MBQC and more generally real quantum computing is known to be universal for quantum computing. Real MBQC has been used for interactive proofs by McKague. The two-prover case corresponds to real-MBQC on bipartite graphs. While (complex) MBQC on bipartite graphs are universal, the universality of real MBQC on bipartite graphs was an open question. We show that real bipartite MBQC is not universal proving that all measurements of real bipartite MBQC can be parallelised leading to constant depth computations. As a consequence, McKague techniques cannot lead to two-prover interactive proofs.

Joint work with Simon Perdrix.

Algorithms and complexity

Tuesday November 22, 2016, 11AM, Salle 1007

**Anca Nitulescu** (ENS Paris) *On the (In)security of SNARKs in the Presence of Oracles*

First, we formalize the question of extraction in the presence of oracles by proposing a suitable proof of knowledge definition for this setting. We call SNARKs satisfying this definition O SNARKs. Second, we show how to use O-SNARKs to obtain formal and intuitive security proofs for three applications (homomorphic signatures, succinct functional signatures, and SNARKs on authenticated data) where we recognize an issue while doing the proof under the standard proof of knowledge definition of SNARKs. Third, we study whether O-SNARKs exist, providing both negative and positive results. On the negative side, we show that, assuming one way functions, there do not exist O-SNARKs in the standard model for every signing oracle family (and thus for general oracle families as well). On the positive side, we show that when considering signature schemes with appropriate restrictions on the message length O-SNARKs for the corresponding signing oracles exist, based on classical SNARKs and assuming extraction with respect to specific distributions of auxiliary input.

Algorithms and complexity

Tuesday November 8, 2016, 11AM, Salle 1007

**Arpita Korwar** *Polynomial Identity Testing of Sum of ROABPs*

Polynomial identity testing (PIT) asks if a polynomial, input in the form of an arithmetic circuit, is identically zero.

One special kind of arithmetic circuits are read-once arithmetic branching programs (ROABPs), which can be written as a product of univariate polynomial matrices over distinct variables. We will be studying the characterization of an ROABP. In the process, we can give a polynomial time PIT for the sum of constantly many ROABPs.

Algorithms and complexity

Tuesday October 25, 2016, 11AM, Salle 1007

**Eric Angel** (Université d'Évry Val d'Essonne IBISC) *Clustering on k-edge-colored graphs.*

Algorithms and complexity

Tuesday October 18, 2016, 11AM, Salle 1007

**Carola Doerr** *Provable Performance Gains via Dynamic Parameter Choices in Heuristic Optimization*

Algorithms and complexity

Tuesday October 11, 2016, 11AM, Salle 1007

**Dieter van Melkebeek** (University of Wisconsin, Madison) *Deterministic Isolation for Space-Bounded Computation*

All of these algorithms are randomized, and the only reason is the use of the Isolation Lemma – that for any set system over a finite universe, a random assignment of small integer weights to the elements of the universe has a high probability of yielding a unique set of minimum weight in the system. For each of the underlying problems it is open whether deterministic algorithms of similar efficiency exist.

This talk is about the possibility of deterministic isolation in the space-bounded setting. The question is: Can one always make the accepting computation paths of nondeterministic space-bounded machines unique without changing the underlying language and without blowing up the space by more than a constant factor? Or equivalently, does there exist a deterministic logarithmic space mapping reduction from directed st-connectivity to itself that transforms positive instances into ones where there is a unique path from s to t?

I will present some recent results towards a resolution of this question, obtained jointly with Gautam Prakriya. Our approach towards a positive resolution can be viewed as derandomizing the Isolation Lemma in the context of space-bounded computation.

Algorithms and complexity

Tuesday September 20, 2016, 11AM, Salle 1007

**Eldar Fischer** (Faculty of CS, Technion - Israel Institue of Technology) *Improving and extending testing of distributions for shape restrictions.*

A test has to distinguish a distribution satisfying a given property from a distribution that is far in the variation distance from satisfying it. A range of properties such as monotonicity and log-concavity has been unified under the banner of L-decomposable properties. Here we improve upon the basic model test for all such properties, as well as provide a new test under the conditional model whose number of queries does not directly depend on n. We also provide a conditional model test for a wider range of properties, that in particular yields tolerant testing for all L-decomposable properties. For tolerant testing conditional samples are essential, as an efficient test in the basic model is known not to exist.

Our main mechanism is a way of efficiently producing a partition of {1,…,n} into intervals satisfying a small-weight requirement with respect to the unknown distribution. Also, we show that investigating just one such partition is sufficient for solving the testing question, as opposed to prior works where a search for the “correct” partition was performed.

Joint work with Oded Lachish and Yadu Vasudev.

Algorithms and complexity

Tuesday September 13, 2016, 11AM, Salle 1007

**Tatiana Starikovskaya** (IRIF, Université Paris Diderot) *Streaming and communication complexity of Hamming distance*

Algorithms and complexity

Monday August 29, 2016, 11AM, Room 2002

**Sanjeev Khanna** (University of Pennsylvania) *On the Single-Pass Streaming Complexity of the Set Cover Problem*

We show that to compute an $\alpha$-approximate set cover (for any $\alpha= o(\sqrt{n})$) via a single-pass streaming algorithm, $\Theta(mn/\alpha)$ space is both necessary and sufficient (up to an $O(\log{n})$ factor). We further study the problem of estimating the size of a minimum set cover (as opposed to finding the actual sets), and show that this turns out to be a distinctly easier problem. Specifically, we prove that $\Theta(mn/\alpha^2)$ space is both sufficient and necessary (up to logarithmic factors) for estimating the size of a minimum set cover to within a factor of $\alpha$. Our algorithm in fact works for the more general problem of estimating the optimal value of a covering integer program. These results provide a tight resolution of the space-approximation tradeoff for single-pass streaming algorithms for the set cover problem.

This is joint work with my students Sepehr Assadi and Yang Li.

Algorithms and complexity

Tuesday July 5, 2016, 11AM, Salle 1007

**Alexandra Kolla** (University of Illinois at Urbana-Champaign) *Towards Constructing Expanders via Lifts: Hopes and Limitations.*

Based on joint work with Naman Agarwal Karthik Chandrasekaran and Vivek Madan.

Algorithms and complexity

Tuesday June 21, 2016, 11AM, Salle 1007

**Nathanaël Fijalkow** *Alternating Communication Complexity, with Applications to Online Space Complexity*

Algorithms and complexity

Tuesday May 31, 2016, 11AM, Salle 1007

**Stacey Jeffery** (Institute for Quantum Information and Matter, Caltech) *Span Programs, NAND-Trees, and Graph Connectivity*

This is joint work with Shelby Kimmel.

Algorithms and complexity

Tuesday May 24, 2016, 11AM, Salle 1007

**Tim Black** (University of Chicago) *Monotone Properties of k-Uniform Hypergraphs are Weakly Evasive.*

Rivest and Vuillemin (1976) proved that all non-constant monotone graph properties (k=2) are weakly evasive, confirming a conjecture of Aanderaa and Rosenberg (1973). Kulkarni, Qiao, and Sun (2013) proved the analogous result for 3-graphs. We extend these results to k-graphs for every fixed k. From this, we show that monotone Boolean functions invariant under the action of a large primitive group are weakly evasive.

While KQS (2013) employ the powerful topological approach of Kahn, Saks, and Sturtevant (1984) combined with heavy number theory, our argument is elementary and self-contained (modulo some basic group theory). Inspired by the outline of the KQS approach, we formalize the general framework of “orbit augmentation sequences” of sets with group actions. We show that a parameter of such sequences, called the “spacing,” is a lower bound on the decision-tree complexity for any nontrivial monotone property that is G-invariant for all groups G involved in the orbit augmentation sequence, assuming all those groups are p-groups. We develop operations on such sequences such as composition and direct product which will provide helpful machinery for our applications. We apply this general technique to k-graphs via certain liftings of k-graphs with wreath product action of p-groups.

Algorithms and complexity

Tuesday May 17, 2016, 11AM, Salle 1007

**Nikhil Bansal** (Eindhoven University of Technology) *Solving optimization problems on noisy planar graphs*

We show that using linear programming methods such as configuration LPs and spreading metrics, one can get around these barriers and obtain PTASes for many problems on noisy planar graphs. This resolves an open question of Magen and Moharrami, that was recently popularized by Claire Mathieu.

Algorithms and complexity

Tuesday May 10, 2016, 11AM, Salle 1007

**Jean Cardinal** *Solving k-SUM using few linear queries*

Joint work with John Iacono and Aurélien Ooms

Algorithms and complexity

Tuesday May 3, 2016, 11AM, Salle 1007

**Mehdi Mhalla** (LIG Grenoble) *Pseudotelepathy games with graph states, contextuality and multipartiteness width.*

This is based on a joint work with Peter Hoyer and Simon Perdrix.

Algorithms and complexity

Tuesday April 26, 2016, 11AM, Salle 4033

**Jan Hackfeld** (TU Berlin) *Undirected Graph Exploration with Θ(log log n) Pebbles*

This talk is based on joint work with Yann Disser and Max Klimm (SODA'16).

Algorithms and complexity

Tuesday April 19, 2016, 11AM, Salle 1007

**Charles Bennett** *Is there such a thing as private classical information?*

Algorithms and complexity

Wednesday March 30, 2016, 2PM, Salle 3058

**Manoj Prabhakaran** (University of Illinois, Urbana-Champaign) *Rényi Information Complexity and an Information Theoretic Characterization of the Partition Bound*

- IC∞ is similar to information complexity IC, except that it uses Rényi mutual information of order ∞ instead of Shannon's mutual information (which is Rényi mutual information of order 1). Hence, the relaxation of IC∞ that yields IC is to change the order of Rényi mutual information used in its definition from ∞ to 1.

- The relaxation that connects IC∞ with partition complexity is to replace protocol transcripts used in the definition of IC∞ with what we term “pseudotranscripts,” which omits the interactive nature of a protocol, but only requires that the probability of any transcript given inputs x and y to the two parties, factorizes into two terms which depend on x and y separately. While this relaxation yields an apparently different definition than (log of) partition function, we show that the two are in fact identical. This gives us a surprising characterization of the partition bound in terms of an information-theoretic quantity.

Further understanding IC∞ might have consequences for important direct-sum problems in communication complexity, as it lies between communication complexity and information complexity.

We also show that if both the above relaxations are simultaneously applied to IC∞, we obtain a complexity measure that is lower-bounded by the (log of) relaxed partition complexity, a complexity measure introduced by Kerenidis et al. (FOCS 2012). We obtain a similar (but incomparable) connection between (external) information complexity and relaxed partition complexity as Kerenidis et al., using an arguably more direct proof.

This is joint work with Vinod Prabhakaran.

Algorithms and complexity

Friday March 11, 2016, 11AM, Salle 1007

**Christian Konrad** (Reykjavik University) *Streaming Algorithms for Partitioning Sequences and Trees*

In this talk, I will present streaming algorithms for both problems. The presented algorithms require a random access memory whose size is only logarithmic in the size of the input, which makes them good candidates for performing well in practice. This work will be presented next week at ICDT 2016, the 19th International Conference on Database Theory.

Algorithms and complexity

Tuesday February 23, 2016, 11AM, Salle 1007

**Ashwin Nayak** (University of Waterloo) *Sampling quantum states*

Joint work with Ala Shayeghi.

Algorithms and complexity

Tuesday February 16, 2016, 11AM, Salle 1007

**Johan Thapper** (Université Paris-Est, Marne-la-Vallée, LIGM) *Constraint Satisfaction Problems, LP relaxations and Polymorphisms*

A quite general optimisation version of the CSP is obtained by replacing the relations by arbitrary functions from tuples of domain values to the rationals extended with positive infinity. The goal of this problem, called the Valued Constraint Satisfaction Problem (VCSP), is to minimise a sum of such functions over all assignments. The complexity classification project of the VCSP has taken some great strides over the last four years and has recently been reduced to its more famous decision problem counterpart: the dichotomy conjecture for the CSP.

I will talk about how polymorphisms appear in the study of the CSP and some of what universal algebra has taught us. I will then show how these results can be used for characterising the efficacy of Sherali-Adams linear programming relaxations of the VCSP.

This is based on joint work with Standa Zivny, University of Oxford (UK).

Algorithms and complexity

Tuesday February 2, 2016, 11AM, Salle 1007

**Balthazar Bauer** *Compression of communication protocols*

Algorithms and complexity

Tuesday January 26, 2016, 11AM, Salle 1007

**Chien-Chung Huang** (Chalmers University of Technology and Göteborg University) *Exact and Approximation Algorithms for Weighted Matroid Intersection*

The core of our algorithms is a decomposition technique: we decompose an instance of the weighted matroid intersection problem into a set of instances of the unweighted matroid intersection problem. The computational advantage of this approach is that we can make use of fast unweighted matroid intersection algorithms as a black box for designing algorithms. Precisely speaking, we prove that we can solve the weighted matroid intersection problem via solving $W$ instances of the unweighted matroid intersection problem, where $W$ is the largest given weight. Furthermore, we can find a $(1-\epsilon)$-approximate solution via solving $O(\epsilon^{-1} \log r)$ instances of the unweighted matroid intersection problem, where $r$ is the smallest rank of the given two matroids.