Here you find a selection of some of my recent papers.
I study families of depth measures defined by natural sets of axioms. I show that any such depth measure is a constant factor approximation of Tukey depth. I further investigate the dimensions of depth regions, showing that the Cascade conjecture, introduced by Kalai for Tverberg depth, holds for all depth measures which satisfy the most restrictive set of axioms, which includes Tukey depth. Along the way, I introduce and study a new depth measure called enclosing depth, which I believe to be of independent interest, and show its relation to a constant-fraction Radon theorem on certain two-colored point sets.
Regression depth, introduced by Rousseeuw and Hubert in 1999, is a notion that measures how good of a regression hyperplane a given query hyperplane is with respect to a set of data points. Under projective duality, this can be interpreted as a depth measure for query points with respect to an arrangement of data hyperplanes. The study of depth measures for query points with respect to a set of data points has a long history, and many such depth measures have natural counterparts in the setting of hyperplane arrangements. For example, regression depth is the counterpart of Tukey depth. Motivated by this, together with Pablo Soberon we study general families of depth measures for hyperplane arrangements and show that all of them must have a deep point. Along the way we prove a Tverberg-type theorem for hyperplane arrangements, giving a positive answer to a conjecture by Rousseeuw and Hubert from 1999. We also get three new proofs of the centerpoint theorem for regression depth, all of which are either stronger or more general than the original proof by Amenta, Bern, Eppstein, and Teng. Finally, we prove a version of the center transversal theorem for regression depth.
Schaefer's dichotomy theorem states that a boolean constraint satisfaction problem (CSP) is polynomial-time solvable if one of six given conditions holds for every type of constraint allowed in its instances. Otherwise, it is NP-complete. In this paper, together with Simon Weber we analyze boolean CSPs in terms of their topological complexity, instead of their computational complexity. We attach a natural topological space to the set of solutions of a boolean CSP and introduce the notion of projection-universality. We prove that a boolean CSP is projection-universal if and only if it is categorized as NP-complete by Schaefer's dichotomy theorem, showing that the dichotomy translates exactly from computational to topological complexity. We show a similar dichotomy for SAT variants and homotopy-universality.