Electrical and Computer Engineering, Carnegie Mellon University

Let’s say that you’ve been tasked with locking away a stash of treasure in a safe. There is a group of 6 people, each of whom wants access to the safe, but since they don’t trust each other, they decide that in order to open the safe, at least 4 of them need to come together. You can put as many locks as you want on the safe, and for each lock you can distribute as many keys as you want to the participants. How many locks do you put on the safe and how do you distribute the keys?

(If you don’t know the answer and don’t want to spoil the fun, stop reading now.)

What we want in solving this problem is to distribute the keys among the participants in such a way that (1) any group of 4 or more participants collectively own keys for each lock on the safe (and of course the group can have more than one key for the same lock), and (2) any group of 3 or fewer participants will be missing a key for at least one lock on the safe. It’s actually this second property that gives us the insight to solve this problem. The idea is that we select every possible subgroup of three people in the group, and for each subgroup we put a lock on the safe and give keys for the lock to everyone else in the group except for those three. So in this case we would need 6 choose 3 locks, which equals 20 locks. Then we give every subgroup of three people keys to a lock, so for example the first key would be given to participants 1, 2, and 3, the second key would be given to participants 1, 2, and 4, and so on.

Why does this work? Consider participants 1, 2, and 3. There is one key that they don’t have, namely the key given to participants 4, 5, and 6. We also know that they have all of the other keys except this one, since the only way to not give a key to any of 1, 2, or 3 would be to give the key to 4, 5, and 6. We also know that adding any participant to this subgroup would give them all the keys, because 4, 5, and 6 all have the one key that they’re missing. We can substitute any 3 different numbers above, and get the same result. So any group of 4 people are required to unlock the safe!

Now let’s see what happens when we generalize the problem. We have n participants, at least t of whom are needed to open the safe. We can use a similar approach as earlier. For every subgroup of t-1 participants there should be a key that nobody in the subgroup has. So we can make one lock for each of these subgroups (and there are n choose t-1 of these subgroups) and for each lock give keys to all participants not in this subgroup. Thus in total we distribute (n choose t-1) * (n-t+1) keys. So now we can do this for all kinds of groups and thresholds!

In cryptography, secret sharing allows a secret to be split among n people in such a way that at least t of them need to agree to unlock the secret. This is a nice mathematical equivalent of solving the above problem without having to deal with lots of separate locks and keys. Shamir’s secret sharing is a particularly elegant solution: since t points are sufficient to define a polynomial of degree t-1, we can define such a polynomial P(x) with P(0) equal to the secret and distribute one point of the polynomial (1 and P(1) for example) to each participant. Then, any t of them can reconstruct the polynomial using Lagrange interpolation to find the secret.

When I was an undergraduate, I wanted to do everything I could. There were tons of courses I wanted to take, extracurriculars I wanted to participate in, and events I wanted to attend. I’ve always been the kind of person who wants to try new things, so I tend not to say “no” to many opportunities that come my way.

As a result, I ended up taking the maximum course load (or more) for six straight semesters and participated in around four extracurriculars each semester (which totaled to an extra 10-15 hours per week). To be honest, I went to a school where taking a maximum course load was not that unusual, but as I later learned, “it’s like being a kid in a candy store. Even though you might want to try everything, that doesn’t mean you should.”

I loved my college years, but I won’t deny that they were pretty rough at times. In my first year I was in Army ROTC, which required me to show up for physical training three times a week at 6:30 am. I’m not a morning person – you can imagine how that went. Even in my senior year when I reduced my course load to just about the minimum that I could, I decided to apply for pretty much every study abroad scholarship and graduate fellowship I could, as well as take the GREs and apply to 9 graduate schools. I wrote applications for almost the entire semester, 16 in total, of which 5 were successful. I slept very little at night, and very frequently in class.

When I started grad school, I planned to do something similar – get involved in as many projects as I could and narrow my focus to something that interested me. Fortunately for me, this backfired fairly quickly when I realized that the standard for publishing research in my field was much higher and much more competitive than I thought. I really didn’t know a thing about how to write a good research paper, but I was trying to take on a full load of projects anyway.

Then my advisor told me one day, “Saying no is an important skill you need to learn in grad school.” It’s stuck with me ever since.

Grad school can be an especially stressful time, and the pressure to do as much as possible is quite strong at some universities. But it’s also a very common time for students to burn out. Saying no to activities, be they academic or extracurricular, is important. The Ph.D. is about depth, not breadth, and while it’s certainly important to keep in mind how your field and your specialty fits into the big picture, it’s good to focus on the important task: making contributions to open problems at the edge of human knowledge. Don’t be afraid to say no to something that might sidetrack you from that goal.

However, I will conclude by saying that it’s important to have a life too. Get involved in an extracurricular or two, whether it’s a student organization or just a weekly game night with friends. On the days when you’re really stressed, having some sort of activity where you can unwind a bit can work wonders for your well-being and your productivity.

The Ice Cube

Yesterday I went to a small cafe at ETH for a language tandem meeting. To those who aren’t familiar with tandems, a language tandem is a partnership of two people with differing mother tongues who help each other learn the other’s language, mostly through speaking practice. For people like me who want to speak the language as much as possible, it’s a great system, and to top it off, it’s also free here.

Anyways, I went to this cafe and ordered a Coke. The barista asked me if I wanted ice and lemon, so I said yes. He picks up a glass, opens up a bucket of ice, and with a pair of tongs puts one ice cube into the glass. Just one.

The nice thing was that my Coke wasn’t watered down as it often gets with a lot of ice. The not-so-nice thing was that the Coke was warm after about a minute.

Bella Bellinzona

Quick note: hopefully, I’ll include pictures in this post soon.

I’ve been spending the last days of my summer here in Switzerland taking a much-needed vacation. Due to some unforeseen circumstances requiring me to make some changes to my master’s thesis, it’s not a complete vacation, but it’s been very relaxing and rejuvenating. I’ve even found myself able to think much more clearly than I could last week, which is a bit surprising.

Anyway, tomorrow the traveling portion of my vacation comes to an end. I’ve spent the last two days in Ticino, the canton which covers almost all of the Italian part of Switzerland (and the only canton where Italian is the only official language). I spent most of yesterday in Locarno, riding the funicular (or incline for those of you from Pittsburgh) up to Orselina (home to the Madonna del Sasso sanctuary) and then a cable car and chairlift to Cardada/Cimetta. Cimetta is more than a mile high, and offers a beautiful view of Locarno and Lago Maggiore (a lake bordering Locarno and extending into Italy, because let’s face it, what Swiss town would be complete without a bordering lake?) as well as other peaks of the Alps.

Having grown up in Southern California, I’ve always been partial to the ocean rather than the mountains, but there was something simply magical about the chairlift to Cimetta that really took my breath away. There are few things like experiencing the air rushing through the chairlift car, breathing fresh mountain air, and watching as more of the turquoise lake and distant towns come into view. The city of Locarno was also nice, with its narrow, twisting streets, colorful buildings, and various piazzas, but that ride on the chairlift to Cimetta is one that I will never forget.

Today I spent most of the day in Bellinzona, the capital of Ticino. As you might guess from the title of this post, Bellinzona has become one of my favorite cities. Like most cities in Switzerland, it’s rather small, with fewer than 18,000 people, but it’s a beautiful city. There are three castles quite close to each other which are UNESCO World Heritage Sites and the pride of the city. Today I got the chance to see two of them – the Castelgrande and the Castello Montebello – and they were stunning.

The Castelgrande has a wall which extends way out into the city, with the top of the wall covered in a beautiful lawn of grass. You can walk along the lawn on top, or walk inside a dimly-lit tunnel in the wall. Both were quite fascinating experiences. In addition, there were two tall towers from which you could get a great view of the city. And the history of the place is amazing! It’s been around since at least the 1st century BC, and was fought over by the Milanese and the Swiss, among others.

And of course, Bellinzona’s food is cheaper than Zurich (well, pretty much every Swiss city is cheaper than Zurich) and delicious. I’ve also found the people to be a bit friendlier than in Zurich – even though much fewer of them speak English, they are a bit warmer and don’t mind striking up a conversation. I even had a lovely conversation in a cafe today with an old Italian Swiss man who spoke to me in German (though having only studied German for a couple months, I still have a long way to go), and I was able to pick up a bit of Italian just by listening to him talk to another random guy and the bartender behind the counter. Of course, things are a bit more disorganized than in the German part of Switzerland (I’ve personally found that the German Swiss are extremely attentive to even the smallest of details), but for some reason I feel very comfortable here in Bellinzona.

In any case, I hope tomorrow is as good a day as the others have been, and I’ll definitely miss beautiful Ticino – especially Bellinzona. Till next time.

As a grad student, I do all of my academic paper writing in LaTeX.

Using LaTeX rather than Microsoft Office or its open-source cousin LibreOffice allows me to write papers much more quickly using Vim, my text editor of choice. Like any good text editor, Vim is endlessly customizable with plugins, making editing almost any sort of text a breeze. Supertab is one of my favorite plugins, saving me keystrokes and helping me avoid errors through TAB completion.

However, one problem I frequently encountered while writing my most recent paper was in using Supertab to complete reference keys. Like many others, I use the common convention of using reference keys that have the reference type in the key itself (such as naming section labels in the form sec:foo and figures in the form fig:bar). In this case, though,  using TAB completion alone will open up a large list of options, almost all of which are from the dictionary word completion list.

It took me a while to figure out how to solve this problem, but the actual fix was quite simple. In fact, I stumbled onto it on a short help page for Vim-Latex (which I highly recommend for anyone who edits LaTeX in Vim). The help page is here, but it lacks a bit of explanation as to what’s actually happening under the hood.

The Vim command that does the trick is

set iskeyword+=:

This tells Vim that when using generic completion (which is what Supertab is actually doing when you hit TAB), it should consider the colon character as part of the keyword. This isn’t enabled by default, since the completion engine generally shouldn’t put colons when suggesting completions. As a somewhat contrived example, if you had already written

We need the following ingredients for our smoothie: oranges juice, berries, and
tartar sauce.

then if you later tried to TAB complete smooth, you would get smoothie: as a suggested completion. (You would almost certainly get this as the main suggestion if your auto-completion engine suggests the longest match, which most do.) However, when you type fig: and press TAB, you want to have your completion options show the various figure labels you’ve included in your document so far. By adding the colon character to the set of characters the completion engine should include in searching for completions, you can get the desired effect, making inserting references in LaTeX a breeze.

I further suggest adding the hyphen to the iskeyword variable. Personally, I often label my figures with keys such as “fig:design-diagram,” and thus I add the hyphen to allow completion for key names like this one. You can do this by changing the command to

set iskeyword+=:,-

A final note: the help page I referred to above suggests placing the line in ~/.vim/ftplugin/tex.vim, which only enables the option when editing .tex files. Unless you want colons and hyphen to be included in auto-completion for every file you edit, you should not put this in your .vimrc file. However, if you use Vundle (a plugin manager for Vim and perhaps the most useful plugin in my setup), your ftplugin/ directory will not be automatically loaded with Vim unless you configure it that way. For a cleaner setup, I recommend putting the following line in your .vimrc:

autocmd BufRead,BufNewFile *.tex set iskeyword+=:,-

This causes colon and hyphen to be added to the iskeyword variable only when editing .tex files, and does so in a way that plays very nicely with Vundle.

Swiss Windows

This summer I’ve been working in Switzerland. The hot and humid weather over the past month or so is starting to get rather unbearable, particularly because Zurich has almost no air-conditioned buildings. (I could talk about their desire to be energy-efficient at the expense of intellectual productivity between June and August, but we’ll leave that for another day.) However, there’s one thing in particular that really irks about my living situation here in Zurich.

None of the buildings seem to have screens.

This is especially problematic, since opening the windows is a refreshing and energy-efficient way to keep a living space cool, particularly at night. In the US I do this on a nightly basis in the summer months. However, here in Switzerland it seems that every night I am faced with a choice of keeping the windows closed and turning my room into a close approximation of a sauna, or opening the window and inviting every insect in the vicinity to join me in my brightly-lit room.

As if this weren’t bad enough, I recently had a conversation with someone at the office who remarked (somewhat derisively) how unbelievable it was that buildings in North America don’t have double-pane glass windows. The Swiss apparently put these windows in by default any time they get a new window, and it’s supposed to be much more energy-efficient due to the better insulation. While I’m inclined to agree with this idea, I find it unbelievable that the Swiss don’t put screens in their windows. It’s not energy-inefficient to do so, and it’s not even that difficult to do. Yet somehow they criticize Americans for not using double-pane windows, while they lack window screens in almost every building in the country.

Now I’ll get back to writing my paper in the cool of the night, all the while fending off mosquitoes, moths, and other creatures that could be easily kept out with a simple screen…

The MU Puzzle

I’ve just started reading Gödel, Escher, Bach: An Eternal Golden Braid by Douglas Hofstadter. Though I’m only a couple chapters in, it’s a really interesting read, and I highly recommend it.

In the second chapter, Hofstadter introduces the MU Puzzle. You are given a starting string, MI, and must obtain MU by using any combination of the following four rules:

  1. If you have a string ending in I, you can obtain that string with U appended. So if you have MI you can get MIU, and if you have MUII you can get MUIIU.
  2. If you have a string Mx, where x is any string, you can obtain Mxx. So if you have MI you can get MII, and if you have MUM you can get MUMUM.
  3. If you have a string containing three consecutive I’s, you can obtain the string that replaces them with a single U. So if you have MIIIU you can get MUU, and if you have MUIIIMU, you can get MUUMU.
  4. If you have a string containing two consecutive U’s, you can obtain the string that deletes them. So if you have MUUIU, you can get MIU, and if you have MUMUU you can get MUM.

Also note that you “obtain” strings because once you generate them, you have them in your possession for the duration of the puzzle. That is, if you have MI and generate MIU, then you can also generate MII, because you still have MI. You can’t lose strings.

If you’d like to play around with this and try your hand at solving the puzzle, you should stop reading now, because I’m going to start discussing the techniques I used to solve it.

 

If you start playing around with the strings, you should quickly realize that the M at the beginning of your starting string cannot be modified in any way. In fact, you can just get rid of it. In that case, the only rule that changes is Rule 2, which essentially becomes “you can concatenate a string with itself.” In the end, this ends up being a somewhat unimportant observation, but it is an interesting one.

But back to solving the puzzle. The only way to eliminate I’s is to do so by Rule 3. And in particular, we need to eliminate all of the I’s in a string to get even the possibility of a string that reduces to MU. This is a key observation to make. Why? Because in order to eliminate all of the I’s, we have to get the number of I’s in the string to some multiple of 3.

Notice also that Rule 2 is the only way to add I’s to the string. Furthermore, you can’t add I’s in any number you want; you can only double the number of I’s currently in the string. Since you start out with a single I and can only double the numbers, if you never eliminate I’s, the number of I’s in your string will always be 1 or 2 mod 3. This is because 2*1 mod 3 = 2 mod 3, and 2*2 mod 3 = 1 mod 3.

But notice that if you eliminate I’s, you can only do so three at a time, which means that the number of I’s in your string will always be 1 or 2 mod 3. Thus we can never get the number of I’s in the string to be some multiple of 3, and thus we can never eliminate all of the I’s. Therefore, this puzzle can’t be solved.

This is a really neat puzzle, because it requires careful thought about what the rules imply. In essence, you’re deriving strings based on a set of predefined rules, and Hofstadter’s point is that these rules do not allow you to generate even a string a simple as MU. But to see this, you have to think about what conditions need to be satisfied in order to solve the problem, and then observe that these conditions can never be satisfied.

I hope this inspires you to check out the book, and I hope that the rest of it is as thought-provoking and fun as this puzzle was.

Tag Cloud