4-5 Juillet 2017, Lyon

Sébastien Tavenas, Reconstruction of full rank Algebraic Branching Programs
Abstract: See https://eccc.weizmann.ac.il/report/2017/021/.

William Aufort, Polygones de Newton : autour du problème fg+1
Abstract: La tau-conjecture sur les polygones de Newton est une conjecture sur le nombre de sommets de polygones associés à des polynômes bivariés d'une certaine forme. Elle implique la séparation des classes de complexité VP et VNP.  Le problème fg+1 est un cas extrèmement particulier de ce problème qui pose déjà des difficultés : si f et g ont t monômes, que dire du nombre de sommets du polygone de Newton de fg+1 ? Nous exposerons le travail effectué pendant mon stage à ce sujet, notamment une borne linéaire dans le cas où l'ensemble des monômes d'un des polynômes est convexe.

Nicolas Ressayre, Le programme de Mulmuley-Sohoni après Burgisser-Ikenmeyer-Panova
Abstract: La GCT est une approche via la théorie des représentation de la conjecture VP\neq VNP. Dans un article récent Burgisser-Ikenmeyer-Panova ont montré que stricto-sensu, cette approche ne pouvait fonctionner. Nous exposerons ce résultat et tenterons une discussion sur l'avenir de la GCT.

​Sylvain Périfel , Lempel-Ziv : la catastrophe du premier bit
Abstract: La robustesse du célèbre algorithme de compression de Lempel et Ziv n'est pas encore bien établie : en particulier, jusqu'à présent on ne savait pas si l'ajout d'un bit au début d'un mot compressible pouvait le rendre incompressible. C'est à cette question, popularisée par Jack Lutz sous le
nom de « one-bit catastrophe » et dont on trouve trace dès 1998, que cet exposé va répondre. Nous montrerons qu'un mot « très compressible » reste
compressible lorsqu'on ajoute un bit devant, mais que certains mots « peu compressibles » deviennent en effet incompressibles.

C'est un travail en commun avec Guillaume Lagarde.

Arpita Korwar, Blackbox PIT for Read-once oblivious unambiguous parse trees (ROUPT)
Abstract: ROUPTs are special arithmetic circuits. They are a generalization of read-once oblivious arithmetic branching programs (ROABPs).
               After defining a ROUPT, we will see a quasi-polynomial time blackbox hitting set for ROUPTs. For this purpose, a "basis isolating weight assignment" is used. Along the way, we will also see how to reduce the depth of an ROUPT.

Guillaume Lagarde, Non-Commutative Arithmetic circuits with Restricted Parse Trees
Abstract: In the non-commutative setting, we consider circuits that are restricted in the ways in which they can compute monomials: this can be seen as restricting the families of parse trees that appear in the
circuit. We will overview:
                    - Lower bounds for circuits with up to an exponential number of parse  trees.
                    - The "Formulas vs. ABP" question of Nisan; in particular we  will show some tight lower bounds for formulas computing IMM with  restrictions on the parse trees.
                    - If there is time left, a poly-time white-box PIT algorithm for sums of a constant number of UPT circuits with different parse trees.