The idea behind those algorithms is to build a graph on words, using WordNet, or a corpus such as Wikipedia. Edges are added between words which are semantically close, or which often appear in the same documents. Then, to compare two words (or two bags of words), you compute the limiting distributions of the two random walks starting at each of the words. Those random walks will more explore nodes which are close to the starting nodes, and so, similar words will have similar random walks.
[1] Hughes, T. and Ramage, D. 2007. Lexical semantic relatedness with random graph walks ( http://acl.ldc.upenn.edu/D/D07/D07-1061.pdf )
[2] Ramage, D. and Rafferty, A.N. and Manning, C.D. 2009. Random walks for text semantic similarity ( http://nlp.stanford.edu/pubs/wordwalk-textgraphs09.pdf )
[3] Yeh, E. and Ramage, D. and Manning, C.D. and Agirre, E. and Soroa, A.. 2009. WikiWalk: random walks on Wikipedia for semantic relatedness ( http://nlp.stanford.edu/pubs/wikiwalk-textgraphs09.pdf )
[Update] Added the third reference.
That said, my method is somewhat different than these in the way that it explicitly treats unlinked documents as distributions over a graph of words and the theoretical framework (based on a theoretical process for document generation) employed to derive it.
[1] http://www.iro.umontreal.ca/~nie/IFT6255/lafferty-zhai.pdf
I use OpenCalais to compute keywords for texts; where does it stand vs. [6] and LSA in general?
Final output would likely use some hand curated rules on how to combine the above with infromation from curated databases like dbepida.
________________
There is this thing called random projection based on the observation that in high dimensions, most direction are nearly orthogonal to each other. This is a wonderful observation because it allows us to write stupendously simple (and fast) algorithms that give good results for mathematically sound reasons.
I strongly suggest anyone who is interested in LSA but wants something scalable, simpler to write and faster to look into Random Indexing.
Based on his emphasis on markov chains and his diagrams, I think his algorithm works by building a markov chain from word co-ocurrances. Then when the user searches, it uses the words from the highest incoming edges to keywords to disambiguate word meaning and cluster tweets.
I would argue based on his justification by random walks that given enough time and study he would have ended up with LDA and not LSA.
LSA[1] has been around since the 80s and is used in many applications from GRE testing to Apple's junk mail filtering[2]. It's used a lot since the patent expired, it's relatively good and can be computed quickly. Of course, a lot of text-retrieval research has happened in the past few decades, one of my favorites being LDA[3] which relies on a much more sound statistical basis than finding lower-dimensional representations of term-document vectors. Unfortunately LDA's model is not directly computable and answers must be determined via Monte-Carlo methods.
As for 'indepdendence,' his terminology gets a little confused here. At first I thought he was talking about the 'bag-of-words' assumption that most large-scale language models have. These effectively ignore grammar (other than stemming) in order to efficiently determine the 'gist' of a document without its intricacies. However, his videos imply he is talking about word-sense disambiguation[4], which is certainly known about and was the crux of LSA in the first place. If he is talking about lifting the bag-of-words assumption, there has been some interesting work going on, such as [5] (disclaimer: I am a coauthor on that paper).
If you're interested in this stuff, I highly recommend trying out the LSA demo server at [6] (it can get swamped sometimes so don't kill it) and David Blei's LDA implementation at [7]. The LDA-C inputs and parameters are a little obtuse when you first look at it, and I don't have my notes on how to use it at the moment but if you play around with it it should make sense.
This kid is crazy smart, and I hope he gets exposed to a lot of really cool research since he can obviously pull off a lot at a young age. Best of luck to him.
[1] http://en.wikipedia.org/wiki/Latent_semantic_analysis
[2] http://developer.apple.com/library/mac/#samplecode/LSMSmartC...
[3] http://en.wikipedia.org/wiki/Latent_Dirichlet_allocation
[4] http://en.wikipedia.org/wiki/Word-sense_disambiguation
[5] http://aclweb.org/anthology-new/D/D12/D12-1020.pdf
[6] http://lsa.colorado.edu/
[7] http://www.cs.princeton.edu/~blei/lda-c/