An Appreciation of Locality Sensitive Hashing

Posted on Categories Computer Science, Exciting Techniques, Expository Writing, math programming, Opinion, TutorialsTags , , 1 Comment on An Appreciation of Locality Sensitive Hashing

We share our admiration for a set of results called “locality sensitive hashing” by demonstrating a greatly simplified example that exhibits the spirit of the techniques. Continue reading An Appreciation of Locality Sensitive Hashing

What Did Theorists Do Before The Age Of Big Data?

Posted on Categories Computer Science, Expository Writing, MathematicsTags , , , , , , , , 1 Comment on What Did Theorists Do Before The Age Of Big Data?

We have been living in the age of “big data” for some time now. This is an age where incredible things can be accomplished through the effective application of statistics and machine learning at large scale (for example see: “The Unreasonable Effectiveness of Data” Alon Halevy, Peter Norvig, Fernando Pereira, IEEE Intelligent Systems (2009)). But I have gotten to thinking about the period before this. The period before we had easy access to so much data, before most computation was aggregation and before we accepted numerical analysis style convergence as “efficient.” A small problem I needed to solve (as part of a bigger project) reminded me what theoretical computer scientists did then: we worried about provable worst case efficiency.

Continue reading What Did Theorists Do Before The Age Of Big Data?

Volunteers in Large Clubs: The Theorist’s View

Posted on Categories Expository Writing, MathematicsTags , ,

I have just posted a new write-up: Volunteers in Large Clubs: The Theorist’s View. This paper describes some interesting issues in organizing volunteers in a large club and tries to show (without math) how a theoretical computer scientist attacks such problems. Continue reading Volunteers in Large Clubs: The Theorist’s View