Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
László Babai and Bohdan Kivva. Matrix Rigidity Depends on the Target Field. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 41:1-41:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{babai_et_al:LIPIcs.CCC.2021.41, author = {Babai, L\'{a}szl\'{o} and Kivva, Bohdan}, title = {{Matrix Rigidity Depends on the Target Field}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {41:1--41:26}, 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.41}, URN = {urn:nbn:de:0030-drops-143153}, doi = {10.4230/LIPIcs.CCC.2021.41}, annote = {Keywords: Matrix rigidity, field extension} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Lars Jaffke, Mateus de Oliveira Oliveira, and Hans Raj Tiwary. Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 50:1-50:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{jaffke_et_al:LIPIcs.MFCS.2020.50, author = {Jaffke, Lars and de Oliveira Oliveira, Mateus and Tiwary, Hans Raj}, title = {{Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {50:1--50:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.50}, URN = {urn:nbn:de:0030-drops-127161}, doi = {10.4230/LIPIcs.MFCS.2020.50}, annote = {Keywords: Permutation Groups, Context Free Grammars, Extension Complexity, Graph Embedding Complexity} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Ankit Garg, Nikhil Gupta, Neeraj Kayal, and Chandan Saha. Determinant Equivalence Test over Finite Fields and over Q. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{garg_et_al:LIPIcs.ICALP.2019.62, author = {Garg, Ankit and Gupta, Nikhil and Kayal, Neeraj and Saha, Chandan}, title = {{Determinant Equivalence Test over Finite Fields and over Q}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {62:1--62: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.62}, URN = {urn:nbn:de:0030-drops-106382}, doi = {10.4230/LIPIcs.ICALP.2019.62}, annote = {Keywords: Determinant equivalence test, full matrix algebra isomorphism, Lie algebra} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
László Babai, Timothy J. F. Black, and Angela Wuu. List-Decoding Homomorphism Codes with Arbitrary Codomains. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 29:1-29:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{babai_et_al:LIPIcs.APPROX-RANDOM.2018.29, author = {Babai, L\'{a}szl\'{o} and Black, Timothy J. F. and Wuu, Angela}, title = {{List-Decoding Homomorphism Codes with Arbitrary Codomains}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {29:1--29:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-085-9}, ISSN = {1868-8969}, year = {2018}, volume = {116}, editor = {Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David}, 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.2018.29}, URN = {urn:nbn:de:0030-drops-94338}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.29}, annote = {Keywords: Error-correcting codes, Local algorithms, Local list-decoding, Finite groups, Homomorphism codes} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Tom Gur and Ron D. Rothblum. A Hierarchy Theorem for Interactive Proofs of Proximity. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 39:1-39:43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{gur_et_al:LIPIcs.ITCS.2017.39, author = {Gur, Tom and Rothblum, Ron D.}, title = {{A Hierarchy Theorem for Interactive Proofs of Proximity}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {39:1--39:43}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.39}, URN = {urn:nbn:de:0030-drops-81536}, doi = {10.4230/LIPIcs.ITCS.2017.39}, annote = {Keywords: Complexity Theory, Property Testing, Interactive Proofs} }
Published in: Dagstuhl Reports, Volume 5, Issue 12 (2016)
László Babai, Anuj Dawar, Pascal Schweitzer, and Jacobo Torán. The Graph Isomorphism Problem (Dagstuhl Seminar 15511). In Dagstuhl Reports, Volume 5, Issue 12, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@Article{babai_et_al:DagRep.5.12.1, author = {Babai, L\'{a}szl\'{o} and Dawar, Anuj and Schweitzer, Pascal and Tor\'{a}n, Jacobo}, title = {{The Graph Isomorphism Problem (Dagstuhl Seminar 15511)}}, pages = {1--17}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2016}, volume = {5}, number = {12}, editor = {Babai, L\'{a}szl\'{o} and Dawar, Anuj and Schweitzer, Pascal and Tor\'{a}n, Jacobo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.5.12.1}, URN = {urn:nbn:de:0030-drops-58028}, doi = {10.4230/DagRep.5.12.1}, annote = {Keywords: canonical forms, complexity, computational group theory, graph isomorphism} }
Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
László Babai and Youming Qiao. Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 453-464, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@InProceedings{babai_et_al:LIPIcs.STACS.2012.453, author = {Babai, L\'{a}szl\'{o} and Qiao, Youming}, title = {{Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {453--464}, 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.453}, URN = {urn:nbn:de:0030-drops-34008}, doi = {10.4230/LIPIcs.STACS.2012.453}, annote = {Keywords: polynomial-time algorithm, group isomorphism, solvable group} }
Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)
László Babai, Anandam Banerjee, Raghav Kulkarni, and Vipul Naik. Evasiveness and the Distribution of Prime Numbers. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 71-82, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{babai_et_al:LIPIcs.STACS.2010.2445, author = {Babai, L\'{a}szl\'{o} and Banerjee, Anandam and Kulkarni, Raghav and Naik, Vipul}, title = {{Evasiveness and the Distribution of Prime Numbers}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {71--82}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, 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.2010.2445}, URN = {urn:nbn:de:0030-drops-24451}, doi = {10.4230/LIPIcs.STACS.2010.2445}, annote = {Keywords: Decision tree complexity, evasiveness, graph property, group action, Dirichlet primes, Extended Riemann Hypothesis} }
Feedback for Dagstuhl Publishing