Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, and Roshan Raj. Border Complexity of Symbolic Determinant Under Rank One Restriction. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 2:1-2:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{chatterjee_et_al:LIPIcs.CCC.2023.2, author = {Chatterjee, Abhranil and Ghosh, Sumanta and Gurjar, Rohit and Raj, Roshan}, title = {{Border Complexity of Symbolic Determinant Under Rank One Restriction}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {2:1--2:15}, 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.2}, URN = {urn:nbn:de:0030-drops-182721}, doi = {10.4230/LIPIcs.CCC.2023.2}, annote = {Keywords: Border Complexity, Symbolic Determinant, Valuated Matroid} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Pranjal Dutta, Gorav Jindal, Anurag Pandey, and Amit Sinhababu. Arithmetic Circuit Complexity of Division and Truncation. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 25:1-25:36, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{dutta_et_al:LIPIcs.CCC.2021.25, author = {Dutta, Pranjal and Jindal, Gorav and Pandey, Anurag and Sinhababu, Amit}, title = {{Arithmetic Circuit Complexity of Division and Truncation}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {25:1--25:36}, 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.25}, URN = {urn:nbn:de:0030-drops-142990}, doi = {10.4230/LIPIcs.CCC.2021.25}, annote = {Keywords: Arithmetic Circuits, Division, Truncation, Division elimination, Rational function, Algebraic power series, Transcendental power series, Integer factorization} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Pranjal Dutta, Nitin Saxena, and Thomas Thierauf. A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 23:1-23:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{dutta_et_al:LIPIcs.ITCS.2021.23, author = {Dutta, Pranjal and Saxena, Nitin and Thierauf, Thomas}, title = {{A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {23:1--23:21}, 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.23}, URN = {urn:nbn:de:0030-drops-135629}, doi = {10.4230/LIPIcs.ITCS.2021.23}, annote = {Keywords: VP, VNP, hitting set, circuit, polynomial, sparsity, SOS, SOC, PIT, lower bound} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Amit Sinhababu and Thomas Thierauf. Factorization of Polynomials Given By Arithmetic Branching Programs. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 33:1-33:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{sinhababu_et_al:LIPIcs.CCC.2020.33, author = {Sinhababu, Amit and Thierauf, Thomas}, title = {{Factorization of Polynomials Given By Arithmetic Branching Programs}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {33:1--33:19}, 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.33}, URN = {urn:nbn:de:0030-drops-125854}, doi = {10.4230/LIPIcs.CCC.2020.33}, annote = {Keywords: Arithmetic Branching Program, Multivariate Polynomial Factorization, Hensel Lifting, Newton Iteration, Hardness vs Randomness} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Rohit Gurjar, Thomas Thierauf, and Nisheeth K. Vishnoi. Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 74:1-74:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{gurjar_et_al:LIPIcs.ICALP.2018.74, author = {Gurjar, Rohit and Thierauf, Thomas and Vishnoi, Nisheeth K.}, title = {{Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {74:1--74:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.74}, URN = {urn:nbn:de:0030-drops-90782}, doi = {10.4230/LIPIcs.ICALP.2018.74}, annote = {Keywords: Derandomization, Isolation Lemma, Total unimodularity, Near-shortest vectors in Lattices, Regular matroids} }
Published in: Dagstuhl Reports, Volume 6, Issue 10 (2017)
Valentine Kabanets, Thomas Thierauf, Jacobo Tóran, and Christopher Umans. Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411). In Dagstuhl Reports, Volume 6, Issue 10, pp. 13-32, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@Article{kabanets_et_al:DagRep.6.10.13, author = {Kabanets, Valentine and Thierauf, Thomas and T\'{o}ran, Jacobo and Umans, Christopher}, title = {{Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411)}}, pages = {13--32}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2017}, volume = {6}, number = {10}, editor = {Kabanets, Valentine and Thierauf, Thomas and T\'{o}ran, Jacobo and Umans, Christopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.10.13}, URN = {urn:nbn:de:0030-drops-69504}, doi = {10.4230/DagRep.6.10.13}, annote = {Keywords: Computational Complexity, lower bounds, approximation, pseudo-randomness, derandomization, circuits} }
Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)
Rohit Gurjar, Arpita Korwar, Nitin Saxena, and Thomas Thierauf. Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 323-346, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)
@InProceedings{gurjar_et_al:LIPIcs.CCC.2015.323, author = {Gurjar, Rohit and Korwar, Arpita and Saxena, Nitin and Thierauf, Thomas}, title = {{Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs}}, booktitle = {30th Conference on Computational Complexity (CCC 2015)}, pages = {323--346}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.323}, URN = {urn:nbn:de:0030-drops-50647}, doi = {10.4230/LIPIcs.CCC.2015.323}, annote = {Keywords: PIT, Hitting-set, Sum of ROABPs, Evaluation Dimension, Rank Concentration} }
Published in: Dagstuhl Reports, Volume 4, Issue 9 (2015)
Manindra Agrawal, Valentine Kabanets, Thomas Thierauf, and Christopher Umans. Algebra in Computational Complexity (Dagstuhl Seminar 14391). In Dagstuhl Reports, Volume 4, Issue 9, pp. 85-105, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)
@Article{agrawal_et_al:DagRep.4.9.85, author = {Agrawal, Manindra and Kabanets, Valentine and Thierauf, Thomas and Umans, Christopher}, title = {{Algebra in Computational Complexity (Dagstuhl Seminar 14391)}}, pages = {85--105}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2015}, volume = {4}, number = {9}, editor = {Agrawal, Manindra and Kabanets, Valentine and Thierauf, Thomas and Umans, Christopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.9.85}, URN = {urn:nbn:de:0030-drops-48851}, doi = {10.4230/DagRep.4.9.85}, annote = {Keywords: Computational Complexity, lower bounds, approximazation, pseudo-randomness, derandomization, circuits} }
Published in: Dagstuhl Reports, Volume 2, Issue 10 (2013)
Manindra Agrawal, Thomas Thierauf, and Christopher Umans. Algebraic and Combinatorial Methods in Computational Complexity (Dagstuhl Seminar 12421). In Dagstuhl Reports, Volume 2, Issue 10, pp. 60-78, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)
@Article{agrawal_et_al:DagRep.2.10.60, author = {Agrawal, Manindra and Thierauf, Thomas and Umans, Christopher}, title = {{Algebraic and Combinatorial Methods in Computational Complexity (Dagstuhl Seminar 12421)}}, pages = {60--78}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2013}, volume = {2}, number = {10}, editor = {Agrawal, Manindra and Thierauf, Thomas and Umans, Christopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.10.60}, URN = {urn:nbn:de:0030-drops-39034}, doi = {10.4230/DagRep.2.10.60}, annote = {Keywords: Computational Complexity, lower bounds, approximazation, pseudo-randomness, derandomization, circuits} }
Published in: Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)
Manindra Agrawal, Lance Fortnow, Thomas Thierauf, and Christopher Umans. 09421 Abstracts Collection – Algebraic Methods in Computational Complexity. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{agrawal_et_al:DagSemProc.09421.1, author = {Agrawal, Manindra and Fortnow, Lance and Thierauf, Thomas and Umans, Christopher}, title = {{09421 Abstracts Collection – Algebraic Methods in Computational Complexity}}, booktitle = {Algebraic Methods in Computational Complexity}, pages = {1--22}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9421}, editor = {Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09421.1}, URN = {urn:nbn:de:0030-drops-24181}, doi = {10.4230/DagSemProc.09421.1}, annote = {Keywords: Computational Complexity, Algebra} }
Published in: Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)
Manindra Agrawal, Lance Fortnow, Thomas Thierauf, and Christopher Umans. 09421 Executive Summary – Algebraic Methods in Computational Complexity. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{agrawal_et_al:DagSemProc.09421.2, author = {Agrawal, Manindra and Fortnow, Lance and Thierauf, Thomas and Umans, Christopher}, title = {{09421 Executive Summary – Algebraic Methods in Computational Complexity}}, booktitle = {Algebraic Methods in Computational Complexity}, pages = {1--4}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9421}, editor = {Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09421.2}, URN = {urn:nbn:de:0030-drops-24100}, doi = {10.4230/DagSemProc.09421.2}, annote = {Keywords: Computational Complexity, Algebra} }
Published in: Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)
Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. An Axiomatic Approach to Algebrization. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{impagliazzo_et_al:DagSemProc.09421.3, author = {Impagliazzo, Russell and Kabanets, Valentine and Kolokolova, Antonina}, title = {{An Axiomatic Approach to Algebrization}}, booktitle = {Algebraic Methods in Computational Complexity}, pages = {1--19}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9421}, editor = {Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09421.3}, URN = {urn:nbn:de:0030-drops-24150}, doi = {10.4230/DagSemProc.09421.3}, annote = {Keywords: Oracles, arithmetization, algebrization} }
Published in: Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)
Noga Alon, Rina Panigrahy, and Sergey Yekhanin. Deterministic approximation algorithms for the nearest codeword problem. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{alon_et_al:DagSemProc.09421.4, author = {Alon, Noga and Panigrahy, Rina and Yekhanin, Sergey}, title = {{Deterministic approximation algorithms for the nearest codeword problem}}, booktitle = {Algebraic Methods in Computational Complexity}, pages = {1--13}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9421}, editor = {Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09421.4}, URN = {urn:nbn:de:0030-drops-24133}, doi = {10.4230/DagSemProc.09421.4}, annote = {Keywords: } }
Published in: Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)
Harry Buhrman, David Garcia-Soriano, and Arie Matsliah. Learning Parities in the Mistake-Bound model. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-9, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{buhrman_et_al:DagSemProc.09421.5, author = {Buhrman, Harry and Garcia-Soriano, David and Matsliah, Arie}, title = {{Learning Parities in the Mistake-Bound model}}, booktitle = {Algebraic Methods in Computational Complexity}, pages = {1--9}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9421}, editor = {Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09421.5}, URN = {urn:nbn:de:0030-drops-24178}, doi = {10.4230/DagSemProc.09421.5}, annote = {Keywords: Attribute-efficient learning, parities, mistake-bound} }
Published in: Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)
Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner. Planar Graph Isomorphism is in Log-Space. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-32, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{datta_et_al:DagSemProc.09421.6, author = {Datta, Samir and Limaye, Nutan and Nimbhorkar, Prajakta and Thierauf, Thomas and Wagner, Fabian}, title = {{Planar Graph Isomorphism is in Log-Space}}, booktitle = {Algebraic Methods in Computational Complexity}, pages = {1--32}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9421}, editor = {Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09421.6}, URN = {urn:nbn:de:0030-drops-24169}, doi = {10.4230/DagSemProc.09421.6}, annote = {Keywords: Planar Graphs, Graph Isomorphism, Logspace} }
Feedback for Dagstuhl Publishing