Electronic vs Physical Program Committees

I have served on program committees that have entirely electronic discussions and others that meet in person. What works better?

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.

On the other hand I have heard that a physical PC meeting rewards the PC members but allowing them to spend time together and enjoy a fine meal.

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.

Victims of the Digital Age

During my Thanksgiving trip two store closings caught my eye.

• 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.

Both of these stores just couldn't keep up with the world of the Internet. Tower Records made their mark by having an amazing collection, one of the best collection of classical in the country in their Lincoln Center store. But their collection cannot compete with online stores like Amazon, Walmart beats them in price on the popular CDs, not to mention the convenience of music downloads, both legal and illegal.

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 CAPTCHA-type tests to leave comments. Sorry for the inconvenience.

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.

Microfiche

A graduate student complained that Indiana University requires him to pay $60 to make a microfiche copy of his Ph.D. dissertation.

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 high-quality PDF now instead of an expensive scanned PDF in the future?

Since We Can't All Win Turing Awards

In 1993 ACM created their Fellows program

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.

Favorite Theorems: Nonuniform Complexity

October Edition

The class P/poly is the set of languages that have polynomial-size circuit families, i.e., L is in P/poly if there is a k, a sequence of Boolean circuits C₀, C₁, … where C_n has n inputs and at most n^k gates, such that and all x=x₁x₂…x_n,

x is in L iff C_n(x₁,x₂,…,x_n)=1. This is a nonuniform model of computation, C₂₇ may have no relation whatsoever to C₂₈.

Suppose NP is in P/poly and has a (non-uniform) circuit family that accepts it. Karp and Lipton show that NP in P/poly implies collapses in uniform models of computation as well.

Richard Karp and Richard Lipton, Some connections between nonuniform and uniform complexity classes, STOC 1980.

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 Σ₂^p∩Π₂^p if EXP is in P/poly (credited to Meyer), and similar results for PSPACE and the Permanent.

Kannan uses Karp-Lipton to show that some language in Σ₂^p∩Π₂^p does not have linear-size circuits, or more generally for every k, there is a language L_k in Σ₂^p∩Π₂^p that cannot be computed by nonuniform n^k-size circuits.

Later extensions to Karp-Lipton:

1. If NP in P/poly then the polynomial-time hierarchy collapses to S₂^P ⊆ ZPP^NP ⊆ Σ₂^p∩Π₂^p. (see Cai and Köbler-Watanabe)
2. If EXP, PSPACE or the Permanent is in P/poly then EXP, PSPACE or the Permanent is in MA ⊆ S₂^P respectively. (see Babai-Fortnow-Lund)
3. If NP is in BPP (in P/poly) then the polynomial-time hierarchy is in BPP. (Zachos)

Using Kannan's proof, (1) implies that S₂^P does not have n^k-size circuit for any fixed k. Can one improve (1) to show that if NP in P/poly then the polynomial-time hierarchy collapses to MA? This would imply MA does not have n^k-size circuits for any fixed k.

The Future of Science

New Scientist celebrates their 50 years by asking about 70 "Brilliant Minds" to forecast the next 50 years of science. Several researchers (all well-known though a few overrated) talk about math and computing including Tim Gowers focusing on the P versus NP problem.

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.

Pepsi Math

I bought a Diet Pepsi yesterday and the label described a bottle top promotion: One in six wins "Buy One Get One Free". Suppose you drink a large amount of Diet Pepsi, what is your asymptotic expected discount?

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%.

Key References

Carlos Castillo asks for comments on his Key References Proposal.

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 well-written "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?

Puzzles That Keep You Awake at Night

Dartmouth Professor Peter Winkler visited our department yesterday and today, the first stop of a two-week five-university tour. Winkler gives great seminar talks and is easy to talk to about hard combinatorial problems. Unfortunately whenever I see him he also brings very tantalizing puzzles that you have to work hard at not thinking about, lest they consume you. For example Love in Kleptopia

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.

Virtual Academics

The Chicago Tribune today had a few articles on Second Life, a growing virtual world that even has its own economic markets with its own currency exchangable with US dollars. As the article says, Harvard Law School taught a class in Second Life and I have heard of many other universities in the process of establishing Second Life courses as part of their on-line degrees. Taken to an extreme, why do we need hundreds of graduate complexity courses taught world-wide every year when everyone can sit in on one of a handful of the best lecturers giving the class?

Indeed we now have the technology to have virtual seminars or even entire conferences on-line 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 real-world meeting and nearly every aspect of the conference experience could be simulated.

One advantage of a real-world conference is not so much what one can do but what a real-world 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?

Math-Love Songs

Guest Post from Weblog VJ Bill Gasarch

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.

1. 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.)

2. 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.

3. 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.

Finding Academic Jobs

An anonymous student writes

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.]

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.

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.

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 on-line 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.

Prediction Map Post Mortem

As I've mentioned before, David Pennock, Yiling Chen and I developed a map predicting the 2006 Senate races based on market prices from tradesports.com. So how did those predictions go? In short you can say the markets predicted every individual race correctly but got the senate wrong, but let us look a little more carefully.

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.

Podcast Q&A

For the next Complexitycast, Bill Gasarch and I will attempt to answer reader's questions. We will pick the best questions and answer them in the next podcast.

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.

PIR Update

A guest post from Bill Gasarch.

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 Information-Theoretic 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 n-bit 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?

1. 2 DBs, O(n^1/3) bits; for k≥ 4, k DBs O(n^1/k)
   Private Information Retrieval, Chor, Kushilevitz, Goldreich, Sudan, JACM-1998, (Earlier version FOCS 95)

   NOTE: Introduced the field. Journal version has easy constructions. Conference version had slightly harder poly-interpolation 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.

2. k DB's, O(n^1/(2k-1))
   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).

3. k DB's, n^{O(loglog k/(k log k))}
   Breaking the O(n^1/(2k-1)) barrier for information-theoretic Private Information Retrieval Beimel, Ishai, Kushilevitz, Raymond. FOCS 02.
   NOTE: Brilliant use of polynomials.
   NOTE3: Techniques yield k=3, O(n^1/5.25)
   

4. 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 2-DB-Private Information Retrieval via Latin Squares and then used representation theory of finite groups to push through the lower bound. ALL current 2-DB 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 2-DB protocols so who knows…

5. 3 DB O(n^1/32,586,658) PIR! Really!
   New Locally Decodable Codes and Private Information Retrieval Schemes, Sergey Yekhanin

   NOTE: 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
   

In the constructions in items (2) and (3) above the k-DB PIR was constructed recursively out of k'-DB PIR's for k'<k. Hence this massive improvement for 3-DB PIRs leads to improvements for these schemes.
PIR scheme (2): the new 3-DB PIR leads to a k-DB, O(n^1/(bk-1)) where b is enormous.
PIR scheme (3): the new 3-DB PIR leads to the same asymptotic k-DB n^{O(loglog k/(k log k)} but with a much smaller constant in the O-of term.

Time Zones

For the first 18 years of my life I never left the Eastern time zone. Everyone I knew including all my relatives lived on the US East coast. I never had to do time conversions.

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 co-author in a far-away land you can each work on the paper while the other one sleeps. This strategy never worked with my most frequent co-author Harry Buhrman in Amsterdam. I am an early riser and he sleeps late so we keep the same hours, seven hours apart.

Fifteen Seconds

The University of Chicago wrote a press release about the prediction market maps for the Senate and Governor races that I created with Yahoo!'s David Pennock and Yiling Chen. The press release led to short articles on the New Scientist and Scientific American web sites and a handful of other blogs. Although even with the nice virtual ink, there was never a day more people looked at the maps than at this weblog.

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.

A Thesis to Forget

It is rumored that a graduate student once wrote a whole thesis on the set of functions mapping reals to reals such that for some fixed c and α>1, |f(x)-f(y)| ≤ c|x-y|^α for all reals x and y.

A committee member then asked what happens when you compute the derivative of f.

[From The Way of Analysis by Robert Strichartz]

FCRC Deadlines

The 2007 Federated Computing Research Conference will bring together a large number computer science conferences for one meeting June 8-16 in San Diego. Here is a run down of the FCRC theory-related conferences with submission deadlines and links to their call-for-papers.

• 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.

Meanwhile not at FCRC

• Computational Geometry, Titles and Abstracts, November 22. Papers, December 4. Video, February 15. Conference, June 6-8 in South Korea.
• TARK (Rationality and Knowledge), January 30. Conference, June 20-22 in Belgium.
• ICALP, January 25. Workshop Proposals, November 30. Conference, July 9-13 in Poland.
• LICS (Logic in CS), Titles and Abstracts, January 15. Papers, January 22. Conference co-located with ICALP, July 10-14 in Poland.