Sébastien Tavenas

According to our database, Sébastien Tavenas authored at least 28 papers between 2013 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2025

On Closure Properties of Read-Once Oblivious Algebraic Branching Programs.

Jules Armand, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen, Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

CoRR, September, 2025

The Algebraic Cost of a Boolean Sum.

Ian Orzel, Srikanth Srinivasan, Sébastien Tavenas, Amir Yehudayoff

Electron. Colloquium Comput. Complex., 2025

On the Complexity of Client-Waiter and Waiter-Client Games.

Valentin Gledel, Nacim Oijid, Sébastien Tavenas, Stéphan Thomassé

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

2024

On the Power of Homogeneous Algebraic Formulas.

Hervé Fournier, Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

2023

Towards Optimal Depth-Reductions for Algebraic Formulas.

Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan, Sébastien Tavenas

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Guest Column: Lower Bounds Against Constant-Depth Algebraic Circuits.

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

SIGACT News, 2022

Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication.

Sébastien Tavenas, Nutan Limaye, Srikanth Srinivasan

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials.

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

Proceedings of the 37th Computational Complexity Conference, 2022

2021

New Non-FPT Lower Bounds for Some Arithmetic Formulas.

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

Electron. Colloquium Comput. Complex., 2021

On the Markov numbers: Fixed numerator, denominator, and sum conjectures.

Clément Lagisquet, Edita Pelantová, Sébastien Tavenas, Laurent Vuillon

Adv. Appl. Math., 2021

Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits.

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2019

Nonnegative Rank Measures and Monotone Algebraic Branching Programs.

Hervé Fournier, Guillaume Malod, Maud Szusterman, Sébastien Tavenas

Proceedings of the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2019

2017

Reconstruction of Full Rank Algebraic Branching Programs.

Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

VNP=VP in the multilinear world.

Meena Mahajan, Nitin Saurabh, Sébastien Tavenas

Inf. Process. Lett., 2016

On the size of homogeneous and of depth four formulas with low individual degree.

Neeraj Kayal, Chandan Saha, Sébastien Tavenas

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

On the Sensitivity Conjecture for Read-k Formulas.

Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, Ameya Velingker

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits.

Neeraj Kayal, Chandan Saha, Sébastien Tavenas

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

On the Sensitivity Conjecture for Disjunctive Normal Forms.

Karthik C. S., Sébastien Tavenas

Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2016

2015

A Wronskian approach to the real τ-conjecture.

Pascal Koiran, Natacha Portier, Sébastien Tavenas

J. Symb. Comput., 2015

A $$\tau $$ τ -Conjecture for Newton Polygons.

Pascal Koiran, Natacha Portier, Sébastien Tavenas, Stéphan Thomassé

Found. Comput. Math., 2015

On the Intersection of a Sparse Curve and a Low-Degree Curve: A Polynomial Version of the Lost Theorem.

Pascal Koiran, Natacha Portier, Sébastien Tavenas

Discret. Comput. Geom., 2015

Log-Concavity and Lower Bounds for Arithmetic Circuits.

Ignacio García-Marco, Pascal Koiran, Sébastien Tavenas

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Building Efficient and Compact Data Structures for Simplicial Complexes.

Jean-Daniel Boissonnat, Karthik C. S., Sébastien Tavenas

Proceedings of the 31st International Symposium on Computational Geometry, 2015

2014

Bornes infe'rieures et supe'rieures dans les circuits arithme'tiques. (Upper and lower bounds for arithmetic circuits).

Sébastien Tavenas

PhD thesis, 2014

2013

The complexity of Shortest Common Supersequence for inputs with no identical consecutive letters.

Aurélie Lagoutte, Sébastien Tavenas

CoRR, 2013

A tau-conjecture for Newton polygons.

Pascal Koiran, Natacha Portier, Sébastien Tavenas, Stéphan Thomassé

CoRR, 2013

Detecting wheels.

Emilie Diot, Sébastien Tavenas, Nicolas Trotignon

CoRR, 2013

Improved Bounds for Reduction to Depth 4 and Depth 3.

Sébastien Tavenas

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013