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.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 234, 37th Computational Complexity Conference (CCC 2022)
Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 32:1-32:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{limaye_et_al:LIPIcs.CCC.2022.32, author = {Limaye, Nutan and Srinivasan, Srikanth and Tavenas, S\'{e}bastien}, title = {{On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {32:1--32:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.32}, URN = {urn:nbn:de:0030-drops-165942}, doi = {10.4230/LIPIcs.CCC.2022.32}, annote = {Keywords: Partial Derivative Method, Barriers to Lower Bounds} }
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.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 79, 32nd Computational Complexity Conference (CCC 2017)
Neeraj Kayal, Vineet Nair, Chandan Saha, and Sébastien Tavenas. Reconstruction of Full Rank Algebraic Branching Programs. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 21:1-21:61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{kayal_et_al:LIPIcs.CCC.2017.21, author = {Kayal, Neeraj and Nair, Vineet and Saha, Chandan and Tavenas, S\'{e}bastien}, title = {{Reconstruction of Full Rank Algebraic Branching Programs}}, booktitle = {32nd Computational Complexity Conference (CCC 2017)}, pages = {21:1--21:61}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-040-8}, ISSN = {1868-8969}, year = {2017}, volume = {79}, editor = {O'Donnell, Ryan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.21}, URN = {urn:nbn:de:0030-drops-75318}, doi = {10.4230/LIPIcs.CCC.2017.21}, annote = {Keywords: Circuit reconstruction, algebraic branching programs, equivalence test, iterated matrix multiplication, Lie algebra} }
Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Karthik C. S. and Sébastien Tavenas. On the Sensitivity Conjecture for Disjunctive Normal Forms. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{s._et_al:LIPIcs.FSTTCS.2016.15, author = {S., Karthik C. and Tavenas, S\'{e}bastien}, title = {{On the Sensitivity Conjecture for Disjunctive Normal Forms}}, booktitle = {36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)}, pages = {15:1--15:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-027-9}, ISSN = {1868-8969}, year = {2016}, volume = {65}, editor = {Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.15}, URN = {urn:nbn:de:0030-drops-68504}, doi = {10.4230/LIPIcs.FSTTCS.2016.15}, annote = {Keywords: Boolean function, Sensitivity, Block sensitivity, DNF} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Neeraj Kayal, Chandan Saha, and Sébastien Tavenas. An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{kayal_et_al:LIPIcs.ICALP.2016.33, author = {Kayal, Neeraj and Saha, Chandan and Tavenas, S\'{e}bastien}, title = {{An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {33:1--33:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.33}, URN = {urn:nbn:de:0030-drops-63126}, doi = {10.4230/LIPIcs.ICALP.2016.33}, annote = {Keywords: arithmetic circuits, depth-3 circuits, shifted partials} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, and Ameya Velingker. On the Sensitivity Conjecture for Read-k Formulas. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{bafna_et_al:LIPIcs.MFCS.2016.16, author = {Bafna, Mitali and Lokam, Satyanarayana V. and Tavenas, S\'{e}bastien and Velingker, Ameya}, title = {{On the Sensitivity Conjecture for Read-k Formulas}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {16:1--16:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.16}, URN = {urn:nbn:de:0030-drops-64317}, doi = {10.4230/LIPIcs.MFCS.2016.16}, annote = {Keywords: sensitivity conjecture, read-k formulas, analysis of Boolean functions} }
Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)
Jean-Daniel Boissonnat, Karthik C. S., and Sébastien Tavenas. Building Efficient and Compact Data Structures for Simplicial Complexes. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 642-657, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{boissonnat_et_al:LIPIcs.SOCG.2015.642, author = {Boissonnat, Jean-Daniel and S., Karthik C. and Tavenas, S\'{e}bastien}, title = {{Building Efficient and Compact Data Structures for Simplicial Complexes}}, booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)}, pages = {642--657}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-83-5}, ISSN = {1868-8969}, year = {2015}, volume = {34}, editor = {Arge, Lars and Pach, J\'{a}nos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.642}, URN = {urn:nbn:de:0030-drops-50981}, doi = {10.4230/LIPIcs.SOCG.2015.642}, annote = {Keywords: Simplicial complex, Compact data structures, Automaton, NP-hard} }
Feedback for Dagstuhl Publishing