# Machinations

Puzzle
November 28, 2011, 4:45 pm
Filed under: Uncategorized | Tags: ,

One of my graduating PhD students has been interviewing with several big Internet companies (Google, Amazon, Microsoft, etc).  One of the benefits of this is that my research group gets to hear many of the new job interview puzzles for this year.  Here’s one of the more interesting ones:

You are given a large array in the form:

$a_1, a_2, \ldots a_n, b_1, b_2, \ldots, b_n$

You want to output an array in the form:

$a_1, b_1, a_2, b_2, a_3, b_3, \ldots, a_n, b_n$

The catch is that you have very little external memory (only O(log n)), so you need to change the array in place.

It’s not too hard to get a solution to this problem that runs in O(n log n) time (think recursion).  But surprisingly, you can do better.  Can you get a linear time solution? Beware: this is harder than it seems!

Yao’s Millionaire Problem
November 18, 2011, 4:27 pm
Filed under: Uncategorized | Tags: , , ,

In this post, I want to talk about a research problem that I think even our new Republican legislatures can get excited about: Yao’s millionaire problem.  In this problem, two millionaires want to determine who is richer, but neither wants to reveal their private net worth.  Can we develop a protocol to help these millionaires?  This problem is important  because it kicked off the the study of secure multiparty computation.

Below is a picture of the protocol originally proposed by Yao.  Alice and Bob are the two millionaires and i and j are the private net worths of Alice and Bob respectively.  The protocol makes use of public key cryptography: Alice is assumed to be able to generate a public encryption key E_a() along with a private decryption key D_a().  To see that the protocol reveals who is richer, note that y_j = D_a(k) = x.  Thus w_j = x if j<= i and w_j = x+1 if j>i.  Showing that the protocol doesn’t reveal any information beyond who is richer is more challenging and is presented in detail in  the paper.

I should point out that this protocol takes exponential time and that this run time has been improved in subsequent papers.  However, there is a question about this problem I haven’t been able to answer.  In the case where there are n players, do we need private channels or cryptographic assumptions to solve the problem?  Are private channels needed even if we’re happy with a Monte Carlo solution?  I’ve seen several papers that remove cryptographic assumptions, but none that seem to remove the need for private channels.  Conversely, I’ve seen no papers that prove that private channels are necessary…

Cruel and Unusual?
November 4, 2011, 5:48 pm
Filed under: Uncategorized | Tags: , ,

Below is the last problem on a midterm for my graduate algorithms class.  A few years ago, I started creating problems for this class that were based on (simplifications of) research problems.  There’s a subset of the students that really like these problems and do well on them, but I worry sometimes that they hurt the students who are struggling in the class.  I’m curious if others assign these types of problems for general graduate classes?

midterm problem