About Olivia

“Please see window for assistance”

A graduate student at UCSD, enjoying all the sun, sand, and graph theory that San Diego has to offer.

Algorithms Fit for Compilation?

Most researchers differ in their workflow.  For researchers in the algorithms world (or at least, those I know), the work is in the design. Our hours are spent at the blueprint stage. Algorithms are designed, improved, reformulated, or reapplied in different problems, mostly on paper. But this is unarguably only the first stage in successfully developing a new algorithm. There are still the matters of proving and testing the algorithm, and submitting the result to the public. When are we done drafting our blueprint? How do we package and ship the blueprint to the engineers and construction team?

Let’s address the more straight-forward question first. What is the best way to present an algorithm? How descriptive and specific should it be? Should it be entirely self-contained or, for instance, could we have a pointer to a “… subroutine of choice”? Is implementability more important than readability?

Continue reading

Talks of Talks of Estimators

This week, TCS+ hosted a talk by Greg Valiant via a Google+ hangout.  Valiant gave a talk on his work with brother, Paul, on an efficient estimator for entropy and support size of an unknown probability distribution requiring only O(n/log n) samples, where n is a bound on the support size of the distribution.  This work diverges from the existing literature by demonstrating that the estimate can be obtained with a concrete linear program; an algorithm which outputs a distribution very similar to the unknown distribution with respect to certain statistical properties.

Continue reading