default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDBibTeX records: Dieter van Melkebeek
@inproceedings{DBLP:conf/coco/MelkebeekS23,
author = {Dieter van Melkebeek and
Nicollas M. Sdroievski},
editor = {Amnon Ta{-}Shma},
title = {Instance-Wise Hardness Versus Randomness Tradeoffs for Arthur-Merlin
Protocols},
booktitle = {38th Computational Complexity Conference, {CCC} 2023, July 17-20,
2023, Warwick, {UK}},
series = {LIPIcs},
volume = {264},
pages = {17:1--17:36},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2023},
url = {https://doi.org/10.4230/LIPIcs.CCC.2023.17},
doi = {10.4230/LIPICS.CCC.2023.17},
timestamp = {Wed, 21 Aug 2024 22:46:00 +0200},
biburl = {https://dblp.org/rec/conf/coco/MelkebeekS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/fsttcs/MelkebeekS23,
author = {Dieter van Melkebeek and
Nicollas M. Sdroievski},
editor = {Patricia Bouyer and
Srikanth Srinivasan},
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, December 18-20, 2023,
{IIIT} Hyderabad, Telangana, India},
series = {LIPIcs},
volume = {284},
pages = {29:1--29:22},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2023},
url = {https://doi.org/10.4230/LIPIcs.FSTTCS.2023.29},
doi = {10.4230/LIPICS.FSTTCS.2023.29},
timestamp = {Wed, 21 Aug 2024 22:46:00 +0200},
biburl = {https://dblp.org/rec/conf/fsttcs/MelkebeekS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/HuMM23,
author = {Ivan Hu and
Dieter van Melkebeek and
Andrew Morgan},
editor = {Nikhil Bansal and
Viswanath Nagarajan},
title = {Query Complexity of Inversion Minimization on Trees},
booktitle = {Proceedings of the 2023 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2023, Florence, Italy, January 22-25, 2023},
pages = {2836--2866},
publisher = {{SIAM}},
year = {2023},
url = {https://doi.org/10.1137/1.9781611977554.ch107},
doi = {10.1137/1.9781611977554.CH107},
timestamp = {Fri, 17 Feb 2023 09:28:57 +0100},
biburl = {https://dblp.org/rec/conf/soda/HuMM23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/SdroievskiM23,
author = {Nicollas M. Sdroievski and
Dieter van Melkebeek},
title = {Instance-Wise Hardness versus Randomness Tradeoffs for Arthur-Merlin
Protocols},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR23-029}},
year = {2023},
url = {https://eccc.weizmann.ac.il/report/2023/029},
eprinttype = {ECCC},
eprint = {TR23-029},
timestamp = {Tue, 13 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/SdroievskiM23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/MelkebeekM22,
author = {Dieter van Melkebeek and
Andrew Morgan},
editor = {Mark Braverman},
title = {Polynomial Identity Testing via Evaluation of Rational Functions},
booktitle = {13th Innovations in Theoretical Computer Science Conference, {ITCS}
2022, January 31 - February 3, 2022, Berkeley, CA, {USA}},
series = {LIPIcs},
volume = {215},
pages = {119:1--119:24},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2022},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2022.119},
doi = {10.4230/LIPICS.ITCS.2022.119},
timestamp = {Wed, 21 Aug 2024 22:46:00 +0200},
biburl = {https://dblp.org/rec/conf/innovations/MelkebeekM22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2211-01062,
author = {Dieter van Melkebeek and
Andrew Morgan},
title = {Polynomial Identity Testing via Evaluation of Rational Functions},
journal = {CoRR},
volume = {abs/2211.01062},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2211.01062},
doi = {10.48550/ARXIV.2211.01062},
eprinttype = {arXiv},
eprint = {2211.01062},
timestamp = {Fri, 04 Nov 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2211-01062.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2211-12441,
author = {Ivan Hu and
Dieter van Melkebeek and
Andrew Morgan},
title = {Query Complexity of Inversion Minimization on Trees},
journal = {CoRR},
volume = {abs/2211.12441},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2211.12441},
doi = {10.48550/ARXIV.2211.12441},
eprinttype = {arXiv},
eprint = {2211.12441},
timestamp = {Thu, 24 Nov 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2211-12441.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/HuMM22,
author = {Ivan Hu and
Andrew Morgan and
Dieter van Melkebeek},
title = {Query Complexity of Inversion Minimization on Trees},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR22-158}},
year = {2022},
url = {https://eccc.weizmann.ac.il/report/2022/158},
eprinttype = {ECCC},
eprint = {TR22-158},
timestamp = {Fri, 10 Feb 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/eccc/HuMM22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/MelkebeekM22,
author = {Dieter van Melkebeek and
Andrew Morgan},
title = {Polynomial Identity Testing via Evaluation of Rational Functions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR22-115}},
year = {2022},
url = {https://eccc.weizmann.ac.il/report/2022/115},
eprinttype = {ECCC},
eprint = {TR22-115},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/MelkebeekM22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/MelkebeekP19,
author = {Dieter van Melkebeek and
Gautam Prakriya},
title = {Derandomizing Isolation in Space-Bounded Settings},
journal = {{SIAM} J. Comput.},
volume = {48},
number = {3},
pages = {979--1021},
year = {2019},
url = {https://doi.org/10.1137/17M1130538},
doi = {10.1137/17M1130538},
timestamp = {Wed, 24 Jul 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/MelkebeekP19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/AllenderGMMM18,
author = {Eric Allender and
Joshua A. Grochow and
Dieter van Melkebeek and
Cristopher Moore and
Andrew Morgan},
title = {Minimum Circuit Size, Graph Isomorphism, and Related Problems},
journal = {{SIAM} J. Comput.},
volume = {47},
number = {4},
pages = {1339--1372},
year = {2018},
url = {https://doi.org/10.1137/17M1157970},
doi = {10.1137/17M1157970},
timestamp = {Mon, 03 Jan 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/AllenderGMMM18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/AllenderGMMM18,
author = {Eric Allender and
Joshua A. Grochow and
Dieter van Melkebeek and
Cristopher Moore and
Andrew Morgan},
editor = {Anna R. Karlin},
title = {Minimum Circuit Size, Graph Isomorphism, and Related Problems},
booktitle = {9th Innovations in Theoretical Computer Science Conference, {ITCS}
2018, January 11-14, 2018, Cambridge, MA, {USA}},
series = {LIPIcs},
volume = {94},
pages = {20:1--20:20},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2018},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2018.20},
doi = {10.4230/LIPICS.ITCS.2018.20},
timestamp = {Mon, 03 Jan 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/innovations/AllenderGMMM18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/AydinliogluM17,
author = {Baris Aydinlioglu and
Dieter van Melkebeek},
title = {Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin
games},
journal = {Comput. Complex.},
volume = {26},
number = {1},
pages = {79--118},
year = {2017},
url = {https://doi.org/10.1007/s00037-014-0095-y},
doi = {10.1007/S00037-014-0095-Y},
timestamp = {Sun, 15 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cc/AydinliogluM17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/MelkebeekP17,
author = {Dieter van Melkebeek and
Gautam Prakriya},
editor = {Ryan O'Donnell},
title = {Derandomizing Isolation in Space-Bounded Settings},
booktitle = {32nd Computational Complexity Conference, {CCC} 2017, July 6-9, 2017,
Riga, Latvia},
series = {LIPIcs},
volume = {79},
pages = {5:1--5:32},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.CCC.2017.5},
doi = {10.4230/LIPICS.CCC.2017.5},
timestamp = {Thu, 02 Feb 2023 13:27:05 +0100},
biburl = {https://dblp.org/rec/conf/coco/MelkebeekP17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1710-09806,
author = {Eric Allender and
Joshua A. Grochow and
Dieter van Melkebeek and
Cristopher Moore and
Andrew Morgan},
title = {Minimum Circuit Size, Graph Isomorphism, and Related Problems},
journal = {CoRR},
volume = {abs/1710.09806},
year = {2017},
url = {http://arxiv.org/abs/1710.09806},
eprinttype = {arXiv},
eprint = {1710.09806},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1710-09806.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AllenderGMMM17,
author = {Eric Allender and
Joshua A. Grochow and
Dieter van Melkebeek and
Cristopher Moore and
Andrew Morgan},
title = {Minimum Circuit Size, Graph Isomorphism, and Related Problems},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR17-158}},
year = {2017},
url = {https://eccc.weizmann.ac.il/report/2017/158},
eprinttype = {ECCC},
eprint = {TR17-158},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AllenderGMMM17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/MelkebeekP17,
author = {Dieter van Melkebeek and
Gautam Prakriya},
title = {Derandomizing Isolation in Space-Bounded Settings},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR17-052}},
year = {2017},
url = {https://eccc.weizmann.ac.il/report/2017/052},
eprinttype = {ECCC},
eprint = {TR17-052},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/MelkebeekP17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/AndersonMV15,
author = {Matthew Anderson and
Dieter van Melkebeek and
Ilya Volkovich},
title = {Deterministic polynomial identity tests for multilinear bounded-read
formulae},
journal = {Comput. Complex.},
volume = {24},
number = {4},
pages = {695--776},
year = {2015},
url = {https://doi.org/10.1007/s00037-015-0097-4},
doi = {10.1007/S00037-015-0097-4},
timestamp = {Sun, 15 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cc/AndersonMV15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/DellM14,
author = {Holger Dell and
Dieter van Melkebeek},
title = {Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time
Hierarchy Collapses},
journal = {J. {ACM}},
volume = {61},
number = {4},
pages = {23:1--23:27},
year = {2014},
url = {https://doi.org/10.1145/2629620},
doi = {10.1145/2629620},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jacm/DellM14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/DellKMW13,
author = {Holger Dell and
Valentine Kabanets and
Dieter van Melkebeek and
Osamu Watanabe},
title = {Is Valiant-Vazirani's isolation probability improvable?},
journal = {Comput. Complex.},
volume = {22},
number = {2},
pages = {345--383},
year = {2013},
url = {https://doi.org/10.1007/s00037-013-0059-7},
doi = {10.1007/S00037-013-0059-7},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/cc/DellKMW13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/KinneMS12,
author = {Jeff Kinne and
Dieter van Melkebeek and
Ronen Shaltiel},
title = {Pseudorandom Generators, Typically-Correct Derandomization, and Circuit
Lower Bounds},
journal = {Comput. Complex.},
volume = {21},
number = {1},
pages = {3--61},
year = {2012},
url = {https://doi.org/10.1007/s00037-011-0019-z},
doi = {10.1007/S00037-011-0019-Z},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/cc/KinneMS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/EtessamiMPWV12,
author = {Kousha Etessami and
Dieter van Melkebeek and
Seth Pettie and
John Watrous and
Salil P. Vadhan},
title = {Special Section on the Forty-Third Annual {ACM} Symposium on Theory
of Computing {(STOC} 2011)},
journal = {{SIAM} J. Comput.},
volume = {41},
number = {5},
pages = {1233--1234},
year = {2012},
url = {https://doi.org/10.1137/12097324X},
doi = {10.1137/12097324X},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/EtessamiMPWV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/AndersonMSS12,
author = {Matthew Anderson and
Dieter van Melkebeek and
Nicole Schweikardt and
Luc Segoufin},
title = {Locality from Circuit Lower Bounds},
journal = {{SIAM} J. Comput.},
volume = {41},
number = {6},
pages = {1481--1523},
year = {2012},
url = {https://doi.org/10.1137/110856873},
doi = {10.1137/110856873},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/AndersonMSS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/KarakostasKM12,
author = {George Karakostas and
Jeff Kinne and
Dieter van Melkebeek},
title = {On derandomization and average-case complexity of monotone functions},
journal = {Theor. Comput. Sci.},
volume = {434},
pages = {35--44},
year = {2012},
url = {https://doi.org/10.1016/j.tcs.2012.02.017},
doi = {10.1016/J.TCS.2012.02.017},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/tcs/KarakostasKM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/MelkebeekW12,
author = {Dieter van Melkebeek and
Thomas Watson},
title = {Time-Space Efficient Simulations of Quantum Computations},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {1--51},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a001},
doi = {10.4086/TOC.2012.V008A001},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/MelkebeekW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/DellKMW12,
author = {Holger Dell and
Valentine Kabanets and
Dieter van Melkebeek and
Osamu Watanabe},
title = {Is Valiant-Vazirani's Isolation Probability Improvable?},
booktitle = {Proceedings of the 27th Conference on Computational Complexity, {CCC}
2012, Porto, Portugal, June 26-29, 2012},
pages = {10--20},
publisher = {{IEEE} Computer Society},
year = {2012},
url = {https://doi.org/10.1109/CCC.2012.22},
doi = {10.1109/CCC.2012.22},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/DellKMW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/AydinliogluM12,
author = {Baris Aydinlioglu and
Dieter van Melkebeek},
title = {Nondeterministic Circuit Lower Bounds from Mildly De-randomizing Arthur-Merlin
Games},
booktitle = {Proceedings of the 27th Conference on Computational Complexity, {CCC}
2012, Porto, Portugal, June 26-29, 2012},
pages = {269--279},
publisher = {{IEEE} Computer Society},
year = {2012},
url = {https://doi.org/10.1109/CCC.2012.32},
doi = {10.1109/CCC.2012.32},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/AydinliogluM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AydinliogluM12,
author = {Baris Aydinlioglu and
Dieter van Melkebeek},
title = {Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin
Games},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-080}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/080},
eprinttype = {ECCC},
eprint = {TR12-080},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AydinliogluM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/Melkebeek11,
author = {Dieter van Melkebeek},
title = {Special Issue "Conference on Computational Complexity 2010"
Guest Editor's Foreword},
journal = {Comput. Complex.},
volume = {20},
number = {2},
pages = {173--175},
year = {2011},
url = {https://doi.org/10.1007/s00037-011-0008-2},
doi = {10.1007/S00037-011-0008-2},
timestamp = {Sun, 15 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cc/Melkebeek11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jco/DiehlMW11,
author = {Scott Diehl and
Dieter van Melkebeek and
Ryan Williams},
title = {An improved time-space lower bound for tautologies},
journal = {J. Comb. Optim.},
volume = {22},
number = {3},
pages = {325--338},
year = {2011},
url = {https://doi.org/10.1007/s10878-009-9286-x},
doi = {10.1007/S10878-009-9286-X},
timestamp = {Fri, 30 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jco/DiehlMW11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AaronsonM11,
author = {Scott Aaronson and
Dieter van Melkebeek},
title = {On Circuit Lower Bounds from Derandomization},
journal = {Theory Comput.},
volume = {7},
number = {1},
pages = {177--184},
year = {2011},
url = {https://doi.org/10.4086/toc.2011.v007a012},
doi = {10.4086/TOC.2011.V007A012},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/AaronsonM11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/AndersonMV11,
author = {Matthew Anderson and
Dieter van Melkebeek and
Ilya Volkovich},
title = {Derandomizing Polynomial Identity Testing for Multilinear Constant-Read
Formulae},
booktitle = {Proceedings of the 26th Annual {IEEE} Conference on Computational
Complexity, {CCC} 2011, San Jose, California, USA, June 8-10, 2011},
pages = {273--282},
publisher = {{IEEE} Computer Society},
year = {2011},
url = {https://doi.org/10.1109/CCC.2011.18},
doi = {10.1109/CCC.2011.18},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/coco/AndersonMV11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/AndersonMSS11,
author = {Matthew Anderson and
Dieter van Melkebeek and
Nicole Schweikardt and
Luc Segoufin},
editor = {Luca Aceto and
Monika Henzinger and
Jir{\'{\i}} Sgall},
title = {Locality of Queries Definable in Invariant First-Order Logic with
Arbitrary Built-in Predicates},
booktitle = {Automata, Languages and Programming - 38th International Colloquium,
{ICALP} 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part
{II}},
series = {Lecture Notes in Computer Science},
volume = {6756},
pages = {368--379},
publisher = {Springer},
year = {2011},
url = {https://doi.org/10.1007/978-3-642-22012-8\_29},
doi = {10.1007/978-3-642-22012-8\_29},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/AndersonMSS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/dagstuhl-reports/GroheKRM11,
author = {Martin Grohe and
Michal Kouck{\'{y}} and
R{\"{u}}diger Reischuk and
Dieter van Melkebeek},
title = {Computational Complexity of Discrete Problems (Dagstuhl Seminar 11121)},
journal = {Dagstuhl Reports},
volume = {1},
number = {3},
pages = {42--66},
year = {2011},
url = {https://doi.org/10.4230/DagRep.1.3.42},
doi = {10.4230/DAGREP.1.3.42},
timestamp = {Thu, 02 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/dagstuhl-reports/GroheKRM11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AndersonMSS11,
author = {Matthew Anderson and
Dieter van Melkebeek and
Nicole Schweikardt and
Luc Segoufin},
title = {Locality from Circuit Lower Bounds},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR11-158}},
year = {2011},
url = {https://eccc.weizmann.ac.il/report/2011/158},
eprinttype = {ECCC},
eprint = {TR11-158},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AndersonMSS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/KinneM10,
author = {Jeff Kinne and
Dieter van Melkebeek},
title = {Space Hierarchy Results for Randomized and other Semantic Models},
journal = {Comput. Complex.},
volume = {19},
number = {3},
pages = {423--475},
year = {2010},
url = {https://doi.org/10.1007/s00037-009-0277-1},
doi = {10.1007/S00037-009-0277-1},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/cc/KinneM10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DellM10,
author = {Holger Dell and
Dieter van Melkebeek},
editor = {Leonard J. Schulman},
title = {Satisfiability allows no nontrivial sparsification unless the polynomial-time
hierarchy collapses},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {251--260},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806725},
doi = {10.1145/1806689.1806725},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/DellM10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AaronsonABHM10,
author = {Scott Aaronson and
Baris Aydinlioglu and
Harry Buhrman and
John M. Hitchcock and
Dieter van Melkebeek},
title = {A note on exponential circuit lower bounds from derandomizing Arthur-Merlin
games},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-174}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/174},
eprinttype = {ECCC},
eprint = {TR10-174},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AaronsonABHM10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AaronsonM10,
author = {Scott Aaronson and
Dieter van Melkebeek},
title = {A note on circuit lower bounds from derandomization},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-105}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/105},
eprinttype = {ECCC},
eprint = {TR10-105},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AaronsonM10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AndersonMV10,
author = {Matthew Anderson and
Dieter van Melkebeek and
Ilya Volkovich},
title = {Derandomizing Polynomial Identity Testing for Multilinear Constant-Read
Formulae},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-188}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/188},
eprinttype = {ECCC},
eprint = {TR10-188},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AndersonMV10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KinneMS10,
author = {Jeff Kinne and
Dieter van Melkebeek and
Ronen Shaltiel},
title = {Pseudorandom Generators, Typically-Correct Derandomization, and Circuit
Lower Bounds},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-129}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/129},
eprinttype = {ECCC},
eprint = {TR10-129},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KinneMS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/MelkebeekD10,
author = {Dieter van Melkebeek and
Holger Dell},
title = {Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time
Hierarchy Collapses},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-038}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/038},
eprinttype = {ECCC},
eprint = {TR10-038},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/MelkebeekD10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/MelkebeekW10,
author = {Dieter van Melkebeek and
Thomas Watson},
title = {Time-Space Efficient Simulations of Quantum Computations},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-147}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/147},
eprinttype = {ECCC},
eprint = {TR10-147},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/MelkebeekW10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/AaronsonGKMMS09,
author = {Scott Aaronson and
Sudipto Guha and
Jon M. Kleinberg and
Frank McSherry and
Dieter van Melkebeek and
Amit Sahai},
title = {Special Issue On The Thirty-Eighth Annual {ACM} Symposium On Theory
Of Computing {(STOC} 2006)},
journal = {{SIAM} J. Comput.},
volume = {39},
number = {1},
pages = {vii},
year = {2009},
url = {https://doi.org/10.1137/SMJCAT000039000001000vii000001},
doi = {10.1137/SMJCAT000039000001000VII000001},
timestamp = {Mon, 13 Mar 2017 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/AaronsonGKMMS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/KinneMS09,
author = {Jeff Kinne and
Dieter van Melkebeek and
Ronen Shaltiel},
editor = {Irit Dinur and
Klaus Jansen and
Joseph Naor and
Jos{\'{e}} D. P. Rolim},
title = {Pseudorandom Generators and Typically-Correct Derandomization},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, 12th International Workshop, {APPROX} 2009, and 13th
International Workshop, {RANDOM} 2009, Berkeley, CA, USA, August 21-23,
2009. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {5687},
pages = {574--587},
publisher = {Springer},
year = {2009},
url = {https://doi.org/10.1007/978-3-642-03685-9\_43},
doi = {10.1007/978-3-642-03685-9\_43},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/approx/KinneMS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoon/DiehlMW09,
author = {Scott Diehl and
Dieter van Melkebeek and
Ryan Williams},
editor = {Hung Q. Ngo},
title = {An Improved Time-Space Lower Bound for Tautologies},
booktitle = {Computing and Combinatorics, 15th Annual International Conference,
{COCOON} 2009, Niagara Falls, NY, USA, July 13-15, 2009, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {5609},
pages = {429--438},
publisher = {Springer},
year = {2009},
url = {https://doi.org/10.1007/978-3-642-02882-3\_43},
doi = {10.1007/978-3-642-02882-3\_43},
timestamp = {Tue, 14 May 2019 10:00:35 +0200},
biburl = {https://dblp.org/rec/conf/cocoon/DiehlMW09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dagstuhl/DellM09,
author = {Holger Dell and
Dieter van Melkebeek},
editor = {Erik D. Demaine and
MohammadTaghi Hajiaghayi and
D{\'{a}}niel Marx},
title = {Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time
Hierarchy Collapses},
booktitle = {Parameterized complexity and approximation algorithms, 13.12. - 17.12.2009},
series = {Dagstuhl Seminar Proceedings},
volume = {09511},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik, Germany},
year = {2009},
url = {http://drops.dagstuhl.de/opus/volltexte/2010/2504/},
timestamp = {Thu, 10 Jun 2021 13:02:08 +0200},
biburl = {https://dblp.org/rec/conf/dagstuhl/DellM09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/KinneM08,
author = {Jeff Kinne and
Dieter van Melkebeek},
editor = {Susanne Albers and
Pascal Weil},
title = {Space Hierarchy Results for Randomized Models},
booktitle = {{STACS} 2008, 25th Annual Symposium on Theoretical Aspects of Computer
Science, Bordeaux, France, February 21-23, 2008, Proceedings},
series = {LIPIcs},
volume = {1},
pages = {433--444},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik, Germany},
year = {2008},
url = {https://doi.org/10.4230/LIPIcs.STACS.2008.1363},
doi = {10.4230/LIPICS.STACS.2008.1363},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stacs/KinneM08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/dagstuhl/2008P8381,
editor = {Peter Bro Miltersen and
R{\"{u}}diger Reischuk and
Georg Schnitger and
Dieter van Melkebeek},
title = {Computational Complexity of Discrete Problems, 14.09. - 19.09.2008},
series = {Dagstuhl Seminar Proceedings},
volume = {08381},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik, Germany},
year = {2008},
url = {http://drops.dagstuhl.de/portals/08381/},
timestamp = {Thu, 10 Jun 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/dagstuhl/2008P8381.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dagstuhl/MiltersenRSM08,
author = {Peter Bro Miltersen and
R{\"{u}}diger Reischuk and
Georg Schnitger and
Dieter van Melkebeek},
editor = {Peter Bro Miltersen and
R{\"{u}}diger Reischuk and
Georg Schnitger and
Dieter van Melkebeek},
title = {08381 Abstracts Collection - Computational Complexity of Discrete
Problems},
booktitle = {Computational Complexity of Discrete Problems, 14.09. - 19.09.2008},
series = {Dagstuhl Seminar Proceedings},
volume = {08381},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik, Germany},
year = {2008},
url = {http://drops.dagstuhl.de/opus/volltexte/2008/1779/},
timestamp = {Thu, 10 Jun 2021 13:02:05 +0200},
biburl = {https://dblp.org/rec/conf/dagstuhl/MiltersenRSM08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dagstuhl/MiltersenRSM08a,
author = {Peter Bro Miltersen and
R{\"{u}}diger Reischuk and
Georg Schnitger and
Dieter van Melkebeek},
editor = {Peter Bro Miltersen and
R{\"{u}}diger Reischuk and
Georg Schnitger and
Dieter van Melkebeek},
title = {08381 Executive Summary - Computational Complexity of Discrete Problems},
booktitle = {Computational Complexity of Discrete Problems, 14.09. - 19.09.2008},
series = {Dagstuhl Seminar Proceedings},
volume = {08381},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik, Germany},
year = {2008},
url = {http://drops.dagstuhl.de/opus/volltexte/2008/1778/},
timestamp = {Thu, 23 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/dagstuhl/MiltersenRSM08a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/MelkebeekW08,
author = {Dieter van Melkebeek and
Thomas Watson},
title = {A Quantum Time-Space Lower Bound for the Counting Hierarchy},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR08-017}},
year = {2008},
url = {https://eccc.weizmann.ac.il/eccc-reports/2008/TR08-017/index.html},
eprinttype = {ECCC},
eprint = {TR08-017},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/MelkebeekW08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/MelkebeekP07,
author = {Dieter van Melkebeek and
Konstantin Pervyshev},
title = {A Generic Time Hierarchy with One Bit of Advice},
journal = {Comput. Complex.},
volume = {16},
number = {2},
pages = {139--179},
year = {2007},
url = {https://doi.org/10.1007/s00037-007-0227-8},
doi = {10.1007/S00037-007-0227-8},
timestamp = {Sun, 15 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cc/MelkebeekP07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KinneM07,
author = {Jeff Kinne and
Dieter van Melkebeek},
title = {Space Hierarchy Results for Randomized and Other Semantic Models},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR07-134}},
year = {2007},
url = {https://eccc.weizmann.ac.il/eccc-reports/2007/TR07-134/index.html},
eprinttype = {ECCC},
eprint = {TR07-134},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KinneM07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Melkebeek07,
author = {Dieter van Melkebeek},
title = {A Survey of Lower Bounds for Satisfiability and Related Problems},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR07-099}},
year = {2007},
url = {https://eccc.weizmann.ac.il/eccc-reports/2007/TR07-099/index.html},
eprinttype = {ECCC},
eprint = {TR07-099},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Melkebeek07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/fttcs/Melkebeek06,
author = {Dieter van Melkebeek},
title = {A Survey of Lower Bounds for Satisfiability and Related Problems},
journal = {Found. Trends Theor. Comput. Sci.},
volume = {2},
number = {3},
pages = {197--303},
year = {2006},
url = {https://doi.org/10.1561/0400000012},
doi = {10.1561/0400000012},
timestamp = {Thu, 20 Aug 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/fttcs/Melkebeek06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/CaiCM06,
author = {Jin{-}yi Cai and
Venkatesan T. Chakaravarthy and
Dieter van Melkebeek},
title = {Time-Space Tradeoff in Derandomizing Probabilistic Logspace},
journal = {Theory Comput. Syst.},
volume = {39},
number = {1},
pages = {189--208},
year = {2006},
url = {https://doi.org/10.1007/s00224-005-1264-9},
doi = {10.1007/S00224-005-1264-9},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mst/CaiCM06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/AllenderBKMR06,
author = {Eric Allender and
Harry Buhrman and
Michal Kouck{\'{y}} and
Dieter van Melkebeek and
Detlef Ronneburger},
title = {Power from Random Strings},
journal = {{SIAM} J. Comput.},
volume = {35},
number = {6},
pages = {1467--1493},
year = {2006},
url = {https://doi.org/10.1137/050628994},
doi = {10.1137/050628994},
timestamp = {Thu, 02 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/AllenderBKMR06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/DiehlM06,
author = {Scott Diehl and
Dieter van Melkebeek},
title = {Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized
Machines},
journal = {{SIAM} J. Comput.},
volume = {36},
number = {3},
pages = {563--594},
year = {2006},
url = {https://doi.org/10.1137/050642228},
doi = {10.1137/050642228},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/DiehlM06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/AntunesFMV06,
author = {Luis Antunes and
Lance Fortnow and
Dieter van Melkebeek and
N. V. Vinodchandran},
title = {Computational depth: Concept and applications},
journal = {Theor. Comput. Sci.},
volume = {354},
number = {3},
pages = {391--404},
year = {2006},
url = {https://doi.org/10.1016/j.tcs.2005.11.033},
doi = {10.1016/J.TCS.2005.11.033},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/AntunesFMV06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/MelkebeekP06,
author = {Dieter van Melkebeek and
Konstantin Pervyshev},
title = {A Generic Time Hierarchy for Semantic Models with One Bit of Advice},
booktitle = {21st Annual {IEEE} Conference on Computational Complexity {(CCC} 2006),
16-20 July 2006, Prague, Czech Republic},
pages = {129--144},
publisher = {{IEEE} Computer Society},
year = {2006},
url = {https://doi.org/10.1109/CCC.2006.7},
doi = {10.1109/CCC.2006.7},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/MelkebeekP06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/dagstuhl/2006P6111,
editor = {Matthias Krause and
Pavel Pudl{\'{a}}k and
R{\"{u}}diger Reischuk and
Dieter van Melkebeek},
title = {Complexity of Boolean Functions, 12.03. - 17.03.2006},
series = {Dagstuhl Seminar Proceedings},
volume = {06111},
publisher = {Internationales Begegnungs- und Forschungszentrum fuer Informatik
(IBFI), Schloss Dagstuhl, Germany},
year = {2006},
url = {http://drops.dagstuhl.de/portals/06111/},
timestamp = {Thu, 10 Jun 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/dagstuhl/2006P6111.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dagstuhl/DiehlM06,
author = {Scott Diehl and
Dieter van Melkebeek},
editor = {Matthias Krause and
Pavel Pudl{\'{a}}k and
R{\"{u}}diger Reischuk and
Dieter van Melkebeek},
title = {Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized
Machines},
booktitle = {Complexity of Boolean Functions, 12.03. - 17.03.2006},
series = {Dagstuhl Seminar Proceedings},
volume = {06111},
publisher = {Internationales Begegnungs- und Forschungszentrum fuer Informatik
(IBFI), Schloss Dagstuhl, Germany},
year = {2006},
url = {http://drops.dagstuhl.de/opus/volltexte/2006/605},
timestamp = {Thu, 10 Jun 2021 13:02:07 +0200},
biburl = {https://dblp.org/rec/conf/dagstuhl/DiehlM06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dagstuhl/KrauseMPR06,
author = {Matthias Krause and
Dieter van Melkebeek and
Pavel Pudl{\'{a}}k and
R{\"{u}}diger Reischuk},
editor = {Matthias Krause and
Pavel Pudl{\'{a}}k and
R{\"{u}}diger Reischuk and
Dieter van Melkebeek},
title = {06111 Executive Summary -- Complexity of Boolean Functions},
booktitle = {Complexity of Boolean Functions, 12.03. - 17.03.2006},
series = {Dagstuhl Seminar Proceedings},
volume = {06111},
publisher = {Internationales Begegnungs- und Forschungszentrum fuer Informatik
(IBFI), Schloss Dagstuhl, Germany},
year = {2006},
url = {http://drops.dagstuhl.de/opus/volltexte/2006/840},
timestamp = {Thu, 23 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/dagstuhl/KrauseMPR06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dagstuhl/KrausePRM06,
author = {Matthias Krause and
Pavel Pudl{\'{a}}k and
R{\"{u}}diger Reischuk and
Dieter van Melkebeek},
editor = {Matthias Krause and
Pavel Pudl{\'{a}}k and
R{\"{u}}diger Reischuk and
Dieter van Melkebeek},
title = {06111 Abstracts Collection -- Complexity of Boolean Functions},
booktitle = {Complexity of Boolean Functions, 12.03. - 17.03.2006},
series = {Dagstuhl Seminar Proceedings},
volume = {06111},
publisher = {Internationales Begegnungs- und Forschungszentrum fuer Informatik
(IBFI), Schloss Dagstuhl, Germany},
year = {2006},
url = {http://drops.dagstuhl.de/opus/volltexte/2006/759},
timestamp = {Thu, 23 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/dagstuhl/KrausePRM06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dagstuhl/MelkebeekP06,
author = {Dieter van Melkebeek and
Konstantin Pervyshev},
editor = {Matthias Krause and
Pavel Pudl{\'{a}}k and
R{\"{u}}diger Reischuk and
Dieter van Melkebeek},
title = {A Generic Time Hierarchy for Semantic Models With One Bit of Advice},
booktitle = {Complexity of Boolean Functions, 12.03. - 17.03.2006},
series = {Dagstuhl Seminar Proceedings},
volume = {06111},
publisher = {Internationales Begegnungs- und Forschungszentrum fuer Informatik
(IBFI), Schloss Dagstuhl, Germany},
year = {2006},
url = {http://drops.dagstuhl.de/opus/volltexte/2006/615},
timestamp = {Thu, 23 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/dagstuhl/MelkebeekP06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/BuhrmanLM05,
author = {Harry Buhrman and
Troy Lee and
Dieter van Melkebeek},
title = {Language compression and pseudorandom generators},
journal = {Comput. Complex.},
volume = {14},
number = {3},
pages = {228--255},
year = {2005},
url = {https://doi.org/10.1007/s00037-005-0199-5},
doi = {10.1007/S00037-005-0199-5},
timestamp = {Sun, 15 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cc/BuhrmanLM05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/FortnowLMV05,
author = {Lance Fortnow and
Richard J. Lipton and
Dieter van Melkebeek and
Anastasios Viglas},
title = {Time-space lower bounds for satisfiability},
journal = {J. {ACM}},
volume = {52},
number = {6},
pages = {835--865},
year = {2005},
url = {https://doi.org/10.1145/1101821.1101822},
doi = {10.1145/1101821.1101822},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jacm/FortnowLMV05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/MelkebeekS05,
author = {Dieter van Melkebeek and
Rahul Santhanam},
title = {Holographic Proofs and Derandmization},
journal = {{SIAM} J. Comput.},
volume = {35},
number = {1},
pages = {59--90},
year = {2005},
url = {https://doi.org/10.1137/S0097539703438629},
doi = {10.1137/S0097539703438629},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/MelkebeekS05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/MelkebeekR05,
author = {Dieter van Melkebeek and
Ran Raz},
title = {A time lower bound for satisfiability},
journal = {Theor. Comput. Sci.},
volume = {348},
number = {2-3},
pages = {311--320},
year = {2005},
url = {https://doi.org/10.1016/j.tcs.2005.09.020},
doi = {10.1016/J.TCS.2005.09.020},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/tcs/MelkebeekR05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/DiehlM05,
author = {Scott Diehl and
Dieter van Melkebeek},
editor = {Lu{\'{\i}}s Caires and
Giuseppe F. Italiano and
Lu{\'{\i}}s Monteiro and
Catuscia Palamidessi and
Moti Yung},
title = {Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized
Machines},
booktitle = {Automata, Languages and Programming, 32nd International Colloquium,
{ICALP} 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3580},
pages = {982--993},
publisher = {Springer},
year = {2005},
url = {https://doi.org/10.1007/11523468\_79},
doi = {10.1007/11523468\_79},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/DiehlM05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR05-111,
author = {Dieter van Melkebeek and
Konstantin Pervyshev},
title = {A Generic Time Hierarchy for Semantic Models With One Bit of Advice},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR05-111}},
year = {2005},
url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-111/index.html},
eprinttype = {ECCC},
eprint = {TR05-111},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-111.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/BuhrmanLM04,
author = {Harry Buhrman and
Troy Lee and
Dieter van Melkebeek},
title = {Language Compression and Pseudorandom Generators},
booktitle = {19th Annual {IEEE} Conference on Computational Complexity {(CCC} 2004),
21-24 June 2004, Amherst, MA, {USA}},
pages = {15--28},
publisher = {{IEEE} Computer Society},
year = {2004},
url = {https://doi.org/10.1109/CCC.2004.1313772},
doi = {10.1109/CCC.2004.1313772},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/BuhrmanLM04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/MelkebeekR04,
author = {Dieter van Melkebeek and
Ran Raz},
editor = {Josep D{\'{\i}}az and
Juhani Karhum{\"{a}}ki and
Arto Lepist{\"{o}} and
Donald Sannella},
title = {A Time Lower Bound for Satisfiability},
booktitle = {Automata, Languages and Programming: 31st International Colloquium,
{ICALP} 2004, Turku, Finland, July 12-16, 2004. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3142},
pages = {971--982},
publisher = {Springer},
year = {2004},
url = {https://doi.org/10.1007/978-3-540-27836-8\_81},
doi = {10.1007/978-3-540-27836-8\_81},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/MelkebeekR04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/CaiCM04,
author = {Jin{-}yi Cai and
Venkatesan T. Chakaravarthy and
Dieter van Melkebeek},
editor = {Volker Diekert and
Michel Habib},
title = {Time-Space Tradeoff in Derandomizing Probabilistic Logspace},
booktitle = {{STACS} 2004, 21st Annual Symposium on Theoretical Aspects of Computer
Science, Montpellier, France, March 25-27, 2004, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2996},
pages = {571--583},
publisher = {Springer},
year = {2004},
url = {https://doi.org/10.1007/978-3-540-24749-4\_50},
doi = {10.1007/978-3-540-24749-4\_50},
timestamp = {Tue, 14 May 2019 10:00:48 +0200},
biburl = {https://dblp.org/rec/conf/stacs/CaiCM04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-002,
author = {Troy Lee and
Dieter van Melkebeek and
Harry Buhrman},
title = {Language Compression and Pseudorandom Generators},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-002}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-002/index.html},
eprinttype = {ECCC},
eprint = {TR04-002},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-002.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/SanthanamM03,
author = {Rahul Santhanam and
Dieter van Melkebeek},
title = {Holographic Proofs and Derandomization},
booktitle = {18th Annual {IEEE} Conference on Computational Complexity (Complexity
2003), 7-10 July 2003, Aarhus, Denmark},
pages = {269--283},
publisher = {{IEEE} Computer Society},
year = {2003},
url = {https://doi.ieeecomputersociety.org/10.1109/COMPLEXITY.2003.10000},
doi = {10.1109/COMPLEXITY.2003.10000},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/SanthanamM03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/HayesKM02,
author = {Thomas P. Hayes and
Samuel Kutin and
Dieter van Melkebeek},
title = {The Quantum Black-Box Complexity of Majority},
journal = {Algorithmica},
volume = {34},
number = {4},
pages = {480--501},
year = {2002},
url = {https://doi.org/10.1007/s00453-002-0981-6},
doi = {10.1007/S00453-002-0981-6},
timestamp = {Wed, 17 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/algorithmica/HayesKM02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/KlivansM02,
author = {Adam R. Klivans and
Dieter van Melkebeek},
title = {Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time
Hierarchy Collapses},
journal = {{SIAM} J. Comput.},
volume = {31},
number = {5},
pages = {1501--1526},
year = {2002},
url = {https://doi.org/10.1137/S0097539700389652},
doi = {10.1137/S0097539700389652},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/KlivansM02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AllenderBKMR02,
author = {Eric Allender and
Harry Buhrman and
Michal Kouck{\'{y}} and
Dieter van Melkebeek and
Detlef Ronneburger},
title = {Power from Random Strings},
booktitle = {43rd Symposium on Foundations of Computer Science {(FOCS} 2002), 16-19
November 2002, Vancouver, BC, Canada, Proceedings},
pages = {669--678},
publisher = {{IEEE} Computer Society},
year = {2002},
url = {https://doi.org/10.1109/SFCS.2002.1181992},
doi = {10.1109/SFCS.2002.1181992},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AllenderBKMR02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR02-028,
author = {Eric Allender and
Harry Buhrman and
Michal Kouck{\'{y}} and
Detlef Ronneburger and
Dieter van Melkebeek},
title = {Power from Random Strings},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR02-028}},
year = {2002},
url = {https://eccc.weizmann.ac.il/eccc-reports/2002/TR02-028/index.html},
eprinttype = {ECCC},
eprint = {TR02-028},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR02-028.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eatcs/Melkebeek01,
author = {Dieter van Melkebeek},
title = {The Computational Complexity Column Time-Space Lower Bounds for Satisfiability},
journal = {Bull. {EATCS}},
volume = {73},
pages = {57--77},
year = {2001},
timestamp = {Thu, 18 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eatcs/Melkebeek01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/AntunesFM01,
author = {Luis Antunes and
Lance Fortnow and
Dieter van Melkebeek},
title = {Computational Depth},
booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational
Complexity, Chicago, Illinois, USA, June 18-21, 2001},
pages = {266--273},
publisher = {{IEEE} Computer Society},
year = {2001},
url = {https://doi.org/10.1109/CCC.2001.933893},
doi = {10.1109/CCC.2001.933893},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/AntunesFM01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@book{DBLP:books/sp/Melkebeek00,
author = {Dieter van Melkebeek},
title = {Randomness and Completeness in Computational Complexity},
series = {Lecture Notes in Computer Science},
volume = {1950},
publisher = {Springer},
year = {2000},
url = {https://doi.org/10.1007/3-540-44545-5},
doi = {10.1007/3-540-44545-5},
isbn = {3-540-41492-4},
timestamp = {Tue, 14 May 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/books/sp/Melkebeek00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/BuhrmanFMT00,
author = {Harry Buhrman and
Lance Fortnow and
Dieter van Melkebeek and
Leen Torenvliet},
title = {Separating Complexity Classes Using Autoreducibility},
journal = {{SIAM} J. Comput.},
volume = {29},
number = {5},
pages = {1497--1520},
year = {2000},
url = {https://doi.org/10.1137/S0097539798334736},
doi = {10.1137/S0097539798334736},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/BuhrmanFMT00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/BuhrmanMRSS00,
author = {Harry Buhrman and
Dieter van Melkebeek and
Kenneth W. Regan and
D. Sivakumar and
Martin Strauss},
title = {A Generalization of Resource-Bounded Measure, with Application to
the {BPP} vs. {EXP} Problem},
journal = {{SIAM} J. Comput.},
volume = {30},
number = {2},
pages = {576--601},
year = {2000},
url = {https://doi.org/10.1137/S0097539798343891},
doi = {10.1137/S0097539798343891},
timestamp = {Tue, 19 Dec 2017 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/BuhrmanMRSS00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/Melkebeek00,
author = {Dieter van Melkebeek},
title = {The zero-one law holds for {BPP}},
journal = {Theor. Comput. Sci.},
volume = {244},
number = {1-2},
pages = {283--288},
year = {2000},
url = {https://doi.org/10.1016/S0304-3975(00)00191-2},
doi = {10.1016/S0304-3975(00)00191-2},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/Melkebeek00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/FortnowM00,
author = {Lance Fortnow and
Dieter van Melkebeek},
title = {Time-Space Tradeoffs for Nondeterministic Computation},
booktitle = {Proceedings of the 15th Annual {IEEE} Conference on Computational
Complexity, Florence, Italy, July 4-7, 2000},
pages = {2--13},
publisher = {{IEEE} Computer Society},
year = {2000},
url = {https://doi.org/10.1109/CCC.2000.856730},
doi = {10.1109/CCC.2000.856730},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/FortnowM00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/BuhrmanFFM00,
author = {Harry Buhrman and
Stephen A. Fenner and
Lance Fortnow and
Dieter van Melkebeek},
editor = {Horst Reichel and
Sophie Tison},
title = {Optimal Proof Systems and Sparse Sets},
booktitle = {{STACS} 2000, 17th Annual Symposium on Theoretical Aspects of Computer
Science, Lille, France, February 2000, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1770},
pages = {407--418},
publisher = {Springer},
year = {2000},
url = {https://doi.org/10.1007/3-540-46541-3\_34},
doi = {10.1007/3-540-46541-3\_34},
timestamp = {Tue, 14 May 2019 10:00:48 +0200},
biburl = {https://dblp.org/rec/conf/stacs/BuhrmanFFM00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR00-028,
author = {Lance Fortnow and
Dieter van Melkebeek},
title = {Time-Space Tradeoffs for Nondeterministic Computation},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR00-028}},
year = {2000},
url = {https://eccc.weizmann.ac.il/eccc-reports/2000/TR00-028/index.html},
eprinttype = {ECCC},
eprint = {TR00-028},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR00-028.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/BuhrmanM99,
author = {Harry Buhrman and
Dieter van Melkebeek},
title = {Hard Sets Are Hard to Find},
journal = {J. Comput. Syst. Sci.},
volume = {59},
number = {2},
pages = {327--345},
year = {1999},
url = {https://doi.org/10.1006/jcss.1999.1650},
doi = {10.1006/JCSS.1999.1650},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/BuhrmanM99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KlivansM99,
author = {Adam R. Klivans and
Dieter van Melkebeek},
editor = {Jeffrey Scott Vitter and
Lawrence L. Larmore and
Frank Thomson Leighton},
title = {Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time
Hierarchy Collapses},
booktitle = {Proceedings of the Thirty-First Annual {ACM} Symposium on Theory of
Computing, May 1-4, 1999, Atlanta, Georgia, {USA}},
pages = {659--667},
publisher = {{ACM}},
year = {1999},
url = {https://doi.org/10.1145/301250.301428},
doi = {10.1145/301250.301428},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KlivansM99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/Melkebeek98,
author = {Dieter van Melkebeek},
title = {Deterministic and Randomized Bounded Truth-Table Reductions of P,
NL, and {L} to Sparse Sets},
journal = {J. Comput. Syst. Sci.},
volume = {57},
number = {2},
pages = {213--232},
year = {1998},
url = {https://doi.org/10.1006/jcss.1998.1589},
doi = {10.1006/JCSS.1998.1589},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/Melkebeek98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/BuhrmanM98,
author = {Harry Buhrman and
Dieter van Melkebeek},
title = {Hard Sets are Hard to Find},
booktitle = {Proceedings of the 13th Annual {IEEE} Conference on Computational
Complexity, Buffalo, New York, USA, June 15-18, 1998},
pages = {170--181},
publisher = {{IEEE} Computer Society},
year = {1998},
url = {https://doi.org/10.1109/CCC.1998.694602},
doi = {10.1109/CCC.1998.694602},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/BuhrmanM98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/BuhrmanMRSS98,
author = {Harry Buhrman and
Dieter van Melkebeek and
Kenneth W. Regan and
D. Sivakumar and
Martin Strauss},
editor = {Michel Morvan and
Christoph Meinel and
Daniel Krob},
title = {A Generalization of Resource-Bounded Measure, With an Application
(Extended Abstract)},
booktitle = {{STACS} 98, 15th Annual Symposium on Theoretical Aspects of Computer
Science, Paris, France, February 25-27, 1998, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1373},
pages = {161--171},
publisher = {Springer},
year = {1998},
url = {https://doi.org/10.1007/BFb0028558},
doi = {10.1007/BFB0028558},
timestamp = {Tue, 14 May 2019 10:00:48 +0200},
biburl = {https://dblp.org/rec/conf/stacs/BuhrmanMRSS98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR98-058,
author = {Harry Buhrman and
Dieter van Melkebeek and
Kenneth W. Regan and
Martin Strauss and
D. Sivakumar},
title = {A Generalization of Resource-Bounded Measure, With Application to
the {BPP} vs. {EXP} Problem},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR98-058}},
year = {1998},
url = {https://eccc.weizmann.ac.il/eccc-reports/1998/TR98-058/index.html},
eprinttype = {ECCC},
eprint = {TR98-058},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR98-058.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR98-075,
author = {Adam R. Klivans and
Dieter van Melkebeek},
title = {Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time
Hierarchy Collapses},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR98-075}},
year = {1998},
url = {https://eccc.weizmann.ac.il/eccc-reports/1998/TR98-075/index.html},
eprinttype = {ECCC},
eprint = {TR98-075},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR98-075.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/birthday/MelkebeekO97,
author = {Dieter van Melkebeek and
Mitsunori Ogihara},
editor = {Ding{-}Zhu Du and
Ker{-}I Ko},
title = {Sparse Hard Sets for {P}},
booktitle = {Advances in Algorithms, Languages, and Complexity - In Honor of Ronald
V. Book},
pages = {191--208},
publisher = {Kluwer},
year = {1997},
timestamp = {Wed, 30 Mar 2016 17:34:58 +0200},
biburl = {https://dblp.org/rec/conf/birthday/MelkebeekO97.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/Melkebeek96,
author = {Dieter van Melkebeek},
editor = {Steven Homer and
Jin{-}Yi Cai},
title = {Reducing {P} to a Sparse Set using a Constant Number of Queries Collapses
{P} to {L}},
booktitle = {Proceedings of the Eleveth Annual {IEEE} Conference on Computational
Complexity, Philadelphia, Pennsylvania, USA, May 24-27, 1996},
pages = {88--96},
publisher = {{IEEE} Computer Society},
year = {1996},
url = {https://doi.org/10.1109/CCC.1996.507672},
doi = {10.1109/CCC.1996.507672},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/Melkebeek96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-04-24 23:15 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
