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 log2(n!) for sorting n items. For trees with n leaves we show, in increasing order of closeness to the sorting lower bound: (a) log2((α(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) log2(n!) — O(log n) queries are needed in case the tree is binary. (c) log2(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.

Computer-aided decision making--where a human decision-maker is aided by a computational classifier in making a decision--is becoming increasingly prevalent. For instance, judges in at least nine states make use of algorithmic tools meant to determine "recidivism risk scores" for criminal defendants in sentencing, parole, or bail decisions. A subject of much recent debate is whether such algorithmic tools are "fair" in the sense that they do not discriminate against certain groups (e.g., races) of people. Our main result shows that for "non-trivial" computer-aided decision making, either the classifier must be discriminatory, or a rational decision-maker using the output of the classifier is forced to be discriminatory. We further provide a complete characterization of situations where fair computer-aided decision making is possible.

We study the computational power of deciding whether a given truth table can be described by a circuit of a given size (the minimum circuit size problem, or MCSP for short) and of the variant denoted as MKTP, where circuit size is replaced by a polynomially related Kolmogorov measure. Prior to our work, all reductions from supposedly intractable problems to MCSP/MKTP hinged on the power of MCSP/MKTP to distinguish random distributions from distributions produced by hardness-based pseudorandom generator constructions. We develop a fundamentally different approach inspired by the well-known interactive proof system for the complement of graph isomorphism (GI). It yields a randomized reduction with zero-sided error from GI to MKTP. We generalize the result and show that GI can be replaced by any isomorphism problem for which the underlying group satisfies some elementary properties. Instantiations include linear code equivalence, permutation group conjugacy, and matrix subspace conjugacy. Along the way we develop encodings of isomorphism classes that are efficiently decodable and achieve compression that is at or near the information-theoretic optimum; those encodings may be of independent interest.

In this paper, we describe a model-based, non-linear reconstruction method for mapping internal building structures using through-wall radar data. We based the model on canonical geometry constructs that are commonly used in construction practices. These constructs are then formulated as sets of simple scattering mechanisms, which can be estimated from the data. Our non-linear approach employs an iterative, conditional estimation method as a function of the intervening structures between the sensor and the object under consideration. Specific associations of scattering mechanisms are then used to re-create various building structures such as walls, doors, stairs, etc. We discuss some examples of estimating specific scattering mechanisms and a model-based reasoning approach for assembling them to reconstruct the interior structure of a building.