Dieter van Melkebeek

SODA Conference 2023 Conference Paper

Query Complexity of Inversion Minimization on Trees

• Ivan Hu
• Dieter van Melkebeek
• Andrew Morgan

We consider the following computational problem: Given a rooted tree and a ranking of its leaves, what is the minimum number of inversions of the leaves that can be attained by ordering the tree? This variation of the well-known problem of counting inversions in arrays originated in mathematical psychology. It has the evaluation of the Mann-Whitney statistic for detecting differences between distributions as a special case. We study the complexity of the problem in the comparison-query model, the standard model for problems like sorting, selection, and heap construction. The complexity depends heavily on the shape of the tree: for trees of unit depth, the problem is trivial; for many other shapes, we establish lower bounds close to the strongest known in the model, namely the lower bound of log 2 ( n!) for sorting n items. For trees with n leaves we show, in increasing order of closeness to the sorting lower bound: (a) log 2 ((α(1 — α) n )!) — O (log n ) queries are needed whenever the tree has a subtree that contains a fraction α of the leaves. This implies a lower bound of for trees of degree k. (b) log 2 ( n!) — O (log n ) queries are needed in case the tree is binary. (c) log 2 ( n!) — O ( k log k ) queries are needed for certain classes of trees of degree k, including perfect trees with even k. The lower bounds are obtained by developing two novel techniques for a generic problem Π in the comparison-query model and applying them to inversion minimization on trees. Both techniques can be described in terms of the Cayley graph of the symmetric group with adjacent-rank transpositions as the generating set, or equivalently, in terms of the edge graph of the permutahedron, the polytope spanned by all permutations of the vector (1, 2, …, n ). Consider the subgraph consisting of the edges between vertices with the same value under Π. We show that the size of any decision tree for Π must be at least: (i) the number of connected components of this subgraph, and (ii) the factorial of the average degree of the complementary subgraph, divided by n. Lower bounds on query complexity then follow by taking the base-2 logarithm. Technique (i) represents a discrete analog of a classical technique in algebraic complexity and allows us to establish (c) and a tight lower bound for counting cross inversions, as well as unify several of the known lower bounds in the comparison-query model. Technique (ii) represents an analog of sensitivity arguments in Boolean complexity and allows us to establish (a) and (b). Along the way to proving (b), we derive a tight upper bound on the maximum probability of the distribution of cross inversions, which is the distribution of the Mann-Whitney statistic in the case of the null hypothesis. Up to normalization the probabilities alternately appear in the literature as the coefficients of polynomials formed by the Gaussian binomial coefficients, also known as Gaussian polynomials.

TCS Journal 2012 Journal Article

On derandomization and average-case complexity of monotone functions

• George Karakostas
• Jeff Kinne
• Dieter van Melkebeek

We investigate whether circuit lower bounds for monotone circuits can be used to derandomize randomized monotone circuits. We show that, in fact, any derandomization of randomized monotone computations would derandomize all randomized computations, whether monotone or not. We prove similar results in the settings of pseudorandom generators and average-case hard functions — that a pseudorandom generator secure against monotone circuits is also secure with somewhat weaker parameters against general circuits, and that an average-case hard function for monotone circuits is also hard with somewhat weaker parameters for general circuits.

STOC Conference 2010 Conference Paper

Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses

• Holger Dell
• Dieter van Melkebeek

Consider the following two-player communication process to decide a language L: The first player holds the entire input x but is polynomially bounded; the second player is computationally unbounded but does not know any part of x; their goal is to cooperatively decide whether x belongs to L at small cost, where the cost measure is the number of bits of communication from the first player to the second player. For any integer d ≥ 3 and positive real ε we show that if satisfiability for n-variable d-CNF formulas has a protocol of cost O(n d-ε ) then coNP is in NP/poly, which implies that the polynomial-time hierarchy collapses to its third level. The result even holds when the first player is conondeterministic, and is tight as there exists a trivial protocol for ε = 0. Under the hypothesis that coNP is not in NP/poly, our result implies tight lower bounds for parameters of interest in several areas, namely sparsification, kernelization in parameterized complexity, lossy compression, and probabilistically checkable proofs. By reduction, similar results hold for other NP-complete problems. For the vertex cover problem on n-vertex d-uniform hypergraphs, the above statement holds for any integer d ≥ 2. The case d=2 implies that no NP-hard vertex deletion problem based on a graph property that is inherited by subgraphs can have kernels consisting of O(k 2-ε ) edges unless coNP is in NP/poly, where k denotes the size of the deletion set. Kernels consisting of O(k^2) edges are known for several problems in the class, including vertex cover, feedback vertex set, and bounded-degree deletion.

TCS Journal 2006 Journal Article

Computational depth: Concept and applications

• Luis Antunes
• Lance Fortnow
• Dieter van Melkebeek
• N.V. Vinodchandran

We introduce Computational Depth, a measure for the amount of “nonrandom” or “useful” information in a string by considering the difference of various Kolmogorov complexity measures. We investigate three instantiations of Computational Depth: • Basic Computational Depth, a clean notion capturing the spirit of Bennett's Logical Depth. We show that a Turing machine M runs in time polynomial on average over the time-bounded universal distribution if and only if for all inputs x, M uses time exponential in the basic computational depth of x. • Sublinear-time Computational Depth and the resulting concept of Shallow Sets, a generalization of sparse and random sets based on low depth properties of their characteristic sequences. We show that every computable set that is reducible to a shallow set has polynomial-size circuits. • Distinguishing Computational Depth, measuring when strings are easier to recognize than to produce. We show that if a Boolean formula has a nonnegligible fraction of its satisfying assignments with low depth, then we can find a satisfying assignment efficiently.

TCS Journal 2005 Journal Article

A time lower bound for satisfiability

• Dieter van Melkebeek
• Ran Raz

We show that a deterministic Turing machine with one d-dimensional work tape and random access to the input cannot solve satisfiability in time n a for a < ( d + 2 ) / ( d + 1 ). For conondeterministic machines, we obtain a similar lower bound for any a such that a 3 < 1 + a / ( d + 1 ). The same bounds apply to almost all natural NP -complete problems known.

FOCS Conference 2002 Conference Paper

Power from Random Strings

• Eric Allender
• Harry Buhrman
• Michal Koucký 0001
• Dieter van Melkebeek
• Detlef Ronneburger

We show that sets consisting of strings of high Kolmogorov complexity provide examples of sets that are complete for several complexity classes under probabilistic and non-uniform reductions. These sets are provably not complete under the usual many-one reductions. Let R/sub K/, R/sub Kt/, R/sub KS/, R/sub KT/ be the sets of strings x having complexity at least |x|/2, according to the usual Kolmogorov complexity measure K, Levin's time-bounded Kolmogorov complexity Kt [27], a space-bounded Kolmogorov measure KS, and the time-bounded Kolmogorov complexity measure KT that was introduced in [4], respectively. Our main results are: 1. R/sub KS/ and R/sub Kt/ are complete for PSPACE and EXP, respectively, under P/poly-truth-table reductions. 2. EXP = NP/sup R(Kt)/. 3. PSPACE = ZPP/sup R(KS)/ /spl sube/ P/sup R(K)/. 4. The Discrete Log, Factoring, and several lattice problems are solvable in BPP/sup R(KT)/.

TCS Journal 2000 Journal Article

The zero-one law holds for BPP

• Dieter van Melkebeek

We show that BPP has p-measure zero if and only if BPP differs from EXP. The same holds when we replace BPP by any complexity class C that contains BPP and is closed under tt-reductions. The zero–one law for each of these classes C follows: Within EXP, C has either measure zero or else measure one.

STOC Conference 1999 Conference Paper

Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses

• Adam R. Klivans
• Dieter van Melkebeek