Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Abhranil Chatterjee, Mrinal Kumar, and Ben Lee Volk. Determinants vs. Algebraic Branching Programs. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 27:1-27:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chatterjee_et_al:LIPIcs.ITCS.2024.27, author = {Chatterjee, Abhranil and Kumar, Mrinal and Volk, Ben Lee}, title = {{Determinants vs. Algebraic Branching Programs}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {27:1--27:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.27}, URN = {urn:nbn:de:0030-drops-195550}, doi = {10.4230/LIPIcs.ITCS.2024.27}, annote = {Keywords: Determinant, Algebraic Branching Program, Lower Bounds, Singular Variety} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Shir Peleg, Amir Shpilka, and Ben Lee Volk. Tensor Reconstruction Beyond Constant Rank. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 87:1-87:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{peleg_et_al:LIPIcs.ITCS.2024.87, author = {Peleg, Shir and Shpilka, Amir and Volk, Ben Lee}, title = {{Tensor Reconstruction Beyond Constant Rank}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {87:1--87:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.87}, URN = {urn:nbn:de:0030-drops-196157}, doi = {10.4230/LIPIcs.ITCS.2024.87}, annote = {Keywords: Algebraic circuits, reconstruction, tensor decomposition, tensor rank} }
Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)
Ami Paz and Liat Peterfreund. Playing Guess Who with Your Kids. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 23:1-23:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{paz_et_al:LIPIcs.FUN.2022.23, author = {Paz, Ami and Peterfreund, Liat}, title = {{Playing Guess Who with Your Kids}}, booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)}, pages = {23:1--23:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-232-7}, ISSN = {1868-8969}, year = {2022}, volume = {226}, editor = {Fraigniaud, Pierre and Uno, Yushi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.23}, URN = {urn:nbn:de:0030-drops-159935}, doi = {10.4230/LIPIcs.FUN.2022.23}, annote = {Keywords: Guess Who?, Binary Search, Error Correcting Codes, Erasure Codes} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Mrinal Kumar, C. Ramya, Ramprasad Saptharishi, and Anamay Tengse. If VNP Is Hard, Then so Are Equations for It. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 44:1-44:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{kumar_et_al:LIPIcs.STACS.2022.44, author = {Kumar, Mrinal and Ramya, C. and Saptharishi, Ramprasad and Tengse, Anamay}, title = {{If VNP Is Hard, Then so Are Equations for It}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {44:1--44:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.44}, URN = {urn:nbn:de:0030-drops-158547}, doi = {10.4230/LIPIcs.STACS.2022.44}, annote = {Keywords: Computational Complexity, Algebraic Circuits, Algebraic Natural Proofs} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Shir Peleg, Ben Lee Volk, and Amir Shpilka. Lower Bounds on Stabilizer Rank. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 110:1-110:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{peleg_et_al:LIPIcs.ITCS.2022.110, author = {Peleg, Shir and Volk, Ben Lee and Shpilka, Amir}, title = {{Lower Bounds on Stabilizer Rank}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {110:1--110:4}, 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.110}, URN = {urn:nbn:de:0030-drops-157063}, doi = {10.4230/LIPIcs.ITCS.2022.110}, annote = {Keywords: Quantum Computation, Lower Bounds, Stabilizer rank, Simulation of Quantum computers} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Mrinal Kumar and Ben Lee Volk. A Lower Bound on Determinantal Complexity. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{kumar_et_al:LIPIcs.CCC.2021.4, author = {Kumar, Mrinal and Volk, Ben Lee}, title = {{A Lower Bound on Determinantal Complexity}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {4:1--4:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.4}, URN = {urn:nbn:de:0030-drops-142781}, doi = {10.4230/LIPIcs.CCC.2021.4}, annote = {Keywords: Determinantal Complexity, Algebraic Circuits, Lower Bounds, Singular Variety} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Mrinal Kumar and Ben Lee Volk. A Polynomial Degree Bound on Equations for Non-Rigid Matrices and Small Linear Circuits. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 9:1-9:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{kumar_et_al:LIPIcs.ITCS.2021.9, author = {Kumar, Mrinal and Volk, Ben Lee}, title = {{A Polynomial Degree Bound on Equations for Non-Rigid Matrices and Small Linear Circuits}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {9:1--9:9}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.9}, URN = {urn:nbn:de:0030-drops-135486}, doi = {10.4230/LIPIcs.ITCS.2021.9}, annote = {Keywords: Rigid Matrices, Linear Circuits, Degree Bounds, Circuit Lower Bounds} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Prerona Chatterjee, Mrinal Kumar, Adrian She, and Ben Lee Volk. A Quadratic Lower Bound for Algebraic Branching Programs. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 2:1-2:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{chatterjee_et_al:LIPIcs.CCC.2020.2, author = {Chatterjee, Prerona and Kumar, Mrinal and She, Adrian and Volk, Ben Lee}, title = {{A Quadratic Lower Bound for Algebraic Branching Programs}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {2:1--2:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.2}, URN = {urn:nbn:de:0030-drops-125546}, doi = {10.4230/LIPIcs.CCC.2020.2}, annote = {Keywords: Algebraic Branching Programs, Lower Bound} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Mrinal Kumar and Ben Lee Volk. Lower Bounds for Matrix Factorization. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kumar_et_al:LIPIcs.CCC.2020.5, author = {Kumar, Mrinal and Volk, Ben Lee}, title = {{Lower Bounds for Matrix Factorization}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {5:1--5:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.5}, URN = {urn:nbn:de:0030-drops-125578}, doi = {10.4230/LIPIcs.CCC.2020.5}, annote = {Keywords: Algebraic Complexity, Linear Circuits, Matrix Factorization, Lower Bounds} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Mrinal Kumar, Rafael Oliveira, and Ramprasad Saptharishi. Towards Optimal Depth Reductions for Syntactically Multilinear Circuits. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 78:1-78:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kumar_et_al:LIPIcs.ICALP.2019.78, author = {Kumar, Mrinal and Oliveira, Rafael and Saptharishi, Ramprasad}, title = {{Towards Optimal Depth Reductions for Syntactically Multilinear Circuits}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {78:1--78:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.78}, URN = {urn:nbn:de:0030-drops-106548}, doi = {10.4230/LIPIcs.ICALP.2019.78}, annote = {Keywords: arithmetic circuits, multilinear circuits, depth reduction, lower bounds} }
Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)
Noga Alon, Mrinal Kumar, and Ben Lee Volk. Unbalancing Sets and an Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{alon_et_al:LIPIcs.CCC.2018.11, author = {Alon, Noga and Kumar, Mrinal and Volk, Ben Lee}, title = {{Unbalancing Sets and an Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits}}, booktitle = {33rd Computational Complexity Conference (CCC 2018)}, pages = {11:1--11:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-069-9}, ISSN = {1868-8969}, year = {2018}, volume = {102}, editor = {Servedio, Rocco A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.11}, URN = {urn:nbn:de:0030-drops-88799}, doi = {10.4230/LIPIcs.CCC.2018.11}, annote = {Keywords: Algebraic Complexity, Multilinear Circuits, Circuit Lower Bounds} }
Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)
Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk. Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 30:1-30:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{anderson_et_al:LIPIcs.CCC.2016.30, author = {Anderson, Matthew and Forbes, Michael A. and Saptharishi, Ramprasad and Shpilka, Amir and Volk, Ben Lee}, title = {{Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs}}, booktitle = {31st Conference on Computational Complexity (CCC 2016)}, pages = {30:1--30:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-008-8}, ISSN = {1868-8969}, year = {2016}, volume = {50}, editor = {Raz, Ran}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.30}, URN = {urn:nbn:de:0030-drops-58255}, doi = {10.4230/LIPIcs.CCC.2016.30}, annote = {Keywords: Algebraic Complexity, Lower Bounds, Derandomization, Polynomial Identity Testing} }
Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)
Rafael Oliveira, Amir Shpilka, and Ben Lee Volk. Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 304-322, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{oliveira_et_al:LIPIcs.CCC.2015.304, author = {Oliveira, Rafael and Shpilka, Amir and Volk, Ben Lee}, title = {{Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas}}, booktitle = {30th Conference on Computational Complexity (CCC 2015)}, pages = {304--322}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-81-1}, ISSN = {1868-8969}, year = {2015}, volume = {33}, editor = {Zuckerman, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.304}, URN = {urn:nbn:de:0030-drops-50548}, doi = {10.4230/LIPIcs.CCC.2015.304}, annote = {Keywords: Arithmetic Circuits, Derandomization, Polynomial Identity Testing} }
Feedback for Dagstuhl Publishing