The main result of this paper is a polynomial time version of Rademacher's theorem. We show that if z is p-random, then every polynomial time computable Lipschitz function f:R^n->R is differentiable at z. This is a generalization of the main result of [Nies, STACS2014]. To prove our main result, we introduce and study a new notion, p-porosity, and prove several results of independent interest. In particular, we characterize p-porosity in terms of polynomial time computable martingales and we show that p-randomness in R^n is invariant under polynomial time computable linear isometries.

Brenier's theorem is a landmark result in Optimal Transport. It postulates existence, monotonicity and uniqueness of an optimal map, with respect to the quadratic cost function, between two given probability measures (under some weak regularity conditions). We prove an effective version of Brenier's theorem: we show that for any two computable absolutely continuous measures on Rn, μ, and ν, with some restrictions on their support, there exists a computable convex function φ, whose gradient ▽φ is the optimal transport map between μ and ν.