LIPIcs, Volume 137
CCC 2019, July 18-20, 2019, New Brunswick, NJ, USA
Editors: Amir Shpilka
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Jop Briët, Matthias Christandl, Itai Leigh, Amir Shpilka, and Jeroen Zuiddam. Discreteness of Asymptotic Tensor Ranks (Extended Abstract). In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{briet_et_al:LIPIcs.ITCS.2024.20, author = {Bri\"{e}t, Jop and Christandl, Matthias and Leigh, Itai and Shpilka, Amir and Zuiddam, Jeroen}, title = {{Discreteness of Asymptotic Tensor Ranks}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {20:1--20:14}, 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.20}, URN = {urn:nbn:de:0030-drops-195483}, doi = {10.4230/LIPIcs.ITCS.2024.20}, annote = {Keywords: Tensors, Asymptotic rank, Subrank, Slice rank, Restriction, Degeneration, Diagonalization, SLOCC} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Yuval Filmus, Edward A. Hirsch, Artur Riazanov, Alexander Smal, and Marc Vinyals. Proving Unsatisfiability with Hitting Formulas. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 48:1-48:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{filmus_et_al:LIPIcs.ITCS.2024.48, author = {Filmus, Yuval and Hirsch, Edward A. and Riazanov, Artur and Smal, Alexander and Vinyals, Marc}, title = {{Proving Unsatisfiability with Hitting Formulas}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {48:1--48: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.48}, URN = {urn:nbn:de:0030-drops-195762}, doi = {10.4230/LIPIcs.ITCS.2024.48}, annote = {Keywords: hitting formulas, polynomial identity testing, query complexity} }
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 264, 38th Computational Complexity Conference (CCC 2023)
Abhibhav Garg, Rafael Oliveira, Shir Peleg, and Akash Kumar Sengupta. Radical Sylvester-Gallai Theorem for Tuples of Quadratics. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 20:1-20:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{garg_et_al:LIPIcs.CCC.2023.20, author = {Garg, Abhibhav and Oliveira, Rafael and Peleg, Shir and Sengupta, Akash Kumar}, title = {{Radical Sylvester-Gallai Theorem for Tuples of Quadratics}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {20:1--20:30}, 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.20}, URN = {urn:nbn:de:0030-drops-182903}, doi = {10.4230/LIPIcs.CCC.2023.20}, annote = {Keywords: Sylvester-Gallai theorem, arrangements of hypersurfaces, algebraic complexity, polynomial identity testing, algebraic geometry, commutative algebra} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Suryajith Chillara, Coral Grichener, and Amir Shpilka. On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chillara_et_al:LIPIcs.STACS.2023.22, author = {Chillara, Suryajith and Grichener, Coral and Shpilka, Amir}, title = {{On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {22:1--22:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.22}, URN = {urn:nbn:de:0030-drops-176744}, doi = {10.4230/LIPIcs.STACS.2023.22}, annote = {Keywords: algebraic complexity, shift equivalence, polynomial equivalence, Hilbert’s Nullstellensatz, hardness of approximation} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
V. Arvind, Abhranil Chatterjee, and Partha Mukhopadhyay. Black-Box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial Time. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{arvind_et_al:LIPIcs.APPROX/RANDOM.2022.23, author = {Arvind, V. and Chatterjee, Abhranil and Mukhopadhyay, Partha}, title = {{Black-Box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial Time}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {23:1--23:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.23}, URN = {urn:nbn:de:0030-drops-171451}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.23}, annote = {Keywords: Rational Identity Testing, Black-box Derandomization, Cyclic Division Algebra, Matrix coefficient realization theory} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Venkatesan Guruswami, Peter Manohar, and Jonathan Mosheiff. 𝓁_p-Spread and Restricted Isometry Properties of Sparse Random Matrices. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{guruswami_et_al:LIPIcs.CCC.2022.7, author = {Guruswami, Venkatesan and Manohar, Peter and Mosheiff, Jonathan}, title = {{𝓁\underlinep-Spread and Restricted Isometry Properties of Sparse Random Matrices}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {7:1--7:17}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.7}, URN = {urn:nbn:de:0030-drops-165695}, doi = {10.4230/LIPIcs.CCC.2022.7}, annote = {Keywords: Spread Subspaces, Euclidean Sections, Restricted Isometry Property, Sparse Matrices} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Shir Peleg and Amir Shpilka. Robust Sylvester-Gallai Type Theorem for Quadratic Polynomials. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{peleg_et_al:LIPIcs.SoCG.2022.43, author = {Peleg, Shir and Shpilka, Amir}, title = {{Robust Sylvester-Gallai Type Theorem for Quadratic Polynomials}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {43:1--43:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-227-3}, ISSN = {1868-8969}, year = {2022}, volume = {224}, editor = {Goaoc, Xavier and Kerber, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.43}, URN = {urn:nbn:de:0030-drops-160515}, doi = {10.4230/LIPIcs.SoCG.2022.43}, annote = {Keywords: Sylvester-Gallai theorem, quadratic polynomials, Algebraic computation} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, and Akshayaram Srinivasan. Bounded Indistinguishability for Simple Sources. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bogdanov_et_al:LIPIcs.ITCS.2022.26, author = {Bogdanov, Andrej and Dinesh, Krishnamoorthy and Filmus, Yuval and Ishai, Yuval and Kaplan, Avi and Srinivasan, Akshayaram}, title = {{Bounded Indistinguishability for Simple Sources}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {26:1--26:18}, 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.26}, URN = {urn:nbn:de:0030-drops-156223}, doi = {10.4230/LIPIcs.ITCS.2022.26}, annote = {Keywords: Pseudorandomness, bounded indistinguishability, complexity of sampling, constant-depth circuits, secret sharing, leakage-resilient cryptography} }
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 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Gaurav Sinha. Efficient Reconstruction of Depth Three Arithmetic Circuits with Top Fan-In Two. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 118:1-118:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{sinha:LIPIcs.ITCS.2022.118, author = {Sinha, Gaurav}, title = {{Efficient Reconstruction of Depth Three Arithmetic Circuits with Top Fan-In Two}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {118:1--118:33}, 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.118}, URN = {urn:nbn:de:0030-drops-157143}, doi = {10.4230/LIPIcs.ITCS.2022.118}, annote = {Keywords: Arithmetic Circuits, Circuit Reconstruction} }
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 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Suryajith Chillara. Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{chillara:LIPIcs.FSTTCS.2021.14, author = {Chillara, Suryajith}, title = {{Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {14:1--14:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-215-0}, ISSN = {1868-8969}, year = {2021}, volume = {213}, editor = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.14}, URN = {urn:nbn:de:0030-drops-155251}, doi = {10.4230/LIPIcs.FSTTCS.2021.14}, annote = {Keywords: Functional Lower Bounds, Boolean Circuit Lower Bounds, Depth Four, Connections to Boolean Complexity, Iterated Matrix Multiplication} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Dori Medini and Amir Shpilka. Hitting Sets and Reconstruction for Dense Orbits in VP_{e} and ΣΠΣ Circuits. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 19:1-19:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{medini_et_al:LIPIcs.CCC.2021.19, author = {Medini, Dori and Shpilka, Amir}, title = {{Hitting Sets and Reconstruction for Dense Orbits in VP\underline\{e\} and \Sigma\Pi\Sigma Circuits}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {19:1--19:27}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.19}, URN = {urn:nbn:de:0030-drops-142930}, doi = {10.4230/LIPIcs.CCC.2021.19}, annote = {Keywords: Algebraic complexity, VP, VNP, algebraic circuits, algebraic formula} }
Feedback for Dagstuhl Publishing