Travelled to:1 × Finland
1 × Portugal
1 × Switzerland
2 × USA
Collaborated with:H.Dell S.Diehl R.Raz A.Klivans M.Anderson N.Schweikardt L.Segoufin
Talks about:time (5) hierarchi (3) polynomi (3) satisfi (2) collaps (2) unless (2) lower (2) bound (2) subexponenti (1) nonisomorph (1)
Person: Dieter van Melkebeek
DBLP: Melkebeek:Dieter_van
Contributed to:
2011
2010200520041999Wrote 5 papers:
- ICALP-v2-2011-AndersonMSS #first-order #invariant #locality #logic #query
- Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates (MA, DvM, NS, LS), pp. 368–379.
- STOC-2010-DellM #polynomial #satisfiability
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses (HD, DvM), pp. 251–260.
- ICALP-2005-DiehlM #bound #polynomial #random
- Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines (SD, DvM), pp. 982–993.
- ICALP-2004-MelkebeekR #bound #satisfiability
- A Time Lower Bound for Satisfiability (DvM, RR), pp. 971–982.
- STOC-1999-KlivansM #graph #morphism #polynomial #proving
- Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses (AK, DvM), pp. 659–667.