Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Peter Bürgisser, Mahmut Levent Doğan, Visu Makam, Michael Walter, and Avi Wigderson. Complexity of Robust Orbit Problems for Torus Actions and the abc-Conjecture. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 14:1-14:48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{burgisser_et_al:LIPIcs.CCC.2024.14, author = {B\"{u}rgisser, Peter and Do\u{g}an, Mahmut Levent and Makam, Visu and Walter, Michael and Wigderson, Avi}, title = {{Complexity of Robust Orbit Problems for Torus Actions and the abc-Conjecture}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {14:1--14:48}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.14}, URN = {urn:nbn:de:0030-drops-204100}, doi = {10.4230/LIPIcs.CCC.2024.14}, annote = {Keywords: computational invariant theory, geometric complexity theory, orbit problems, abc-conjecture, closest vector problem} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, and Amir Shpilka. Lower Bounds for Set-Multilinear Branching Programs. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chatterjee_et_al:LIPIcs.CCC.2024.20, author = {Chatterjee, Prerona and Kush, Deepanshu and Saraf, Shubhangi and Shpilka, Amir}, title = {{Lower Bounds for Set-Multilinear Branching Programs}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {20:1--20:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.20}, URN = {urn:nbn:de:0030-drops-204167}, doi = {10.4230/LIPIcs.CCC.2024.20}, annote = {Keywords: Lower Bounds, Algebraic Branching Programs, Set-multilinear polynomials} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Frederik L. Jatzkowski, Antonia Schmidt, Robert Mank, Steffen Schüler, and Matthias Müller-Hannemann. Barcode Selection and Layout Optimization in Spatial Transcriptomics. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 17:1-17:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{jatzkowski_et_al:LIPIcs.SEA.2024.17, author = {Jatzkowski, Frederik L. and Schmidt, Antonia and Mank, Robert and Sch\"{u}ler, Steffen and M\"{u}ller-Hannemann, Matthias}, title = {{Barcode Selection and Layout Optimization in Spatial Transcriptomics}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {17:1--17:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.17}, URN = {urn:nbn:de:0030-drops-203821}, doi = {10.4230/LIPIcs.SEA.2024.17}, annote = {Keywords: Spatial Transcriptomics, Array Layout, Optimization, Computational Complexity, GPU Computing, Integer Linear Programming, Metaheuristics} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Omkar Baraskar, Agrim Dewan, Chandan Saha, and Pulkit Sinha. NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 16:1-16:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{baraskar_et_al:LIPIcs.ICALP.2024.16, author = {Baraskar, Omkar and Dewan, Agrim and Saha, Chandan and Sinha, Pulkit}, title = {{NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {16:1--16:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.16}, URN = {urn:nbn:de:0030-drops-201598}, doi = {10.4230/LIPIcs.ICALP.2024.16}, annote = {Keywords: Equivalence testing, MCSP, sparse polynomials, 3SAT} }
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 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Prerona Chatterjee and Ramprasad Saptharishi. Constructing Faithful Homomorphisms over Fields of Finite Characteristic. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chatterjee_et_al:LIPIcs.FSTTCS.2019.11, author = {Chatterjee, Prerona and Saptharishi, Ramprasad}, title = {{Constructing Faithful Homomorphisms over Fields of Finite Characteristic}}, booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)}, pages = {11:1--11:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-131-3}, ISSN = {1868-8969}, year = {2019}, volume = {150}, editor = {Chattopadhyay, Arkadev and Gastin, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.11}, URN = {urn:nbn:de:0030-drops-115733}, doi = {10.4230/LIPIcs.FSTTCS.2019.11}, annote = {Keywords: Faithful Homomorphisms, Identity Testing, Algebraic Independence, Finite characteristic fields} }
Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)
Ramprasad Saptharishi and Anamay Tengse. Quasipolynomial Hitting Sets for Circuits with Restricted Parse Trees. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{saptharishi_et_al:LIPIcs.FSTTCS.2018.6, author = {Saptharishi, Ramprasad and Tengse, Anamay}, title = {{Quasipolynomial Hitting Sets for Circuits with Restricted Parse Trees}}, booktitle = {38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)}, pages = {6:1--6:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-093-4}, ISSN = {1868-8969}, year = {2018}, volume = {122}, editor = {Ganguly, Sumit and Pandya, Paritosh}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.6}, URN = {urn:nbn:de:0030-drops-99050}, doi = {10.4230/LIPIcs.FSTTCS.2018.6}, annote = {Keywords: Unambiguous Circuits, Read-once Oblivious ABPs, Polynomial Identity Testing, Lower Bounds, Algebraic Circuit Complexity} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Manindra Agrawal, Nitin Saxena, and Shubham Sahai Srivastava. Integer Factoring Using Small Algebraic Dependencies. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{agrawal_et_al:LIPIcs.MFCS.2016.6, author = {Agrawal, Manindra and Saxena, Nitin and Srivastava, Shubham Sahai}, title = {{Integer Factoring Using Small Algebraic Dependencies}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {6:1--6:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.6}, URN = {urn:nbn:de:0030-drops-64234}, doi = {10.4230/LIPIcs.MFCS.2016.6}, annote = {Keywords: integer, factorization, factoring integers, algebraic dependence, dependencies} }
Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)
Manindra Agrawal, Diptarka Chakraborty, Debarati Das, and Satyadev Nandakumar. Dimension, Pseudorandomness and Extraction of Pseudorandomness. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 221-235, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{agrawal_et_al:LIPIcs.FSTTCS.2015.221, author = {Agrawal, Manindra and Chakraborty, Diptarka and Das, Debarati and Nandakumar, Satyadev}, title = {{Dimension, Pseudorandomness and Extraction of Pseudorandomness}}, booktitle = {35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)}, pages = {221--235}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-97-2}, ISSN = {1868-8969}, year = {2015}, volume = {45}, editor = {Harsha, Prahladh and Ramalingam, G.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.221}, URN = {urn:nbn:de:0030-drops-56184}, doi = {10.4230/LIPIcs.FSTTCS.2015.221}, annote = {Keywords: Pseudorandomness, Dimension, Martingale, Unpredictability, Pseudoentropy, Pseudorandom Extractor, Hard Function} }
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: } }