## Workshop du groupe de travail “*Complexité & modèles finis*” du GDR CNRS IM

4 Juillet 2012, / Amphi B, ENS Lyon, France

Exposés (en anglais) par Pablo Arrighi (Université Joseph Fourier et ENS Lyon), Bruno Grenet (ENS Lyon), Marc Kaplan (Télécom ParisTech), Guillaume Malod (Paris 7), Sylvain Perifel (Paris 7), Nicolas Ressayre (Lyon 1), Maurice Rojas (Texas A & M).

Titres et résumés sont en bas de la page.

09:30 – 10:15 | Maurice Rojas |

10:20 – 11:05 | Bruno Grenet |

11:25 – 12:10 | Nicolas Ressayre |

12:15 – 13:15 | déjeuner (buffet) |

13:25 – 14:10 | Guillaume Malod |

14:15 – 15:00 | Sylvain Perifel |

15:20 – 16:05 | Pablo Arrighi |

16:10 – 16:55 | Marc Kaplan |

### Titres et résumés :

**Maurice Rojas : ** Arithmetic Approaches to P vs. NP.

Abstract: We survey some new families of NP-complete problems related to detecting roots of sparse polynomials over certain fields. We then give a new version of the Shub-Smale tau-Conjecture. (The original version asserts that polynomials with low evaluation complexity have few integer roots, and its truth implies separations close to the P vs. NP problem.) Our version makes use of recent observations of Koiran, and suggests a p-adic approach to new lower bounds in circuit complexity. Our results are joint (in various combinations) with Martin Avendano, Jingguo Bi, Qi Cheng, Kaitlyn Hellenbrand, Ashraf Ibrahim, and Korben Rusek. We assume no background in p-adic arithmetic.

** Bruno Grenet : **Factoring bivariate lacunary polynomials without heights (joint work with Arkadev Chattopadhyay, Pascal Koiran, Natacha Portier, Yann Strozecki).

Abstract: The lacunary, or superpsarse, representation of a multivariate polynomial P is a list of pairs (c,e) where c is a coefficient of P and e is a vector of exponent. Each pair defines a term of the polynomial, and P equals the sum of all these terms. The factorization of lacunary polynomial has been investigated in a series of papers by Cucker, Koiran and Smale, Lenstra, and Kaltofen and Koiran. In this paper, we are interested in more elementary proofs for some of these results. We focus on Kaltofen and Koiran’s results dealing with linear factors of bivariate lacunary polynomials. In particular, we give a polynomial-time algorithm to find linear factors of bivariate polynomials that is not based on heights of algebraic numbers. This simplification also allows us to give a similar results for some fields of positive characteristic. Our main technical result is an upper bound on the valuation of polynomials of the form P(X,1+X) where P is a bivariate lacunary polynomial, and can be viewed as a generalization of a result of Hajos.

** Nicolas Ressayre : **Some remarks on the Mulmuley-Sohoni variety.

Abstract: Let A be a d by d matrix with variables a_{ij} as entries. The permanent per_d of A is a polynomial in the variables a_{ij}. A central question in Valiant’s complexity theory is to find lower bounds on the size of a matrix M of affine forms in a_{ij}

whose determinant is equal to perm_d. Mulmuley-Sohoni proposed an approach for this question via algebraic geometry and representation theory. In this talk, we present this approach. We also explain some very partial results on the orbit closure X of the

determinant. More precisely, we deduce from the formula det(M)=det(M^t) the

vanishing of some multiplicities in the decomposition of the ring of regular functions on

X as a sum of irreducible modules.

** Guillaume Malod : **Succinct algebraic branching programs characterizing non-uniform complexity classes.

Abstract: We study characterizations of algebraic complexity classes by branching programs of possibly exponential size, using a succinctness condition to replace the usual one based on uniformity. We obtain characterizations of VPSPACE, the class corresponding to computations in polynomial space, and observe that algebraic polynomial space can be seen as constant algebraic space with auxiliary polynomial space Boolean computations. We also obtain the first examples of natural complete polynomials for VPSPACE, in particular showing that polynomials like the determinant, the permanent or the Hamiltonian become VPSPACE-complete when the matrix is succinctly encoded. Using the same techniques we also characterize VNP. In general, we argue that characterizations by branching programs apply to different classes, both Boolean and algebraic, with or without uniformity, and thus provide a general and uniform technique in these different settings.

** Sylvain Perifel : **Separating multilinear branching programs and formulas (joint work with Zeev Dvir, Guillaume Malod and Amir Yehudayoff).

Abstract: Arithmetic circuits compute polynomials but in such a general framework, lower bounds are difficult to obtain. Thus restricted models have been studied, like formulas (the most restrictive case) or the intermediate model of Algebraic Branching Programs (ABP) which captures the complexity of iterated matrix multiplication and of the determinant. We show that ABP are strictly more powerful than formulas in the “multilinear” framework, hence improving on a result of Raz who separated circuits from formulas.

**Pablo Arrighi :** The physical Church-Turing thesis and the principles of quantum theory(joint work with Gilles Dowek).

Abstract: Notoriously, quantum computation shatters complexity theory, but is innocuous to computability theory. Yet several works have shown how quantum theory as it stands could breach the physical Church-Turing thesis. We draw a clear line as to when this is the case, in a way that is inspired by Gandy. Gandy formulates postulates about physics, such as homogeneity of space and time, bounded density and velocity of information — and proves that the physical Church-Turing thesis is a consequence of these postulates. We provide a quantum version of the theorem. Thus this approach exhibits a formal non-trivial interplay between theoretical physics symmetries and computability assumptions.

**Marc Kaplan:** Merkle Puzzles in a Quantum World (joint work with Gilles Brassard, Peter Hoyer, Kassem Kalach, Sophie Laplante, Louis Salvail).

Abstract: In 1974, Ralph Merkle proposed the first unclassified scheme for secure communications over insecure channels. When legitimate communicating parties are willing to spend an amount of computational effort proportional to some parameter N, an eavesdropper cannot break into their communication without spending a time proportional to N^2, which is quadratically more than the legitimate effort. We showed in an earlier paper that Merkle’s schemes are completely insecure against a quantum adversary, but that their security can be partially restored if the legitimate parties are also allowed to use quantum computation: the eavesdropper needed to spend a time proportional to N^{3/2} to break our earlier quantum scheme. Furthermore, all previous classical schemes could be broken completely by the onslaught of a quantum eavesdropper and we conjectured that this is unavoidable. We give two novel key establishment schemes in the spirit of Merkle’s. The first one can be broken by a quantum adversary that makes an effort proportional to N^{5/3} to implement a quantum random walk in a Johnson graph reminiscent of Andris Ambainis’ quantum algorithm for the element distinctness problem. This attack is optimal up to logarithmic factors. Our second scheme is purely classical, yet it cannot be broken by a quantum eavesdropper who is only willing to expend effort proportional to that of the legitimate parties.