## Algorithms and complexity

#### Day, hour and place

Tuesday at 11am, room 1007

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 BigBlueButton or Zoom.

The video recordings are on Youtube.

### Next talk

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.

### Previous talks

#### Year 2021

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.