Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)
Ittai Abraham and Gilad Stern. New Dolev-Reischuk Lower Bounds Meet Blockchain Eclipse Attacks. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{abraham_et_al:LIPIcs.OPODIS.2022.16, author = {Abraham, Ittai and Stern, Gilad}, title = {{New Dolev-Reischuk Lower Bounds Meet Blockchain Eclipse Attacks}}, booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)}, pages = {16:1--16:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-265-5}, ISSN = {1868-8969}, year = {2023}, volume = {253}, editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.16}, URN = {urn:nbn:de:0030-drops-176368}, doi = {10.4230/LIPIcs.OPODIS.2022.16}, annote = {Keywords: consensus, crusader broadcast, Byzantine fault tolerance, blockchain, synchrony, lower bounds} }
Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)
Shir Cohen, Idit Keidar, and Alexander Spiegelman. Make Every Word Count: Adaptive Byzantine Agreement with Fewer Words. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 18:1-18:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{cohen_et_al:LIPIcs.OPODIS.2022.18, author = {Cohen, Shir and Keidar, Idit and Spiegelman, Alexander}, title = {{Make Every Word Count: Adaptive Byzantine Agreement with Fewer Words}}, booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)}, pages = {18:1--18:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-265-5}, ISSN = {1868-8969}, year = {2023}, volume = {253}, editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.18}, URN = {urn:nbn:de:0030-drops-176385}, doi = {10.4230/LIPIcs.OPODIS.2022.18}, annote = {Keywords: Byzantine Agreement, Byzantine Broadcast, Adaptive communication} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic, and Manuel Vidigueira. Byzantine Consensus Is Θ(n²): The Dolev-Reischuk Bound Is Tight Even in Partial Synchrony!. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{civit_et_al:LIPIcs.DISC.2022.14, author = {Civit, Pierre and Dzulfikar, Muhammad Ayaz and Gilbert, Seth and Gramoli, Vincent and Guerraoui, Rachid and Komatovic, Jovan and Vidigueira, Manuel}, title = {{Byzantine Consensus Is \Theta(n²): The Dolev-Reischuk Bound Is Tight Even in Partial Synchrony!}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {14:1--14:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.14}, URN = {urn:nbn:de:0030-drops-172059}, doi = {10.4230/LIPIcs.DISC.2022.14}, annote = {Keywords: Optimal Byzantine consensus, Communication complexity, Latency complexity} }
Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, and Till Tantau. Dynamic Kernels for Hitting Sets and Set Packing. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bannach_et_al:LIPIcs.IPEC.2021.7, author = {Bannach, Max and Heinrich, Zacharias and Reischuk, R\"{u}diger and Tantau, Till}, title = {{Dynamic Kernels for Hitting Sets and Set Packing}}, booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)}, pages = {7:1--7:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-216-7}, ISSN = {1868-8969}, year = {2021}, volume = {214}, editor = {Golovach, Petr A. and Zehavi, Meirav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.7}, URN = {urn:nbn:de:0030-drops-153900}, doi = {10.4230/LIPIcs.IPEC.2021.7}, annote = {Keywords: Kernelization, Dynamic Algorithms, Hitting Set, Set Packings} }
Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)
Atsuki Momose and Ling Ren. Optimal Communication Complexity of Authenticated Byzantine Agreement. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{momose_et_al:LIPIcs.DISC.2021.32, author = {Momose, Atsuki and Ren, Ling}, title = {{Optimal Communication Complexity of Authenticated Byzantine Agreement}}, booktitle = {35th International Symposium on Distributed Computing (DISC 2021)}, pages = {32:1--32:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-210-5}, ISSN = {1868-8969}, year = {2021}, volume = {209}, editor = {Gilbert, Seth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.32}, URN = {urn:nbn:de:0030-drops-148341}, doi = {10.4230/LIPIcs.DISC.2021.32}, annote = {Keywords: Byzantine Agreement, Communication Complexity, Lower Bound} }
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-dev.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: 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-dev.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: 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} }
Published in: Dagstuhl Seminar Proceedings, Volume 8131, Ontologies and Text Mining for Life Sciences : Current Status and Future Perspectives (2008)
Heiko Dietze, Dimitra Alexopoulou, Michael R. Alvers, Bill Barrio-Alvers, Andreas Doms, Jörg Hakenberg, Jan Mönnich, Conrad Plake, Andreas Reischuk, Loic Royer, Thomas Wächter, Matthias Zschunke, and Michael Schroeder. GoPubMed: Exploring Pubmed with Ontological Background Knowledge. In Ontologies and Text Mining for Life Sciences : Current Status and Future Perspectives. Dagstuhl Seminar Proceedings, Volume 8131, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{dietze_et_al:DagSemProc.08131.6, author = {Dietze, Heiko and Alexopoulou, Dimitra and Alvers, Michael R. and Barrio-Alvers, Bill and Doms, Andreas and Hakenberg, J\"{o}rg and M\"{o}nnich, Jan and Plake, Conrad and Reischuck, Andreas and Royer, Loic and W\"{a}chter, Thomas and Zschunke, Matthias and Schroeder, Michael}, title = {{GoPubMed: Exploring Pubmed with Ontological Background Knowledge}}, booktitle = {Ontologies and Text Mining for Life Sciences : Current Status and Future Perspectives}, pages = {1--1}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8131}, editor = {Michael Ashburner and Ulf Leser and Dietrich Rebholz-Schuhmann}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08131.6}, URN = {urn:nbn:de:0030-drops-15204}, doi = {10.4230/DagSemProc.08131.6}, annote = {Keywords: Text mining, literature search, Gene Ontology, NLP, ontology, thesaurus, PubMed} }
Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)
Matthias Krause, Dieter van Melkebeek, Pavel Pudlák, and Rüdiger Reischuk. 06111 Executive Summary – Complexity of Boolean Functions. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
@InProceedings{krause_et_al:DagSemProc.06111.2, author = {Krause, Matthias and van Melkebeek, Dieter and Pudl\'{a}k, Pavel and Reischuk, R\"{u}diger}, title = {{06111 Executive Summary – Complexity of Boolean Functions}}, booktitle = {Complexity of Boolean Functions}, pages = {1--5}, 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-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.2}, URN = {urn:nbn:de:0030-drops-8409}, doi = {10.4230/DagSemProc.06111.2}, annote = {Keywords: Boolean and quantum circuits, discrete problems, computational complexity, lower bounds, communication complexity, proof and query complexity, randomization, pseudo-randomness, derandomization, approximation, cryptography, computational learning} }
Feedback for Dagstuhl Publishing