Sébastien Tavenas

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

Collaborative distances:

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

2025

The Algebraic Cost of a Boolean Sum.

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

CoRR, February, 2025

2024

Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits.

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

Commun. ACM, February, 2024

2023

Towards Optimal Depth-Reductions for Algebraic Formulas.

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

Electron. Colloquium Comput. Complex., 2023

On the Power of Homogeneous Algebraic Formulas.

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

Electron. Colloquium Comput. Complex., 2023

2022

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

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

SIGACT News, 2022

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

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

Electron. Colloquium Comput. Complex., 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

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

2019

Nonnegative rank measures and monotone algebraic branching programs.

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

Electron. Colloquium Comput. Complex., 2019

2017

Reconstruction of full rank Algebraic Branching Programs.

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

Electron. Colloquium Comput. Complex., 2017

Building Efficient and Compact Data Structures for Simplicial Complexes.

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

Algorithmica, 2017

2016

VNP=VP in the multilinear world.

Meena Mahajan, Nitin Saurabh, Sébastien Tavenas

Inf. Process. Lett., 2016

An almost Cubic Lower Bound for Depth Three Arithmetic Circuits.

Neeraj Kayal, Chandan Saha, Sébastien Tavenas

Electron. Colloquium Comput. Complex., 2016

On the Sensitivity Conjecture for Read-k Formulas.

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

Electron. Colloquium Comput. Complex., 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

Improved bounds for reduction to depth 4 and depth 3.

Sébastien Tavenas

Inf. Comput., 2015

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

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

Found. Comput. Math., 2015

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

Neeraj Kayal, Chandan Saha, Sébastien Tavenas

Electron. Colloquium Comput. Complex., 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

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