Given a distribution p​​ on {-1,1}^d​​, we want to test whether p​​ is uniform. If p is assumed to be a product distribution, this can be done with Theta(sqrt{d}) samples; without this assumption, then things get exponentially worse and Theta(sqrt{2^d}) are necessary and sufficient. Assume however we can condition on arbitrary bits: does the problem become easier? If so, how much?

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.

This half-day of talks is in celebration of Algorithms, the research domain of Claire Mathieu, 2019 recipient of a CNRS Silver Medal. The talks, aimed at a non-specialized audience, will present a sample of research on Algorithms in France in a few selected areas: Computational Geometry (Monique Teillaud), Strings (Tatiana Starikoskaya), Graphs and Complexity (Marthe Bonamy), and Social Choice (Claire Mathieu). The afternoon will conclude with a discussion of new research directions in Algorithms. The participants to the roundtable will give their viewpoint on problems in the design and analysis of algorithms arising from their respective research domains. We may hear about statistical machine learning, clustering, and social networks (Anne Boyer), data journalism, detection of fake news, and magaging data in the Cloud (Ioana Manolescu), and economics and society (Camille Terrier).

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.

Today’s massive and dynamic data sets have motivated many computer scientists and mathematicians to study classical problems in combinatorics and graph theory in various settings. In certain settings the algorithms’ access to the data is restricted while in others the resources are limited. In this talk we explore such settings in three directions: ranking of objects, property testing in social networks and finding communities in dynamic graphs.

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.

We study the adaptive complexity of maximizing the multilinear extension of a submodular function, subject to a matroid constraint, or multiple packing constraints. The goal is to match the best approximation guarantees known in the classical sequential setting while performing only few adaptive rounds, each of which consists of a polynomially bounded number of queries to an evaluation oracle.

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.

In this talk, I will describe how preferential attachment arises from the first principle using game theory. Next, I will extend the model of preferential attachment into a general model, which allows for the incorporation of Homophily ties in the network. This talk is based on joint works with Prof. Chen Avin, Avi Cohen, Yinon Nahum, Prof. Pierre Fraigniaud, and Prof. David Peleg.

We consider classical clustering problems such as k-Median or k-Means in metric spaces that generalize Euclidean space, namely doubling metrics. We give a surprisingly simple framework that yields nearly linear-time approximation schemes for each problem, making a significant improvement over the state-of-the-art algorithms which run in time n^(d/\eps)^O(d), for metric of doubling dimension d. Moreover, we show how to extend the techniques used to get the first efficient approximation schemes for the problems of prize-collecting $k$-Medians and $k$-Means, and efficient bicriteria approximation schemes for k-Medians with outliers, k-Means with outliers and k-Center.

We show that for every pair of strings (x,y) the mutual information between x and y in the sense of Kolmogorov complexity is equal (within logarithmic precision) to the length of the longest shared secret key that two parties, one having x and the other one having y, can establish via a probabilistic protocol with interaction on a public channel. We extend this result to the setting of L>2 parties holding mutually correlated strings x_1 … x_L. [Joint work with Marius Zimand]

Most real-world optimization problems do not have an explicit problem formulation, but only allow to compute the quality of selected solution candidates. Solving such black-box optimization problems requires iterative procedures which use the feedback gained from previous evaluations to determine the strategy by which the next solution candidates are generated. Many black-box optimization algorithms, such as Simulated Annealing, Evolutionary Algorithms, Swarm Intelligence Algorithms, are randomized – making it very difficult to analyze their performances mathematically.

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.

We present a simple combinatorial 1/2(1-1/e^2)-approximation algorithm for maximizing a monotone submodular function subject to a knapsack and a matroid constraint. This classic problem is known to be hard to approximate within factor better than 1-1/e. We extend the algorithm to yield 1/(k+1)(1-1/e^(k+1)) approximation for submodular maximization subject to a single knapsack and k matroid constraints, for any fixed k > 1. Our algorithms, which combine the greedy algorithm of [Khuller, Moss and Naor, 1999] and [Sviridenko, 2004] with local search, show the power of this natural framework in submodular maximization with combined constraints.

This is joint work with Kanthi Sarpatwar and Hadas Shachnai

I will introduce a new tool for quantum algorithms called quantum fast-forwarding (QFF). The tool uses quantum walks as a means to quadratically fast-forward a reversible Markov chain. In a number of quantum walk steps that scales as the square root of the classical runtime, and inversely proportional to the 2-norm of the classical distribution, it retrieves a quantum superposition that encodes the classical distribution. This shows that quantum walks can accelerate the transient dynamics of Markov chains, thereby complementing the line of results that proves the acceleration of their limit behavior.

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.

We investigate the computational complexity of the discrete logarithm, the computational Diffie-Hellman and the decisional Diffie-Hellman problems in some identity black-box groups G_{p,t}, where p is a prime number and t is a positive integer. These are defined as quotient groups of vector space Z_p^{t+1} by a hyperplane H given through an identity oracle. While in general black-box groups with unique encoding these computational problems are classically all hard and quantumly all easy, we find that in the groups G_{p,t} the situation is more contrasted. We prove that while there is a polynomial time probabilistic algorithm to solve the decisional Diffie-Hellman problem in G_{p,1}, the probabilistic query complexity of all the other problems is Omega(p) and their quantum query complexity is Omega(\sqrt{p}). Our results therefore provide a new example of a group where the computational and the decisional Diffie-Hellman problems have widely different complexity.

Joint work with Gabor Ivanyos and Antoine Joux.

Diffie-Hellman key exchange is at the foundations of public-key cryptography, but conventional group-based Diffie-Hellman is vulnerable to Shor's quantum algorithm. A range of 'post-quantum Diffie-Hellman' protocols have been proposed to mitigate this threat, including the Couveignes, Rostovtsev-Stolbunov, SIDH, and CSIDH schemes, all based on the combinatorial and number-theoretic structures formed by isogenies of elliptic curves. Pre-and post-quantum Diffie-Hellman schemes resemble each other at the highest level, but the further down we dive, the more differences emerge-differences that are critical when we use Diffie-Hellman as a basic component in more complicated constructions. In this survey we compare and contrast pre-and post-quantum Diffie-Hellman algorithms, highlighting some important subtleties.

Independent samples from an unknown probability distribution p on a domain of size k are distributed across n players, with each player holding one sample. Each player can send a message to a central referee in a simultaneous message passing (SMP) model of communication, whose goal is to solve a pre-specified inference problem on p. The catch, however, is that each player cannot simply send their own sample to the referee; instead, the message they send must obey some (local) information constraint. For instance, each player may be limited to communicating only L bits, where L « log k; or they may seek to reveal as little information as possible, and preserve local differential privacy.

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

It is well known that there is a connection between resolution complexity of a formula and complexity of (very weak) branching programs for the corresponding search problem. In the talk, we will discuss proof systems that allow to generalize this statement and explain the lower bounds for these proof systems. In order to achieve this lower bounds, we show how to transform functions with a high fixed-partition communication complexity into functions with a high best-partition communication complexity and as a result, we translate the landscape of fixed-partition communication complexity classes into the landscape of best-partition communication complexity classes.

In this seminar, we take a closer look at the parameterized complexity of problems belonging in Σ^p_2 and Π^p_2, the second level of the polynomial hierarchy. We provide tight fine-grained bounds on their complexity with respect to the most important structural graph parameter, the treewidth. We observe that these problems exhibit similar behavior: we show that a variety of problems including Choosability, ∃∀SAT, along with several problems from AI such as Abduction, Abstract Argumentation and others, while they admit a $2^{2^{O(tw)}}$ algorithm, they cannot be solved in time $2^{2^{o(tw)}}$ under the Exponential Time Hypothesis.

We develop a tractable model for a matching market where students form preferences through costly information acquisition. As the market outcome consists of both an assignment as well as the acquired information, we study how the marketplace can direct both the allocation and the information acquisition process. We define regret-free stable outcomes, where the matching is stable under the partial preferences and each student has acquired information optimally, as if she were last to market; regret-free stable outcomes are optimal in settings where students make decentralized decisions about how to acquire information and can wait for more information. We show that regret-free stable outcomes always exist and can be characterized by cutoffs. However, we also show that regret-free stable outcomes cannot be discovered under practical restrictions – any discovery process can reach deadlocks where every student would like to wait for additional market information before acquiring information. Instead, historical information can facilitate the implementation of approximate regret-free stable outcomes, suggesting that an important role of matching markets is to aggregate information from multiple years. We also provide a method for bootstrapping information acquisition when historical information is not available.

The PPSZ algorithm, due to Paturi, Pudlak, Saks and Zane, is currently the fastest known algorithm for the k-SAT problem, for every k>3. For 3-SAT, a tiny improvement over PPSZ was obtained by Hertli. We introduce a biased version of the PPSZ algorithm using which we obtain an improvement over PPSZ for every k>=3. For k=3 we also improve on Herli's result and get a much more noticeable improvement over PPSZ, though still relatively small. In particular, for Unique 3-SAT, we improve the current bound from 1.308^n to 1.307^n.

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

This talk concerns the problem of quickly computing distances and shortest paths on distributed networks (the CONGEST model). There have been many developments for this problem in the last few year, resulting in tight approximation schemes. This left open whether exact algorithms can perform equally well. In this talk, we will discuss some recent progress in answering this question. Most recent works that this talk is based on are with Sebastian Krinninger (FOCS 2018) and Aaron Bernstein (ArXiv 2018).

The hash function are very important primitives in cryptology. To use it, we need to trust the designer. To solve this problem, we can combine several hash functions independently built. But we have to suppose that the designers could communicate. That's why we can reduce the security properties to communication complexity problems. After a presentation of these reductions, we will look in details the communication problems linked to these properties, our knowledge, new results about them. And at the end the open problems that challenge us will be presented.