Published in: Dagstuhl Reports, Volume 13, Issue 3 (2023)
Anna Gál, Meena Mahajan, Rahul Santhanam, Till Tantau, and Manaswi Paraashar. Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111). In Dagstuhl Reports, Volume 13, Issue 3, pp. 17-31, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@Article{gal_et_al:DagRep.13.3.17, author = {G\'{a}l, Anna and Mahajan, Meena and Santhanam, Rahul and Tantau, Till and Paraashar, Manaswi}, title = {{Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111)}}, pages = {17--31}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2023}, volume = {13}, number = {3}, editor = {G\'{a}l, Anna and Mahajan, Meena and Santhanam, Rahul and Tantau, Till and Paraashar, Manaswi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.3.17}, URN = {urn:nbn:de:0030-drops-192261}, doi = {10.4230/DagRep.13.3.17}, annote = {Keywords: circuit complexity, communication complexity, computational complexity, lower bounds, randomness} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Joshua Cook and Ron D. Rothblum. Efficient Interactive Proofs for Non-Deterministic Bounded Space. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 47:1-47:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{cook_et_al:LIPIcs.APPROX/RANDOM.2023.47, author = {Cook, Joshua and Rothblum, Ron D.}, title = {{Efficient Interactive Proofs for Non-Deterministic Bounded Space}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {47:1--47:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.47}, URN = {urn:nbn:de:0030-drops-188727}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.47}, annote = {Keywords: Interactive Proofs, Alternating Algorithms, AC0\lbrack2\rbrack, Doubly Efficient Proofs} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Sourav Chakraborty, Anna Gál, Sophie Laplante, Rajat Mittal, and Anupa Sunny. Certificate Games. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 32:1-32:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{chakraborty_et_al:LIPIcs.ITCS.2023.32, author = {Chakraborty, Sourav and G\'{a}l, Anna and Laplante, Sophie and Mittal, Rajat and Sunny, Anupa}, title = {{Certificate Games}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {32:1--32:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.32}, URN = {urn:nbn:de:0030-drops-175353}, doi = {10.4230/LIPIcs.ITCS.2023.32}, annote = {Keywords: block sensitivity, boolean function complexity, certificate complexity, query complexity, sensitivity, zero-communication two-player games} }
Published in: Dagstuhl Reports, Volume 11, Issue 2 (2021)
Anna Gál, Meena Mahajan, Rahul Santhanam, and Till Tantau. Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121). In Dagstuhl Reports, Volume 11, Issue 2, pp. 1-16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@Article{gal_et_al:DagRep.11.2.1, author = {G\'{a}l, Anna and Mahajan, Meena and Santhanam, Rahul and Tantau, Till}, title = {{Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121)}}, pages = {1--16}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2021}, volume = {11}, number = {2}, editor = {G\'{a}l, Anna and Mahajan, Meena and Santhanam, Rahul and Tantau, Till}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.2.1}, URN = {urn:nbn:de:0030-drops-146836}, doi = {10.4230/DagRep.11.2.1}, annote = {Keywords: circuit complexity, communication complexity, computational complexity, lower bounds, randomness} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Siddhesh Chaubal and Anna Gál. Diameter Versus Certificate Complexity of Boolean Functions. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 31:1-31:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{chaubal_et_al:LIPIcs.MFCS.2021.31, author = {Chaubal, Siddhesh and G\'{a}l, Anna}, title = {{Diameter Versus Certificate Complexity of Boolean Functions}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {31:1--31:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.31}, URN = {urn:nbn:de:0030-drops-144713}, doi = {10.4230/LIPIcs.MFCS.2021.31}, annote = {Keywords: Sensitivity Conjecture, Boolean Functions, Certificate Complexity, Block Sensitivity, Log-rank Conjecture, Alternating Number} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Yuval Filmus, Or Meir, and Avishay Tal. Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0 (Extended Abstract). In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 89:1-89:7, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{filmus_et_al:LIPIcs.ITCS.2021.89, author = {Filmus, Yuval and Meir, Or and Tal, Avishay}, title = {{Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {89:1--89:7}, 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.89}, URN = {urn:nbn:de:0030-drops-136281}, doi = {10.4230/LIPIcs.ITCS.2021.89}, annote = {Keywords: De Morgan formulas, KRW Conjecture, shrinkage, random restrictions, random projections, bounded depth circuits, constant depth circuits, formula complexity} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Anna Gál and Robert Robere. Lower Bounds for (Non-Monotone) Comparator Circuits. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 58:1-58:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{gal_et_al:LIPIcs.ITCS.2020.58, author = {G\'{a}l, Anna and Robere, Robert}, title = {{Lower Bounds for (Non-Monotone) Comparator Circuits}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {58:1--58:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.58}, URN = {urn:nbn:de:0030-drops-117431}, doi = {10.4230/LIPIcs.ITCS.2020.58}, annote = {Keywords: comparator circuits, circuit complexity, Nechiporuk, lower bounds} }
Published in: Dagstuhl Reports, Volume 9, Issue 3 (2019)
Anna Gál, Rahul Santhanam, and Till Tantau. Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121). In Dagstuhl Reports, Volume 9, Issue 3, pp. 64-82, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@Article{gal_et_al:DagRep.9.3.64, author = {G\'{a}l, Anna and Santhanam, Rahul and Tantau, Till}, title = {{Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121)}}, pages = {64--82}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2019}, volume = {9}, number = {3}, editor = {G\'{a}l, Anna and Santhanam, Rahul and Tantau, Till}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.3.64}, URN = {urn:nbn:de:0030-drops-112920}, doi = {10.4230/DagRep.9.3.64}, annote = {Keywords: circuit complexity, communication complexity, computational complexity, parametrisation, randomness} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
William M. Hoza. Typically-Correct Derandomization for Small Time and Space. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 9:1-9:39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{hoza:LIPIcs.CCC.2019.9, author = {Hoza, William M.}, title = {{Typically-Correct Derandomization for Small Time and Space}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {9:1--9:39}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.9}, URN = {urn:nbn:de:0030-drops-108317}, doi = {10.4230/LIPIcs.CCC.2019.9}, annote = {Keywords: Derandomization, pseudorandomness, space complexity} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Anna Gál, Avishay Tal, and Adrian Trejo Nuñez. Cubic Formula Size Lower Bounds Based on Compositions with Majority. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 35:1-35:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{gal_et_al:LIPIcs.ITCS.2019.35, author = {G\'{a}l, Anna and Tal, Avishay and Trejo Nu\~{n}ez, Adrian}, title = {{Cubic Formula Size Lower Bounds Based on Compositions with Majority}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {35:1--35:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.35}, URN = {urn:nbn:de:0030-drops-101283}, doi = {10.4230/LIPIcs.ITCS.2019.35}, annote = {Keywords: formula lower bounds, random restrictions, KRW conjecture, composition} }
Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)
Siddhesh Chaubal and Anna Gál. New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity. 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. 13:1-13:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{chaubal_et_al:LIPIcs.FSTTCS.2018.13, author = {Chaubal, Siddhesh and G\'{a}l, Anna}, title = {{New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity}}, booktitle = {38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)}, pages = {13:1--13:16}, 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.13}, URN = {urn:nbn:de:0030-drops-99129}, doi = {10.4230/LIPIcs.FSTTCS.2018.13}, annote = {Keywords: Sensitivity Conjecture, Boolean Functions, Complexity Measures} }
Published in: Dagstuhl Reports, Volume 7, Issue 3 (2017)
Anna Gál, Michal Koucký, Oded Regev, and Till Tantau. Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121). In Dagstuhl Reports, Volume 7, Issue 3, pp. 45-69, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@Article{gal_et_al:DagRep.7.3.45, author = {G\'{a}l, Anna and Kouck\'{y}, Michal and Regev, Oded and Tantau, Till}, title = {{Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121)}}, pages = {45--69}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2017}, volume = {7}, number = {3}, editor = {G\'{a}l, Anna and Kouck\'{y}, Michal and Regev, Oded and Tantau, Till}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.3.45}, URN = {urn:nbn:de:0030-drops-73611}, doi = {10.4230/DagRep.7.3.45}, annote = {Keywords: Computational Complexity} }
Published in: Dagstuhl Reports, Volume 4, Issue 3 (2014)
Anna Gal, Michal Koucky, Oded Regev, and Rüdiger Reischuk. Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121). In Dagstuhl Reports, Volume 4, Issue 3, pp. 62-84, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)
@Article{gal_et_al:DagRep.4.3.62, author = {Gal, Anna and Koucky, Michal and Regev, Oded and Reischuk, R\"{u}diger}, title = {{Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121)}}, pages = {62--84}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2014}, volume = {4}, number = {3}, editor = {Gal, Anna and Koucky, Michal and Regev, Oded and Reischuk, R\"{u}diger}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.3.62}, URN = {urn:nbn:de:0030-drops-45921}, doi = {10.4230/DagRep.4.3.62}, annote = {Keywords: discrete problems, computational complexity, Turing machines, Boolean circuits, arithmetic circuits, quantum computing, communication complexity, pseudorandomness, derandomization, approximation, data streams} }
Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Anna Gal and Andrew Mills. Three Query Locally Decodable Codes with Higher Correctness Require Exponential Length. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 673-684, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2011)
@InProceedings{gal_et_al:LIPIcs.STACS.2011.673, author = {Gal, Anna and Mills, Andrew}, title = {{Three Query Locally Decodable Codes with Higher Correctness Require Exponential Length}}, booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)}, pages = {673--684}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-25-5}, ISSN = {1868-8969}, year = {2011}, volume = {9}, editor = {Schwentick, Thomas and D\"{u}rr, Christoph}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.673}, URN = {urn:nbn:de:0030-drops-30534}, doi = {10.4230/LIPIcs.STACS.2011.673}, annote = {Keywords: error correcting codes} }
Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)
Anna Gál, Pierre McKenzie, and Michal Koucký. Incremental branching programs. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2006)
@InProceedings{gal_et_al:DagSemProc.06111.10, author = {G\'{a}l, Anna and McKenzie, Pierre and Kouck\'{y}, Michal}, title = {{Incremental branching programs}}, booktitle = {Complexity of Boolean Functions}, pages = {1--20}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {6111}, editor = {Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.10}, URN = {urn:nbn:de:0030-drops-6230}, doi = {10.4230/DagSemProc.06111.10}, annote = {Keywords: Complexity theory, branching programs, logarithmic space, marking machines} }
Feedback for Dagstuhl Publishing