## Wednesday, December 10, 2008

### Succincter

'Tis the season to be doing succinct data structures.

[P] My FOCS'08 paper demonstrated how to use recursion to achieve better redundancy. For many fundamental problems, it achieved a redundancy of n / (lg n / t)t bits with query time O(t). The toy problem that people remember from my paper is storing trits: store A[1..n], where A[i] in {1,2,3}, using close to n log23 bits and fast access to A[i].

[Golynski] In SODA'09, Alexander Golynski (PhD from Waterloo, currently at Google NY) showed a remarkable lower bound for succinct data structures. Suppose you want to represent a permutation π such that you can access π(x) and π-1(x) in time t. Then, your data structure needs redundancy Ω(n lg n / t2) bits. In particular, for constant access time, your data structure needs a constant factor more space than the minimum!

This is essentially the first "meaningful" lower bound for succinct data structures. [Gal-Miltersen] did prove a previous lower bound, but for a much harder problem: polynomial evaluation. (For this problem, we believe sublinear query time requires superpolynomial space, so never mind succinct data structures.)

Notice that Golynski's lower bound is much higher than my upper bound for storing trits and other problems. His bound is in fact tight for storing a permutation.

[Viola] Emanuele Viola looks at the trits problem in the bit-probe model and shows that, with bit probe complexity t, the redundancy needs to be at least n / 2O(t). My result implies a redundancy of n / 2O(sqrt{t}) if t is the bit-probe complexity.

As I always want to point out, the true model is the word RAM, but the bit-probe model is sometimes interesting as a mathematical curiosity.

[Mitzenmacher-Wiener] Michael has a student working on an implementation of the results in my paper. You could've guessed it from here, I suppose.

[P.-Thorup] In recent ongoing work, we gave a very strong result for the trits problem: we can achieve a redundancy of exactly 2 bits, with O(1) query time. This completely kills the problem.

In the bit-probe model, it immediately implies an upper bound matching [Viola].

It is not yet clear whether such strong upper bounds can be extended beyond the trits problem (e.g., for dictionaries and arithmetic coding). But we have some ideas and we are working hard on it (i.e. drinking and hiking).

## Monday, December 1, 2008

### B.A.M. 2

The Berkeley Algorithmists' Meeting will continue on Tuesday at 3:30pm.

Scheduling. There have been enough calls to change the time that I will do a recount of the votes and probably change it starting next week. If you would like to come and have not sent me your time constraints, please send them ASAP to mip@alum-mit-edu

Lecture notes. There are definite plans to post lecture notes here, though scheduling constraints will delay this for another week or so.

New topic: Orthogonal Range Queries

I want to spend a couple of meeting talking about range queries, a hugely important topic (in my opinion) that we don't teach too much of. The theory that has developed around this topic is one of the deepest examples of a coherent theory in TCS (maybe close to PCPs, depending on your subjective perception of depth).

Some ideas we will discuss, in an order TBD:

• persistence
• predecessor search (especially van Emde Boas)
• buffer trees
• RMQ
• the 3D structure of Nekrich
• rank/select
• lower bounds

## Saturday, November 29, 2008

### Changes in TCS

At the first BAM, I got an idea of how little complexity theory has changed in three decades: after I described Morgenstern's lower bound for arithmetic circuits with bounded constants, Christos noted that he gave a talk about the same paper in 1978, when he was a postdoc at Berkeley. We still have no clue how to prove a superlinear lower bound in the unrestricted model.

At the same meeting, I got to observe a change in the people that define our community, a change that fed right into my anxiety that "Theory of Computer Science" is becoming "Theory." After I defined and drew a butterfly graph, I asked how many people have seen this before; some 3 or 4 people raised their hands (which drops to a very small number once you subtract Christos and Dick Karp). But when I asked who knew that "Fourier characters are orthogonal," all but one had their hands up!

I, for one, grew up thinking supercomputers were cool, and knew all about routing messages, before I learned about those "linear systems" that people apparently wanted to solve on big machines. And, yes, I am suspicious of people who had a "theory is cool!" moment before 100 "CS is cool!" moments.

## Sunday, November 23, 2008

### Berkeley Algorithmists' Meetings

I am starting a new reading group at Berkeley. (Actually, I prefer the term "discussion group," since I was never too passionate about reading papers anyway; instead, I very much enjoy cafe-style discussion of open problems.)

For lack of a better name, this series will go by BAM (Berkeley Algorithmists' Meetings). Regarding coverage, I did not promise anything more specific than:

Since nobody can decide whether I'm doing complexity or algorithms, I will aim to keep this discussion group at the same level of ambiguity.

Presentations will transcend the boundaries of any single paper, as we will try to get a more comprehensive view of each topic, without getting bogged down in technicalities. We will talk amply about open problems.
I am hoping that all presentations will be transcribed as posts on this blog. Thus, feel free to request topics that you want to read about. You will get slightly less weight than the physical audience, but your comments will be heard.

The pilot meeting is this Tuesday, at 3:30pm. If you are in the area and would like to attend, check back tomorrow for the room details.

The topic for the first meeting is convolution and the FFT:
• how to think combinatorially about the FFT
• an Ω(nlg n) lower bound for arithmetic circuits with bounded coefficients [Morgenstern, JACM'73]
• an Ω(nlglg n) lower bound for offline range counting [Chazelle, STOC'95]
• discussion of open problems

## Thursday, November 20, 2008

### Three Days in San Francisco

I started the week with a Misfits concert, those 31-year-old punk classics that have influenced all-time favorites like Slayer and Metallica.

Historical note: If the following are familiar to you...
• "Die, die, die, my darling..."
• "Here in this place lies the genie of death"
• "I got something to say: I killed your baby today"
... chances are it is the Metallica inflections that are now ringing in your head. However, it is worth remembering that these are originally Misfits songs.

I continued with Alistair Sinclair's "Mixing times for the solid-on-solid model". As usual, I think this is great theory, but not theory of computer science. (Here, Mikkel tries to make a similar point, cutting even deeper to define theory of computer science.)
Personal note: Attending such talks is always very interesting to me. In a short previous life, I was a Physicist (I even won 1st and 2nd prizes in the Romanian Physics Olympiad in '96 - '97). This left me with great physics intuition, but not that much mathematical intuition on how to formalize "physics proofs" (at that age, my appreciation of Math was very limited). It is very rewarding to catch up on the mathematical intuition, whenever I get a chance.

Finally, I had a chance to listen to some great music from Nels Cline and his band. This led to the interesting exercise of trying to triangulate Cline's heavy, academic jazz relative to black jazz and the Béla Bartók classical music.

The U.S. is a big country, but there are not many places where you can hear the Misfits, Sinclair, and Cline in a span of three days.

## Monday, November 17, 2008

### STOC

I decided yesterday not to submit anything to STOC, so I spent my most relaxing deadline day yet. For one paper, I found a deadly bug, while for another I found an improvement (moving it back to the column of things I need to think more about).

The main lesson for me was that there are limits to everything, and that dealing with an endless stream of stuff (from my defense, to writing a thesis, to visa issues, to searching for an apartment, to IBM sign on stuff, to paperwork for buying a motorcycle...) can really kill research.

Now I look forward to a year without deadlines (I am on the FOCS program committee). I hope to spend the first month catching up with things, and the rest doing what I actually enjoy doing, i.e. thinking about my problems. If this plan fails, I might have to elope to Africa again for a few months :)

As for this blog, I will probably get back to writing interesting technical stuff soon. I expect the non-technical stuff to be kept to a minimum. (For one, we've got too much blogging in the community, and I'm bored. Plus, I've felt disappointed with the TCS community for quite a while, and there's not much I can say in between lying and insulting some folks.)

## Tuesday, November 11, 2008

### Internet Access

Some 18 days ago, I set up a contract with ATT to get internet access at home. Now, finally, it works. The level of incompetence that ATT demonstrated during this process makes me very happy --- if they ever decide to cut jobs starting with the least competent people in the company, it will be a long while before my research job is threatened.

The main issue was that they sent me a non-working modem, in the most basic sense: the power led didn't come on when I plugged it in (you get an idea of how much quality control is being done). To fix this, I had to assure a lady that I did check several power plugs before waiting on the phone for half an hour to talk to somebody, and then we counted together 30 seconds while I was holding the reset button pressed. When she was finally convinced the thing was broken, she told me the "replacements department" was closed at that hour, and I had to call the next day. (Some operators need to be specially trained to fill out the replacement form?)

After I went through the same routine the second day, the replacement department assured me that they would mail a replacement with overnight delivery. And that's exactly what they did, 3 days later. (I eventually got a tracking number from them, which tells me exactly when the mailing happened.) Somebody should explain that they could probably save money and time by sending things via regular mail, just promptly.

And then comes the most unbelievable part: the package had the wrong address! Yes, I mean the package from the phone company, which should know my address pretty damn well in order to activate my line and bill me. And yes, the package from the same company that had already sent me a modem at the correct address. I just can't believe that the guy at the "replacement department" has to type in my address manually, again!

Of course, the original delivery date had to be on a Friday, so I couldn't pick up the package from UPS until Monday... Hence the whole issue was only resolved today.

## Wednesday, November 5, 2008

• US citizens ellected a professor instead of a military guy to run the country. Maybe there is hope after all.

• I am on the FOCS'09 PC, which basically means that the remaining 2 weeks until the STOC deadline will be crazy.

• As of this Monday, I finally started at IBM Almaden. (I had been stuck waiting for my work authorization for several months.) You can deterministically find me at IBM on Mondays, and probabilistically on other days. Finding me in space might be a bit difficult, since I greatly prefer the hills over my office.

• I am now physically at Berkeley, where I will be visiting each Wednesday and on other random days. I have a desk in Soda 645.

• The day before FOCS, I moved into an 18th floor apartment at the intersection of Market and 10th in San Francisco. The location is a compromise between many constraints...

• My commute plan (to IBM) is:
1. use this to get to the train station (the English word is apparently "scooter", so I call it Vespa 1.0)
2. take the Caltrain "baby bullet" (so called, because it travels slightly faster than the slowest trains in Europe, and decidedly faster than muels)
3. ride a motorcycle (to be bought) for the remaining 12 miles to IBM.

• While you may hear me complain about IBM's location, I must admit that the benefit of a location up on a hill several miles from civilisation is that I share an office with 2 other people, and have a great view of the next wing of the building.

• My way to FOCS involved BART, Caltrain to San Jose, bus to SJC, flight to Santa Barbara, flight to LA, flight to New Ark, NJ transit to Trenton, and SEPTA to Philly. It all took a reasonable 16 hours, and cost under 200 (which is amazing given that I bought the tickets 2 days before, and important because unemployed people can't get their conference travel reimbursed.)

## Wednesday, October 29, 2008

### For SODA attendees

Howard Karloff asked me to post the following:

Outing To See "South Pacific" on Broadway During SODA'09

I have reserved, for SODA attendees and their friends / spouses / significant others, 50 tickets in the loge section at Lincoln Center for the 7:00 PM, Tuesday, Jan. 6 show of "South Pacific," so popular a show that already both Saturday Jan. 3 performances are sold out. If you want to buy one or two tickets, send mail to howard@research.att.com with "South Pacific" as the subject field, specifying the number of tickets you want in the body of the e-mail. Tickets will go to the first SODA attendees who pay by credit card via PayPal. I'll send instructions by e-mail. The tickets are \$120 each--the face value is \$115, and the extra \$5 is to cover the PayPal fee--and are NONREFUNDABLE: once you pay, there will be no refunds. However, I imagine someone at SODA, some random theatre-goer, or an ebay user would be thrilled to take tickets to such a popular show off your hands.

So, please, start those e-mails coming. Should the demand far exceed 50 tickets, I may arrange a second outing, to a different play, either Saturday or Tuesday.

A few reminders: "South Pacific" starts at 7PM, not the typical 8PM start time, on the last day of SODA. The venue is Lincoln Center, not in the heart of Broadway. Once you pay, there's no backing out.

See you in New York in a couple months!

Howard Karloff

## Wednesday, October 1, 2008

### Cheaper Arguments

A New York Times opinion piece spends two pages bashing classical economists for not understanding the computational aspects of economics and phase transitions. But who comes to the rescue? It is not theoretical computer scientists, with all our love of phase transitions and computational economics --- it is the damned PHYSICISTS!

Of course, 90% of this post is meant as a joke :). But I would like to point out that 10% is not.

We have witnessed a trend in TCS to focus on the philosophical implications of our work. But it should be obvious that those same philosophical implications can be obtained through cheaper arguments by other fields. When a new proposal to deregulate the Illinois energy market is made (to take the Times' example), who will be the first to point out a potential issue? The Physicists / whoever decides to run some simulations of the new market over the weekend? Or the TCS researchers, who have spent a month proving that a phase transition occurs, assuming that their precise model makes sense?

The point is that if you only want philosophical implications, a solid proof is not necessary ("Dear members of the Illinois Congress, I know you took the issues pointed out by our colleagues in the Physics Department very seriously, but you should realize they never had a complete proof before!"). Think about how hard it is to prove some things about random graphs or random SAT, even though they are obvious from experiments.

I would hate it if we became so engaged in the market for philosophical implications, that we would sacrifice our core TCS values to avoiding always coming in second place.

## Tuesday, September 30, 2008

### Macs and Romanian keyboards

As I found out the other night, the effects of beer on laptops are not nearly as positive as on researchers.

Having to get a new laptop, I decided to bring a Mac "into the family." Everything seems great so far --- it didn't take more than a day to figure out the basics and install several Gb of software essentials (starting with MacTex and Aqumacs Emacs, on to Unison, and recovering all my files from the MIT servers).

Of course, the transition is helped by my insistence on pretending that my Windows was actually Unix (via Cygwin). It feels good to return to a true Unix (after 6 years or so) and stop the pretending. The Mac's superiority seems undeniable (it is Unix, and therefore strictly better than Windows, and it has a wonderful graphical interface, significantly better than X).

Keyboard layouts. The one thing that MacOS did lack was an ergonomic Romanian keyboard layout. As I mentioned before, I find the standard Romanian keyboard horrible, since it banishes some of the most useful Romanian characters (ășțîâ) to the end of keyboard, where they replace other useful characters ([, ], :, etc). The solution is to put the useful Romanian keys on the Latin letters that are not normally used in Romanian (q->ă, w->ș, x->â, k->î, y->ț). To get the original Latin key, press Alt+key. The mapping may seem ad hoc at first, but my experience is that you learn in within minutes, because ț is right next to t, ă right next to a, ș right next to s, and î right next to i. The credit for the original idea goes to ErgoRomanian, a keyboard layout for Windows.

Download. To get what I wanted, I hacked the standard US layout on the Mac. Here is the resulting Romanian Ergo keyboard layout. For the Romanian flag in the menu bar, also download this icon.

Installation:

2. Log out and back in
3. Go to System Preferences > International > Input Menu. Look for Romanian Ergonomic, and check it.
4. [optional] Click on Keyboard Shortcuts, disable the Spotlight check buttons, and enable the Input Methods ones. This allows you to switch keyboard layouts by pressing Command-Space.
Alternative spelling. Admittedly, the one slightly annoying feature of this layout is the x->â replacement, since x does sometimes get used in Romanian. But if you did not adopt the spelling recommendations of the Romanian Academy (i.e., if you spell pîine instead of pâine), you shouldn't have a problem, since â is a very uncommon letter for you. I made an alternative Ergo-X layout, in which x remains the default, and Alt-x gives you â.

As always, please report any bugs or suggestions.

## Tuesday, September 23, 2008

### Tango trees

At the request of Sanjeev Arora, I prepared the following lecture notes about O(lglg n)-competitive binary search trees (our Tango trees).

The main innovation is the proof of the Wilber-1 bound. As opposed to the somewhat hairy proof in Wilber's paper and in our paper's appendix, I show Wilber-1 by arguing about the problem geometry and maintaining partial sums (forget trees!). Hopefully this gives a more intuitive proof. In any case, it shows the students something very important in its own right.

If you read these notes, I am interested in anything you have to say, including things you didn't understand, or suggestions for clarifications.

## Sunday, September 14, 2008

### SODA (II)

The SODA accepted papers, with abstracts, can be found in this text file, or as a PDF file (curtesy of Suresh).

Each year, looking at the SODA list of papers makes me depressed. It is hard to see --- among all the quantum dogs and ponies exhibiting Braess's paradox in stochastic networks with piecewise linear costs --- how we are working to understand the fundamental questions about computation.

What we're missing badly is innovation in solution space, not innovation in problem space. Remember this when you sit down to work on your next paper.

## Friday, August 29, 2008

### SODA

I am happy to report that our SODA submission on The Geometry of Binary Search Trees was accepted.

This paper works on the old question of competitiveness in the binary search tree model (some old posts of mine: 1, 2, 3), and makes some progress that is not easy to quantify. We propose a geometric interpretation of the problem, which seems to eliminate all the messiness attached to trees, and makes previous lower bounds (the Wilber bounds) very clear. The geometric view is somehow very appealing; a referee called this "an amusing paper" (in a very positive comment), and I will happily agree to this description.

Unfortunately, our work does not lead to a new upper bound, though it leads to a reformulation of an old conjecture. Joan Lucas and Ian Munro independently introduced a natural offline greedy algorithm, which they conjectured to be an O(1) approximation. Speaking informally, the prevailing opinion seemed to be that this had to be an O(1) approximation (modulo technical details in proving it!), but the really interesting question was to show an online O(1)-competitive algorithm. Well, our work shows that this view was wrong: we can make the Lucas-Munro algorithm online, with a constant slow-down.

Thus, if the conjectures of Lucas and Munro are correct, this tree achieves dynamic optimality. This is the first proposal for dynamic optimality after the famous splay trees that started the whole field.

Our geometric view also has consequences for the lower bounds (which are crucial if we want constant approximation). The only known lower bounds were Wilber's 2 bounds from FOCS'06. Wilber's first bound was used in our O(lg lg n)-competitive algorithm. Though Wilber conjectured that his second bound is stronger, we still have no idea how the two compare.

In our framework, Wilber's bounds are special cases of a very natural class of "cut bounds," and they get very simple descriptions. Instead of comparing the two Wilber bounds, we now face a broader question of finding the best possible cut bound. We solve this by proposing a new lower bound that is shown to be an O(1)-approximation to the best cut bound. This supersedes Wilber's results, though we do not know that it is strictly stronger than Wilber's bounds.

## Monday, August 25, 2008

### FOCS Best Student Paper

It seems I won the best student paper at FOCS. Yay. I suppose having 3 of the 5 student papers finally did the trick. :)

The prize goes to Succincter, which seems to make it the first "best student paper" at STOC or FOCS given for a data structure. I can't remember any "best paper" given for a data structure either, though I cannot find these lists. My special thanks for people in approximation algorithms, hardness of approximation, game theory, coding theory, complexity theory, quantum computing, and cryptography for making this possible :)

All in all, I think "Succincter" is a decent pick. It's a paper that might have a big impact on how we think about succinct data structures in the future. It's also a problem that's been pestering me since June'05, when Seth described it to me during my visit at Max Planck, Saarbrücken. (Thanks, Seth!) Finally, it got some brilliant reviews, including one that only said "Yes" and one calling the question a "target known for at least 2 decades".

On this last point, the key lesson seems to be that you should write your introduction in the last 45 minutes before the deadline, after sleeping 2 hours/night for 3 days in a row. After an incoherent introduction, the reviewers will feel the need to sing their praise of the paper. By contrast, as I learned from the reviews of another student paper, it is "incredibly poor taste" to say in your introduction that your results are clean, or, god forbid, explain how they simplify a proof by some other people.

## Friday, August 22, 2008

### Olympics

It's been a bad olympics year...

In rowing/women's eights, Romania got a scandalous Bronze, breaking a streak of Golds lasting since '92. It was also the first time since 1976 when they didn't get Gold or Silver.

Gymnastics disappointed badly, with nothing more than a Bronze in women's team and a Gold in women's floor (compared, say, to 4 Golds + 3 Silvers + 3 Bronze in Athens 2004).

Handball is bound to finish on the 7th or 8th place. As a Romanian editorialist aptly noted, the intensity of online swearing that this has produced was previously reserved for soccer.

But above all, Romania got 1 Gold, 1 Silver, 1 Bronze (and 1 nothing) in the IOI happening this week. While the team deserve our warm congratulations, we must be honest and say that this is a disappointing result. In my years, we got 2 Golds + 1 Silver + 1 Bronze several times, and we kept thinking that we should do better...

Nevertheless, our IOI performance was stellar compared to what Romania did in the IMO. For a country used to perfect scores and top participants, getting no Gold in IMO'08 is outright abysmal.

Romania has to get its act together before it's too late. The one thing that we cannot afford to learn from Europe is their acceptance of mediocrity. It is not particularly bad being a mediocre Westerner, in no small part due to a pervasive feeling of entitlement. But Romanians share no feeling of this sort. In the global conscience, the mediocre Romanian is the strawberry harvester of Spain, the construction worked of Israel, and the purse snatcher of Italy. Without a constant flow of outstanding results, these images will define how the nation thinks of itself.

## Tuesday, August 12, 2008

### Puzzles

I have a deep aversion of the "puzzle" concept. Delving into a problem is a very taxing process for me, and I just refuse to do it for the gratification of solving something that people actually expected me to solve fairly quickly. My brain can only internalize so many concepts in one day (like, maybe 2), and I can't waste this resource just so I can feel good about solving a small little problem.

Thus, when I read a recent blog post about how a theorist and two mathematicians spent their time after meeting randomly on a bus tour, I felt as if I was reading about an entirely outlandish experience, and I couldn't stop thinking "Why the heck... I can't believe they actually did this..."

Of course, I reminded myself that many people seem to love puzzles. An old friend used to say that "the brain doesn't rest, it atrophies." My adviser's office is the nightmare of any claustrophobic person: it is overflowing with small physical puzzles. I often fidget with them when I'm talking to Erik. The fact that I usually "solve" these problems by 5 minutes of random hand movement only confirms that I should never think about such things :)

My brain applies the same self-defense strategies when it comes to olympiad problems, which is why you don't see too many olympiad problems on this blog. When I originally read the Dwarves problem, I said "DP" (dynamic programming) and stopped. Only the next day, when 3 IOI guys claimed they really couldn't solve it, did I persuade myself to think about it...

## Thursday, August 7, 2008

### Thesis Defense

Yesterday, I defended my non-existent thesis, apparently with success. (The thesis itself will be done on August 29, at or around 2:58pm. There are plans to make it readable.)

Here are the slides from the defense in PPTX (also saved as PPT with minor screw-ups). Sorry, no reasonable PDF. Due to lack of time in making the slides, a lot of the presentation was verbal commentary, but hopefully the slides also have some value.

In other news, I am once again fed up with Powerpoint, and I will be switching back to LaTeX/Beamer. Last time I quit Beamer because xfig sucked, but in the mean time I discovered TikZ and it is impressive.

By the way, when discussing the history of cell-probe lower bounds, it occurred to me that the two major foundational papers that really started the whole field were:

• [Ajtai 88], published in Combinatorica, but proving a false result.
• [Fredman, Saks 89], published in STOC, containing tons of claims without proofs, and not followed by any journal version.
Idiots. It's not as anybody will remember them 20 years later for starting an entire research field. Research is about proving immortal theorems that represent absolute truth. This requires triple-checking of all proofs, and inclusion of absolutely all details (even in SODA submissions). The proofs of such absolute truth must be deposited in journals for perpetual archiving*, thus preserving the name of the author forever.

[[ *Though paper is an almost perfect solution to preserving your ideas into cold immortality, some care must be exercised. To prevent ware and tare, it is recommended that your piece of absolute truth does not motivate any reckless readers to actually open the journal at the pages of your paper. ]]

Incidentally, these two papers are also the "second paper" in the field (after Andy Yao defined the model a decade earlier). This reminded me of Luca's very sensible "second paper" observation.

## Sunday, August 3, 2008

### Algorithms for Farey Sequences

I recently uploaded the final version of my paper with Jakub Pawlewicz, due to appear in Algorithmica. The paper has a sparkling story (from my own perspective, at least) that should be told.

Starting research. In my glorious freshman year at MIT, when I was working on P vs NP and convincing random professors to pay me, I was trying to understand what research meant. This was not an easy task, since the closest thing I had to a mentor was Alex, who had just started research the previous summer. (Erik didn't quite qualify, since my second meeting with him was 3 or 4 months after he had started paying me.)

In any case, the lesson that I managed to absorb from the environment was that you're supposed to ignore all the cool stuff that's in books, and come up with new algorithms that were not known before Earth was graced with your existence. Then, you write papers describing these new algorithms, and you join the cool club of people who are in the business.

Judging that I might not have a paper on P vs NP soon, I decided to start looking for other problems, and I remembered a book on algorithms that I had read in middle school. This was the kind of book that Romanian associate professors write (because you need to have a number of books before becoming full professor): it contained all sorts of unrelated random topics that the author had come across since writing his previous book. Next to planar closest pair in O(n lg n) was a discussion of Farey sequences and an optimal algorithm for generating them. (See my older post for a definition of Farey sequences and a cool application.)

As soon as I remembered this algorithm, I saw potential for a "result": if we ask for just the kth element of the sequence, can we obtain a sublinear algorithm that doesn't generate the whole sequence? Here "sublinear" means better than O(n2), because the Farey sequence of order n has O(n2) elements. Of course, there is no real motivation to this problem, but this didn't bother me at the time.

A result. Soon enough, I had an algorithm running in O(n lg n) time, and summer was coming up. I was a member of the Scientific Committee of the Balkan Olympiad in Informatics happening that summer, so I assigned the problem in the competition. (Don't worry, I'm not a big fan of assigning "unrealistic" problems, so my time bounds allowed for an easier and less efficient algorithm that I had discovered at first. Even so, it turned out to be the perfect "hard problem," that required some unusual ideas and was solved only by a couple of people.)

Returning to "research mode," I used Google to check if my result was known (seemed not), and discovered the Algorithmic Number Theory Symposium (ANTS). I then wrote a paper with my ex and sent it to the conference. Looking at it in retrospect, it looks like a very childish paper. Nonetheless, Math conferences are not competitive, and it got accepted. The referee report contained the best polite equivalent of "the authors don't know what the heck they're talking about" that I have yet seen. It read: "The authors unintentionally hide the fact that the quantities A(.) that they define in the course of the solution are actually the Mertens function."

At the conference, people were entertained by the paper. They asked if we could get an O(poly(lg n)) algorithm on a quantum computer (I maintain my original response: What??), and asked whether we could count primitive lattice points inside polygons efficiently. A primitive lattice point is a point (x,y) where x and y are coprime; the Farey problem can be reduced to counting primitive lattice points in a special class of triangles.

I kept thinking at odd times about getting a faster algorithm, and about counting primitive lattice points in larger classes of polygons. I had a complicated algorithm running in O~(n3/4) time, and some results for primitive lattice points. However, by then I was engaged in doing research on more high profile problems, and I could never get myself to write another paper on this topic.

Shock and awe. As it turns out, not publishing a follow-up was a brilliant decision. Last year, Krzysztof flew to California for my birthday party. Before the discussion got elevated by consumption of alcoholic beverages, he managed to tell me that Jakub Pawlewicz, a student at his alma mater in Poland, had written a follow-up paper about algorithms for Farey sequences. As it turned out, Jakub had a very nice algorithm achieving O(n3/4) time.

At first, I was amused and surprised by the fact that someone had actually picked up the problem! Then, I found out that the paper was accepted to ESA'07, and I was even more surprised (I had never considered mainstream CS conferences for such a problem). But only when I found out that it got the Best Student Paper Award at ESA, was I totally blown away!

Now, had I published my follow-up paper, then almost certainly history would have been different. I would have never found out that the best student paper at ESA can be won for a follow-up paper to something I did in freshman year! As you can imagine, this made for some entertaining pub discussions, like:

Admired top-notch researchers get research awards. Also, there are some godly figures, so established, so influential, that research awards are being handed out for works in the fields that they created. But who else can claim that research awards are being given for work in a field that they introduced in freshman year? :)
The aftermath. Despite the entertainment value, getting scooped was not entirely a nice feeling, since I am, like any researcher, a bit attached to my results. My consolation was that Jakub is also a former medal winner at Informatics Olympiads (IOI and CEOI), so at least I had been scooped by a very worthy person.

Fortunately, I lucked out for the second time. I asked Jakub for the paper, and his solution was so clear and elegant, that I found it easy to plug my old ideas into it. Within the hour, I saw how to improve his algorithm to O(n2/3) and was writing him an email about it. Yes, I imagine he hates me for this episode :)...

In the end, we merged the two results into the paper I mentioned in the beginning, which appears in the Algorithmica special issue for ESA'07. This was the ideal outcome for me: I got my ideas published with minimal effort, and with a bonus story.

## Friday, August 1, 2008

### Open Access?

I recently received an invitation to join the editorial board of a new journal called Algorithms, which claims to be an open access journal. Circumstantial evidence suggests the invitation was distributed to more than a handful of people. The list of people who have already accepted contains some established members of the community, as well as many names I have never heard before.

The main idea of this particular publisher is to have a publication model in which authors pay to get published (in the neighborhood of 1000 dollars!), and readers can access the papers for free on the Internet. Though you may choose to call this "open access," I profoundly dislike the name. As soon as you attach a big cost at either of the two ends of the business (publishing or reading), it stops being "open." It seems to me that we have another case of a creative publisher trying to scheme us into paying them large amounts of money for no value added.

You will not find my name on this editorial board.

While on the topic of open access, I must say that all my support is behind Theory of Computing. This wonderful initiative gives us a truly open access journal (zero cost for everyone), and a journal of superb quality. Based on articles published so far, I view ToC as being in the same constellation with SICOMP.

In the unlikely future universe in which I will not be overcommitted by several notches above the sanity level, I will be able to do things without deadlines. Then, I may write some journal papers without the deadlines/incentives of special issue, and I will try to send them to ToC.

## Tuesday, June 24, 2008

### Dwarves

Last week I was at the Romanian training camp for the IOI, after several years of absence. (If you don't know what I'm talking about, I wrote a series of posts about informatics olympiads a while ago.) To my great surprise, I was still able to solve the competition problems :)

Unlike Math, CS doesn't have a culture for tough puzzles, i.e. problems that are not "important" for any reason, but are fun and intellectually challenging. Perhaps the difference is that CS folks are vastly superior to Mathematicians when it comes to bull-shitting (our ability to draw targets around any arrow we shoot makes all our problems "serious research"...)

In any case, here's a rewarding problem from the competition, for your own enjoyment. It captures my intuitive notion of a "CS puzzle" very well, but beware: it is not a trivial puzzle. (It may have taken me one hour of thinking, of course in my current rusty state.)

Dwarves. n dwarves fell in a hole that is H meters deep. Each dwarf is characterized by the distance from his feet to his shoulders (hi), and the length of his arms (li). Dwarves can pile up as a tower, with each dwarf sitting on the shoulders of another. The dwarf at the top of the tower can climb out of the hole if his hands, stretched up, can reach to the top.

Given n, H, hi, and li, find the maximum number of dwarves that can escape from the hole (through forming towers as above; of course, once a dwarf escapes he cannot take part in another tower).

Desired running time: O(n2). Can you do better?

## Friday, June 20, 2008

### FOCS and Euro

I finished watching a spectacular game at Euro 2008 between Turkey and Croatia. It went into overtime with both teams obviously stressed by the importance of the match. Croatia scored 3 minutes before the end of overtime, prompting a huge display of joy among supporters. But Turkey never stopped believing, and in minute 122 (two minutes past the official end of overtime and seconds before the final whistle) scored to tie the game. Then the joy of Turkish supporters made the Croatian moment seem like nothing. Turkey eventually won on penalty kicks.

I then returned to life, and checked to see why my Blackberry had been buzzing so much. I saw 4 accept notifications for FOCS 2008, and realized that supporters may cheer, but it's nothing like the feeling of joy for the players.

As always, my 4 submissions can be found on my papers page (top 4).

## Thursday, June 19, 2008

### LSD Randomized Lower Bounds

Apparently a few people took issue with my (Data) Structures paper because it claimed a randomized lower bound for LSD without a proof, and this propagated to the FOCS PC. I recently received an email from the PC asking for a sketch of the proof, pronto.

As I explained before to anon commenters on this blog, I don't know what the big fuss is about. The paper is certainly not trying to claim credit for this proof (it is not even mentioned in the introduction). It's just trying to say "yeah, we know how to do it, and it's not interesting; don't waste your time on it." The results of the paper are interesting independently of any LSD proofs. If you don't like my claim, you only get deterministic lower bounds (see here for deterministic LSD lower bounds, which were known since STOC 95). No big loss.

But since I had already claimed that the randomized LSD lower bounds are straightforward (once you understand the literature), I had the moral obligation to support my claim. So here is my PDF response, in which I give a (sketch of a) proof for the randomized bounds. Don't be too harsh on this; due to the whole context I only had a few hours to write the thing, so some calculations of constants are left out. The writing is also bad, but hopefully if you're actually interested in the topic you already know enough to follow.

I think we need to grow up as a discipline, and understand that the ideas of a paper are not measured by the formula depth. If it's painfully complicated (which this proof is), it doesn't mean it's actually interesting or cool or worthy.

## Saturday, June 7, 2008

### Being Rich (II): Motivating LSD

We now continue our introduction to asymmetric communication complexity and its applications. In the first episode, we showed a deterministic lower bound for Lopsided Set Disjointness: Alice and Bob each have a set (of very different sizes), and they want to communicate to determine whether the sets are disjoint.

But are we using LSD just for entertainment, or is it a fundamental to our understading of the world? (Ahem.) In this post I want to convince you that LSD is a truly fundamental problem, something like the root of all evil in data structures. You will hopefully be motivated to continue watching this "Being Rich" series very carefully.

The central importance of LSD was understood in a recent paper entitled (Data) Structures that I submitted to FOCS. Quite possibly, it is the best paper I've written so far.

In this paper, I show that a lot of data-structure lower bounds can be shown directly by reduction from set disjointness (and by a lot, I mean almost all known ones, and several new ones). This leads to greatly simplified proofs of many known results, as well as several new and interesting lower bounds.

Since a picture is worth 1000 words, here it is:

For the problems in red, we get better results that what was previously known. For the rest, our reductions simplify existing proofs. The solid arrows are the new reductions, where all the magic happens. The dotted arrows are known or folklore reductions.

If you don't know what these problems are, or if you want to know about the reductions themselves, just hold until the sequel posts. This post is merely ment as an appetizer :)

Note that our tree contains problems from very different "classes" of data structures, for which previous lower bounds used very different techniques with with no suspected relationship:

• dynamic problems, where we study the trade-offs between update and query times.

• "easy" static problems, which can be solved in some poly(lg n) time with space O(n polylog(n)). One usually asks for the best possible query time with space O(n polylog(n)).

• "hard" static problems, typically suffering for a course of dimensionality. Upper bounds typically involve very large space (often superpolynomial).
The way I see it, this paper is a classic example of scientific luck :) Each reduction is technically easy, but the overall result is conceptually hard: you need 2-3 reduction steps, and you need to magically come up with the intermediate problems in the reduction chain (the most unexpected being reachability oracles in butterfly graphs). I was very lucky to be looking at precisely the right problem at the right time, and this beautiful tree suddenly came together.

To finish on a funny note, let me summarize the 3 different feelings that I have had towards this paper:
• Oh cool! Putting structures in "data structures." Now the complexity types have no excuse not to pay attention :)

• Finally, I can teach some lower bounds! All I need is a very simple bound for LSD, and then it's all clean reductions instead of lower-bound mess. I can even assign some of the simple reductions as homework!

• :( ... The beautiful theory and understanding that we've been building for 20 years collapses to one single problem. We know so little. We're now just like main-stream complexity, big dreams and few proved lower bounds.

## Tuesday, June 3, 2008

### Best Of, Take Two

First of all, appologies for the last post. I managed to explain the purpose of the game very badly. It generated a long list of names of very common suspects, which of course contained zero information.

Now let's try to fix it. Please nominate your favorite theory researcher, together with a 3-line description of the reasons for your nomination. I imagine a comma-separated list of results would work very well, as would more complex explanations.

With this ammendment, maybe we can answer the original questions of (1) understanding how we appreciate researchers these days -- actually state a short explanation for why we value these people; (2) having a somewhat meaningful narrative for the junior people who might ask such a question -- a list of names without any justification is not so inspiring, since they haven't been exposed to our mob's peculiar mentality.

Also, here are the rules to keep this interesting and decent:

• only post anonymously;

• feel free to ask for clarifications on somebody else's nomination. What the heck, post rebuttals if you like;

• understand that this is just a summer game for a bit of fun and a bit of understanding the community we live in (I think it would be enlightening to see what our peers value);

• focus on the goal is to understand what we value, and ignore the impact that your nomination (or rebuttal?) might have on a specific person. Of course all these people are too senior to care whether some anonymous commenters on my blog like them or not :) You don't need to make them happy, and there no way you're realistically going to insult one of them...

• don't complain that there's no way to compare so many uncomparable people. I am hoping we're all old enough to understand the impossibility of such a pure comparison. Be subjective! That's what we want to understand -- out community's subjective thinking.

### Best of?

Today was the third time in a couple of months when I was asked to make a "most super of the superstars" list for TCS. I never had anything close to a good answer, so let's hear it from the readers of this blog :)

Please nominate people for the following 2 categories:

1. "best" 5 TCS researchers ever;
2. "best" 5 TCS researchers based on work from the past 15 years only.
If this is not obvious, the purpose of the best-of list is not to give these people some praise. I'm sure they couldn't care less about how much some anonymous commenters on my blog like them :)

It's also not to say that brilliant work in TCS is concentrated in the papers of these 5 guys. Some of the best results ever came from people with just 1 or 2 nice results in their entire career, and presumably these people will not be on the best-of list.

The purpose of these nominations is to see what we tend to appreciate in TCS these days, when it comes to appreciating researchers instead of results. From the questions I'm getting, it seems junior people need a few role models while struggling to get started, and it would be nice to let them pick an idol or two :)

This is one of the few posts where I would appreciate anonymous responses, but please think seriously about your nominations (top 5 makes for a nontrivial threshold).

## Friday, May 23, 2008

### Being Rich (I)

[Updated May 26: writing improved based on a "referee report" by an anonymous commenter. Let me also point out that use of paper and pencil while reading this text is encouraged.]

Let switch gears from politics to science... I am going to run a short series of posts talking about asymmetric communication complexity and how it relates to data structures. In this post, I start by defining the problems and the model, and give a simple (but very interesting) example of a lower bound.

No background is assumed. I believe a high school student should be able to follow this as a gentle introduction to lower bounds. (Yes, yes, I mean a high school student educated in Easter Europe, who knows the European "basic Math." For example, we use (1 + 1/n)n --> e at some point.)

If there are steps that you want clarified, you are welcome to post a question.

Set disjointness. Today, we start with a simple, abstract problem: set disjointness. Let's say Alice has a set S, Bob has a set T, and they are trying to communicate somehow, to determine whether S and T intersect. To quantify the problem, say |S|=n, |T|=m, and both sets come from a universe [u]={1,...,u}.

For now, we will only be interested in deterministic communication protocols (as opposed to protocols using randomization). In "symmetric" communication complexity, we are primarily interested in the dense case, n=m=Θ(u), and we ask how many bits of communication Alice and Bob must exchange to solve the problem correctly.

The trivial upper bound is u+1: Alice sends a bit vector of size u, specifying her set, and Bob replies with the answer. Alternatively, Bob can send his bit vector, and Alice computes the answer. It can be shown easily (see below) that any protocol must use Ω(u) bits of communication in the worst case, so the trivial protocol is asymptotically optimal.

In the asymmetric case, assume n<<m, and m=Θ(u). Because the input sizes are rather different, it is more interesting to measure the number of bits sent by Alice and Bob separately, instead of measuring the total communication. Denote by a the number of bits sent by Alice throughout the protocol, and b the number of bits sent by Bob.

Clearly, there is a trade-off between a and b. The trivial protocols from above give two points on the trade-off curve. Alice can describe her set using a = lg(u choose n) = O(n lg(u/n)) bits, and Bob replies with b=1 bit. Alternatively, Bob can describe his set using b=u bits, and Alice replies with a=1 bit.

Pause for a second, and try to come up with the best trade-off curve interpolating between these two extreme points.

x
x
x
x
x
This space intentionally left blank.
x
x
x
x
x

Here is how the trade-off looks like:
Values of a = o(n) are ineffective, i.e. Bob cannot save asymptotically over sending u bits. Similarly for values of b=o(n). The interesting portion of the trade-off is the curved one, which is described by: b = u / 2O(a/n).

Here is how we can achieve this trade-off. First, let k≥a be a parameter. We break the universe [u] into k blocks of roughly equal size, u/k. Now:

• Alice begins by specifying the blocks containing her elements. This takes a=lg(k choose n) = O(n lg(k/n)) bits (if there are fewer than n distinct blocks, pad arbitrarily).
• for every block containing an element of Alice, Bob sends a bit vector of size u/k, specifying which elements are in T. This takes b = nu/k bits.
• Alice replies with one more bit giving the anwer.
We have a=O(n lg(k/n)) and b=nu/k. Now eliminate the parameter: k=n*2O(a/n) and thus b = u / 2O(a/n).

Lower bounds. We are now going to prove that this trade-off is the best possible for determinstic protocols. This proof originates from [Miltersen, Nisan, Safra, Wigderson STOC'95], the paper that defined asymmetric communication complexity.
Without disparaging this great paper, I must say that the presentation is awful. The authors fail to realize the vast conceptual contributions that their asymmetric communication model can make. Think of the implications to understanding social interactions between humans (potentially, we may finally understand communication inside a marriage!). Instead, the authors chose to concentrate on boring technical aspects, like showing that their concept can prove lower bounds for computational problems.
To prove lower bounds for set disjointness, we are going to look carefully at the truth table of the function. This is a gigantic object, a 2D array with (u choose n) rows (corresponding to Alice's possible inputs), and (u choose m) columns (corresponding to Bob's inputs). Every entry is 1 if the set described by the column is disjoint from the set described by the row, and 0 otherwise.

The starting point of most communication lower bounds is the concept of (combinatorial) rectangles. A rectangle is a matrix minor of the truth table, i.e. a set AxB, where A is a subset of the rows and B is a subset of the columns. [Warning: this does not look like a rectangle in the geometric sense, since the rows in A and columns in B may not be consecutive.]

Suppose you are an outside observer, who doesn't know the inputs of Alice and Bob, but watches the communication taking places and tries to guess the inputs. After seeing some transcript of the communication, what have you learned about the input? It turns out, the possible problem instances that lead to a fixed communication trascript are always a combinatorial rectangle!

This can be seen by induction on the communication protocol. Before any communication, any inputs look plausible to the outside observer, i.e. the plausible inputs are the the entire truth table matrix. Say that in the next step, Alice sends a bit. This breaks the plausible inputs of Alice in 2 disjoint classes: the inputs for which she would send a 1, and the inputs for which she would send a 0. Observing the bit she sent, your belief about the input changes to a subset for Alice, and does not change in any way for Bob. Thus, your belief changes to a subrectangle, that drops some of the rows of the old rectangle. By analogous reasoning, when Bob sends a bit, your belief changes by dropping some columns.

Communication lower bounds follow by proving two facts:
1. If the communication protocol is short, the rectangle reached at the end is "large". (Intuitively, there weren't many steps of the induction to shrink it.) But in the final rectangle, all entries must be identical, either zero or one, because the protocol finishes by announcing the answer to the problem. In other words, if the protocol finished by announcing an answer, and there's still a plausible input for which the answer is different, the protocol is sometimes wrong.

2. Combinatorially, one shows that any large rectangle is bichromatic (contains both zeros and ones).
We are now going to show lower bounds for set disjointness, implementing these 2 steps.

1: Richness and large rectangles. How do we prove a useful result saying that the final rectangle must be "large"? For this, [MNSW] introduce the notion of "richness" (I don't know the story behind the name). We say (the truth table of) a function is [U,V]-rich if it contains at least V columns, each of which has at least U one-entries.

Lemma: If Alice and Bob compute a [U,V]-rich function by communicating a total of a, respectively b bits, the function contains a rectangle of size (U/2a) x (V/2a+b) with only one entries.

Proof: By induction on the length of the protocol. Let's say that we are currently in a rectangle AxB that is [U,V]-rich. We have two cases:
• Bob communicates the next bit. Let's say B0 is the set of columns for which he sends zero, and B1 is the set for which he sends one. Since AxB contains V columns with at least U ones, either AxB0 or AxB1 contain V/2 columns with at least U ones. We continue the induction in the [U,V/2]-rich rectangle.

• Alice communicates the next bit, breaking A into A0 and A1. Each of the V columns that made AxB rich has at least U/2 ones in either A0xB or A1xB. Thus, in either A0xB or A1xB we have find at least V/2 columns that have at least U/2 ones. We can continue the induction in a rectangle that is [U/2, V/2]-rich.
At the end of the protocol, we reach a monochromatic rectangle that is [U/2a, V/2a+b]-rich. Since the rectangle has nonzero richness, it contains some ones, and therefore it contains only ones. Furthermore, it must have size at least U/2a by V/2a+b to accomodate the richness.

2: Rectangles in set disjointness. Remember that we are interested in the case of a dense T; let's assume m=u/2 for concreteness. A column of the truth table is a set T of m=u/2 elements from the universe [u]. For each T, there are (u/2 choose n) sets S which are disjoint from T. Thus, the problem is [(u/2 choose n), (u choose u/2)]-rich. By the richness lemma, we obtain a one-rectangle of size (u/2 choose n) / 2a by (u choose u/2) /2a+b.

Assume we have a rectangle {S1, S2, ...} x { T1, T2, ...} that is all ones. Then, evey Si is disjoint from every Tj. Defining S'= S1 ∪ S2 ∪ ... and T'= T1 ∪ T2 ∪ ..., it must be that S' is disjoint from T', therefore
(1) |S'| + |T'| ≤ u.
But also, the size of the rectangle is at most (|S'| choose n) by (|T'| choose u/2), because every row is an n-subset of S', and every column an m-subset of T'. Therefore:
(2) (|S'| choose n) ≥ (u/2 choose n) / 2a
(3) (|T'| choose u/2) ≥ (u choose u/2) / 2a+b
We now pull the following binomial inequality out of our hat:
(A choose C) / (B choose C) ≥ (A/B)C
Then (2) becomes (u/(2|S'|))n < 2a, and thus |S'| > u / 2O(a/n). From (1) we have |T'| ≤ u - |S'| ≤ u (1 - 2-O(a/n)). Applying the binomial inequality to (3), we have:
(u / |T'|)u/2 ≤ 2a+b => (1+2-O(a/n))Θ(u) ≤ 2a+b => eu/2O(a/n) ≤ 2a+b => b ≥ u / 2O(a/n), QED.
The first implication used 1 / (1 - ε) > 1 + ε. The second implication used (1 + 1/A)B = ((1 + 1/A)A)B/A = eΘ(B/A).

### The Great Conceptual Debate

If you're a theorist and you haven't been hiding at the South Pole in the past month, you probably know about the great conceptual debate, initiated by this letter, discussed at STOC (great coverage by James), and recently picked up by Michael and Luca. In general, I found the opinions of James and Luca to be close to mine, and I much enjoyed the way they expressed their thoughts. Let me now expand on a few bits of my opinion that I did not hear somewhere else already.

Philosophy. First, we begin with a joke:

While the university is planning its budget for the next year, the Physics department puts in a request for 1 billion dollars for a new accelerator. The president of the university goes to the head of the department, and complains:
"Why can't you guys be more like the Math department? All they need is pencils, paper, and waste-paper bins..."
"Or better yet, why can't you guys be like the Philosophy department? All they need is pencils and paper."
The great danger that I see in our current trends is that we may be moving towards a philosophy department (and we don't want that, if for no other reason then because we don't envy the funding and respect they get).

With every new model from a new field that we understand only partially, and with every problem open to endless interpretation over a beer (like modeling communication with aliens or social networks), it becomes harder and harder to say what should make it to the waste-paper bins.

A theoretical field is meant to generate depth, and we should never forget that depth is our only strength. I would say that in TCS, the conceptual contributions we make when introducing new models are nothing compared to the conceptual contributions we make in developing proofs.

The only place where we can make a difference is in developing brilliant ideas for hard problems. We will never beat more practical fields at their favorite game (modelling many different problems intelligently, and recasting known theoretical ideas in that framework). And this is not what we should be trying to do.

I should emphasize that my point is not חדש אסור מן התורה. We need to adjust to a changing environment. But the rate of introducing new problems should be kept very low (I would say, even lower that we have it now), to give us time to concentrate on deep solutions. And we should be wary of problems that are an endless modelling game.

The AI lesson. If the Philosophy department seems too far away, let us focus on something across the hall from us. Do you remember the period when AI was obsessed about the "great questions," like what intelligence really is, what knowledge is, what the universal principle is for dividing preprogrammed and learned behavior, etc etc? I was not around the CS departments in the 70s, but I hear theorists were not too deeply respectful of those perennial ideological debates.

Thus, I will not be among the people to welcome papers on a computational view of consciousness, communicating with aliens, etc. This is not because I share the sadly common opinion that this is junk research (see comment 5 here, ahem). Saying that this is junk is typical theory snobbery, and is the last thing we need to be saying. (Plus, some of the guys who were in AI 30 years ago are our colleagues, and I actually like some of those people.)

These things are a valid topic for thought --- but I just don't think we should be the community thinking about them. Theory has a huge advantage in being concrete and objective, inheriting that immortal coldness of Math. I don't want us to lose this advantage because we find questions about consciousness and aliens entertaining. There are other forums for these questions, which also have more experience on how to deal with scientific publication on such issues.

The conceptual letter. After so much debate, dissecting the conceptual letter feels like dissecting a cadaver, but for completeness' sake, here goes:

1. As everyone observed, the conceptual manifesto shot itself in the foot by being too vacuous. What is it really saying? Of course we all want simple and elegant proofs for major open problems with great practical applications. But what is this conceptual business? Since I don't like very under-specified problems rife with ideological debates, I shouldn't be the one trying to define what a "conceptual" paper is. Unfortunately, the letter doesn't do a great job either.

2. As many people have pointed out already, purely conceptual papers are not so easy to gauge, whereas author names are. Making an official push for more conceptual papers can easily politicize the process and give a lot of weight to big names. I wish the signers of the letter (most of them highly influential people) had thought about this more carefully when they were adding their names to the list.

I am told that this effect is visible even in STOC'08. Some people are making statistics on the "big name effect" at this conference (hopefully to be released soon), and I am told numbers look bad compared to previous conferences.

3. As you already know, I disagreed strongly with some decisions by this STOC PC, and I am not the only unhappy person. Unfortunately, the part where the letter is praising STOC'08 is one of the few unambiguous ones...

4. Confusing the notion of concept with the notion of new model is major mistake that we are making. Great concepts are developed all the time in new, beautiful proofs of important theorems. To me as a theoretician, these concepts seem much more important and valuable than modelling a problem correctly.

5.
Trying to distill concepts, explanations, taglines etc in what we have done is a great goal with major impact to our funding, recruiting, status among disciplines etc. But let's spend our energy finding a nice description for some deep understanding that we already have, not searching for some theorems that are an excuse for nice descriptions and taglines.

6.
Referee reports lie big time, because people think being conservative and polite is more important than being honest. In my short experience as PC member, this was painfully obvious. Just because the PC said your paper is not technical enough doesn't really mean this is why they rejected it. It's just something they can say easily, as opposed to attacking your model. I wish PC chairs were much more active in combating such reviews.

That said, I do agree that we enjoy technical difficulty too much. It has happened that we accept a new problem when somebody comes up with a complicated algorithm for it, and then we reject the 2nd paper that has a simple and better algorithm. This is entirely unacceptable.

7.
Yes, we were wrong about some crypto papers in 1982. But mentioning it so often in 2008 is like using the original sin to explain sexism. (Not to mention that the connection drawn to these papers seems wrong, as Luca aptly explains.)

## Sunday, May 18, 2008

### STOC'08 update

My call for confirmation worked. I got a second member of the FOCS'07 PC to confirm that 15 rejections appeared in STOC'08. So pending new developments, let's treat this number as roughly correct.

The next steps are to:

• also get a 2nd confirmation for SODA'08.
• look at previous FOCS / SODA, and see how many rejects appeared in next STOC to see whether the numbers are really different. If you were on a previous FOCS / SODA PC and would like to help anonymously, please let me know... I think these statistics would be an interesting factoid for everybody, regardless of what we think of the current STOC.
To clarify where I'm going with these numbers: my goal for now is to simply get them out. I'll let you, the community, interpret them. My gut feeling is that the numbers are high (15 is roughly a fifth of the program!). Coupled with the unobjectionably low count of algorithmic papers, I think there are good reasons for discontent.

## Friday, May 16, 2008

### Jobs

Normally, Lance has a yearly post asking where people around the theory world ended up at the conclusion of their job search. But this year I'm going to organize a coup :). Please leave a comment and let us know where you or your friends are going next year, if graduating or changing jobs. Many decisions are still to be made, but let us know when you do decide.

For now let me begin with my personal story. The hiring season is finally over for me. It's been a very hard few weeks (deciding what I want to do), and a much harder day telling people about it. I really look forward to getting back to research after this.

The outcome is that I am going to AT&T Labs, the fittest descendant of the legendary Bell Labs and seemingly a good place to work towards a Nevanlinna prize ;). The lab has certainly had its share of corporate nightmares in the past decade, but it seems it is coming back as a major force in this confused landscape of corporate research.

Next year proper, I will be at IBM Almaden, on a Raviv fellowship. I think IBM Almaden has one of the most amazing groups in theory from the US, featuring some 5 theory hires in the past few years, and some true all-time classics (including an almost mythological figure of concrete complexity, Miki Ajtai). The dedication of the relevant people there to "sell" a theory group to the corporation is truly admirable; theory would not be the same without such efforts. It was very difficult for me to reject a permanent offer from this group, but in the end ATT was slightly better for personal reasons.

I am one of those people who treat labs as a long postdoc, and I think my path will be to return to academia after a number of years. For a second, declining university offers to go to labs felt like a step into the void. The decision was not particularly easy, since I had to turn down Georgia Tech, a place with an admirable dedication to theory, who many see as the big rising star in our field; and UCSD, a place with a truly captivating personality, a disarming feeling of friendliness, and some very ambitious plans for the future (I liked to call it the Google of academia).

Why did I choose labs? Hard to say... I could use a few years to work on some problems that I really want to solve. I value industrial experience, and (I think) I'm interested in networking -- SIGCOMM / SIGMETRICS kind of stuff. Things are too dynamic now and I want to keep my flexibility and avoid the big commitments that a university job requires. And, in the end, some of the values I admire the most are courage and ambition, and I should stick to them now.

## Wednesday, May 14, 2008

### STOC 2008

STOC 2008 is coming up in a few days. Though I think it is important to attend STOC/FOCS even when you don't have a paper, I was simply too disappointed by this conference to go.

Scrolling down the list of 83 accepted papers, I could not help marvel at the almost-complete lack of (non-approximation) algorithms from the program. Alas, this was not really for lack of submissions. I know of several papers that were submitted, and in my opinion, should have been very easy STOC/FOCS accepts. (Since these are not my own papers and not yet published, I cannot really talk about them.)

Quite likely, the heavy bias against algorithms was due in part to the composition of the PC, which essentially contained nobody in the area. But another way to view it is that algorithms were collateral damage in the raging war on whether it is conceptually more important to approximate the Stochastic Traveling Dog and Pony Problem with Piecewise Linear Costs, or the Games that People Don't PlayTM. (IMHO, the best papers from these fields always got in; it is only the marginal papers that need a boost for being "conceptual"... But that is a topic for another discussion.)

Based on the rantings that you can hear left and right (and, during this spring's interviews, STOC'08 was a popular topic of conversation), it seems the war might have taken its toll on the quality of the conference as a whole. Reportedly, this STOC contains about 10 papers rejected from SODA'08 and 15 papers rejected from FOCS'07.

If these numbers are true, there is serious reason to worry about what this conceptual drive is doing to our academic standards (no, we don't really believe that all these papers were improved substantially from the past submission...) To quote a PC member from a past conference: "These papers were not rejected for being too conceptual, they were rejected for being too weak."

If you were on the SODA or FOCS PC and would like to confirm these numbers or post your own count, please leave an anonymous comment or send me personal email. The latter is preferable because it makes the message trustworthy. I will post your recount, but your identity will remain forever secret.

## Monday, April 28, 2008

### Christos Anesti

Christ is Risen! to all the Orthodox out there.

At MIT, we use the opportunity to cook some Romanian food and have a party (and an after-party at my house, it seems). As prototypes of our post-communist generation, we don't really believe in anything, including religion. But it is a cool opportunity to get together.

To celebrate this atheist Orthodox party, let me share a timely joke told tonight.

Yitzhak is very sad: his son converted to Christianity. His friends advise him to talk to the Rabi.

He goes to the Rabi and tells him his story.

The Rabi says: "You know, Yitzhak, I had the same problem, and I asked God about it..."

"And what did God say, Rabi?"

"He said: You know, Rabi, I had the same problem... "
Incidentally, I flew back on Friday night, and I'm flying away in the morning... I promise to get back to some blogging in about 1.5 weeks, when my interviews and visits are over.

## Monday, April 7, 2008

### SWAT'08 accepted papers

Via Dense Outliers, the SWAT'08 list of accepted papers is out.

Evidently, if your paper was rejected, it is because *I* thought it was too good for this worthless conference.

Now seriously... if you've never been on a PC, the way these things get decided is the following:

• people vote on what they want to review, by reading the author names (primarily), the titles, and maybe the abstract.

• papers get distributed, and PC members may outsource them to external reviewers. I think it is a good idea to outsource the paper, because an expert might see things that you're missing (like "the main idea appears in this other paper that is not cited"). Alas, for some papers the class of experts on the topic coincides with the list of authors.

• in addition to outsourcing the paper, you absolutely should read it yourself, to adjust the paper evaluation based on the average level of the submissions. Outsiders can easily overestimate or underestimate the level. I got comments like "this paper is crap, but it's good enough for something like SWAT" (for some terrible papers that we trashed very quickly), or "they give a better running time for an important problem using novel ideas, so I'd say it's a borderline accept" (for some of the best papers at the conference).

• after all comments get uploaded, a blogging-style discussion starts, by leaving comments for each paper. Yes, ultimately, your fortunes are decided by some sort of blogging. And no, the comments for your paper are not much better than regular comments on blog posts, though they are more polite because people are not anonymous.

## Friday, April 4, 2008

### Rankings

The well-known (and very often criticized) US News Rankings have been released this year. Here are the ranking for computer science, and specifically for theory. Apparently, you don't need an account to access them.

As we all know, it is a bad idea to take these ranking too seriously, but at least they contain a list of the top schools in some order. For the theory rankings, I would diagree with the position of Stanford (too high) and Princeton (too low).

## Friday, March 28, 2008

### Romanian keyboards

This is a public service announcement for the Romanians in the audience.

Romanian needs 5 letters outside the Latin alphabet (ă, â, ş, ţ, î). In the dark ages of computers, we would just substitute the Latin/ASCII letter for the Romanian letter, sometimes with comic effects (consider tata=father vs. ţâţă=breast :P ). Fortunately, Unicode has been the Internet reality for quite a few years, so we should now spell correctly.

But how can we generate the Romanian letters easily? Romanian keyboards are terrible in my opinion, because they banish these highly used letters to the edge of the keyboard. The alternative I have found is a little bit of freeware called ER1. This keyboard layout replaces unused Latin letters, which are very conveniently located on the keyboard, with the Romanian letters (e.g. q-->ă, w-->ş etc). I found I was able to type at high speed in a matter of minutes.

In Windows, you can change between keyboard layouts with LeftAlt+LeftShift, so switching between English and Romanian text is extremely easy.

## Tuesday, March 25, 2008

### Searching for the right word

In a true liberal-arts school, searching for the right word may take two weeks...

Later:

Attachment:

## Sunday, March 23, 2008

### Easter Aggregates

We celebrate the western Easter (incidentally, not our Orthodox Pascha) with news from around the world:

• via IHT, we hear the opinion of Zhang Qingli (张庆黎), the party secretary in charge of Tibet: "The Communist Party is like the parent to the Tibetan people, and it is always considerate about what the children need. The Central Party Committee is the real Buddha for Tibetans."

• Bin Laden threatens the EU for implicitly endorsing the Danish cartoons. The message features a cartoon of a spear hitting the map of Europe and blood spilling around. Very professional for a terrorist message.

Sometimes, you may think the bad guys stand a chance (like, when Hitler came close to ruling all Europe; or when all the world hates the American war machine and may think Bin Laden can be excused on some points). But fear not --- the bad guys are driven by their extreme ideology, so they are bound to do something extremely stupid sooner or later (like attacking Russia, or picking a fight with mostly neutral Europe).

By the way, if you're in the US or the UK, there's a high chance that you haven't seen the Danish cartoons, since the press here never actually showed them. To see what the rest of the world sees in their papers, go here. Personally, I like this one the most:

• If you're not watching the exchange rates, let me tell you that 1 EUR is close to 1.6 USD these days. We all remember the days when 1 EUR was 0.8 USD, no?

It's funny how the funds, banks and Journals can get excited about the stocks going up a bit every once in a while. Guys, those prices are in dollars! A better option for your money might be a European company heading to bankruptcy.

People (e.g. Muthu) sometimes wonder how to build a perfect research environment, and what it would take to move us all somewhere else (Europe). I never had a very good answer to that, but these days I often think I will not be interested in tenure in the US.

## Thursday, March 13, 2008

### Correctness, conference ranking, etc

I missed a few events on the blogosphere, because I've been on the campaign trail (aka interviewing), but also because I'm not such a regular reader these days. There was a bit of follow-up to my now-famous post on correctness and SWAT (including whining in emails to the PC chair, which I find hilarious --- but YMMV).

Daniel Lemire writes a post essentially saying that top-conferences are for trend-followers who can't have an original idea. Commenters pick on the opportunity to congratulate themselves for all papers they couldn't get into top conferences (after all, those had truly original insights).

Yes, we do have a bit of trend-following and bias towards some topics, but I like to think that is an unfortunate inefficiency in the system, not the model itself. In any case, until we get the perfect conference system, accept the following reality: top conferences give your ideas a broader audience, generate more following, and make life easier for you in terms of funding, jobs, etc.

So for those of you who think you are the hot shot of hot shots and the first to walk on water in 2 millenia... (and I truly hope most of you think that, since my readers come from a community doing advanced research)

... after you have managed to solve the most important problem on Earth, please accept another challenge: that of explaining to the rest of us why this was the most important problem on Earth, and why we should accept your papers. It doesn't need to work from the first attempt, but eventually your goal should be to get your research accepted in the canon, and hence to top conferences. (Guys who walk on water tend to get attention eventually...)

I will not deny that this is often a serious challenge; most times I feel I am up against the current at STOC/FOCS. But we are living in times of extraordinary activism in research, and if you're lazy about taking on the dissemination challenge after solving the technical challenge, you will soon find yourself in the middle of a research community that is just a wrong fit for you.

Michael Mitzenmacher wonders about the role of conferences, and what our stance on correctness should be. I reiterate my point the conferences are for dissemination, and for the very related goal of marking how important some research contribution looks in the eyes of the community. Journals are bad at that, unless we are willing to revamp the system:

• they have slow turn-around time, in part for an unavoidable reason (correctness checking)
• the paper is not compared against a sample of many papers, rather it is evaluated by a non-anonymous editor
• the paper is seen by 1 editor (from a small fixed set), and 1-2 reviewers. In a conference, we have a permanently changing set of people, 3 of which look at your paper, plus a few external reviewers.
Of course, conferences are not perfect, but it seems more productive to fight the problems than to trash the whole system.

Now if conference = badge of quality, what should you do about correctness? I am a big fan of the allowing papers to begin with "This is an extended abstract of a paper that has just been accepted to journal ..."

Of course, this mechanism will not be necessary for most papers, but it fixes a big flaw in the system: how to get dissemination/the quality badge for a result which does not sound 100% plausible, and is not too easily verifiable.