Hurah!!I've got some excellent news:
I was co-awarded the
2012 Presburger Award, to be shared with Venkat Guruswami ,the young superstar of error correcting codes.

In short, the Presburger Award is the European "young-scientist award" in Theory.

It is given anually by the European Association for Theoretical Computer Science (EATCS)

to a scientist under 35 "for outstanding contributions in

Theoretical Computer Sciene as documented by a series of published papers."

Not surprisingly, I got the award for my work on data-structure lower bounds.The citation has a lot of nice things to say. Go read it :)

## Sunday, May 6, 2012

### Presburger Award

Posted by Mihai at 8:43 PM 21 comments Links to this post

## Sunday, April 15, 2012

### Happy Easter

Happy Easter!

...to all my readers cellebrating today in the Eastern Orthodox tradition.

According to persistent rumours:

Χριστός ἀνέστη

Christos a înviat!

Posted by Mihai at 10:11 AM 0 comments Links to this post

## Thursday, April 5, 2012

### Happpy recovery from the FOCS deadline:with a funny picture :)

Happpy recovery from the FOCS deadline everyone:)

Posted by Mihai at 1:01 PM 8 comments Links to this post

## Sunday, November 6, 2011

### New York Theory Day

The Fall 2011 New York Theory Day is happening this Friday, November 11th, at NYU (Courant), and features yours truly as a speaker.

I hope to see many of you there!

Posted by Mihai at 11:05 PM 1 comments Links to this post

## Monday, September 19, 2011

### Follow-up: Sampling a discrete distribution

This is a follow-up to my last post, on a puzzle about "Sampling a discrete distribution" (see my comment there for the solution I originally thought of).

*probability less than 1/n*

__LO__—*– probability precisely 1/n*

__GOOD__*– probability greater then 1/n*

__HI__Posted by Mihai at 4:03 PM 5 comments Links to this post

## Friday, September 16, 2011

### Sampling a discrete distribution

The following cute question came up at lunch today (all credit goes to Aaron Archer).

*n*possible outputs (and you know the probability p

_{i}of each output), and you want to sample from the distribution. You can use a primitive that returns a random real number in [0,1].

^{6 }and use a regular machine as your machine model (real number means a "double" or something like that).

*w*-bit machine and probabilities have

*w*-bit precision. The distribution is given by

*n*integers x

_{i}, and these values sum to exactly 2

^{w}. Output "i" should be produced with probability exactly x

_{i}/ 2

^{w}. You are given a primitive that produces a uniformly distributed

*w*-bit number.

Posted by Mihai at 1:55 PM 11 comments Links to this post

## Thursday, July 28, 2011

### International Olympiad, Day 2

**Problem Crocodile.**You have a weighted undirected graph with a start node and

*k*designated target nodes. Two players play a full-information game, taking turns:

- Player 1 moves on the nodes of the graph, starting at the designated start node, and aiming to reach a target node. In each turn, she can traverse any edge out of her current node [except the blocked edge / see below], incurring a cost equal to the weight of the edge.
- Player 2 can block one edge at every turn. When an edge is blocked, Player 1 cannot traverse it in the next turn. An edge can be blocked multiple times, and any past edge is "unblocked" when a new edge is blocked.

*B*,

*regardless*of what Play 2 does. Running time: O~(

*n*+

*m*).

**Problem Elephants**. You have

*n*elephants on the line at given coordinates. The elephants make

*n*moves: in each unit of time, some elephant moves to another position. You have cameras that can photograph any interval of length L of the line. After each move, output the minimum number of cameras needed to phtograph all elephants in the current configuration.

*n*.

**Problem Parrots.**You are given a message of

*M*bytes (0..255) to transmit over a weird channel. The channel can carry elements between 1 and

*R*, but elements don't arrive in order (they are permuted adversarially). Send the message, minimizing the number L of elements sent across the channel.

Posted by Mihai at 10:42 AM 10 comments Links to this post