Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
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)
@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} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, and Bhargav Thankey. Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{amireddy_et_al:LIPIcs.ICALP.2023.12, author = {Amireddy, Prashanth and Garg, Ankit and Kayal, Neeraj and Saha, Chandan and Thankey, Bhargav}, title = {{Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {12:1--12:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.12}, URN = {urn:nbn:de:0030-drops-180642}, doi = {10.4230/LIPIcs.ICALP.2023.12}, annote = {Keywords: arithmetic circuits, low-depth circuits, lower bounds, shifted partials} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Dieter van Melkebeek and Andrew Morgan. Polynomial Identity Testing via Evaluation of Rational Functions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 119:1-119:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{vanmelkebeek_et_al:LIPIcs.ITCS.2022.119, author = {van Melkebeek, Dieter and Morgan, Andrew}, title = {{Polynomial Identity Testing via Evaluation of Rational Functions}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {119:1--119:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.119}, URN = {urn:nbn:de:0030-drops-157158}, doi = {10.4230/LIPIcs.ITCS.2022.119}, annote = {Keywords: Derandomization, Gr\"{o}bner Basis, Lower Bounds, Polynomial Identity Testing} }
Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Hervé Fournier, Guillaume Malod, Maud Szusterman, and Sébastien Tavenas. Nonnegative Rank Measures and Monotone Algebraic Branching Programs. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{fournier_et_al:LIPIcs.FSTTCS.2019.15, author = {Fournier, Herv\'{e} and Malod, Guillaume and Szusterman, Maud and Tavenas, S\'{e}bastien}, title = {{Nonnegative Rank Measures and Monotone Algebraic Branching Programs}}, booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)}, pages = {15:1--15:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-131-3}, ISSN = {1868-8969}, year = {2019}, volume = {150}, editor = {Chattopadhyay, Arkadev and Gastin, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.15}, URN = {urn:nbn:de:0030-drops-115774}, doi = {10.4230/LIPIcs.FSTTCS.2019.15}, annote = {Keywords: Elementary symmetric polynomials, lower bounds} }
Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
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)
@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} }
Feedback for Dagstuhl Publishing