Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, and Shadab Romani. Does Looking Inside a Circuit Help?. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 1:1-1:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{impagliazzo_et_al:LIPIcs.MFCS.2017.1, author = {Impagliazzo, Russell and Kabanets, Valentine and Kolokolova, Antonina and McKenzie, Pierre and Romani, Shadab}, title = {{Does Looking Inside a Circuit Help?}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {1:1--1:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.1}, URN = {urn:nbn:de:0030-drops-80975}, doi = {10.4230/LIPIcs.MFCS.2017.1}, annote = {Keywords: Black-Box Hypothesis, Rice's theorem, circuit complexity, SAT, sensitivity of boolean functions, decision tree complexity} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Nathan Grosshans, Pierre McKenzie, and Luc Segoufin. The Power of Programs over Monoids in DA. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 2:1-2:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{grosshans_et_al:LIPIcs.MFCS.2017.2, author = {Grosshans, Nathan and McKenzie, Pierre and Segoufin, Luc}, title = {{The Power of Programs over Monoids in DA}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {2:1--2:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.2}, URN = {urn:nbn:de:0030-drops-80909}, doi = {10.4230/LIPIcs.MFCS.2017.2}, annote = {Keywords: Programs over monoids, DA, lower-bounds} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Eric Allender, Andreas Krebs, and Pierre McKenzie. Better Complexity Bounds for Cost Register Automata. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 24:1-24:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{allender_et_al:LIPIcs.MFCS.2017.24, author = {Allender, Eric and Krebs, Andreas and McKenzie, Pierre}, title = {{Better Complexity Bounds for Cost Register Automata}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {24:1--24:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.24}, URN = {urn:nbn:de:0030-drops-80661}, doi = {10.4230/LIPIcs.MFCS.2017.24}, annote = {Keywords: computational complexity, cost registers} }
Published in: Dagstuhl Reports, Volume 4, Issue 3 (2014)
Javier Esparza, Alain Finkel, Pierre McKenzie, and Joel Ouaknine. Reachability Problems for Infinite-State Systems (Dagstuhl Seminar 14141). In Dagstuhl Reports, Volume 4, Issue 3, pp. 153-180, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)
@Article{esparza_et_al:DagRep.4.3.153, author = {Esparza, Javier and Finkel, Alain and McKenzie, Pierre and Ouaknine, Joel}, title = {{Reachability Problems for Infinite-State Systems (Dagstuhl Seminar 14141)}}, pages = {153--180}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2014}, volume = {4}, number = {3}, editor = {Esparza, Javier and Finkel, Alain and McKenzie, Pierre and Ouaknine, Joel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.3.153}, URN = {urn:nbn:de:0030-drops-46121}, doi = {10.4230/DagRep.4.3.153}, annote = {Keywords: Infinite-State Systems, Reachability Problems, Formal Verification, Well-Structured Transition Systems, Counter Machines, Vector Addition Systems, Timed Systems} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Balagopal Komarath and Jayalal M. N. Sarma. Pebbling, Entropy and Branching Program Size Lower Bounds. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 622-633, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)
@InProceedings{komarath_et_al:LIPIcs.STACS.2013.622, author = {Komarath, Balagopal and Sarma, Jayalal M. N.}, title = {{Pebbling, Entropy and Branching Program Size Lower Bounds}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {622--633}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.622}, URN = {urn:nbn:de:0030-drops-39709}, doi = {10.4230/LIPIcs.STACS.2013.622}, annote = {Keywords: Pebbling, Entropy Method, Branching Programs, Size Lower Bounds.} }
Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
Mark Braverman, Stephen Cook, Pierre McKenzie, Rahul Santhanam, and Dustin Wehr. Fractional Pebbling and Thrifty Branching Programs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 109-120, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2009)
@InProceedings{braverman_et_al:LIPIcs.FSTTCS.2009.2311, author = {Braverman, Mark and Cook, Stephen and McKenzie, Pierre and Santhanam, Rahul and Wehr, Dustin}, title = {{Fractional Pebbling and Thrifty Branching Programs}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {109--120}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2009}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2311}, URN = {urn:nbn:de:0030-drops-23111}, doi = {10.4230/LIPIcs.FSTTCS.2009.2311}, annote = {Keywords: Branching programs, space complexity, tree evaluation, pebbling} }
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