Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Petr A. Golovach, Dieter Kratsch, Daniël Paulusma, and Anthony Stewart. A Linear Kernel for Finding Square Roots of Almost Planar Graphs. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{golovach_et_al:LIPIcs.SWAT.2016.4, author = {Golovach, Petr A. and Kratsch, Dieter and Paulusma, Dani\"{e}l and Stewart, Anthony}, title = {{A Linear Kernel for Finding Square Roots of Almost Planar Graphs}}, booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)}, pages = {4:1--4:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-011-8}, ISSN = {1868-8969}, year = {2016}, volume = {53}, editor = {Pagh, Rasmus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.4}, URN = {urn:nbn:de:0030-drops-60333}, doi = {10.4230/LIPIcs.SWAT.2016.4}, annote = {Keywords: planar graphs, square roots, linear kernel} }
Published in: Dagstuhl Seminar Proceedings, Volume 9511, Parameterized complexity and approximation algorithms (2010)
Holger Dell and Dieter van Melkebeek. Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses. In Parameterized complexity and approximation algorithms. Dagstuhl Seminar Proceedings, Volume 9511, pp. 1-29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{dell_et_al:DagSemProc.09511.7, author = {Dell, Holger and van Melkebeek, Dieter}, title = {{Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses}}, booktitle = {Parameterized complexity and approximation algorithms}, pages = {1--29}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9511}, editor = {Erik D. Demaine and MohammadTaghi Hajiaghayi and D\'{a}niel Marx}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09511.7}, URN = {urn:nbn:de:0030-drops-25043}, doi = {10.4230/DagSemProc.09511.7}, annote = {Keywords: Sparsification, Kernelization, Parameterized Complexity, Probabilistically Checkable Proofs, Satisfiability, Vertex Cover} }
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} }
Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)
Matthias Krause, Pavel Pudlák, Rüdiger Reischuk, and Dieter van Melkebeek. 06111 Abstracts Collection – Complexity of Boolean Functions. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
@InProceedings{krause_et_al:DagSemProc.06111.1, author = {Krause, Matthias and Pudl\'{a}k, Pavel and Reischuk, R\"{u}diger and van Melkebeek, Dieter}, title = {{06111 Abstracts Collection – Complexity of Boolean Functions}}, booktitle = {Complexity of Boolean Functions}, pages = {1--24}, 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.1}, URN = {urn:nbn:de:0030-drops-7593}, doi = {10.4230/DagSemProc.06111.1}, annote = {Keywords: Complexity of Boolean functions, Boolean circuits, binary decision diagrams, lower bound proof techniques, combinatorics of Boolean functions, communi algorithmic learning, cryptography, derandomization} }
Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)
Andreas Jakoby and Till Tantau. Computing Shortest Paths in Series-Parallel Graphs in Logarithmic Space. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
@InProceedings{jakoby_et_al:DagSemProc.06111.6, author = {Jakoby, Andreas and Tantau, Till}, title = {{Computing Shortest Paths in Series-Parallel Graphs in Logarithmic Space}}, booktitle = {Complexity of Boolean Functions}, pages = {1--9}, 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.6}, URN = {urn:nbn:de:0030-drops-6185}, doi = {10.4230/DagSemProc.06111.6}, annote = {Keywords: Series-parallel graphs, shortest path, logspace} }
Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)
Stasys Jukna. Graphs and Circuits: Some Further Remarks. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
@InProceedings{jukna:DagSemProc.06111.8, author = {Jukna, Stasys}, title = {{Graphs and Circuits: Some Further Remarks}}, booktitle = {Complexity of Boolean Functions}, pages = {1--16}, 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.8}, URN = {urn:nbn:de:0030-drops-6218}, doi = {10.4230/DagSemProc.06111.8}, annote = {Keywords: Graph complexity, single level conjecture, Sylvester graphs, communication complexity, ACC-circuits} }
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-dev.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} }
Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)
Emanuele Viola. On Probabilistic Time versus Alternating Time. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
@InProceedings{viola:DagSemProc.06111.11, author = {Viola, Emanuele}, title = {{On Probabilistic Time versus Alternating Time}}, booktitle = {Complexity of Boolean Functions}, 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.11}, URN = {urn:nbn:de:0030-drops-6194}, doi = {10.4230/DagSemProc.06111.11}, annote = {Keywords: Probabilistic time, alternating time, polynomial-time hierarchy, approximate majority, constant-depth circuit} }
Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)
Frank J. Balbach and Thomas Zeugmann. On the Teachability of Randomized Learners. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
@InProceedings{balbach_et_al:DagSemProc.06111.13, author = {Balbach, Frank J. and Zeugmann, Thomas}, title = {{On the Teachability of Randomized Learners}}, 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-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.13}, URN = {urn:nbn:de:0030-drops-6203}, doi = {10.4230/DagSemProc.06111.13}, annote = {Keywords: Algorithmic Teaching, Complexity of teaching} }
Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)
Andreas Jakoby, Maciej Liskiewicz, and Aleksander Madry. Using Quantum Oblivious Transfer to Cheat Sensitive Quantum Bit Commitment. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
@InProceedings{jakoby_et_al:DagSemProc.06111.21, author = {Jakoby, Andreas and Liskiewicz, Maciej and Madry, Aleksander}, title = {{Using Quantum Oblivious Transfer to Cheat Sensitive Quantum Bit Commitment}}, booktitle = {Complexity of Boolean Functions}, pages = {1--12}, 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.21}, URN = {urn:nbn:de:0030-drops-6223}, doi = {10.4230/DagSemProc.06111.21}, annote = {Keywords: Two-Party Computations, Quantum Protocols, Bit Commitment, Oblivious Transfer.} }
Published in: Dagstuhl Seminar Proceedings, Volume 6291, The Role of Business Processes in Service Oriented Architectures (2006)
Wil van der Aalst, Michael Beisiegel, Kees van Hee, Dieter König, and Christian Stahl. A SOA-Based Architecture Framework. In The Role of Business Processes in Service Oriented Architectures. Dagstuhl Seminar Proceedings, Volume 6291, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
@InProceedings{vanderaalst_et_al:DagSemProc.06291.4, author = {van der Aalst, Wil and Beisiegel, Michael and van Hee, Kees and K\"{o}nig, Dieter and Stahl, Christian}, title = {{A SOA-Based Architecture Framework}}, booktitle = {The Role of Business Processes in Service Oriented Architectures}, pages = {1--17}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {6291}, editor = {Frank Leymann and Wolfgang Reisig and Satish R. Thatte and Wil van der Aalst}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06291.4}, URN = {urn:nbn:de:0030-drops-8277}, doi = {10.4230/DagSemProc.06291.4}, annote = {Keywords: SOA, architecture framework} }
Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)
Dieter van Melkebeek and Konstantin Pervyshev. A Generic Time Hierarchy for Semantic Models With One Bit of Advice. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
@InProceedings{vanmelkebeek_et_al:DagSemProc.06111.3, author = {van Melkebeek, Dieter and Pervyshev, Konstantin}, title = {{A Generic Time Hierarchy for Semantic Models With One Bit of Advice}}, booktitle = {Complexity of Boolean Functions}, pages = {1--39}, 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.3}, URN = {urn:nbn:de:0030-drops-6151}, doi = {10.4230/DagSemProc.06111.3}, annote = {Keywords: Time hierarchy, non-uniformity, one bit of advice, probabilistic algorithms} }
Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)
Igor E. Shparlinski. Bounds on the Fourier Coefficients of the Weighted Sum Function. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
@InProceedings{shparlinski:DagSemProc.06111.5, author = {Shparlinski, Igor E.}, title = {{Bounds on the Fourier Coefficients of the Weighted Sum Function}}, booktitle = {Complexity of Boolean Functions}, pages = {1--9}, 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.5}, URN = {urn:nbn:de:0030-drops-6171}, doi = {10.4230/DagSemProc.06111.5}, annote = {Keywords: Fourier coefficients, congruences, average sensitivity, decision tree} }
Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)
Marcin Gomulkiewicz, Miroslaw Kutylowski, and Pawel Wlaz. Fault Jumping Attacks against Shrinking Generator. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
@InProceedings{gomulkiewicz_et_al:DagSemProc.06111.7, author = {Gomulkiewicz, Marcin and Kutylowski, Miroslaw and Wlaz, Pawel}, title = {{Fault Jumping Attacks against Shrinking Generator}}, booktitle = {Complexity of Boolean Functions}, pages = {1--6}, 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.7}, URN = {urn:nbn:de:0030-drops-6117}, doi = {10.4230/DagSemProc.06111.7}, annote = {Keywords: Pseudorandom generator, shrinking generator, fault cryptanalysis} }
Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)
Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, and Peter Bro Miltersen. On the Complexity of Numerical Analysis. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
@InProceedings{allender_et_al:DagSemProc.06111.12, author = {Allender, Eric and B\"{u}rgisser, Peter and Kjeldgaard-Pedersen, Johan and Miltersen, Peter Bro}, title = {{On the Complexity of Numerical Analysis}}, booktitle = {Complexity of Boolean Functions}, pages = {1--9}, 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.12}, URN = {urn:nbn:de:0030-drops-6130}, doi = {10.4230/DagSemProc.06111.12}, annote = {Keywords: Blum-Shub-Smale Model, Euclidean Traveling Salesman Problem, Counting Hierarchy} }
Feedback for Dagstuhl Publishing