### Algorithmes et complexité

** Date et lieu :** le mardi à 11h, salle 1007, Sophie Germain

** Responsable :** Mathieu Laurière

** Equipe :** Site web

Mardi 31 janvier 2017 · 11h00 · Salle 1007

Chien-Chung Huang · 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.

Mardi 07 février 2017 · 11h00 · Salle 1007

Charles Paperman · Streaming and circuit complexity

Mardi 10 janvier 2017 · 11h00 · 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.

Mardi 13 décembre 2016 · 11h00 · 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.

Mardi 06 décembre 2016 · 11h00 · Salle 1007

Omar Fawzi · Algorithmic aspects of optimal channel coding

Based on joint work with Siddharth Barman. arXiv:1508.04095

Vendredi 02 décembre 2016 · 11h00 · 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.

Mardi 22 novembre 2016 · 11h00 · 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.

Mardi 08 novembre 2016 · 11h00 · 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.

Mardi 25 octobre 2016 · 11h00 · Salle 1007

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

Mardi 18 octobre 2016 · 11h00 · Salle 1007

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

Mardi 11 octobre 2016 · 11h00 · 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.

Mardi 20 septembre 2016 · 11h00 · 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.

Mardi 13 septembre 2016 · 11h00 · Salle 1007

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

Lundi 29 août 2016 · 11h00 · 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.

Mardi 05 juillet 2016 · 11h00 · 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.

Mardi 21 juin 2016 · 11h00 · Salle 1007

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

Mardi 31 mai 2016 · 11h00 · 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.

Mardi 24 mai 2016 · 11h00 · 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.

Mardi 17 mai 2016 · 11h00 · 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.

Mardi 10 mai 2016 · 11h00 · Salle 1007

Jean Cardinal · Solving k-SUM using few linear queries

Joint work with John Iacono and Aurélien Ooms

Mardi 03 mai 2016 · 11h00 · 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.

Mardi 26 avril 2016 · 11h00 · 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).

Mardi 19 avril 2016 · 11h00 · Salle 1007

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

Mercredi 30 mars 2016 · 14h00 · 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.

Vendredi 11 mars 2016 · 11h00 · 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.

Mardi 23 février 2016 · 11h00 · Salle 1007

Ashwin Nayak (University of Waterloo) · Sampling quantum states

Joint work with Ala Shayeghi.

Mardi 16 février 2016 · 11h00 · 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).

Mardi 02 février 2016 · 11h00 · Salle 1007

Balthazar Bauer · Compression of communication protocols

Mardi 26 janvier 2016 · 11h00 · 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.

- 11-03-2016 : Christian Konrad (Reykjavik University),
*Streaming Algorithms for Partitioning Sequences and Trees* - 23-02-2016 : Ashwin Nayak (University of Waterloo),
*Sampling quantum states* - 16-02-2016 : Johan Thapper (Université Paris-Est, Marne-la-Vallée, LIGM),
*Constraint Satisfaction Problems, LP relaxations and Polymorphisms* - 02-02-2016 : Balthazar Bauer,
*Compression of communication protocols* - 26-01-2016 : Chien-Chung Huang (Chalmers University of Technology and Göteborg University),
*Exact and Approximation Algorithms for Weighted Matroid Intersection* - 17-12-2015 : Morteza Monemizadeh (Charles University, Computer Science Institute),
*Matching in Data Streams* - 10-12-2015 : Andrej Bogdanov (The Chinese University of Hong Kong, Institute for Theoretical Computer Science and Communications),
*Threshold secret sharing requires a linear size alphabet* - 04-12-2015 : Tatiana Starikovskaia (University of Bristol, Faculty of Engineering),
*The k-mismatch problem revisited* - 17-11-2015 : Vincent Viallat Cohen-Addad (ENS),
*Diameter and k-Center Clustering in Sliding Windows* - 10-11-2015 : Romain Gay (ENS),
*Communication Complexity of Conditional Disclosure of Secrets and Attribute-Based Encryption* - 20-10-2015 : Ronald de Wolf (CWI and University of Amsterdam),
*The hypercontractive inequality in theoretical computer science* - 06-10-2015 : Claire Mathieu (ENS),
*Carpooling on social networks* - 29-09-2015 : Attila Pereszlényi (LIAFA),
*On the quest for perfect completeness for QMA* - 15-09-2015 : Stacey Jeffery (Institute for Quantum Information and Matter, Caltech),
*Quantum homomorphic encryption for circuits of low T-gate complexity* - 04-09-2015 : Ashwin Nayak (Institute for Quantum Computing, University of Waterloo),
*A simple proof of the quantum data processing inequality*