3 Search Results for "D�jean, Herv�"

Document
DOI: 10.4230/LIPIcs.CCC.2023.28
Towards Optimal Depth-Reductions for Algebraic Formulas

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

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
Classical results of Brent, Kuck and Maruyama (IEEE Trans. Computers 1973) and Brent (JACM 1974) show that any algebraic formula of size s can be converted to one of depth O(log s) with only a polynomial blow-up in size. In this paper, we consider a fine-grained version of this result depending on the degree of the polynomial computed by the algebraic formula. Given a homogeneous algebraic formula of size s computing a polynomial P of degree d, we show that P can also be computed by an (unbounded fan-in) algebraic formula of depth O(log d) and size poly(s). Our proof shows that this result also holds in the highly restricted setting of monotone, non-commutative algebraic formulas. This improves on previous results in the regime when d is small (i.e., d = s^o(1)). In particular, for the setting of d = O(log s), along with a result of Raz (STOC 2010, JACM 2013), our result implies the same depth reduction even for inhomogeneous formulas. This is particularly interesting in light of recent algebraic formula lower bounds, which work precisely in this "low-degree" and "low-depth" setting. We also show that these results cannot be improved in the monotone setting, even for commutative formulas.
Cite as

Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan, and Sébastien Tavenas. Towards Optimal Depth-Reductions for Algebraic Formulas. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 28:1-28:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{fournier_et_al:LIPIcs.CCC.2023.28,
  author =	{Fournier, Herv\'{e} and Limaye, Nutan and Malod, Guillaume and Srinivasan, Srikanth and Tavenas, S\'{e}bastien},
  title =	{{Towards Optimal Depth-Reductions for Algebraic Formulas}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{28:1--28:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.28},
  URN =		{urn:nbn:de:0030-drops-182986},
  doi =		{10.4230/LIPIcs.CCC.2023.28},
  annote =	{Keywords: Algebraic formulas, depth-reduction}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.362
Monomials in arithmetic circuits: Complete problems in the counting hierarchy

Authors: Hervé Fournier, Guillaume Malod, and Stefan Mengel

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
We consider the complexity of two questions on polynomials given by arithmetic circuits: testing whether a monomial is present and counting the number of monomials. We show that these problems are complete for subclasses of the counting hierarchy which had few or no known natural complete problems before. We also study these questions for circuits computing multilinear polynomials.
Cite as

Hervé Fournier, Guillaume Malod, and Stefan Mengel. Monomials in arithmetic circuits: Complete problems in the counting hierarchy. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 362-373, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{fournier_et_al:LIPIcs.STACS.2012.362,
  author =	{Fournier, Herv\'{e} and Malod, Guillaume and Mengel, Stefan},
  title =	{{Monomials in arithmetic circuits: Complete problems in the counting hierarchy}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{362--373},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.362},
  URN =		{urn:nbn:de:0030-drops-34240},
  doi =		{10.4230/LIPIcs.STACS.2012.362},
  annote =	{Keywords: arithmetic circuits, counting problems, polynomials}
}
Document
DOI: 10.4230/DagSemProc.10291.13
Preserving the Intent behind

Authors: Thierry Jaquin, Hervé Déjean, and Jean-Pierre Chanod

Published in: Dagstuhl Seminar Proceedings, Volume 10291, Automation in Digital Preservation (2010)

Abstract
Considering that, in many areas esp. outside cultural heritage, preserving the intent behind activities or projects, is at least as important as preserving the associated digital data, we argue that project policies are the natural means to describe an intent in a sustainable implementation-independent way, after the project actors have reached an agreement.
Cite as

Thierry Jaquin, Hervé Déjean, and Jean-Pierre Chanod. Preserving the Intent behind. In Automation in Digital Preservation. Dagstuhl Seminar Proceedings, Volume 10291, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{jaquin_et_al:DagSemProc.10291.13,
  author =	{Jaquin, Thierry and D\'{e}jean, Herv\'{e} and Chanod, Jean-Pierre},
  title =	{{Preserving the Intent behind}},
  booktitle =	{Automation in Digital Preservation},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10291},
  editor =	{Jean-Pierre Chanod and Milena Dobreva and Andreas Rauber and Seamus Ross},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10291.13},
  URN =		{urn:nbn:de:0030-drops-27704},
  doi =		{10.4230/DagSemProc.10291.13},
  annote =	{Keywords: Digital preservation, policy, intent perservation, consensus}
}
  • Refine by Author
  • 2 Fournier, Hervé
  • 2 Malod, Guillaume
  • 1 Chanod, Jean-Pierre
  • 1 Déjean, Hervé
  • 1 Jaquin, Thierry
  • Show More...

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

  • Refine by Keyword
  • 1 Algebraic formulas
  • 1 Digital preservation
  • 1 arithmetic circuits
  • 1 consensus
  • 1 counting problems
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2010
  • 1 2012
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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