Abstract Gaussian random polytopes have received a lot of attention, especially in the case where the dimension is fixed and the number of points goes to infinity. Our focus is on the less-studied case where the dimension goes to infinity and the number of points is proportional to the dimensiond. We study several natural quantities associated with Gaussian random polytopes in this setting. First, we show that the expected number of facets is equal to$$C(\alpha)^{d+o(d)}$$, where$$C(\alpha)$$is some constant which depends on the constant of proportionality$$\alpha$$. We also extend this result to the expected number ofk-facets. We then consider the more difficult problem of the asymptotics of the expected number of pairs ofestranged facetsof a Gaussian random polytope. When the number of points is 2d, we determine the constantCsuch that the expected number of pairs of estranged facets is equal to$$C^{d+o(d)}$$.
more »
« less
Facets, weak facets, and extreme functions of the Gomory–Johnson infinite group problem
More Like this
-
-
Costa, Constantinos; Pitoura, Evaggelia (Ed.)Data-driven systems can be unfair, in many different ways. All too often, as data scientists, we focus narrowly on one technical aspect of fairness. In this paper, we attempt to address equity broadly, and identify the many different ways in which it is manifest in data-driven systems.more » « less
An official website of the United States government

