Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
William He and Benjamin Rossman. Symmetric Formulas for Products of Permutations. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 68:1-68:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{he_et_al:LIPIcs.ITCS.2023.68, author = {He, William and Rossman, Benjamin}, title = {{Symmetric Formulas for Products of Permutations}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {68:1--68:23}, 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.68}, URN = {urn:nbn:de:0030-drops-175717}, doi = {10.4230/LIPIcs.ITCS.2023.68}, annote = {Keywords: circuit complexity, group-invariant formulas} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Gregory Rosenthal. Bounds on the QAC^0 Complexity of Approximating Parity. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 32:1-32:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{rosenthal:LIPIcs.ITCS.2021.32, author = {Rosenthal, Gregory}, title = {{Bounds on the QAC^0 Complexity of Approximating Parity}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {32:1--32:20}, 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.32}, URN = {urn:nbn:de:0030-drops-135713}, doi = {10.4230/LIPIcs.ITCS.2021.32}, annote = {Keywords: quantum circuit complexity, QAC^0, fanout, parity, nekomata} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Benjamin Rossman. Shrinkage of Decision Lists and DNF Formulas. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 70:1-70:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{rossman:LIPIcs.ITCS.2021.70, author = {Rossman, Benjamin}, title = {{Shrinkage of Decision Lists and DNF Formulas}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {70:1--70:14}, 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.70}, URN = {urn:nbn:de:0030-drops-136098}, doi = {10.4230/LIPIcs.ITCS.2021.70}, annote = {Keywords: shrinkage, decision lists, DNF formulas} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Toniann Pitassi, Morgan Shirley, and Thomas Watson. Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 92:1-92:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{pitassi_et_al:LIPIcs.ICALP.2020.92, author = {Pitassi, Toniann and Shirley, Morgan and Watson, Thomas}, title = {{Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {92:1--92:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.92}, URN = {urn:nbn:de:0030-drops-124992}, doi = {10.4230/LIPIcs.ICALP.2020.92}, annote = {Keywords: Boolean hierarchies, lifting theorems, query complexity} }
Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Gregory Rosenthal. Beating Treewidth for Average-Case Subgraph Isomorphism. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 24:1-24:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{rosenthal:LIPIcs.IPEC.2019.24, author = {Rosenthal, Gregory}, title = {{Beating Treewidth for Average-Case Subgraph Isomorphism}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {24:1--24:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.24}, URN = {urn:nbn:de:0030-drops-114850}, doi = {10.4230/LIPIcs.IPEC.2019.24}, annote = {Keywords: subgraph isomorphism, average-case complexity, AC^0, circuit complexity} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Benjamin Rossman. Criticality of Regular Formulas. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 1:1-1:28, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{rossman:LIPIcs.CCC.2019.1, author = {Rossman, Benjamin}, title = {{Criticality of Regular Formulas}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {1:1--1:28}, 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.1}, URN = {urn:nbn:de:0030-drops-108230}, doi = {10.4230/LIPIcs.CCC.2019.1}, annote = {Keywords: AC^0 circuits, formulas, criticality} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Benjamin Rossman. An Improved Homomorphism Preservation Theorem From Lower Bounds in Circuit Complexity. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 27:1-27:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{rossman:LIPIcs.ITCS.2017.27, author = {Rossman, Benjamin}, title = {{An Improved Homomorphism Preservation Theorem From Lower Bounds in Circuit Complexity}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {27:1--27:17}, 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.27}, URN = {urn:nbn:de:0030-drops-81435}, doi = {10.4230/LIPIcs.ITCS.2017.27}, annote = {Keywords: circuit complexity, finite model theory} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Benjamin Rossman and Srikanth Srinivasan. Separation of AC^0[oplus] Formulas and Circuits. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 50:1-50:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{rossman_et_al:LIPIcs.ICALP.2017.50, author = {Rossman, Benjamin and Srinivasan, Srikanth}, title = {{Separation of AC^0\lbrackoplus\rbrack Formulas and Circuits}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {50:1--50:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.50}, URN = {urn:nbn:de:0030-drops-73904}, doi = {10.4230/LIPIcs.ICALP.2017.50}, annote = {Keywords: circuit complexity, lower bounds, approximate majority, polynomial method} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Benjamin Rossman. Subspace-Invariant AC^0 Formulas. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 93:1-93:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{rossman:LIPIcs.ICALP.2017.93, author = {Rossman, Benjamin}, title = {{Subspace-Invariant AC^0 Formulas}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {93:1--93:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.93}, URN = {urn:nbn:de:0030-drops-74235}, doi = {10.4230/LIPIcs.ICALP.2017.93}, annote = {Keywords: lower bounds, size-depth tradeoff, parity, symmetry in computation} }
Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)
Benjamin Rossman. Correlation Bounds Against Monotone NC^1. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 392-411, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)
@InProceedings{rossman:LIPIcs.CCC.2015.392, author = {Rossman, Benjamin}, title = {{Correlation Bounds Against Monotone NC^1}}, booktitle = {30th Conference on Computational Complexity (CCC 2015)}, pages = {392--411}, 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.392}, URN = {urn:nbn:de:0030-drops-50785}, doi = {10.4230/LIPIcs.CCC.2015.392}, annote = {Keywords: circuit complexity, average-case complexity} }
Published in: Dagstuhl Seminar Proceedings, Volume 10061, Circuits, Logic, and Games (2010)
Benjamin Rossman, Thomas Schwentick, Denis Thérien, and Heribert Vollmer. 10061 Abstracts Collection – Circuits, Logic, and Games. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 10061, pp. 1-8, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{rossman_et_al:DagSemProc.10061.1, author = {Rossman, Benjamin and Schwentick, Thomas and Th\'{e}rien, Denis and Vollmer, Heribert}, title = {{10061 Abstracts Collection – Circuits, Logic, and Games}}, booktitle = {Circuits, Logic, and Games}, pages = {1--8}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {10061}, editor = {Benjamin Rossman and Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10061.1}, URN = {urn:nbn:de:0030-drops-25280}, doi = {10.4230/DagSemProc.10061.1}, annote = {Keywords: Computational complexity theory, Finite model theory, Boolean circuits, Regular languages, Finite monoids, Ehrenfeucht-Fra\{\backslash''i\}ss\'{e}-games} }
Published in: Dagstuhl Seminar Proceedings, Volume 10061, Circuits, Logic, and Games (2010)
Benjamin Rossman, Thomas Schwentick, Denis Thérien, and Heribert Vollmer. 10061 Executive Summary – Circuits, Logic, and Games. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 10061, pp. 1-5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{rossman_et_al:DagSemProc.10061.2, author = {Rossman, Benjamin and Schwentick, Thomas and Th\'{e}rien, Denis and Vollmer, Heribert}, title = {{10061 Executive Summary – Circuits, Logic, and Games}}, booktitle = {Circuits, Logic, and Games}, pages = {1--5}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {10061}, editor = {Benjamin Rossman and Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10061.2}, URN = {urn:nbn:de:0030-drops-25279}, doi = {10.4230/DagSemProc.10061.2}, annote = {Keywords: Computational complexity theory, finite model theory, Boolean circuits, regular languages, finite monoids, Ehrenfeucht-Fra\backslash"\backslashi ss\backslash'e-games} }
Published in: Dagstuhl Seminar Proceedings, Volume 10061, Circuits, Logic, and Games (2010)
Peter Lohmann and Heribert Vollmer. Complexity Results for Modal Dependence Logic. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 10061, pp. 1-15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{lohmann_et_al:DagSemProc.10061.3, author = {Lohmann, Peter and Vollmer, Heribert}, title = {{Complexity Results for Modal Dependence Logic}}, booktitle = {Circuits, Logic, and Games}, pages = {1--15}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {10061}, editor = {Benjamin Rossman and Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10061.3}, URN = {urn:nbn:de:0030-drops-25240}, doi = {10.4230/DagSemProc.10061.3}, annote = {Keywords: Dependence logic, satisfiability problem, computational complexity, poor man's logic} }
Published in: Dagstuhl Seminar Proceedings, Volume 10061, Circuits, Logic, and Games (2010)
Olaf Beyersdorff, Nicola Galesi, and Massimo Lauria. Hardness of Parameterized Resolution. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 10061, pp. 1-28, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{beyersdorff_et_al:DagSemProc.10061.4, author = {Beyersdorff, Olaf and Galesi, Nicola and Lauria, Massimo}, title = {{Hardness of Parameterized Resolution}}, booktitle = {Circuits, Logic, and Games}, pages = {1--28}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {10061}, editor = {Benjamin Rossman and Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10061.4}, URN = {urn:nbn:de:0030-drops-25254}, doi = {10.4230/DagSemProc.10061.4}, annote = {Keywords: Proof complexity, parameterized complexity, Resolution, Prover-Delayer Games} }
Published in: Dagstuhl Seminar Proceedings, Volume 10061, Circuits, Logic, and Games (2010)
Olaf Beyersdorff, Arne Meier, Sebastian Müller, Michael Thomas, and Heribert Vollmer. Proof Complexity of Propositional Default Logic. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 10061, pp. 1-14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{beyersdorff_et_al:DagSemProc.10061.5, author = {Beyersdorff, Olaf and Meier, Arne and M\"{u}ller, Sebastian and Thomas, Michael and Vollmer, Heribert}, title = {{Proof Complexity of Propositional Default Logic}}, booktitle = {Circuits, Logic, and Games}, pages = {1--14}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {10061}, editor = {Benjamin Rossman and Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10061.5}, URN = {urn:nbn:de:0030-drops-25261}, doi = {10.4230/DagSemProc.10061.5}, annote = {Keywords: Proof complexity, default logic, sequent calculus} }
Feedback for Dagstuhl Publishing