Dieter van Melkebeek

Available identifiers

zbMath Open van-melkebeek.dieterMaRDI QIDQ354650

List of research outcomes

Publication	Date of Publication	Type
https://portal.mardi4nfdi.de/entity/Q6126365	2024-04-09	Paper
https://portal.mardi4nfdi.de/entity/Q4993283	2021-06-15	Paper
https://portal.mardi4nfdi.de/entity/Q5111135	2020-05-26	Paper
Derandomizing Isolation in Space-Bounded Settings	2019-09-02	Paper
Minimum Circuit Size, Graph Isomorphism, and Related Problems	2018-07-19	Paper
Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games	2017-07-28	Paper
Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses	2016-09-29	Paper
Time-space lower bounds for satisfiability	2015-12-04	Paper
Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses	2015-08-14	Paper
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses	2014-08-13	Paper
Is Valiant-Vazirani's isolation probability improvable?	2013-07-19	Paper
https://portal.mardi4nfdi.de/entity/Q4910739	2013-03-19	Paper
https://portal.mardi4nfdi.de/entity/Q2913799	2012-09-27	Paper
Pseudorandom generators, typically-correct derandomization, and circuit lower bounds	2012-06-26	Paper
On derandomization and average-case complexity of monotone functions	2012-06-25	Paper
An improved time-space lower bound for tautologies	2011-12-15	Paper
Space hierarchy results for randomized and other semantic models	2011-02-18	Paper
A Survey of Lower Bounds for Satisfiability and Related Problems	2010-09-08	Paper
Pseudorandom Generators and Typically-Correct Derandomization	2009-10-28	Paper
An Improved Time-Space Lower Bound for Tautologies	2009-07-23	Paper
A generic time hierarchy with one bit of advice	2008-02-22	Paper
STACS 2004	2007-10-01	Paper
Time‐Space Lower Bounds for the Polynomial‐Time Hierarchy on Randomized Machines	2007-06-26	Paper
Time-space tradeoff in derandomizing probabilistic logspace	2006-10-25	Paper
Power from Random Strings	2006-06-01	Paper
Computational depth: Concept and applications	2006-04-28	Paper
Language compression and pseudorandom generators	2006-02-08	Paper
Automata, Languages and Programming	2006-01-10	Paper
A time lower bound for satisfiability	2006-01-09	Paper
Holographic Proofs and Derandomization	2005-10-28	Paper
Automata, Languages and Programming	2005-08-24	Paper
https://portal.mardi4nfdi.de/entity/Q4668733	2005-04-15	Paper
The quantum black-box complexity of majority	2003-05-04	Paper
Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses	2002-09-29	Paper
https://portal.mardi4nfdi.de/entity/Q2729236	2001-07-18	Paper
Randomness and completeness in computational complexity	2001-01-10	Paper
https://portal.mardi4nfdi.de/entity/Q4501551	2000-09-04	Paper
The zero-one law holds for BPP	2000-08-21	Paper
https://portal.mardi4nfdi.de/entity/Q4258582	2000-05-04	Paper
Separating Complexity Classes Using Autoreducibility	2000-03-19	Paper
Hard sets are hard to find	2000-01-17	Paper
Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets	1999-01-17	Paper
https://portal.mardi4nfdi.de/entity/Q4336273	1997-08-11	Paper
Invariant finite Borel measures for rational functions on the Riemann sphere	1995-10-31	Paper
Block orthogonal systems for symmetric \(P\)-forms	1994-06-22	Paper

Research outcomes over time

Doctoral students

No records found.

Known relations from the MaRDI Knowledge Graph

Property	Value
MaRDI profile type	MaRDI person profile
instance of	human

This page was built for person: Dieter van Melkebeek