Khovanskii bases, higher rank valuations, and tropical geometry

Given a finitely generated algebra A, it is a fundamental question whether A has a full rank discrete (Krull) valuation \frakv with finitely generated value semigroup. We give a necessary and sufficient condition for this in terms of tropical geometry of A. In the course of this we introduce the notion of a Khovanskii basis for (A, \frakv) which provides a framework for far extending Gr\" obner theory on polynomial algebras to general finitely generated algebras. In particular, this makes a direct connection between the theory of Newton-Okounkov bodies and tropical geometry, and toric degenerations arising in both contexts. We also construct an associated compactification of Spec (A). Our approach includes many familiar examples such as the Gel'fand-Zetlin degenerations of coordinate rings of flag varieties as well as wonderful compactifications of reductive groups. We expect that many examples coming from cluster algebras naturally fit into our framework.