2 Search Results for "Roch, Sebastien"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.28
Faster & Deterministic FPT Algorithm for Worst-Case Tensor Decomposition

Authors: Vishwas Bhargava and Devansh Shringi

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We present a deterministic 2^{k^{𝒪(1)}} poly(n,d) time algorithm for decomposing d-dimensional, width-n tensors of rank at most k over ℝ and ℂ. This improves upon the previous randomized algorithm of Peleg, Shpilka, and Volk (ITCS '24) that takes 2^{k^{k^{𝒪(k)}}} poly(n,d) time and the deterministic n^k^k time algorithms of Bhargava, Saraf, and Volkovich (STOC '21). Our work resolves an open question asked by Peleg, Shpilka, and Volk (ITCS '24) on whether a deterministic Fixed Parameter Tractable (FPT) algorithm exists for worst-case tensor decomposition. We also make substantial progress on the fundamental problem of how the tractability of tensor decomposition varies as the tensor rank increases. Our result implies that we can achieve deterministic polynomial-time decomposition as long as the rank of the tensor is at most (log n)^{1/C}, where C is some fixed constant independent of n and d. Further, we note that there cannot exist a polynomial-time algorithm for k = ω(log n) unless ETH fails. Our algorithm works for all fields; however, the time complexity worsens to 2^{k^{k^{𝒪(1)}}} and requires randomization for finite fields of large characteristics. Both conditions are provably necessary unless there are improvements in the state of the art for system solving over the corresponding fields. Our approach achieves this by designing a proper learning (reconstruction) algorithm for set-multilinear depth-3 arithmetic circuits. On a technical note, we design a "partial" clustering algorithm for set-multilinear depth-3 arithmetic circuits that lets us isolate a cluster from any set-multilinear depth-3 circuit while preserving the structure of the circuit.
Cite as

Vishwas Bhargava and Devansh Shringi. Faster & Deterministic FPT Algorithm for Worst-Case Tensor Decomposition. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhargava_et_al:LIPIcs.ICALP.2025.28,
  author =	{Bhargava, Vishwas and Shringi, Devansh},
  title =	{{Faster \& Deterministic FPT Algorithm for Worst-Case Tensor Decomposition}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{28:1--28:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.28},
  URN =		{urn:nbn:de:0030-drops-234052},
  doi =		{10.4230/LIPIcs.ICALP.2025.28},
  annote =	{Keywords: Algebraic circuits, Deterministic algorithms, FPT algorithm, Learning circuits, Reconstruction, Tensor Decomposition, Tensor Rank}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.931
Distance-based Species Tree Estimation: Information-Theoretic Trade-off between Number of Loci and Sequence Length under the Coalescent

Authors: Elchanan Mossel and Sebastien Roch

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract
We consider the reconstruction of a phylogeny from multiple genes under the multispecies coalescent. We establish a connection with the sparse signal detection problem, where one seeks to distinguish between a distribution and a mixture of the distribution and a sparse signal. Using this connection, we derive an information-theoretic trade-off between the number of genes needed for an accurate reconstruction and the sequence length of the genes.
Cite as

Elchanan Mossel and Sebastien Roch. Distance-based Species Tree Estimation: Information-Theoretic Trade-off between Number of Loci and Sequence Length under the Coalescent. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 931-942, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{mossel_et_al:LIPIcs.APPROX-RANDOM.2015.931,
  author =	{Mossel, Elchanan and Roch, Sebastien},
  title =	{{Distance-based Species Tree Estimation: Information-Theoretic Trade-off between Number of Loci and Sequence Length under the Coalescent}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{931--942},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.931},
  URN =		{urn:nbn:de:0030-drops-53455},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.931},
  annote =	{Keywords: phylogenetic reconstruction, multispecies coalescent, sequence length requirement.}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2015

  • Refine by Author
  • 1 Bhargava, Vishwas
  • 1 Mossel, Elchanan
  • 1 Roch, Sebastien
  • 1 Shringi, Devansh

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 1 Theory of computation → Algebraic complexity theory
  • 1 Theory of computation → Pseudorandomness and derandomization

  • Refine by Keyword
  • 1 Algebraic circuits
  • 1 Deterministic algorithms
  • 1 FPT algorithm
  • 1 Learning circuits
  • 1 Reconstruction
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact