More than Potatoes

It turns out that mashing things is not just good for dinner. I was recently involved in two mash-ups.

• I was recently searching for housing in Waterloo, and found the website padmapper. It is the rental-searching tool of my dreams! It takes all of the entries from craigslist, kijiji etc, and puts them on a single google map, where you can click for full information. Moreover, you can filter by date, keywords, upper/lower price… and the GUI is brilliant, because it barely exists at all, and mainly looks like just a google map.
• Today, I was working on the CS Circles project for learning Python, and was able to install a pretty nifty editor in place of the typical text field. If you click on “Rich Editor” it brings up the free Ace editor, run via delicious JavaScript. It is pretty excellent to get syntax highlighting, parenthesis matching and code folding working in a browser. It’s even better that it’s possible to pull it into other projects.

 

Fold-Fashioned

Continuing on last week’s post, there were a couple of hands-on activities led by Joseph O’Rourke at the geometry minicourse that I attended. In one of them, you start by printing out the following sheet of paper (available at howtofoldit.org):

The red and green lines indicate mountain and valley folds and at this point your job is to follow all of the folds, like in origami. With a little bit of playing around it will look like the following. The left shape is simply creased, and the dreidel-shaped object at right is the fully-folded version.

As an aside, the hands-on activities were a fantastic part of the mini-course. One trivial reason is that it was a long break from lectures. But a deeper thing that happened is that people were struggling, being confused, eventually gaining some insight and getting it to work, and then playing around! A good lecture is very seductive but there’s a limitation to the lecture format in that, without exercising your own mental muscles, it is difficult for the material to “stick” or hook in to your existing corpus of knowledge. In my Game Theory courses/math circles there’s the opportunity to actually play games which was fun. But for me, this was the first time doing origami in a mathematical setting.

Anyway, back to the task at hand. If you notice, there was a black line outlining the original A. If you have done your job correctly, all of that line will be neatly folded so that with one scissor-cut, you will chop the outline of the A, as well as the hole in the centre!

Not too bad, eh?

Unrelated joke. When they were naming the northernmost part of North America, the founders were very much inspired by the USA. It would be so great to have a three-letter acronym like USA! So they put all of the letters of the alphabet in to a hat, and the mayor pulled them out, one by one. “C, eh? N, eh?, D, eh?” And so, Canada was born.

Inspired by the alphabetic shenanigans, I tried to do a free-hand maple leaf afterwards. Here is how it turned out (left):

Is it a recognizable attempt? I would like to think so. But there is a more important question here. What if we also wanted to cut out the red bars on either side of the maple leaf? What if we wanted to do the US flag with all of its stars and stripes? How about an arbitrary line drawing? This elegant question was solved, then discovered to be buggy, and then fixed by two pairs of researchers (history here):

Theorem (Bern-Hayes ’09, Demaine-O’Rourke ’07). For any planar graph (made of straight line segments) embedded in a rectangle, there is a way to fold the rectangle, so that a single straight-line cut will exactly cut out that graph.

Pretty amazing! The proof is quite heavy, as indicated by the bug. At the same time, the methods are quite elegant, and there are two different proof methods.

Let me just briefly mention the other activity we participated in. Take an ordinary rectangular piece of paper. You can fold the left-centre point on to the right-centre point, and get a rectangle. Similarly, folding the top-centre point on to the bottom-centre point gives a different rectangle. But you can fold other shapes, in fact 3D shapes, out of this humble piece of paper! Start by folding any boundary point X on to the boundary point Y that is directly opposite. Then, you should think of the remaining edges as a “zipper” and tape them together both ways from the X-Y point. With a little patience, the paper will turn into a 3D polyhedron with triangular faces.

Joint Meeting

No, this is not about sharing joints (even in moderation).

This week I am at the joint meeting of the American Math Society and Math Association of America in Boston, MA. It is a huge conference with around 7000 participants, but more cohesive than many other mega-conferences including Informs and ISMP that I have visited.

The meeting takes place in two hotels and a conference center, right around the Prudential Centre mall. It is a brisk 7-minute walk between hotels which makes for some good exercise… but I am very happy that the walk is not too brisk, because it is entirely indoors.

The program is immense. Navigating the first two days was easy because I attended a mini-course of Joseph O’Rourke and Satyan Devadoss on discrete (and computational) geometry. I’ll talk some more about one thing from this mini-course once I get back home and find my camera.

The proper conference started on Wednesday and continues until Saturday. Here is one quotable moment from Jim Propp:

A proof is a conjecture’s way of making more conjectures.

(This is a riff on a classical quote.)

I tried going to one talk in a “history of mathematics” session, which I thought was interesting because it talked about intuition, computing, and proof. A pet theory I have about these concepts is that learning to program is good for mathematicians, because debugging a computer program can give some lessons about the importance of writing bug-free proofs. Instead, the talk was about the early history of automated proofs, and posited that Polya’s famous work on fundamental proof methods was actually motivated by early automated proof methods.

Yesterday I gave a talk on discrete geometry using computational methods (pictured) and tomorrow I will give a talk about the Computer Science Circles website. In-between I have been mostly attending talks on graphs, bijections, and voting theory… and enjoying the fine coffee shops in and around Copley Square!

Update: I did two cool things with tools I heard of at a talk by Matthew Leingang. One, I now can use dlvr.it to have my RSS show up in Facebook automatically (sadly G+ seems impossible still). Two, I uploaded my education talk to slideshare.

holidays.happy()!

It has been great to be back in Toronto for the holidays! I have seen a lot of sorely-missed old friends and got great presents from my family (props to my brother’s megaman magnets). So far with Sara (who got me a wonderful coffee grinder) we have made:

• open-face apple pies… it was supposed to be topped but we had enough apples to fill two pies, and two bottomless ones worked out very well
• cinnamon rolls, from a great recipe my sister found years ago
• next planned baked good: biscochitos!

Foreground: Kindle DXG with myts-6 terminal. Background: Lebowski pants.

I also have had an opportunity to hack around a lot on my Kindle DXG (DX Graphite), which I got a few months ago. It is not one of the newest (e.g. ‘fire’) versions of the device, but it’s the most recent one of the large-screen versions, which for me is essential so that I can read my .pdf papers with ease. It has a great e-ink screen and displays grayscale beautifully.

I was pretty happy with the Kindle, but the thing that made me want to keep it for certain rather than possibly return it was that it has free internet access all over the world! Sort of. There is a browser, which can display text and basic images pretty competently. It supports a few aspects of JavaScript and CSS but mostly not. It has problems displaying pages that are larger than 1 MB. It’s best if I’m looking for a restaurant nearby, or trying to read my emails on the bus.

I previously installed the Duokan operating system, which has a much-improved .pdf reader (especially for 2-column documents) and lots of cool-looking Chinese text that I cannot read (but it’s not important). But, this week, I installed a new set of tools which are very neat:

• first, the ability to telnet into the kindle’s linux operating system over USB
• second, some cool screensavers of Samus and Megaman instead of the original bunch of famous authors
• third, a ‘launchpad’ to add custom commands (and make Duokan easier to use)
• finally, a terminal!

The terminal is really pretty amazing. It took a couple days’ worth of trial-and-error before I found the right version that actually works on the DXG, since there are about a dozen different types of kindles out there. I can’t say it has been very useful yet, but definitely playing with this computer was a great christmas toy.

For accessing the web, this opens a limited set of new possibilities. When you access the web with the normal browser, you can go to any web page you like, but you cannot download files like .pdfs and .mp3s to your machine. Through the command-line, it seems you can now actually download anything that you like so long as it is on an Amazon server. The photo of my kindle shows me after I successfully downloaded this pdf, this jpg of Kim-Jong Il looking at stuff, and this mp3. Note that both “amazon.com” and “s3.amazonaws.com” are fair game, but I don’t know of any connections that are possible.

So what possibilities are there other than downloading pictures of dead dictators from tumblr? I’m not really sure. But I have grown more fond of my Kindle over time. Having the ability to play .mp3s has helped, any my friend Mariel’s suggestion to use it in place of a magazine while on gym machines has been great. It’s been a pretty handy way to carry .pdf recipes around. Now that I can access linux, maybe I should install LaTeX on it? An old-school version of Maple?

Pictures: California and New Mexico

Art on a fine restaurant near "La Taqueria," San Francisco's 24th and Mission

Driving in New Mexico

Petroglyph National Park

Satellite coffee, very tasty! This is the Nob Hill location

Éclairs from the affiliated Flying Star Café, ready to fly into your mouth

Thanksgiving Turkeys Times Two

This post is a shout-out to several good friends who hosted me for thanksgiving. As such, I looked up the background on a well-known story: Canadian thanksgiving happens earlier than the American one because it’s colder and therefore the harvest happens earlier.

Wikipedia corroborates this but I was more interested in a link to Canada’s list of all previous individual dates of Thanksgiving. The strangest part to me is that between 1816 and 1849, it was celebrated by both Lower and Upper Canada exactly four times, both on the same years. I guess somebody was copying someone else’s good idea? The timing was a bit different back then, sometimes in February and May, and it was for a variety of different officially festive reasons, such as the “cessation of cholera” or the end of wars between Britain and France.

Although no government-sponsored reasons were so interesting this year, I did give thanks twice! Here are the stats:

	Canadian Thanksgiving	American Thanksgiving
I was in	Boston (America)	LA (America)
well technically,	Medford	Huntington Beach
visiting	Mike and Kathleen.	Jaime and Christina.
We ate	turkey	turkey
pictured being sliced by	Mike (above).	Jaime (below).
I contributed	whiskey	sweet potato pie, sweet potato pie casserole
and for the first time tried	crème brulée beer.	green bean casserole.
I got to see, for the first time,	Bohnanza.	an electric knife-saw.
Everything was	delicious!	delicious!

Thanks from Sara and me to all of you ladies and gentlemen for the edible hospitality! I have never cooked any bird larger than a chicken, but when I do I hope it flies as well as these two!

Applications

This term, while I have been travelling around various parts of the United States, one constant each month is that I have spent some time with job applications. The process of looking over universities, to see if there is a good enough fit to write a cover letter and submit an application, has been quite illuminating… you learn a lot of demographic information about what topics are being studied by various departments and individuals by looking through all these websites!

This month I also learned:

• upon closer inspection, Miami University is not in Florida, rather Ohio (in the Miami Valley)
• that the American Public University is private, not public
• much more usefully, in a very nice talk by Ran Libeskind-Hadas yesterday, that Harvey Mudd College is using bioinformatics to create a very compelling and successful CS course for beginners.

Back to the job search… I have sought openings in both mathematics and computer science, since I like both areas and I’ve been a grad student and TA in both kinds of departments. Briefly, there are many more jobs in mathematics than CS, and there are many more jobs in the US than Canada (and disproportionately few in CS), but the math job market is (at least superficially) not as bad as many people seemed to fear.

Although I looked through a variety of sources, pretty much all of the positions I’ve applied to have been advertised on one of three places:

• mathjobs, by far the best, especially the streamlined reference letter process
• the Computing Research Association job ads website, which you can also get by RSS
• the Canadian Mathematical Society job ads website, which you can also get by e-mail.

In my applications, it has been extremely valuable to get feedback from peers, mentors, and friends. Also, it has been useful to step back and consider the field as a whole to remind myself where my research fits in. Here at UCSD, Christina Boucher and Daniel Lokshtanov have generously helped educate me in bioinformatics and exponential-time algorithms (respectively), two pretty fascinating areas of computer science that I previously knew little about.

The continuing “occupy” movements have also been thought-provoking, especially the aspects of student debt and equity in education. Claire Mathieu at Brown discussed a student’s debt situation in a blog post last month. In a later post I will talk more about a co-creation of mine, a free website for learning (and auto-grading) Python in-browser, supported by the CEMC at Waterloo. I like the opportunity to build high-quality educational tools like this since it seems important that, just like information should be free, so should a good education be freely accessible!

The Joy of Randomness

Ravi Kannan gave a distinguished lecture today at Georgia Tech covering a wide swath of algorithms, randomness, and high-dimensional geometry. There was one particularly excellent slide that gave a very intuitive explanation for a result I have seen, but not fully understood, before.

The result is in the field of streaming algorithms. Specifically, there is a “streaming” data set which consists of a large number m of elements, where each element is some b-bit string — actually it is more convenient to think of each element as integer between 1 and n := 2^b. You only get to see one element from the stream at a time, do a computation and change your working memory, and then the next one arrives. We want to capture some statistical properties of this data set. Storing the entire data set could be done easily in either m log n bits, or n log m bits. But what if this is much more memory than our computer has available? (E.g. if these are a continuous stream of data points from a sensor, or requests on a web server, or Google’s cache of the internet.) We would like to say something useful about the data set using only polylog(m, n) memory.

First, an easier puzzle. Let’s say that we don’t precisely know in advance the total number of items (including repeats) m that will arrive, and want to find m out. (For the puzzle, we don’t care about the items’ contents.) Evidently we can just count this in a streaming manner using log m bits of memory.  Can we do it with less? More precisely, can we come up with a good estimate of m using only O(log log m) bits of memory? I give the answer at the end.

Part of a Stream

Back to Ravi’s talk. The particular statistic we’d like to count is the second moment. For each string i, let f_i be the frequency of that string, or in other words the total number of times it appears in the data set. Then the second moment is defined as . Put differently, the second moment is the probability that two random elements from the stream are the same, up to a factor of n². How can we estimate this value?

Ravi’s explanation of how you could imagine doing this was very nice. Think of f as a vector in high-dimensional space. What we want to measure is (the square of) the Euclidean length of f, but we don’t have the space to explicitly store all of the bits of f in memory. The streaming model amounts to discovering the vector f in unit steps. The key insight in his explanation is to use the projection of f on to a random d-dimensional subspace where d is logarithmic; analogous to the Johnson-Lindenstrauss lemma, the random length of the projection actually gives us a pretty good estimate of the original length. Moreover, the projection of the sum of the steps is the sum of the projections of the steps. So it suffices to keep a running (vector) total of the sum of the projections of the steps.

A possible problem in implementing this is that projecting on to a d-dimensional subspace amounts to multiplying each incoming item (n-dimensional unit basis “step” vector) by a n-by-d matrix, and we cannot store anything of length n. To get around this, we let our n-by-d matrix actually be pseudorandom — that is to say, there should be some small random “seed” so that a computer program can determine the n-by-d matrix from just the seed. In this way, we don’t need to store the whole matrix in memory, rather just the seed, so that we can just recompute the ith row each time an element i shows up. In this way we can keep a running count of the d-dimensional vector sum and complete the idea.

This result is due to Alon, Matias, and Szegedy, which I have heard called one of the first papers in streaming computation (1996). The paper is nice to read and gives a clean explanation where you project on to random ±1 vectors in a derandomizable way. But this intuition helps me follow the proof idea for second moments (section 2.2). I read it previously (without this intuition), back when I was working on my Master’s thesis, because I had looked at an earlier paper of Morris for estimating the first moment… and this brings me to the puzzle’s solution.

***

You may have already deduced that you would need randomness to solve the puzzle, because with only O(log log m) bits of memory, our counter could only have polylog(m) states, and so only count polylog(m) items reliably.

So, let’s say that we have a “log counter” instead. The log counter stores a value k, such that our running estimate of the number of items seen so far is 2^k. Then, we maintain this counter using the probabilistic method: if the counter currently reads k, when the next item shows up, only increment the counter with probability 2^-k. So, the counter reads 1 after the first item arrives; the expected time until it reads 2 is three items; in general the expected time until it reads j is 2^j-1 items. You would need some more formal calculations to see exactly how good of an estimate it is, but this is the main idea.

The paper of Alon et al has a lot of other nice stuff. We saw small-space approximations for the first and second moments; they also formalize a previous idea for the 0th moment (counting distinct items) and show that some higher moments do not admit any small-space approximation. For recent work on this, not a bad place to start is to look at the work of Kane & Nelson et al.!

MANYDCGA

Last Friday, I finished my short visit at MIT in Boston, and on Sunday I arrived in Atlanta to visit Georgia Tech.

During the weekend, I finally got to visit my friends Jeff and Mariel in DC! We went to the National Museum of the American Indian (does it show a bit of homesickness if I made a beeline for the Inuktitut exhibit?), toured the West Wing with Jeff as our guide, and went to an excellent party populated by a strangely high number of Canadians.

We ate very well too: a thai restaurant, delicious quasi-historically native food at the museum, a southern-style restaurant including cajun catfish and bacon-wrapped dates, nachos sans nachos for a midnight snack, and a breakfast of champions prepared by Jeff. I have visited DC once before but this was the first time I got to see the city’s vitality.

In presentations about algorithms, people often draw their tree graphs with the root at the top and the leaves at the bottom, the opposite of a normal tree. Near the White house, we came across a botanical tree that would nonetheless feel right at home on a conference slide:

A Tree

Jeff and Mariel were really awesome hosts! Their place is a nice apartment close to all of the important stuff in the city (including beer stores). We talked about work, school, and I managed to convince them to watch a few episodes of my favourite show, Good Eats. But… I learned what Potatoes O’Brien from them, not TV!

I arrived in Atlanta late on Sunday, and it is really nice. Georgia Tech is extremely active in computer science and discrete mathematics; quite a number of people who I know previously have visits overlapping mine and are giving talks while here (3, randomly all of them Canadian). I am living in Midtown Atlanta and have enjoyed walking all over the place, especially jogging through lovely Piedmont Park in the nice weather.

Two nights ago a bunch of helicopters flew over my place in the evening, which seemed to be related to the shutdown of Occupy Atlanta. I have seen the Occupations in Boston, NYC, and DC in person so far and they all seemed pretty peaceful to me. I hope that they lead to some improvements in fairness.

In NYC (a few weekends ago) I saw one other thing of note. My buddy Ashwyn has previously mentioned Katz’ Deli and I went to check it out first-hand. The place can only be described as epic! The food was expensive, but delicious and with generous portions. It is a tourist trap, no doubt. But, I still enjoyed the trip there. Pictured below are the exterior and interior , as well as my meal — a pastrami on rye with pickles and Cel-Ray celery soda. Pretty good! But in a later tasting with Mike and Kathleen in Boston, we deduced it was hard to distinguish from gingerale; maybe homemade is better.

Better Know Your Metroids

• Metroid. Introduced in 1986  by Gunpei Yokoi and Satoru Okada. Name is a portmanteau of metro and android (android is a combination of andr-, man, and -oid, likeness). Metroids are fictional jellyfish-like creatures with quadripartite nuclei. They are chased by the bounty hunter Samus. Killing them can be done with the help of the ice beam.
  

  A metroid in space. Source: Super Metroid instruction manual, Nintendo, page 35.

• Metroid. Introduced in 1986 by A. Dress and T. F. Havel. Name is a portmanteau of matroid and metric (matroid is a combination of matrix and -oid, likeness). Metroids are a subclass of all polyhedra defined by constraints with {0, +1, -1} coefficients. They are totally dual integral. Optimizing linear functions over them can be done with the help of a greedy algorithm.

A metroid in the plane. Source: Submodular Functions and Optimization, Satoru Fujishige, 2nd ed, page 107.