Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, and Yuichi Yoshida. One-Tape Turing Machine and Branching Program Lower Bounds for MCSP. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 23:1-23:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{cheraghchi_et_al:LIPIcs.STACS.2021.23, author = {Cheraghchi, Mahdi and Hirahara, Shuichi and Myrisiotis, Dimitrios and Yoshida, Yuichi}, title = {{One-Tape Turing Machine and Branching Program Lower Bounds for MCSP}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {23:1--23:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.23}, URN = {urn:nbn:de:0030-drops-136681}, doi = {10.4230/LIPIcs.STACS.2021.23}, annote = {Keywords: Minimum Circuit Size Problem, Kolmogorov Complexity, One-Tape Turing Machines, Branching Programs, Lower Bounds, Pseudorandom Generators, Hitting Set Generators} }
Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)
Juraj Hromkovic and Georg Schnitger. Ambiguity and Communication. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 553-564, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{hromkovic_et_al:LIPIcs.STACS.2009.1805, author = {Hromkovic, Juraj and Schnitger, Georg}, title = {{Ambiguity and Communication}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {553--564}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1805}, URN = {urn:nbn:de:0030-drops-18054}, doi = {10.4230/LIPIcs.STACS.2009.1805}, annote = {Keywords: Nondeterministic finite automata, Ambiguity, Communication complexity} }
Published in: Dagstuhl Seminar Proceedings, Volume 8381, Computational Complexity of Discrete Problems (2008)
Kristoffer Arnsfelt Hansen. Depth Reduction for Circuits with a Single Layer of Modular Counting Gates. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{hansen:DagSemProc.08381.4, author = {Hansen, Kristoffer Arnsfelt}, title = {{Depth Reduction for Circuits with a Single Layer of Modular Counting Gates}}, booktitle = {Computational Complexity of Discrete Problems}, pages = {1--11}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8381}, editor = {Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08381.4}, URN = {urn:nbn:de:0030-drops-17824}, doi = {10.4230/DagSemProc.08381.4}, annote = {Keywords: Boolean Circuits, Randomized Polynomials, Fourier sums} }
Published in: Dagstuhl Seminar Proceedings, Volume 8381, Computational Complexity of Discrete Problems (2008)
Eli Ben-Sasson and Jakob Nordström. Understanding space in resolution: optimal lower bounds and exponential trade-offs. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{bensasson_et_al:DagSemProc.08381.6, author = {Ben-Sasson, Eli and Nordstr\"{o}m, Jakob}, title = {{Understanding space in resolution: optimal lower bounds and exponential trade-offs}}, booktitle = {Computational Complexity of Discrete Problems}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8381}, editor = {Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08381.6}, URN = {urn:nbn:de:0030-drops-17815}, doi = {10.4230/DagSemProc.08381.6}, annote = {Keywords: Proof complexity, Resolution, Pebbling.} }
Published in: Dagstuhl Seminar Proceedings, Volume 8381, Computational Complexity of Discrete Problems (2008)
Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, and Dieter van Melkebeek. 08381 Abstracts Collection – Computational Complexity of Discrete Problems. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{miltersen_et_al:DagSemProc.08381.1, author = {Miltersen, Peter Bro and Reischuk, R\"{u}diger and Schnitger, Georg and van Melkebeek, Dieter}, title = {{08381 Abstracts Collection – Computational Complexity of Discrete Problems}}, booktitle = {Computational Complexity of Discrete Problems}, pages = {1--18}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8381}, editor = {Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08381.1}, URN = {none}, doi = {10.4230/DagSemProc.08381.1}, annote = {Keywords: Computational complexity, discrete problems, Turing machines, circuits, proof complexity, pseudorandomness, derandomization, cryptography, computational learning, communication complexity, query complexity, hardness of approximation} }
Published in: Dagstuhl Seminar Proceedings, Volume 8381, Computational Complexity of Discrete Problems (2008)
Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, and Dieter van Melkebeek. 08381 Executive Summary – Computational Complexity of Discrete Problems. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{miltersen_et_al:DagSemProc.08381.2, author = {Miltersen, Peter Bro and Reischuk, R\"{u}diger and Schnitger, Georg and van Melkebeek, Dieter}, title = {{08381 Executive Summary – Computational Complexity of Discrete Problems}}, booktitle = {Computational Complexity of Discrete Problems}, pages = {1--7}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8381}, editor = {Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08381.2}, URN = {urn:nbn:de:0030-drops-17789}, doi = {10.4230/DagSemProc.08381.2}, annote = {Keywords: Computational complexity, discrete problems, Turing machines, circuits, proof complexity, pseudorandomness, derandomization, cryptography, computational learning, communication complexity, query complexity, hardness of approximation} }
Published in: Dagstuhl Seminar Proceedings, Volume 8381, Computational Complexity of Discrete Problems (2008)
Troy Lee and Adi Shraibman. Approximation norms and duality for communication complexity lower bounds. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{lee_et_al:DagSemProc.08381.3, author = {Lee, Troy and Shraibman, Adi}, title = {{Approximation norms and duality for communication complexity lower bounds}}, booktitle = {Computational Complexity of Discrete Problems}, pages = {1--9}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8381}, editor = {Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08381.3}, URN = {urn:nbn:de:0030-drops-17768}, doi = {10.4230/DagSemProc.08381.3}, annote = {Keywords: Communication complexity, lower bounds} }
Published in: Dagstuhl Seminar Proceedings, Volume 8381, Computational Complexity of Discrete Problems (2008)
Kiran Kedlaya and Christopher Umans. Fast polynomial factorization and modular composition. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, pp. 1-33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{kedlaya_et_al:DagSemProc.08381.5, author = {Kedlaya, Kiran and Umans, Christopher}, title = {{Fast polynomial factorization and modular composition}}, booktitle = {Computational Complexity of Discrete Problems}, pages = {1--33}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8381}, editor = {Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08381.5}, URN = {urn:nbn:de:0030-drops-17771}, doi = {10.4230/DagSemProc.08381.5}, annote = {Keywords: Modular composition; polynomial factorization; multipoint evaluation; Chinese Remaindering} }
Feedback for Dagstuhl Publishing