Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Gábor Ivanyos, Tushant Mittal, and Youming Qiao. Symbolic Determinant Identity Testing and Non-Commutative Ranks of Matrix Lie Algebras. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 87:1-87:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{ivanyos_et_al:LIPIcs.ITCS.2022.87, author = {Ivanyos, G\'{a}bor and Mittal, Tushant and Qiao, Youming}, title = {{Symbolic Determinant Identity Testing and Non-Commutative Ranks of Matrix Lie Algebras}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {87:1--87:21}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.87}, URN = {urn:nbn:de:0030-drops-156837}, doi = {10.4230/LIPIcs.ITCS.2022.87}, annote = {Keywords: derandomization, polynomial identity testing, symbolic determinant, non-commutative rank, Lie algebras} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Gábor Ivanyos, Anupam Prakash, and Miklos Santha. On Learning Linear Functions from Subset and Its Applications in Quantum Computing. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 66:1-66:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{ivanyos_et_al:LIPIcs.ESA.2018.66, author = {Ivanyos, G\'{a}bor and Prakash, Anupam and Santha, Miklos}, title = {{On Learning Linear Functions from Subset and Its Applications in Quantum Computing}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {66:1--66:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.66}, URN = {urn:nbn:de:0030-drops-95299}, doi = {10.4230/LIPIcs.ESA.2018.66}, annote = {Keywords: Learning from subset, hidden shift problem, quantum algorithms, linearization} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Gábor Ivanyos, Youming Qiao, and K Venkata Subrahmanyam. Constructive Non-Commutative Rank Computation Is in Deterministic Polynomial Time. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 55:1-55:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{ivanyos_et_al:LIPIcs.ITCS.2017.55, author = {Ivanyos, G\'{a}bor and Qiao, Youming and Subrahmanyam, K Venkata}, title = {{Constructive Non-Commutative Rank Computation Is in Deterministic Polynomial Time}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {55:1--55:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.55}, URN = {urn:nbn:de:0030-drops-81667}, doi = {10.4230/LIPIcs.ITCS.2017.55}, annote = {Keywords: invariant theory, non-commutative rank, null cone, symbolic determinant identity testing, semi-invariants of quivers} }
Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)
Aleksandrs Belovs, Gábor Ivanyos, Youming Qiao, Miklos Santha, and Siyi Yang. On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 30:1-30:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{belovs_et_al:LIPIcs.CCC.2017.30, author = {Belovs, Aleksandrs and Ivanyos, G\'{a}bor and Qiao, Youming and Santha, Miklos and Yang, Siyi}, title = {{On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz}}, booktitle = {32nd Computational Complexity Conference (CCC 2017)}, pages = {30:1--30:24}, 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.30}, URN = {urn:nbn:de:0030-drops-75260}, doi = {10.4230/LIPIcs.CCC.2017.30}, annote = {Keywords: Chevalley-Warning Theorem, Combinatorail Nullstellensatz, Polynomial Parity Argument, arithmetic circuit} }
Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Gábor Ivanyos, Marek Karpinski, Youming Qiao, and Miklos Santha. Generalized Wong sequences and their applications to Edmonds' problems. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 397-408, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{ivanyos_et_al:LIPIcs.STACS.2014.397, author = {Ivanyos, G\'{a}bor and Karpinski, Marek and Qiao, Youming and Santha, Miklos}, title = {{Generalized Wong sequences and their applications to Edmonds' problems}}, booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)}, pages = {397--408}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-65-1}, ISSN = {1868-8969}, year = {2014}, volume = {25}, editor = {Mayr, Ernst W. and Portier, Natacha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.397}, URN = {urn:nbn:de:0030-drops-44741}, doi = {10.4230/LIPIcs.STACS.2014.397}, annote = {Keywords: symbolic determinantal identity testing, Edmonds' problem, maximum rank matrix completion, derandomization, Wong sequences} }
Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
Gábor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, and Ronald de Wolf. New bounds on the classical and quantum communication complexity of some graph properties. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 148-159, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@InProceedings{ivanyos_et_al:LIPIcs.FSTTCS.2012.148, author = {Ivanyos, G\'{a}bor and Klauck, Hartmut and Lee, Troy and Santha, Miklos and de Wolf, Ronald}, title = {{New bounds on the classical and quantum communication complexity of some graph properties}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)}, pages = {148--159}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-47-7}, ISSN = {1868-8969}, year = {2012}, volume = {18}, editor = {D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.148}, URN = {urn:nbn:de:0030-drops-38523}, doi = {10.4230/LIPIcs.FSTTCS.2012.148}, annote = {Keywords: Graph properties, communication complexity, quantum communication} }