Computational Depth

I'm posting from Oxford University where I will be spending the "Hilary Term" (through late March) as a visiting fellow at Magdalen College. If you are relatively local, reach out if you'd like to connect.

I plan to get back into research after thirteen years of administration, working primarily with Rahul Santhanam and his group. I haven't had a significant sabbatical or leave since Amsterdam 30 years ago, which is what comes from changing jobs too often.

Today I'd like to talk about a 2006 paper about a topic I first thought about in Amsterdam and will likely play a role in this visit, Computational Depth: Concept and Applications by Luis Antunes, Dieter van Melkebeek, Vinod Variyam and myself. 

In Amsterdam, I was hosted by Paul Vitányi and Harry Buhrman at CWI, and naturally worked on Kolmogorov complexity, the algorithmic study of randomness, as well as various problems in computational complexity.

Very simple strings don't have much information. Completely random strings have maximal Kolmogorov complexity but not particularly useful either as we can create our own random strings by flipping coins. Is there some way to measure useful information? 

In particular I had this question: If NP reduces to a sparse set then it has polynomial-size circuits. If NP reduces to a random set then it has polynomial-size circuits. Is this just coincidence or is there a broader principle here?

Charlie Bennett developed a notion of logical depth that has a similar philosophy but it is a difficult definition to work with. Luis Antunes, a student from Porto, came to work with me at NEC Research in New Jersey when I was there around the turn of the century. We developed this simpler notion of computational depth as the difference of two Kolmogorov measures, like time-bounded Kolmogorov complexity minus traditional Kolmogorov complexity. This would be small for both very easy strings and full random strings. With then NEC postdoc (and now Nebraska professor) Vinod Variyam, we found a connection to finding SAT witnesses and with DIMACS and IAS postdoc Dieter van Melkebeek (now Wisconsin professor), we came up with the notion of shallow sets, that generalized both random and sparse sets and, as hoped, if NP reduces to a shallow set than it has polynomial-sized circuits. Luis would title his PhD thesis "Useless Information".

Luis and I would later find a nice connection of computational depth to average-case complexity. 

Computational Depth had a resurgence of popularity with the rise of meta-complexity, with 50 of the original paper's 90 citations coming since 2020.

So I hope to find new applications of computational depth working with Rahul who's at the center of meta-complexity. Maybe computational complexity can help us understand machine learning better based on my frozen concentrate analogy, where the learning process removes the randomness, leaving structured information behind. 

AI and Research Papers

2026 will be a year of AI disruption across all of academia. Let's start by talking about AI is changing how we write research papers. Not the research itself (another post), just about the dissemination thereof.

Technology has changed research distribution since the invention of paper, and the printing press, typewriters, journals and conferences have all had dramatic effects. But we've already seen such dramatic changes just within my research career from authors doing their own formatting (TeX/LaTeX), instant distribution of papers (email/web) and collaborative writing (email/shared repositories/Overleaf).

How AI affects research writing follows a trend not unlike other AI applications. 

The Slop Phase

This is where AI does more harm than good. Useful for finding grammar mistakes and making fancy LaTeX tables, but if you use it for writing it may make stuff up, create citations out of thin air and put in words like "as a large-language model" in the text. Things have gotten much better with the latest models, I'm currently a fan of Gemini 3, but we haven't fully left the slop phase and anything AI written needs close verification.

The Verification Phase

2026 will be the year we go from humans having to look over AI generated content to AI having to look over human-generated content. Already you should give your paper, ideally in LaTeX, to the best model you have access to with a prompt asking for a critical review, or use a specialized service. You don't have to follow what the AI says but you should be open to improving your paper. Google provided an optional tool for those preparing STOC 2026 submission that many found valuable. In 2026 some conferences and journals will start requiring submitted papers to go through an AI review as well as a human review (for now), especially with those overwhelmed by submissions.

At some point, we may require authors, with AI help, have their theorems verified by theorem provers like Lean or Rocq. It will be a while, especially in computational complexity, where it is hard to properly state a theorem in formal logic, let alone its proof. 

The Collaborative Phase

Not just AI critiquing papers, but researchers and AI working together in paper writing. We already see pieces of this, having AI fill in details of arguments, give a first draft of an introduction, help create diagrams, find relevant citations, etc. Right now anything the AI writes requires a careful lookover by the researcher. As these models improve, we'll see more and more generated by the AI and researchers starting to trust the output, maybe more than they should. This will lead to...

The Generation Phase

Here the AI writes the LaTeX from scratch based on proof sketch given by the researchers. As an experiment, I "vibe-coded" a minor research paper and it went better than expected. 

The researcher will go and ask for updates and touch up the LaTeX at the end, but at some point the human won't ever touch the LaTeX file, just a prompt or a markdown file that generates it. 

By the end of the 1980s, researchers just trusted the LaTeX for formatting, fixing only syntax errors and overfull boxes. Most researchers (but not all) stopped fiddling with the look of the paper. At some point, and at higher stakes, we'll do the same with the paper content as well.

Peer Review

Daniel Lemire wrote a blog post Peer Review is Not the Gold Standard in Science. I wonder who was claiming it was. There is whole section of an online Responsible Conduct in Research we are required to take on peer review which discussing its challenges: "honesty, objectivity, quality control, confidentiality and security, fairness, bias, conflicts of interest, editorial independence, and professionalism". With apologies to Winston Churchill, Peer Review is the worst form of measuring academic quality, except for all of the others.

Peer review requires answering two questions.

1. Has the research been done properly?
2. What is the value of the research?

For theoretical research, the first comes down to checking the proofs, which sounds like an objective check. Here we have a "gold standard", formalizing the proof so it can be verified in a proof system like Lean. That's a heavy burden so we generally only require authors to give enough details so it's clear that we could formalize the proof given enough time. That becomes subjective and reviewers, especially for conferences, may not have the time or inclination to check the details of a 40-page proof. Maybe one day AI can take a well-written informal proof and formalize it for a proof system.

But the second question is almost entirely subjective. How does the work advance previous research? What value does it give to a field and how does it set up future research? Different researchers will give different opinions. And then there are the people who consciously or unconsciously cheat, helping their friends get papers accepted to citations rings. As we focus on metrics to judge researchers, too many people will game the system to pump up those metrics.

In 2013, NeurIPS had over 13,000 submission for 3500 slots. Even with the best or reviewer's intentions, it's impossible to maintain any sense of consistency for these large volume conferences.

Despite the problems with peer review, you'd hate to us a different system, say delegating the reviewing to some AI process, even if it could lead to more consistency. I suspect many reviews are being delegated anyway.

Peer review grew in importance as journals and conferences had to make choices to fill a limited proceedings. These days we have the capacity to distribute every papers. So perhaps the best form of measuring academic quality is no review at all.

Peer Review

I ran into a partner of a computer scientist at a social event who asked me "Is the publication system in CS screwed up or really screwed up?" If you don't know my response you haven't been reading this blog long.

Today let's talk about peer review. Kevin McCurley and Adam Mastroianni have recent, not so positive, takes on this topic. 

Peer review came out of a system where we had limited slots in journals and, in computer science, conferences and we had to make tough decisions. Journals and conferences would gain a reputation based somewhat on how difficult it was to get papers published there.

Now we have basically unlimited space to publish your results. And you definitely should do so, posting your papers on your own webpage, and a paper archive site like arXiv or ECCC. The research community would flourish in a world where everyone posts their paper online for public comment, people can promote their favorite papers on social media and we have a TikTok-system for recommending papers to you.

So why do we still need paper review? Mostly because we have to review researchers for jobs and grants, and with the questioning the value of recommendation letters, publication quality and quantity has become a stronger proxy for measuring people for better or for worse.

First of all, peer review is a cornerstone of science. Would you rather have papers reviewed by faceless bureaucrats who know little about the subject area? Or papers only ranked by manipulable statistics like citations.  

But the way we apply peer review, to decide acceptances in conferences, just adds too much randomness to the system. CS conferences have multiplied and continue to get increased submissions as the field grows. It's just impossible to maintain any sort of uniformity in quality of acceptances. Or too often, we find conference committees and funding panels playing it safe rather than take risks with new research. With so much randomness, it's best to try many papers instead of focusing on a stronger result, leading to too much incremental research, especially in academia. 

For hiring, promotion, tenure and funding decisions, we too often rely on short cuts, such as the number of papers accepted to major conferences. Those who don't win the conference lottery get disillusioned and often leave academia for industry and no one wins.

Is Kamala Harris our first female PREZ? No. Do I have a theorem named after me. No. But in both cases...

On Nov 19, 2021 Joe Biden got a colonoscopy and hence the 25th amendment was used to make Kamala Harris the president temporarily (this source: here says 85 minutes, though I thought I heard a few hours from other sources). 

Does this make Kamala Harris our first female president?

I would say NO and I suspect you agree. A friend of mine suggested the phrasing Kamala Harris is the first women to assume the powers of the president under the 25th amendment.  True.  I don't think it means much. She tacked on the under the 25th amendment since Edith Wilson was essentially president when Woodrow Wilson had a stroke (see here).

A student asked me Is there a theorem that is referred to as Gasarch's Theorem or something like that?

I will answer YES and NO, but really the answer is NO.

YES: In 1999 Gasarch and Kruskal had a paper in Mathematics Magazine: 

When can one load of Dice so that the sum is uniformly distributed?

In that paper we have a theorem that gives an exact condition on

(n_1,...,n_k) for when there is a loaded n_1-sided dice, n_2-sided dice,...,n_k-sided dice so that 

the sums are all equally likely.

In 2018 Ian Morrison published a paper in the American Math Monthly:

Sacks of dice with fair totals

which used our work and referred to our main theorem as The Gasarch-Kruskal Theorem.

Hence there is a theorem with my name on it!

NO: The Gasarch-Kruskal paper has only 8 citations (according to Google Scholar). This is more than I would have thought, but its not a lot. The fact that ONE person calls the main theorem THE GASARCH-KRUSKAL THEOREM hardly makes it a named theorem. 

QUESTION: So what criteria can one use?

We could say that X has a theorem with their name on it if there is a Wikipedia entry about the theorem, using that name. That works to a point, but might fun afoul of Goodhart's law (if a measure becomes a target it stops being a measure) in that, for example, I could write a Wikipedia entry on The Gasarch-Kruskal Theorem. 

We could say that 10 people need to refer to the theorem by the name of its authors. Why 10? Any number seems arbitrary. 

CAVEAT: If someone asked Clyde Kruskal is there a theorem that bears your name that is trickier, since The Kruskal Tree Theorem bears his name.... but its not his theorem. Reminds me of the (fictional) scenario where a Alice steals  a Field's medal and tells Bob I have a Field's Medal! and Bob  thinks Alice is a world-class mathematician since she has a fields medal, rather than thinking Alice is a world class thief. See here for my post on that. 

(I originally had Kruskal Three Theorem instead of Tree Theorem. I have corrected this but I hope it inspires Clyde to prove a theorem about the number Three so he can have a named theorem. And if he is lucky, over time, people will confuse it with the Kruskal Tree Theorem!) 

The Roeder Problem was Solved Before I Posed it (how we missed it)

(This is a joint post with David and Tomas Harris.)

In my an earlier post (see here) I discussed the MATH behind a problem that I worked on, with David and Tomas Harris, that we later found out had already been solved. In this post we discuss HOW this happened. 

Recall that Bill Gasarch read a column of Oliver Roeder (see here) on Nate Silvers' blog where he challenged his readers to the following:

Find the longest sequence using numbers from {1,...,100} such that every number is either a factor or multiple of the previous number. (A later column (see here ) revealed the answer to be 77 via a computer search, which we note is not a human-readable proof.)

Bill wrote a blog post (see here) and an open problems column (see here ) asking about the general case of {1,...,n}. Before doing this Bill DID try to check the literature to see what was known, but he didn't check very hard since this was not going to be a published paper. Also, he vaguely thought that if it was a known problem then one of his readers would tell him.

QUESTION: Is it appropriate to blog on things that you have not done a search of the literature on?

ANSWER: Yes, but you should SAY SO in the blog post.

As measured by comments, the post did not generate much interest- 10 comments. 2 were me (Gasarch) responding to comments.

David (who has a PhD from UMCP under Aravind Srinivasan) asked Bill to find a HS project for his son Tomas. Bill gave Tomas the sequence problem (as he called it) to look at- perhaps write a program to find what happens for {1,...,n} for small n, perhaps find human-readable proofs of weaker bound, for small n or for n=100.

David got interested in the MATH behind the problem so the project became three projects: Tomas would look at the programing aspects and the human-readable aspects, David would look at the Math, and Bill would...  hmmm, not clear what Bill would do, but he did write up a great deal of it and cleaned up some of the proofs.

David showed

Omega( n/( (log n)^{1.68} )  LE  L(n)  LE  O( n/( (log n)^{0.79} ). 

Tomas and Bill obtained a human-readable proof that L(100) LE 83. (Comments on my blog sketched a proof that L(100) LE 83, and someone else that L(100) LE 80). See my previous post (here) for more on the known numbers for L. 

At that point David did a brief literature search; however, he didn't know what to look for.

BILL still thought of this as a HS project so he didn't think much about a paper coming out of it, or if it was original. So he didn't do the due diligence of seeing what was already known.

David and Tomas were busy working on it, so they only did a few cursory checks of the literature.

With the two results above,  we had a paper! David then looked much more carefully at the literature. He DID find some earlier papers -- he did a Google search for Roeder's puzzle, which mentioned another mathematician, who was quoted in a blog by another mathematician, who eventually mentioned Pomerance's old paper on the topic. Once he found a reference to an actual math paper it was easy to use Google Scholar to find forward/backward citations and find the current state of the art.

His email had subject title

                        SHUT IT ALL DOWN!!!

Which made Bill think it involved a nuclear reactor undergoing The China Syndrome rather than just telling us that other people did had better and earlier results. 

In 1995 Gerald Tenenbaum showed, in a paper written in French,  that there exists a,b such that 

                               n/(log n)^a LE L(n) LE n/(log n)^b (see here). 

More recently, in 2021, Saias showed, in a paper written in French, that 

                                      L(n) GE (0.3 - o(1)) n/log n (see here). 

SO, why didn't Bill, David, Tomas find that it was already known until late in the process:

1) They didn't know the right search term: Divisor Graph

2) The literature was in French so the right search term is graphe divisoriel

3) The transition from FUN HS PROJECT to SERIOUS MATH PAPER was somewhat abrupt and caught Bill by surprise.

Was this a disappointment?

1) We all learned some math from it, so that was nice.

2) We were in a position to read and understand the paper since we knew all of the difficulties --- however, it was in French which I do not read. David reads some, Tomas does not read French.  I prefer to be scooped in English, but even then  I might not be able to read up on the problem since  math is... hard. When did math get so hard? see my blog on that here. When did CS theory get so hard? See my blog on that here.)

Could this happen again?

1) Yes. Language barriers are hard to overcome. Though this is rare nowadays--- not much serious mathematics seems to be done outside English. French mathematicians seem to like to keep their language alive, although they probably know English as well. There may be a few other countries (China, perhaps), where English language skills are not advanced and researchers are cut off from the English literature.

2) Yes. I've heard of cases where many people discovered the same theorem but were unaware of each others results since they were in different fields.

3) Is it easier or harder to reprove a theorem now then it was X years ago?

We have better search tools, but we also have more to search. 

Why Conferences?

An undergrad thesis from North Carolina State University tries to tackle the question as to why computer science has used conferences as its main and most prestigious publication venues. The author Elijah Bouma-Sims gives a synopsis with some interesting follow up conversation in this Twitter thread.

The upshot is that the conference culture grew organically early in computing and just took hold as the field grew. My personal non-scientific theory is that technology not available to earlier fields, namely jet airplanes, allowed CS to have national and international meetings that researchers could regularly attend. Before that conferences in more established fields like math were held either locally (AMS sectional meetings) or less often (ICM held every four years), traditions that continue to this day.

Covid has temporarily suspended fully on-site conferences, and new technologies allow us to have virtual meetings. It's still not clear what will be the new normal for conferences. I hope we get to the model where we have more virtual meetings and rarer in-person meetings that people make more of an effort to attend. Conferences focused on networking instead of publications.

The culture of conference publications has been slowly changing. Many subfields in CS, though not no much theory, have moved to a hybrid model where papers are submitted to a journal and those accepted are invited to be presented at a conference.

Conferences used to be the first place you would hear about new results but that's no longer the case. Papers posted on arXiv get noticed and Google Scholar doesn't distinguished citations to an arXiv paper differently from any other publication venue. 

Now you don't even need a presentation or a paper, just a promise of one. How many of you are excited about linear-size locally testable codes based on a talk announcement alone?

Why do we give citations? How should we give citations?

Why do we cite past work? There are many reasons and they lead to advice on how we should cite past work

1. Give credit where credit it due. Some people over cite and that diminishes any one citation. I once saw a paper that had in the first paragraph: ''Similar work in this field has been done by [list of 20 citations].'' One of the papers in that list was extremely relevent, the rest much less so. This is not really helpful. There should be less citations and more about each one.
2. If you are using a result in a prior paper the user should be able to read that paper. For that reason I try to give the websites of where the paper is. (this might be  less crucial now then it used to be since if a paper is on lnie someplace for free its usually easy to find). Some students ask me if its okay to cite papers on arXiv. Of course it is, especially if it's to guide the reader to a place to read the result. Note also that papers on arXiv are not behind paywalls.
3. At some point a result is so well known that it does not need a citation. It's not clear when this is. I think people write `by the Cook-Levin theorem' without citing the original source. Nor do people ever cite Ramsey's original paper either. See next item for why this might be a mistake.
4. A reader might want to know WHEN a result was discovered. For this reason, perhaps people should give references for Cook-Levin or for Ramsey. The original source is often NOT a good place to read a result so I often do  ``by a theorem of Curly [1] (see also Moe's simplification [2] or Larry's survey [3])'' so I give the reader WHO did it first, when they did it, but also an alternative place to read it. However, when does it end? `By the Pythagorean theorem [1] (also see [2])'
5. A reader should know the context of the result.  Is the problem new? Is the problem related to other problems? Has there been much work in this field? Inquiring minds want to know!

A Tale of Three Rankings

In the Spring of 2018 the US News and World Report should release their latest rankings of US graduate science programs including computer science. These are the most cited of the deluge of computer science rankings we see out there. The US News rankings have a long history and since they are reputation based they roughly correspond to how we see CS departments though some argue that reputation changes slowly with the quality of a department.

US News and World Report also has a new global ranking of CS departments. The US doesn't fare that well on the list and the ranking of the US programs on the global list are wildly inconsistent with the US list. What's going on?

75% of the global ranking is based on statistics from Web of Science. Web of Science captures mainly journal articles where conferences in computer science typically have a higher reputation and more selectivity. In many European and Asian universities hiring and promotion often depend heavily on publications and citations in Web of Science encouraging their professor to publish in journals thus leading to higher ranked international departments.

The CRA rightly put out a statement urging the CS community to ignore the global rankings, though I wished they made a distinction between the two different US News rankings.

I've never been a fan of using metrics to rank CS departments but there is a relatively new site, Emery Berger's Computer Science Rankings, based on the number of publications in major venues. CS Rankings passes the smell test for both their US and global lists and is relatively consistent with the US News reputation-based CS graduate rankings.

Nevertheless I hope CS Rankings will not become the main ranking system for CS departments. Departments who wish to raise their ranking would hire faculty based mainly on their ability to publish large number of papers in major conferences. Professors and students would then focus on quantity of papers and this would in the long run discourage risk-taking long-range research, as well as innovations in improving diversity or educating graduate students.

As Goodhart's Law states, "when a measure becomes a target, it ceases to be a good measure". Paradoxically CS Rankings can lead to good rankings of CS departments as long as we don't treat it as such.

Feeling Underappreciated

As academics we live and die by our research. While our proofs are either correct or not, the import of our work has a far more subjective feel. One can see where the work is published or how many citations it gets and we often say that we care most about the true intrinsic or extrinsic value of the research. But the measure of success of a research that we truly care most about is how it is viewed within the community. Such measures can have a real value in terms of hiring, tenure, promotion, raises and grants but it goes deeper, filling some internal need to have our research matter to our peers.

So even little things can bother you. Not being cited when you think your work should be. Not being mentioned during a talk. Seeing a review that questions the relevance of your model. Nobody following up on your open questions. Difficulty in finding excitement in others about your work. We tend to keep these feelings bottled up since we feel we shouldn't be bragging about own work.

If you feel this way a few things to keep in mind. It happens to all of us even though we rarely talk about it. You are not alone. Try not to obsess, it's counterproductive and just makes you feel even worse. If appropriate let the authors know that your work is relevant to theirs, the authors truly may have been unaware. Sometimes it is just best to acknowledge to yourself that while you think the work is good, you can't always convince the rest of the world and just move on.

More importantly remember the golden rule, and try to cite all relevant research and show interest in other people's work as well as your own.

The Impact Factor Disease

The Institute of Science Information (ISI) was founded in 1960 to help index the ever growing collection of scientific journals. The founder of ISI, Eugene Garfield, developed a simple impact factor to give a rough estimate of quality and help highlight the more important journals. Roughly the impact factor of a journal in year x is the average number of citations each article from years x-1 and x-2 receives in year x.

Thomson Scientific bought out ISI in 1992 and turned the data collection into a business. Impact factors are not only being used to measure the quality of journals but of authors (i.e. researchers) and institutions as well. In many parts of the world a person's research quality is being measured strongly or sometimes solely by their ability to publish in high impact factor journals.

This is bad news for computer science since conference proceedings in our field have historically more prestige than journals. We mitigate the ISI factors pretty well in the US but in many other countries this puts computer science at a disadvantage. The need for impact factor publications is one of the reasons conferences are experimenting with a hybrid model.

In a new trend I get many announcements of journals highlighting their ISI impact factor, mostly very general and previously unknown to me. Our old friends WSEAS say "The ISI Journals (with Impact Factor from Thomson Reuters) that publish the accepted papers from our Conferences are now 32" in the subject line of their email.

It's the vanity journal with a twist: publish with us and you'll raise your official numerical prestige. So we get a set of journals whose purpose is to raise the value of researchers who should have their value lowered by publishing in these journals.

Raise your research standing the old fashioned way: Do great research that gets published in the best venues. The numbers will take care of themselves.

Metrics in Academics

Congratulations to the San Francisco Giants, winning the World Series last night. In honor of their victory let's talk metrics. Baseball has truly embraced metrics as evidenced in the book and movie Moneyball about focusing on statistics to choose which players to trade for. This year we saw a dramatic increase in the infield shift, the process of moving the infielders to different locations for each batter based on where they hit the ball, all based on statistics.

Metrics work in baseball because we do have lots of statistics, but also an objective goal of winning games and ultimately the World Series. You can use machine learning techniques to predict the effects of certain players and positions and the metrics can drive your decisions.

In the academic world we certainly have our own statistics, publications counts and citations, grant income, teaching evaluation scores, sizes of classes and majors, number of faculty and much more. We certainly draw useful information from these values and they feed into the decisions of hiring and promotion and evaluation of departments and disciplines. But I don't like making decisions solely based on metrics, because we don't have an objective outcome.

What does it mean to be a great computer scientist? It's not just a number, not necessarily the person with a large number of citations or a high h-index, or the one who brings in huge grants, or the one with high teaching scores, or whose students gets high paying jobs. It's a much more subjective measure, the person who has a great impact. in the many various ways one can have an impact. It's why faculty applications require recommendation letters. It's why we have faculty recruiting and P&T committees, instead of just punching in a formula. It's why we have outside review committees that review departments and degrees, and peer review of grant proposals.

As you might have guessed this post is motivated by attempts to rank departments based on metrics, such as described in the controversial guest post last week or by Mitzenmacher. There are so many rankings based on metrics, you just need to find one that makes you look good. But metric-based rankings have many problems, most importantly they can't capture the subjective measure of greatness and people will disagree on which metric to use. If a ranking takes hold, you may optimize to the metric instead of to the real goals, a bad allocation of resources.

I prefer the US News & World report approach to ranking CS Departments, which are based heavily on surveys filled out by department and graduate committee chairs. For the subareas, it would be better to have, for example, theory people rank the theory groups but I still prefer the subjective approach.

In the end, the value of a program is its reputation, for a strong reputation is what attracts faculty and students. Reputation-based rankings can best capture the relative strengths of academic departments in what really matters.

Subhash Khot wins Nevanlinna

At the opening ceremonies of the International Congress of Mathematicians in 2014, Subhash Khot was awarded the Rolf Nevanlinna Prize, given every four years to an under-40 researcher for outstanding contributions in Mathematical Aspects of Information Sciences. Subhash's citation reads

Subhash Khot is awarded the Nevanlinna Prize for his prescient definition of the “Unique Games” problem, and leading the effort to understand its complexity and its pivotal role in the study of efficient approximation of optimization problems; his work has led to breakthroughs in algorithmic design and approximation hardness, and to new exciting interactions between computational complexity, analysis and geometry.

Khot's work has indeed generated a large research agenda over the last decade. I highlighted his work in March's favorite theorems post.

In other big news, we have our first female Fields Medalist Maryam Mirzakhani for contributions to the dynamics and geometry of Riemann surfaces and their moduli spaces. Still no female winners among the nine Nevanlinna winners. Artur Avila, Manjul Bhargava and Martin Hairer also received Fields medalists. Stanley Osher won the Gauss Prize, Phillip Griffiths the Chern Medal and Adrián Paenza the Leelavati Prize.

Pictures and press releases and citations of all the prize winners.

To Write, or Not to Write, That Is the Question

Guest post by Vijay Vazirani

Our field has been blessed with some great books: classics such as Knuth's volumes and Garey & Johnson literally got the field going, and the books of Lovász brought much clarity in difficult, important areas. The new millennium brought a plethora of new books by famous TCS researchers including Arora, Barack, Goldreich, Kleinberg, Nisan and Tardos. With an astonishing 33 short titles in theory, Now Publishers has virtually created an assembly line for producing books.

Even so, when faced with the prospect of writing a new book, I am filled with trepidation and self-doubt: Am I up to the effort needed? Do I have a genuinely new point of view to expound? If so, have I figured out the "right'' format and style for expounding it in the simplest and clearest manner?

The issue arose when I decided to co-teach, with my able postdoc Ruta Mehta, the course Equilibrium Computation in Spring. With her characteristic enthusiasm, Ruta has practically forced me into a long-term commitment of writing a book on this topic. However, knowing what it takes, so far I have managed to resist an unequivocal "yes".

Most people would say it is a losing proposition -- the gains are typically minuscule compared to the toils. So why do so many people write books? I can imagine several reasons, but best to leave this discussion to my esteemed colleagues who are probably yearning for something to ponder on in this holiday season ...

That brings me to another question, "Are some of the books written in this millennium eventually going to be regarded as classics in the style of Knuth or Lovász's books?'' One could look at citation counts or average citations per year to get an "objective'' reading of the situation. However, when one is talking about true class, such crude estimators are clearly not the way to go.

Your thoughts are eagerly sought ...

Our Journal is 99 44/100 percent pure!!

Sometimes we are asked to evaluate how good a journal or conference  formally(Excellent, Very Good, Good, Fair, Better-than-being-poked-by-a-stick,pass the stick). Sometimes we talk about these things informally (ICALP is the European STOC! SODA is as hard to get into as FOCS!, CCC is a topTier topics-conference!)


But is there a way to judge these things formally? And should there be?Be aware of Goodhart's Law:

When a measure becomes a target, it ceases to be a good measure.

 One way to measure how good a journal or conference is  impact factor which is based on number-of-citations. Does this work well? Some issues:

1. Even with an honest effort these things are hard to do well. People may cite the conference version, the journal version, the arXiv version, or just give a website.
2. Even with an honest effort just a few articles can skew the results.
3. Its hard to compare cross-fields.  I suspect that pure math journals have lower citations rates than biology journals.
4. If an author cites himself, should that count?
5. The above points were all about HONEST efforts. Could a journal do things to boost its impact factor and then brag about how high their impact factor is? Would they? Alas yes, see this article and this article.

So what are we left with? We could just go on our gut, but that favors journals that used to be good and aren't any longer. But the problem is deeper than all that--- can't we just say Thats a good article  and not have to proof it by saying where it was published? Alas no- all fields have gotten specialized that we must use these proxies to inform us.

 I COULD rant that we should all be well rounded enough to read outside of our field, but I know how hard that is.

I COULD rant about the dishonesty pointed out in the above links, but that's only part of the problem.

I COULD say What do you think? so I will.

Short Bits

Because some things are too long to tweet and too short for their own blog post.

What's the algorithm for the perfect sushi? Enjoy it with some cool refreshing SODA in Kyoto. Early registration deadline is December 20th and lots of travel support still available (apply by Nov 29).

What's new for STOC 2012 in New York City? An open call for workshops (apply by Dec 2) and a best student presentation award. Practice up. Please also nominate people for Gödel, Knuth and SIGACT Distinguished Service prizes.

Google scholar citations now open to all. Now you can see my papers at Google, Microsoft, ACM, DBLP and my own papers page. Google has the best stats and ranking, DBLP the best links, my page the most accessible downloads and Microsoft has the coolest graphics.

Google gives all the stats so we can rank job applicants. Why stop there? Google can use their magic algorithms to tell us who to hire. No more messy recommendation letters and awkward interviews.

Journals

What is the purpose of an academic journal? To provide a permanent vetted record of a specific research endeavor.

The ways we communicate scientific research has vastly improved, particularly with the advent of the Internet, but the need for that basic mission will never go away.

Noam Nisan laments that journals do not provide a quick form of dissemination or do the proper amount of vetting. He's correct on both points. Computer scientists need to take journals more seriously to improve the vetting process and the speed to publication. But also journals have never played the role of quick dissemination in computer science. That role has been taken by conferences, departmental technical reports and more recently on-line archives. Journals don't compete with sites like ArXiv, they play different roles.

Tim Gowers suggests a commenting/scoring system for reviewing papers. I'd love to see such a system built into ArXiv and ECCC. But it won't supplant the need for academic journals. Most papers won't get reviewed and most researchers won't review papers. Collaborative projects like Wikipedia, Polymath, Math Overflow (and the TCS descendant) are incredible resources but just a small number of researchers are significantly involved. If you reward people for reviewing papers (through reputation or otherwise) then people can decide not to review guilt free. 

We are moving to a world where we rank research papers not on where they appear but by how many citations they achieve, a statistic the Internet has made easier to measure. One can cite an ArXiv paper just as easily as a JACM paper. The incentives for an author to do more than throw up a paper on an on-line site are going away. We will no longer fulfill the mission of journals and future scientists will struggle understanding the how and why of what we did. Is this the gift we want to leave to the next generation?

Factors for getting a job- Arbitrary, random, and complex

The Job Market in Theory (likely in all of academia) has more randomness and arbitrariness (are those the same?) then people may realize. Especially young PhD's who have never been to a faculty meeting where these things are discussed. The process is quite complex (is that the same as random and arbitrary?). I am NOT saying that merit plays no role. I am saying that its very hard to make a clean statement like Person X got a job an school Y because of Z.

With that in mind, I list out some criteria I have heard played a role in a hiring decision. My point is NOT to help you game the system (note that some of the factors I've heard cut both ways) nor to argue that the system is good, bad, or ugly. My point is only that the process is more arbitrary-random-complex then you might think. While its not all merit, its also not all who-you-know or politics.

I invite you to give leave comments on factors you have heard of, but to keep it civil please do not mention the people or schools involved.

1. Merit: This is itself ambiguous. More papers? Longer papers? Co-authors? How about take a sum where each summand is (number of citations)*(importance of paper)*(number of pages)/(number of coauthors). And then there is grant potential.
2. Does a postdoc have a better chance then a fresh PhD? A postdoc has had more time to increase his weighted sum mentioned under Merit, but the school KNOWS he has had more time.
3. Two-body-problems can be GOOD or BAD. Often a school does not have two positions.
4. Being a women can be GOOD or BAD (for getting a job).
5. I would like to say Being black can be GOOD or BAD (for getting a job) however since there are so few black PhD's in computer scientists applying for academic jobs, I have not heard any stories about this. (NOTE- I use the term black instead of African American since they need not be American.)
6. Being socially inept can be GOOD or BAD. How could it be good? It plays to the stereotype. He's so socially inept, he must be a genius. I DO NOT recommend pretending you are socially inept.
7. Speaking your mind can be GOOD or BAD. He'll be a leader in the community or He'll be a pain in the ass
8. Having a Blog- the jury is still out on this one. I have heard of a case where having a blog helped someone get an interview. (It was a serious blog about the field he was in. I can't imagine that complexity blog would help me get a job if I was looking.)
9. Spending too much time deciding what to have for lunch can be a negative. If he can't figure out what to have for lunch then how can he formulate a coherent research plan.
10. Area can be a factor- does a school need or want someone doing area X? This is sometimes formalized, for example the school has money targeted to hire someone who does, a particular area. (Side topic- Targeted positions- Good or Bad? Good in that you are not going to have to compare people in diff areas. Bad in that there may be someone really good in another area who you want to hire but can't.)
11. Subarea is a factor- for example, we want the kind of theorist who can talk to our people in systems.
12. Having a champion in the dept who is helping push your case HELPS unless the person doing the pushing is a jerk or not good at pushing a case.
13. Being an ex-convict probably hurts. If there was a theory genius who served 10 years in jail, that might be a negative. Might be mitigated if he could pull in some serious grant money. However, if the jail term was for embezzling grant money, then maybe not. Actually, the whole question might depend on what he was in jail for and is he now reformed.
14. A very big factor is how good is the job market when you get out. This may be a much bigger factor than anything else on this list.

Conference Acceptance Rates

In the latest CACM, Jilin Chen and Joseph Konstan analyze data from the ACM DL and conclude that low-acceptance rate conference have papers with higher impact (more citations). This shouldn't be too surprising. If Joe believes a conference A bestows more prestige on their paper than conference B, Joe might submit his paper to A instead of B if it Joe's paper had a higher probability of being accepted into conference B. So in equilibrium conferences with higher prestige papers should have a lower acceptance rate.

Chen and Konstan suggest that conferences could lower than acceptance rate to get higher prestige. I have two problems with that advice. First of course my general annoyance of treating CS conferences as "journals that happen be be held at a hotel". 

Chen and Konstan have the causation effect backwards. Prestigious conferences do have a lower acceptance rate with other factors kept the same. But you can't necessarily up the prestige by changing the acceptance rate. The one decision the PC can make is how many papers get accepted into the conference. But accept fewer papers and in the future less people will submit their papers since they no longer believe they have a decent chance of seeing their papers accepted. it's possible in the long run to increase the acceptance rate while lowering the number of papers accepted.

When STOC moved to double sessions and accepted more papers, did the acceptance rate dramatically go up? No, because we had more submissions to match. But why does STOC have a higher acceptance rate than similarly rated conferences in other subfields? Theoretical work by its nature is easier to self-judge and most people whose papers are well below the accept/reject border of quality don't bother to submit to STOC.

You have a prestigious conference by the people that come. You can't engineer prestige, it has to be nourished.

Amir Pnueli (1941-2009)

Amir Pnueli passed away Monday from a brain hemorrhage. Amir was an expert in program verification who won the 1996 Turing Award primarily for his 1977 FOCS paper The Temporal Logic of Programs. Lenore Zuck shares her thoughts.

I'm reading through what people wrote about Amir in the past 30 or so hours since we received the sad news of his passing. I'm leafing through the citations of his numerous awards and honorary degrees, the list of academies of which he was a member, and the lists of his unique accomplishments. Throughout today I was helping with NYU's press release about him. Everybody mentions how brilliant he was, how modest he was, how pleasant he was, how gracious he was. Some mention his patience with those of us who are less talented than him. What is mentioned less is how much fun he was to work with, how he put the people around him at ease, how he managed to find good ideas in seemingly random thoughts people brought to him.

I recall the hours I've spent with Amir as a graduate student: joking, our regular Friday afternoon meetings solving the acrostic puzzle of "Koteret Rashit", discussing books, news, politics, and taking work breaks. It's a wonder we got anything done. It's a wonder we got so much done. This was Amir's style -- alternating between work and play, and making large strides in research while fostering the most pleasant work environment imaginable. Years later, when we were working together at NYU, it was the same with our joint PhD students. Long sessions consisting mainly of laughter, with some breaks for coffee and sweets, at the end of which I always found myself stunned how we made so much progress during all the hilarity.

I'm trying to recall Amir's funniest lines. Some don't translate, some require too much background. But I thought of a few that may illustrate Amir's special humor. When a student of his was called to military reserve duty whenever his oral exam for the completion of his MSc was scheduled, (temporal logic) until he found a note from Amir saying "you had your oral exam in absentia and you passed with flying colors." Or when I interchanged N and M in a paper, on which, upon proof reading, Amir wrote a note "even for N=M" when I claimed I proved something for any N. Or... after long arguments with me that the past operators in temporal logic are not needed, he gave a lecture in which he basically admitted they were useful, with slides whose titles were "Admitting the Past" and "Why Should We be Ashamed of the Past" that I felt were for me. And the list goes on.

I've collaborated with Amir since I was a graduate student. I've had several joint students with him. I've worked with his students. I've held regular meetings with him, the next one is scheduled for this Friday -- I still cannot bring myself to remove it from my calendar. I cannot imagine life without him. He was a genius, a friend, a colleague, one of a kind. I feel fortunate to have had the opportunity to know him, to have worked him, to have learnt so much from him. May his memory, legacy, and example stay with us.

Lenore D. Zuck, Arlington, Virginia, November 3rd, 2009

Update 11/15: NYT Obit for Pnueli