Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)
Dieter van Melkebeek and Nicollas Mocelin Sdroievski. Leakage Resilience, Targeted Pseudorandom Generators, and Mild Derandomization of Arthur-Merlin Protocols. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 29:1-29:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{vanmelkebeek_et_al:LIPIcs.FSTTCS.2023.29, author = {van Melkebeek, Dieter and Mocelin Sdroievski, Nicollas}, title = {{Leakage Resilience, Targeted Pseudorandom Generators, and Mild Derandomization of Arthur-Merlin Protocols}}, booktitle = {43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)}, pages = {29:1--29:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-304-1}, ISSN = {1868-8969}, year = {2023}, volume = {284}, editor = {Bouyer, Patricia and Srinivasan, Srikanth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.29}, URN = {urn:nbn:de:0030-drops-194024}, doi = {10.4230/LIPIcs.FSTTCS.2023.29}, annote = {Keywords: Hardness versus randomness tradeoff, leakage resilience, Arthur-Merlin protocol, targeted hitting set generator} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Dieter van Melkebeek and Nicollas Mocelin Sdroievski. Instance-Wise Hardness Versus Randomness Tradeoffs for Arthur-Merlin Protocols. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 17:1-17:36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{vanmelkebeek_et_al:LIPIcs.CCC.2023.17, author = {van Melkebeek, Dieter and Mocelin Sdroievski, Nicollas}, title = {{Instance-Wise Hardness Versus Randomness Tradeoffs for Arthur-Merlin Protocols}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {17:1--17:36}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.17}, URN = {urn:nbn:de:0030-drops-182870}, doi = {10.4230/LIPIcs.CCC.2023.17}, annote = {Keywords: Hardness versus randomness tradeoff, Arthur-Merlin protocol, targeted hitting set generator} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Dieter van Melkebeek and Andrew Morgan. Polynomial Identity Testing via Evaluation of Rational Functions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 119:1-119:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{vanmelkebeek_et_al:LIPIcs.ITCS.2022.119, author = {van Melkebeek, Dieter and Morgan, Andrew}, title = {{Polynomial Identity Testing via Evaluation of Rational Functions}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {119:1--119:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.119}, URN = {urn:nbn:de:0030-drops-157158}, doi = {10.4230/LIPIcs.ITCS.2022.119}, annote = {Keywords: Derandomization, Gr\"{o}bner Basis, Lower Bounds, Polynomial Identity Testing} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Eric Allender, John Gouwar, Shuichi Hirahara, and Caleb Robelle. Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{allender_et_al:LIPIcs.ISAAC.2021.54, author = {Allender, Eric and Gouwar, John and Hirahara, Shuichi and Robelle, Caleb}, title = {{Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {54:1--54:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.54}, URN = {urn:nbn:de:0030-drops-154875}, doi = {10.4230/LIPIcs.ISAAC.2021.54}, annote = {Keywords: Kolmogorov Complexity, Interactive Proofs, Minimum Circuit Size Problem, Worst-case to Average-case Reductions} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Uma Girish, Ran Raz, and Wei Zhan. Quantum Logspace Algorithm for Powering Matrices with Bounded Norm. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 73:1-73:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{girish_et_al:LIPIcs.ICALP.2021.73, author = {Girish, Uma and Raz, Ran and Zhan, Wei}, title = {{Quantum Logspace Algorithm for Powering Matrices with Bounded Norm}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {73:1--73:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.73}, URN = {urn:nbn:de:0030-drops-141426}, doi = {10.4230/LIPIcs.ICALP.2021.73}, annote = {Keywords: BQL, Matrix Powering, Quantum Circuit, Reversible Computation} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, and Andrew Morgan. Minimum Circuit Size, Graph Isomorphism, and Related Problems. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{allender_et_al:LIPIcs.ITCS.2018.20, author = {Allender, Eric and Grochow, Joshua A. and van Melkebeek, Dieter and Moore, Cristopher and Morgan, Andrew}, title = {{Minimum Circuit Size, Graph Isomorphism, and Related Problems}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {20:1--20:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-060-6}, ISSN = {1868-8969}, year = {2018}, volume = {94}, editor = {Karlin, Anna R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.20}, URN = {urn:nbn:de:0030-drops-83455}, doi = {10.4230/LIPIcs.ITCS.2018.20}, annote = {Keywords: Reductions between NP-intermediate problems, Graph Isomorphism, Minimum Circuit Size Problem, time-bounded Kolmogorov complexity} }
Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)
Dieter van Melkebeek and Gautam Prakriya. Derandomizing Isolation in Space-Bounded Settings. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 5:1-5:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{vanmelkebeek_et_al:LIPIcs.CCC.2017.5, author = {van Melkebeek, Dieter and Prakriya, Gautam}, title = {{Derandomizing Isolation in Space-Bounded Settings}}, booktitle = {32nd Computational Complexity Conference (CCC 2017)}, pages = {5:1--5:32}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-040-8}, ISSN = {1868-8969}, year = {2017}, volume = {79}, editor = {O'Donnell, Ryan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.5}, URN = {urn:nbn:de:0030-drops-75297}, doi = {10.4230/LIPIcs.CCC.2017.5}, annote = {Keywords: Isolation lemma, derandomization, unambiguous nondeterminism, graph reachability, circuit certification} }
Published in: Dagstuhl Reports, Volume 1, Issue 3 (2011)
Martin Grohe, Michal Koucky, Rüdiger Reischik, and Dieter van Melkebeek. Computational Complexity of Discrete Problems (Dagstuhl Seminar 11121). In Dagstuhl Reports, Volume 1, Issue 3, pp. 42-66, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
@Article{grohe_et_al:DagRep.1.3.42, author = {Grohe, Martin and Koucky, Michal and Reischik, R\"{u}diger and van Melkebeek, Dieter}, title = {{Computational Complexity of Discrete Problems (Dagstuhl Seminar 11121)}}, pages = {42--66}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2011}, volume = {1}, number = {3}, editor = {Grohe, Martin and Koucky, Michal and Reischik, R\"{u}diger and van Melkebeek, Dieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.1.3.42}, URN = {urn:nbn:de:0030-drops-31935}, doi = {10.4230/DagRep.1.3.42}, annote = {Keywords: Discrete problems, computational complexity, Turing machines, Boolean circuits, quantum computing, communication and query complexity, extractors, pseudorandomness, derandomization, approximation, coding cryptography, algorithmic learning} }
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 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