Home   •   Publications

Publications

Quand elles existent toutes les deux, les versions "revue" et "conférence" d'un même article apparaissent dans ces deux catégories.

Revues

  •  Neeraj Kayal, Vineet Nair, Chandan Saha, and Sébastien Tavenas. Reconstruction of Full Rank Algebraic Branching Programs.To appear in ACM Transactions on Computation Theory (TOCT).
  • P. Koiran. Root separation for trinomials (arxiv). To appear in Journal of Symbolic Computation.
  • Neeraj Kayal, Chandan Saha, and Sébastien Tavenas.  On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree. Theory of Computing 14 (2018) 1-45.
  • G. Lagarde, N. Limaye, and S. Srinivasan. Lower Bounds and PIT for Non-Commutative Arithmetic Circuits with Restricted Parse Trees. Computational Complexity, 2018.
  • I. Garcia-Marco, P. Koiran, T. Pecatte. On the linear independence of shifted powers. Journal of Complexity, 45:67-82, 2018 (arxiv).
  • J.M. Landsberg and N. Ressayre. Permanent v. determinant: an exponential lower bound assuming symmetry and a potential path towards Valiant's conjecture. Differential Geom. Appl. 55 (2017), 146–166.
  • Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan. The shifted partial derivative complexity of Elementary Symmetric Polynomials. Theory of Computing 13 (2017) 1-34.
  • I. García-Marco, K. Knauer. Graph drawings with vertices and edges in convex position. Computational Geometry 58 (2017) 25–33 (hal).
  • I. García-Marco, P. Koiran, Lower bounds by Birkhoff interpolation. Journal of Complexity, 39:38-50, 2017 (hal).
  • Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh: Homomorphism Polynomials Complete for VP. Chicago Journal of Theoretical Computer Science, 2016.
  •  Nutan Limaye, Guillaume Malod, Srikanth Srinivasan. Lower bounds for non-commutative skew circuits. Theory of Computing 12 (2016) 1-38.
  • L. Manivel, On the asymptotics of Kronecker coefficients 2 . Séminaire Lotharingien de Combinatoire, B75d (2016), 14 pages. (arXiv)
  • M.Mahajan, N.Saurabh and S. Tavenas. VNP= VP in the multilinear world. Information Processing Letters, 2016.
  • Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan. Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication. SIAM J. Comput. 44(5): 1173-1201 (2015).
  • L. Manivel, On the asymptotics of Kronecker coefficients, Journal of Algebraic Combinatorics, published online June 25, 2015 (arXiv)
  • P. Koiran, N. Portier, S. Tavenas, On the intersection of a sparse curve and a low-degree curve: A polynomial version of the lost theorem, Discrete and Computational Geometry, 53(1):48-63, 2015, (arXiv).
  • P. Koiran, N. Portier, S. Tavenas, S. Thomassé, A τ-Conjecture for Newton Polygons, Foundations of Computational Mathematics, 15(1):185-197, 2015 (arXiv, DOI).

Conférences

  • I. Garcia-Marco, P. Koiran and T. Pecatte. Polynomial equivalence problems for sums of affine powers. ISSAC 2018
  • Ignacio Garcia-Marco, Pascal Koiran, Timothée Pecatte. Reconstruction Algorithms for Sums of Affine Powers. ISSAC 2017 (arxiv). Best student paper.
  • G. Lagarde, N. Limaye, and S. Srinivasan. Lower Bounds and PIT for Non-Commutative Arithmetic Circuits with Restricted Parse Trees. MFCS 2017.
  • Ignacio Garcia-Marco, Pascal Koiran, Timothée Pecatte, Stéphan Thomassé. On the complexity of partial derivatives. STACS 2017 (arxiv).
  • N. Kayal, C. Saha, and S. Tavenas. An almost cubic lower bound for depth three arithmetic
    circuits. ICALP 2016. Best paper award.
  • N.Kayal, C.Saha and S. Tavenas. On the size of homogeneous and of depth four formulas with low individual degree. STOC 2016. 
  • Joseph M. Landsberg, Nicolas Ressayre, Permanent v. determinant: an exponential lower bound assuming symmetry and a potential path towards Valiant's conjecture.  ITCS 2016 (arXiv).
  • I. García-Marco, K. Knauer. Graph drawings with vertices and edges in convex position. Graph Drawing and Network Vizualization (GD 2015). LNCS 9411, pages 348-359, 2015.
  • Hervé Fournier, Nutan Limaye, Meena Mahajan and Srikanth Srinivasan. The shifted partial derivative complexity of Elementary Symmetric Polynomials. In Proc. MFCS 2015.
  • I. García-Marco, P. Koiran, S. Tavenas, Log-concavity and lower bounds for arithmetic circuits, In Proc. MFCS 2015 (arXiv)
  • N. Kayal, P. Koiran, C. Saha and T. Pecatte. Lower bounds for sums of powers of low degree univariates. ICALP 2015 (lien).
  • Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh: Homomorphism Polynomials Complete for VP, FSTTCS 2014: 493-504.

Prépublications

  • N. Fijalkow, G. Lagarde, P. Ohlmann and O. Serre. Lower bounds for arithmetic circuits via the Hankel matrix. ECCC, 2018.
  • N. Fijalkow, G. Lagarde, and P. Ohlmann. Tight bounds using Hankel matrix for arithmetic circuits with  unique parse trees. Electronic Colloquium on Computational Complexity, 25:38, 2018.
  • P. Koiran, N. Ressayre. Orbits of monomials and factorization into products of linear forms. 2018 (arxiv).
  • Guillaume Lagarde, Guillaume Malod, Sylvain Perifel. Non-commutative computations: lower bounds and polynomial identity testing. ECCC, juin 2016.

Published on