It wasn't always this way. Just a few years ago, I was a graduate student in chemical physics, working on obscure problems involving terms like quantum mechanics, supercooled liquids and statistical thermodynamics. The work I was doing was fascinating, and I could have explained the basic concepts with ease. Sure, people would sometimes ask about my work in the same way they say "How are you?" when you pass them in the hall, but no one, other than the occasional fellow scientist, would actually want to know. No one wanted to hear about a boring old scientist doing boring old science.I sympathize with the old Brumer. Even among academics, I remember the political scientist who had the great opening line "My business is war, and business is good", or even my friend the food scientist who did his doctorate on starch. Much as I get excited about the P versus NP problem and its great importance to all science and society, trying to express these ideas to uninterested laypeople always seems to end up with "Should I buy an Apple or a Windows machine?"People want to hear only about how there's now a cell phone that plays iTunes, or maybe about cool communications that will facilitate emergency responses. But think about all the science that goes into making a cell phone work. Someone had to figure out the equations of electromagnetic waves, circuitry and myriad other scientific details. People have to figure all that stuff out, people who could have made more money and garnered greater prestige had they applied their skills in fields like patent law, business or medicine.
Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Thursday, November 30, 2006
The Social Scientist
Wednesday, November 29, 2006
The Campers and the Bread
Carol get lost in the woods, where she ran into two campers, Alice and Bob, who also were lost. Alice had three loaves of bread and Bob had two loaves. They all agreed to share the bread equally. Carol was so grateful that, when they found their way back to town, she gave the campers $10,000 for saving her life. Alice said she should get $6,000 because she contributed 3/5 of the bread. Bob said that all had eaten an equal amount so the campers should split the reward. To settle the argument they visited the local wise man, a retired math teacher. Which camper was right?Think about the problem. Here is my short version of Marilyn's answer.
Neither. Carol paid $10,000 for 5/3 loaves or $6000 per loaf. So Alice gets $8,000 for her 4/3 loaves she gave up and Bob gets $2,000 for his 1/3 of a loaf.This solution makes sense mathematically but not economically. Suppose Alice and Bob were poor graduate students. Bob would be willing to eat less bread and undercut the price of Alice's bread. To make this point clearer suppose originally Alice had four loaves and Bob only one. Then by the logic above, not only does Alice get all of Carol's $10,000 but also $4,000 more from Bob for the 2/3 of a loaf he gets from Alice.
To do the correct math one would have to know the exact utility functions of Alice, Bob and Carol, or set up an appropriate auction when distributing the bread. But since the money is split after the sharing has been done, Alice and Bob should just take $5,000 each and be happy with it.
Monday, November 27, 2006
Electronic vs Physical Program Committees
Logistically physical meetings have several disadvantages.
 Must somehow cover travel costs of participants. Often this comes out of the conference budget, raising registration rates.
 Since traveling overseas is difficult just for a committee meeting, physical PCs have less international participation.
 Invariably some PC member misses the meeting and has substantially less influence on the choices.
The dynamics of physical and electronic meetings differ. Both start by quickly accepting the strongest papers and rejecting the weakest. In a physical meeting the remaining papers get discussed serially. There is a tendency to accept more often at the beginning, realizing you accept too much and start being more stringent and bouncing back the other way towards the end. One also spends too much time talking about the first set of papers, leading to rushed discussions later on.
In an electronic meeting the discussion on all papers happens in parallel. When discussion seems to go a certain way, the PC chair will suggest acceptance and rejection and sees if someone objects. A vote is taken for a few contentious papers. But many papers have nobody who loves or hates them. For those the PC chair has tremendous power for no one will object to whatever they recommend.
Both types of PCs suffer from groupthink, a tendency for groups to reinforce viewpoints. A PC chair also has to make sure that everyone participates in the discussions.
My preference goes for a third approach that I have seen used in a few conferences. The PC members send their reviews to the PC chair who, after some emails for clarifications, makes all the final decisions by him or herself. Simple and, with a good PC chair, works surprisingly well.
Sunday, November 26, 2006
Victims of the Digital Age
 The Tower Records just near Lincoln Center in New York has a going out of business sale. I used to kill time there before going to a concert or an opera. In fact all the Tower Records are closing down.
 The small Millburn Camera Shop in New Jersey is no longer.
The Millburn Camera Shop supported the amateur photographer with products, advice and specialized film developing and printing services. In high school I set up a darkroom in my basement with equipment from the store and bought my Black and White film in bulk from them. But as today's amateurs now have mostly gone digital, software replaces most of the equipment and developing. Bulk film comes in the form of a tiny media card. And so the friendly neighborhood camera shop disappears.
It has become much easier to access music and to take and process pictures than it ever has in the past. But I will miss the days of browsing music and developing pictures.
An administrative note: Because of a recent large increase in comment spam I now use CAPTCHAtype tests to leave comments. Sorry for the inconvenience.
Wednesday, November 22, 2006
Happy Thanksgiving!
As happens every year I am off to visit my parents for Thanksgiving.
For my fellow Americans, enjoy your Thanksgiving. For the rest of you enjoy the remainder of the week.
Tuesday, November 21, 2006
Microfiche
Many universities have various hidden fees they charge you just as you are about to graduate. Usually these fees total in the $100 range, low enough so that you just cough up and pay them as $100 doesn't mean too much in the grand scheme of life. Still there should be some warning, perhaps in the admissions letter.
Be aware that after you have fulfilled all the requirements, written and successfully defended your thesis, you will not receive a Ph.D. until you have also paid the following fees…But why Microfiche? Wouldn't an electronic copy of the thesis make more sense. Several universities require a bound paper copy, partly for tradition and part just in case the PDF files of today cannot be read by next century's computers. I doubt the last part—there are too many PDFs around today for us not to have a way to look at them in the future.
I was a microfiche wizard in high school. When I did reports on 20th century history, I would go back to the original New York Times articles to get a first hand perspective. But with the Internet and back articles available electronically, microfiche is an aging technology. In the past decade I've used microfiche exactly once—to track down a box score of a baseball game I went to long ago.
I suspect microfiche will go the way of sliderules and typewriters. Before they die, someone (Google?) will scan in the old microfiche and covert them to PDFs. Wouldn't it be better for the Indiana University library to get a free highquality PDF now instead of an expensive scanned PDF in the future?
Monday, November 20, 2006
Since We Can't All Win Turing Awards
To recognize and honor outstanding ACM members for their achievements in computer science and information technology and for their significant contributions to the mission of the ACM. The ACM Fellows serve as distinguished colleagues to whom the ACM and its members look for guidance and leadership as the world of information technology evolves.Since then over 500 fellows have been named including several theoretical computer scientists.
Last year ACM decided that they needed more grades and recently announced their first class of senior members and distinguished engineers, scientists and members. Only a couple of theorists made these lists.
Becoming an ACM Fellow or Distinguished Scientist doesn't make you a better researcher but it does give you a little more clout in the broader CS community. Also having large numbers of Fellows and Distinguished Scientists makes the theory community seem stronger as a whole. So if you know of someone worthy (and eligible) for Distinction or Fellow, go ahead and nominate them and help give your fellow scientists and the theory community the recognition they deserve.
Sunday, November 19, 2006
Favorite Theorems: Nonuniform Complexity
The class P/poly is the set of languages that have polynomialsize circuit families, i.e., L is in P/poly if there is a k, a sequence of Boolean circuits C_{0}, C_{1}, … where C_{n} has n inputs and at most n^k gates, such that and all x=x_{1}x_{2}…x_{n},
Suppose NP is in P/poly and has a (nonuniform) circuit family that accepts it. Karp and Lipton show that NP in P/poly implies collapses in uniform models of computation as well.
The main result shows that if NP is in P/poly then the polynomial hierarchy collapses to the second level, giving us evidence that NP is not in P/poly and hope that we can prove P≠NP by showing superpolynomial lower bounds on the circuit computing some NP problem.
The paper also gives a general (though controversial) definition of advice and a collapse of EXP to Σ_{2}^{p}∩Π_{2}^{p} if EXP is in P/poly (credited to Meyer), and similar results for PSPACE and the Permanent.
Kannan uses KarpLipton to show that some language in Σ_{2}^{p}∩Π_{2}^{p} does not have linearsize circuits, or more generally for every k, there is a language L_{k} in Σ_{2}^{p}∩Π_{2}^{p} that cannot be computed by nonuniform n^{k}size circuits.
Later extensions to KarpLipton:
 If NP in P/poly then the polynomialtime hierarchy collapses to S_{2}^{P} ⊆ ZPP^{NP} ⊆ Σ_{2}^{p}∩Π_{2}^{p}. (see Cai and KöblerWatanabe)
 If EXP, PSPACE or the Permanent is in P/poly then EXP, PSPACE or the Permanent is in MA ⊆ S_{2}^{P} respectively. (see BabaiFortnowLund)
 If NP is in BPP (in P/poly) then the polynomialtime hierarchy is in BPP. (Zachos)
Friday, November 17, 2006
The Future of Science
This problem gets to the heart of mathematics, because mathematical research itself has the property I have described: it seems to be easier to check that a proof is correct than to discover it in the first place. Therefore, if we found a solution to the P = NP problem it would profoundly affect our understanding of mathematics, and would rank alongside the famous undecidability results of Kurt Gödel and Alan Turing.Thanks to Chris Masse for the pointer.
Thursday, November 16, 2006
Pepsi Math
If you buy six bottles then you expect to have one winning bottle top enabling you to get the next two bottles for the price of one, or eight bottles total for the price of seven. But bottles seven and eight have bottle tops too which may be winners. One can continue this process and take the limit but is there a simpler argument?
Soda bottles are interchangeable, a free soda in the future can be exchanged for your current soda. So you can assume that when you get the "Buy One Get One Free" bottle top, your current soda is free. That means you get one free soda from every six, a discount of 16 2/3%.
You get the same discount if the bottle top said "Buy Two Get One Free" or simply "Get One Free". But if the bottle top said "50% off next purchase" which seems equivalent to the original promotion, the discount is only 8 1/3%.
Wednesday, November 15, 2006
Key References
The key references section of a paper points to the most similar previous articles on the same topic that were extended, improved, challenged, or built upon by the paper. Key references allow the author of a research article to highlight the most closely related previous work in the specific topic of the paper. Key references are the natural complement of keywords.An interesting idea. If it is used (and taken seriously) by many authors it might help automated search systems identify important papers in the field.
On the other hand many journals require keywords and AMS classifications although I have rarely seen this information put to good use. For humans a wellwritten "Previous Work" section will have much greater value than just a list of references.
Key References won't become popular unless a major publisher requires them in their journal or conference articles. Would Key References play a useful role or just become one more thing authors have to do to get their papers published?
Tuesday, November 14, 2006
Puzzles That Keep You Awake at Night
Jan and Maria have fallen in love (via the internet) and Jan wishes to mail her a ring. Unfortunately, they live in the country of Kleptopia where anything sent through the mail will be stolen unless it is enclosed in a padlocked box. Jan and Maria each have plenty of padlocks, but none to which the other has a key. How can Jan get the ring safely into Maria's hands?From Seven Puzzles You Think You Must Not Have Heard Correctly (with solutions). For the more mathematically minded here is the Infinite Hats Problem that he told me earlier this year.
A countable number of people each have either a white hat or black hat on their heads. Each person can see everyone's hats except their own. Each person simultaneously announces a guess for the color of their hat. Is there a strategy for the people so that no matter what the arrangement of hats, only a finite number will incorrectly guess their hat color?For more check out his book Mathematical Puzzles: A Connoisseur's Collection.
Monday, November 13, 2006
Virtual Academics
Indeed we now have the technology to have virtual seminars or even entire conferences online complete with "coffee breaks", business meetings and dance parties. Why not even hold an established conference, like STOC or SODA in a virtual world? The total cost would be much less than traveling to a realworld meeting and nearly every aspect of the conference experience could be simulated.
One advantage of a realworld conference is not so much what one can do but what a realworld conference prevents you from doing. While away at STOC you can't teach your course, attend committee meetings, hold office hours, meet with students, etc. You are forced by circumstance to reschedule these activities and open up your calendar to see talks and meet with your colleagues. But at a virtual meeting, can you tell your chair you have to miss your class and the faculty meeting while you sit at your computer, your body in your office but your mind in a different place?
Sunday, November 12, 2006
MathLove Songs
These aren't songs about loving math, these are love songs that use math as a way to express love. There are three that I know of (if you know more let me know). I'm not counting THEORY GIRL which is more of a Comp Sci song.
 The one that inspired this post:
A finite simple group of order two by The Klein Four.
Lyrics are great!
Math is actually HARD!
Singing quality–they shouldn't quit their day jobs.
Video Quality–they just stand around singing.
(Actually they are grad students so its not clear they have day jobs.) 
The Mathematics
of Love
From SQUARE ONE TV, an old PBS show about math (in a low level) that had some nice satires and songs in it. I watched it when I was younger (when I was 30 actually)
Lyrics are nice!
Math is easy.
Singing quality is pretty good.
Video quality–very good for content and quality.
I think this IS their day job. 
8 percent of my
love
Also from Square One.
Lyrics are great!
Math is easy.
Singing quality is pretty good.
Video quality–very good for content, but quality is fuzzy. (I've got a better quality video of this in my collection.)
I think this IS their day job.
Friday, November 10, 2006
Finding Academic Jobs
I am applying for academic jobs this year. How does one come to know about them? Basically the only source I know is the CRA website. DMANET mailing list is also helpful. [And then there is word of mouth—but that seems to favor a privileged few.]Most CS departments list their faculty positions in the CRA News and CACM and many job positions also get distributed over the DMANET and THEORYNT mailing lists. Also check out the departmental home pages of any university where you might have interest. Even if there is no ad you can apply to any department by sending an email to the chair with the usual supporting material (CV, research statement, teaching statement and list of references), though if the department's web page has specific instructions better to follow those. Get all your applications submitted by December 31 no matter how late the stated deadline.I think the way CRA puts ads on its website could be improved a lot. Right now every university puts its ad in unstructured text. Now if I want to know which university has what deadlines I have to manually sift through their ads and the deadline could be anywhere in the text (if it's there at all). Similarly, there are many other attributes that one might want to use as search criteria: such as type of position being advertised, do they need material in hard copy, or in email, or does one need to fill a web form. I think if this were there it'd save some time.
But I think one could go further; though I understand it's probably rather hard to implement what I am going to suggest for all sorts of reasons. Why not make the whole process centralized. At present one has to fill up the forms on the web for many universities which can be really painful. And then sometimes they ask the letter writers to also fill a form. Hard copies or emails are not much better either. What if there were a centralized trusted server where one applicants could submit their information along with the universities where they wanted to apply? And then their application would be delivered to those universities. This would save a lot of pain for everyone.
Don't limit yourself to departments specifically mentioning theory as they will sometimes hire in theory once they fail to find suitable candidates in other areas. You might also consider positions overseas, while professor positions are difficult to find in most countries, there are more postdoc opportunities outside the US. Also consider a broad range of universities in the US, they might have a higher teaching load but you can still have a successful research career.
Make sure your own home page (pointed to on your CV) has online versions of all your papers, contact information, CV and the rest of your supporting material.
A standardized database for recruiting would make life easier for all involved but don't hold your breath.
Thursday, November 09, 2006
Prediction Map Post Mortem
At about 9 AM CST on the morning of election day I made a snap shot of the map for a Discovery Channel Website article.
Every state colored blue was won by a democrat and every state colored red went to a republican. But also note the 69% given to GOP (Republican) Senate control although this election will give control to the democrats. No outcome would have made all the states and senate control agree with the 9 AM map.
Were the markets inconsistent? No, because the markets predict not absolutely but probabilistically. For example, the markets gave a probability of winning 60% for each of Virginia and Missouri and the democrats needed both to take the senate. If these races were independent events, the probability that the democrats take both is 36% or a 64% chance of GOP senate control assuming no other surprises.
Of course the races were not independent events and there are other states involved making it more difficult to compare the probabilities of the individual races with that of senate control.
So how did the markets do as predictors? Quite well as the outcome seems quite reasonable given the markets. Other outcomes would have also been reasonable such as the Democrats losing Virginia and the senate remaining in republican hands, a possibility that came very close to happening.
We plan a map with a better design and more features for the 2008 Electoral College and Senate races. Stay tuned.
Wednesday, November 08, 2006
Podcast Q&A
You can either email me your question on any topic related to this weblog or better yet record yourself asking the question (in either MP3, WAV or OGG) and send me the audio file.
Think of good questions for if we don't get many we'll make up our own.
Tuesday, November 07, 2006
PIR Update
There have been two important NEW results in the field of Private Information Retrieval so its worth reviewing the field and the new results (Some background here).
This post is about InformationTheoretic Private Information Retrieval. We state the problem and five results in order of discovery, with the last two being the recent ones.
PROBLEM: A database is an nbit string (my wife tells me that databases are more complicated than that). The USER wants to know the ith bit but does not want the DB to have ANY CLUE of which bit he wanted.
EASY ANSWER: Request the ENTIRE DB. That is n bits.
QUESTION: Can we do this with substantially fewer than n bits?
ANSWER: NO if there is only one copy of the database.
NEW QUESTION: What if there are k copies of the DB?
 2 DBs, O(n^{1/3}) bits; for k≥ 4, k DBs
O(n^{1/k})
Private Information Retrieval, Chor, Kushilevitz, Goldreich, Sudan, JACM1998, (Earlier version FOCS 95)NOTE: Introduced the field. Journal version has easy constructions. Conference version had slightly harder polyinterpolation constructions material that are a prelude to item (3) below.
NOTE: FOCS version has O(n^{1/k}) result, Journal omits it since item 2 below had already appeared.
NOTE3: k=3 gives O(n^{1/3})—can't use that its 3 DB's instead of 2. 
k DB's, O(n^{1/(2k1)})
Upper Bound on the Communication Complexity of Private Information Retrieval Ambainis, ICALP97,NOTE: Used Recursion. Constant is exponential. Later papers that reduced the constant to polynomial lead the way to the next paper.
NOTE3: k=3 gives O(n^{1/5}). 
k DB's, n^{O(loglog k/(k log k))}
Breaking the O(n^{1/(2k1)}) barrier for informationtheoretic Private Information Retrieval Beimel, Ishai, Kushilevitz, Raymond. FOCS 02.
NOTE: Brilliant use of polynomials.
NOTE3: Techniques yield k=3, O(n^{1/5.25})
 2 DB Ω(n^{1/3}) LOWER BOUND
An Ω(n^{1/3}) lower bound for bilinear group based Private Information Retrieval Razborov, Yekhanin, FOCS 2006.NOTE: Hard paper! Modeled 2DBPrivate Information Retrieval via Latin Squares and then used representation theory of finite groups to push through the lower bound. ALL current 2DB protocols fit the model, so lower bound is either legitimate or will point way to other techniques. My money is on legit. Even so, there aren't that many 2DB protocols so who knows…

3 DB O(n^{1/32,586,658}) PIR!
Really!
New Locally Decodable Codes and Private Information Retrieval Schemes, Sergey YekhaninNOTE: Wins award for largest distance between GREATNESS of content and AWFULNESS of title. I would have called it
A 3 DB O(n^{1/32,586,658}) PIR! Really!
NOTE: Uses Mersenne primes. The number used is based on the largest Mersenne prime known, which is 2^{32,586,658}1. If there are infinitely many Mersenne primes then, for infinite number of n, get k=3, n^{1/loglog n}Private Information Retrieval
NOTE: Vast improvement on k=3, n^{1/5.25}
PIR scheme (2): the new 3DB PIR leads to a kDB, O(n^{1/(bk1)}) where b is enormous.
PIR scheme (3): the new 3DB PIR leads to the same asymptotic kDB n^{O(loglog k/(k log k)} but with a much smaller constant in the Oof term.
Monday, November 06, 2006
Time Zones
But now as an academic living in Chicago I always need to worry about time zones when I coordinate a phone or IM meeting or have a paper deadline. You end up remembering some key rules: One hour to the East Coast, seven hours to Continental Europe except for Portugal which is six hours like London, eight hours to Israel. I always have to remind myself that California is minus two hours not minus three. And of course there is India, currently eleven and a half hours ahead of Chicago. Time zones are relative—your time differences will vary.
Daylight Savings Time adds to the confusion. Europe and Israel have similar time changes but not always changing on the same weekends. India and China don't change their clocks and Down Under they change in the other direction. Savings time also mean extra thinking when converting from UTC time.
Until recently Indiana didn't do savings time but since time zones are relative, it seemed that Indiana changed from Chicago time in the summer to New York time in the winter. Now Indiana follows daylight savings time so most of the state is in New York time year round. I managed to forget the change when visiting South Bend this summer and ended up an hour late to everything.
Technology helps. You don't need to know the time zone when you send email. I used to use the World Clock to keep track of times in other places but now I use the nifty Time in City feature built into Yahoo! Search.
Sometimes time zones can work to your advantage. If you are close to deadline on a paper with a coauthor in a faraway land you can each work on the paper while the other one sleeps. This strategy never worked with my most frequent coauthor Harry Buhrman in Amsterdam. I am an early riser and he sleeps late so we keep the same hours, seven hours apart.
Sunday, November 05, 2006
Fifteen Seconds
What about the elections? No senate race in Illinois but a governor's race where I have yet to find anyone who likes either candidate. We do have two good candidates in my congressional district, but what difference does it make as which party has control of the house is much more important than the views of the particular candidate we send there.
The Illinois politician garnishing the biggest praise is not even running this year, our junior senator and future president.
Thursday, November 02, 2006
A Thesis to Forget
A committee member then asked what happens when you compute the derivative of f.
[From The Way of Analysis by Robert Strichartz]
Wednesday, November 01, 2006
FCRC Deadlines
 STOC, November 20. Undergraduate Research Competition, February 23.
 EC (Electronic Commerce), Abstracts, November 30. Full Papers, December 7. Tutorial and Workshop Proposals, January 5.
 Computational Complexity, December 3.
 SPAA (Parallel Algorithms and Architectures), December 18. Brief Annoucements, January 8.
 COLT (Learning Theory), January 16. Open Problems, February 15.
 Computational Geometry, Titles and Abstracts, November 22. Papers, December 4. Video, February 15. Conference, June 68 in South Korea.
 TARK (Rationality and Knowledge), January 30. Conference, June 2022 in Belgium.
 ICALP, January 25. Workshop Proposals, November 30. Conference, July 913 in Poland.
 LICS (Logic in CS), Titles and Abstracts, January 15. Papers, January 22. Conference colocated with ICALP, July 1014 in Poland.