If you accept that for many uses of publicly verifiable data structures that centralization is actually OK (and actually often a good thing, as it matches well how most democratic societies function), then there are other simpler alternatives to proof-of-work that still give many of the same benefits.

See for examples the append-only logs used in Certificate Transparency (https://www.certificate-transparency.org), and a more generalized hosted form provided by Continusec (https://www.continusec.com) that builds on the same principles. (disclaimer: founder of Continusec)