I'm looking for a reference on how to sample uniformly (and preferably efficiently, elegantly, etc.) from the vertices of a polytope. I gather that enumerating vertices is hard. I also note the MO questions Uniformly Sampling from Convex Polytopes and Is it possible to sample uniformly on the surface of a highdimensional polytope?. A bit of poking around Google Scholar hasn't turned anything up.

2$\begingroup$ I recently asked a question that turned out to be equivalent: cstheory.stackexchange.com/questions/42705/… I found some interesting references, but nothing definitive yet. $\endgroup$ – Lorenzo Najt Apr 14 '19 at 4:30

$\begingroup$ I think I was able to show it is NPhard. Take a look and see if you believe my argument. :) $\endgroup$ – Lorenzo Najt Apr 20 '19 at 5:17

1$\begingroup$ It is $NP$hard. See updated answer. $\endgroup$ – Lorenzo Najt Nov 13 '19 at 0:22

$\begingroup$ @LorenzoNajt Thanks for the update! $\endgroup$ – Steve Huntsman Nov 13 '19 at 15:37
Here is one efficient approach, performing a random walk with a rapid mixing time, that has been implemented for a particular class of polytopes, but which might well be adaptable to a more general setting: Random Walks on the Vertices of Transportation Polytopes (2008).

$\begingroup$ Interesting bit from the first page: "Markov chain Monte Carlo (MCMC) has not been well explored as a means of sampling, or approximately counting, vertices of general polytopes." $\endgroup$ – Steve Huntsman Jan 2 '19 at 14:52

$\begingroup$ ...and from the conclusions: "The question of whether we can sample vertices of a general [transportation polytope], when the number of sources is not constant, is still open." $\endgroup$ – Steve Huntsman Jan 2 '19 at 14:53