(This is a guest post by MohammadTaghi Hajiaghayi. His name is not a typo- the first name really is MohammadTaghi.)

Due to our belief in the lack of transparency and well-defined measures in methods used by U.S News to rank CS departments in theoretical computer science (and in general), my PhD. student Saeed Seddighin and I have worked for several months to provide a ranking based on a real and measurable method of the number of papers in TCS for the top 50 US Universities. To make this possible, we gathered the information about universities from various resources. You may see the ranking and our exact methodology here.

Indeed we have some initial rankings based on similar measures for computer science in general as well which we plan to release soon (we are still in the process of double-checking or even triple-checking our data and our analysis due to several factors). CS theory ranking is our initial ranking release to get feedback at this point.

Please feel free to give us feedback (hajiagha@cs.umd.edu).

# Computational Complexity

Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch

## Thursday, October 23, 2014

## Wednesday, October 22, 2014

### MSR SVC Letters

The Committee for the Advancement of Theoretical Computer Science put together an open letter to several research leaders at Microsoft.

Yesterday Harry Shum, Microsoft Executive VP for Technology and Research sent a reply.

I'd like to thank the CATCS leadership in putting together the letter which expressed well the thoughts and concerns of the community. The tone of the letter hit the right notes and really made Microsoft research leadership think about the important role the company plays in the larger computer science academic world.

We feel that there should have been a better way to close down this lab, one that would have allowed them to have continuous employment until academic jobs are available again in September 2015. Given that this lab was continuing to produce exceptional — indeed revolutionary — research, we fail to understand why closing it had to be done so suddenly.I recommend reading the whole letter. Many in the theory community and beyond, including myself, signed the original letter or added their support in the comments.

Yesterday Harry Shum, Microsoft Executive VP for Technology and Research sent a reply.

No one at Microsoft feels good about the fact that a significant number of our friends and colleagues were laid off. These people contributed to the success of Microsoft over many years. As one can readily imagine, the decisions made about how the cuts were implemented within MSR were extremely complicated and personally painful. We feel with you the sense of loss that has been evoked by the closing of our Silicon Valley lab.Theory Matters has a cover email. More on the CRA Policy Blog.

I'd like to thank the CATCS leadership in putting together the letter which expressed well the thoughts and concerns of the community. The tone of the letter hit the right notes and really made Microsoft research leadership think about the important role the company plays in the larger computer science academic world.

## Tuesday, October 21, 2014

### Martin Gardner Centennial

Martin Gardner was born on October 21, 1914, so today is his Centennial (he died on May 22, 2010, at the age of 95). We've mentioned him in the blog before:

So what can I add on his centennial?

- The Life of Martin Gardner
- Contribute to the Gardner Centennial
- Another Post on Martin Gardner
- I used the anagram Tim Andrer Gran in both my review of the Lipton-Regan book (see here) and my Applications of Ramsey Theory to History paper (see here)

So what can I add on his centennial?

- He was not the first person to write on recreational mathematics, but he was certainly early and did it for a long time.
- I suspect he influenced everyone reading this who is over 50. For every y, y is under 50 and reading this column, there exists x such that MG influenced x and x influenced y.
- The line between ``recreational'' and ``serious'' math is sometimes blurry or hard to see. An obvious case of this was Euler and the Bridges problem leading to graph theory. At one time solving equations was done for competition, which seems recreational. Galois theory is not recreational.
- Donald Knuth's book Selected Papers in Discrete Math (reviewed by me here) states
*I've never been able to see the boundary between scientific**research and game playing*. - I am reading a book
*Martin Gardner in the 21st century*which is papers by people who were inspired by him. The papers really do blur the distinction between recreational and serious. Some are rather difficult but all start out with a fun problem. - Aside from recreational math he did other things- magic, and debunking bad science.
*(Fads and Fallacies in the name of science*was excellent.) He was a well rounded person which is rare now. - Brian Hayes and Ian Stewart and others do what he did, but given the times we live in now, its hard capture the attention of a large segment of the public. (analogous to that when I was a kid there were only a handful of TV stations, now there are... too many?)
- When I was in high school I went to the library looking for math books I could read (naive?). I found one of his books (collection of his columns) and began reading it. I learned about casting out nines and I learned what was to be the first theorem I ever learned a proof of outside of class (given that I was probably 12 it may be the first proof I learned ever). It was that (in todays lang) a graph is Eulerian iff every vertex is even degree.

## Thursday, October 16, 2014

### The Curious Case of NP and NEXP

NP (nondeterministic polynomial time) and NEXP (nondeterministic exponential time) are provably different classes by the nondeterministic time hierarchy. No surprise, given exponentially more time we expect to solve more problems. But the proof requires collapses at many input lengths and odd things happen when we look at the infinitely-often question.

We say a language L is in i.o.-C for a complexity class C if there is an A in C such that for infinitely many n, A and L agree on strings of length n (for all x of length n, x is in A if and only if x is in L). Straightforward diagonalization shows that EXP is not in i.o.-P.

However we showed a relativized world where NEXP is in i.o.-NP in a recent paper (Theorem 18).

The construction is not particularly difficult but rather surprising: There is a possibility that one can get exponential improvement for nondeterministic computation for infinitely many input lengths.

Also consider the following facts: NEXP is not in i.o.-co-NP by straight diagonalization. If NEXP is is in i.o.-NP then

NEXP in i.o.-NP is not one of my most complicated relativization results, but definitely one of the strangest.

We say a language L is in i.o.-C for a complexity class C if there is an A in C such that for infinitely many n, A and L agree on strings of length n (for all x of length n, x is in A if and only if x is in L). Straightforward diagonalization shows that EXP is not in i.o.-P.

However we showed a relativized world where NEXP is in i.o.-NP in a recent paper (Theorem 18).

The construction is not particularly difficult but rather surprising: There is a possibility that one can get exponential improvement for nondeterministic computation for infinitely many input lengths.

Also consider the following facts: NEXP is not in i.o.-co-NP by straight diagonalization. If NEXP is is in i.o.-NP then

- NEXP is in i.o.-EXP
- EXP is in i.o.-NP and thus EXP is in i.o.-co-NP (since EXP is closed under complement).

NEXP in i.o.-NP is not one of my most complicated relativization results, but definitely one of the strangest.

## Monday, October 13, 2014

### Luddite or not?

My first ever guest post for Lance was on Are you a luddite. I certainly am to some extent a luddite, but there are some things where it not clear if they are luddite-ish or not.

BILL: When I goto that conference I am going to bring some math to read during the talks I don't understand.

DARLING: Isn't that rude?

BILL: Many people in the audience will have their laptops out, reading email, managing their facebook page, etc.

DARLING: But the speaker can at least imagine they are taking notes

BILL: Unlikely. In the next talk the speaker will become the laptop person.

The fact that I don't look at a laptop during a talk is probably a plus- and not a Luddite thing.

- I prefer reading books to blogs. This came up when I reviewed both Lipton and Lipton-Regan blog-books, and I am now reading some of Terry Tao's Blog book. l look forward to reading Scott's Blog book. At first I thought that preferring books was luddite-ish. But some high tech people and some young people who I've asked AGREE with me. Why is this?

- when reading a blog (or doing anything on line) its so easy to get distracted, e.g. OH, I WONDER IF WHITEY FORD IS STILL ALIVE SO I"LL PUT HIM ON MY LIST OF LIVING FAMOUS PEOPLE OVER 80 (he is, he's 85, and has the same birthday (though not year) as Martin Gardner), OH, I wonder if the word Buypartisan (that is NOT misspelled) is on my list-of-cool-new-words that I keep, OH I wonder how many people have registered for Theory Day. OH, Lipton just posted about Definitions not being needed and used that quote from The Treasure of Sierra Madre (see here) that was satirized in the movie UHF, I wonder if that clip is on You-Tube (It is here). OH, I can write a blog about Math in Weird-Al songs, for example Polka Patterns.
- If I read a blog with a proof in it I tend to say
*I'll read that later.*

- (I do not why it restarted at number 1. I don't care to fix it- is that Luddite or not wanting to waste time on something unimportant?)
- Of course, the blog reading issue is MY fault for being distracted.
- I don't pay my bills on line. There have been many data breaches and that gets darling and I nervous. Is this Luddite? Not sure--- is banking off-line any safer? I ask non-rhetorically.
- In a small class I use the blackboard. Some of my systems faculty have gone from board to slides and then
*back to board.*For a big class I have to use slides, though that may be an argument for small classes.

BILL: When I goto that conference I am going to bring some math to read during the talks I don't understand.

DARLING: Isn't that rude?

BILL: Many people in the audience will have their laptops out, reading email, managing their facebook page, etc.

DARLING: But the speaker can at least imagine they are taking notes

BILL: Unlikely. In the next talk the speaker will become the laptop person.

The fact that I don't look at a laptop during a talk is probably a plus- and not a Luddite thing.

- We still don't have Netflix. We watch less TV this way? Worse TV this way? Not clear how this one goes.
- I used to write things out before typing them in, now I type them in directly. I wonder if that's good or bad.
- I used to have notebooks of random math stuff in them. Now I can't get myself to write things out by hand. That's probably bad.
- If someone asks me a question I am too quick to goto the web rather than try to answer it myself. This is mixed--- I don't waste time on problems I can't solve, but I also don't have the joy of solving them. I think of myself as not being a good problems-solver, but this could be a self-fulfilling prophecy that the web makes easier to indulge in.
- This is a DUH-comment- I hate technology that does not work. One of worst episodes of Star Trek was The Ultimate Computer which showed that a good human is better than a MALFUNCTIONING computer. Well DUH. I had a rant about electronic refereeing refereeing- and not a single comment accused me of being a Luddite. In short- I hate technology that doesn't work. Duh.

## Thursday, October 09, 2014

### 2014 Fall Jobs Post

Tis the season for the fall jobs post. Please list any jobs, academic or industrial, in theoretical computer science broadly construed in the comments to this post. If you are a job seeker check this page often as new jobs get added over time.

As always the best places to look for academic CS positions are the job sites at the CRA and the ACM. Also check out postdoc and other opportunities on Theory Announcements. It never hurts to check out the webpages of departments or to contact people to see if positions are available.

I expect the computer science market to be quite robust again. CS enrollments continue to explode putting pressure to hire more faculty. Several good places last year had open positions unfilled.

We should also see a growth in instructor positions, as deans and provosts need to meet enrollment demands but aren't ready to commit faculty positions until they are sure CS is not in another bubble. Don't ignore these positions, think of an instructor as a teaching postdoc.

The market in theoretical computer science is a harder call. What will be the effect of Microsoft adding fifteen theorists to the market? That also suggests fewer industrial research and postdoc opportunities in theory.

Try to make yourself more versatile. Perhaps you could teach machine learning or computer security, areas of strong need closely related to theory.

Good luck to everyone on the market. I look forward to seeing your names in the 2015 spring jobs post.

As always the best places to look for academic CS positions are the job sites at the CRA and the ACM. Also check out postdoc and other opportunities on Theory Announcements. It never hurts to check out the webpages of departments or to contact people to see if positions are available.

I expect the computer science market to be quite robust again. CS enrollments continue to explode putting pressure to hire more faculty. Several good places last year had open positions unfilled.

We should also see a growth in instructor positions, as deans and provosts need to meet enrollment demands but aren't ready to commit faculty positions until they are sure CS is not in another bubble. Don't ignore these positions, think of an instructor as a teaching postdoc.

The market in theoretical computer science is a harder call. What will be the effect of Microsoft adding fifteen theorists to the market? That also suggests fewer industrial research and postdoc opportunities in theory.

Try to make yourself more versatile. Perhaps you could teach machine learning or computer security, areas of strong need closely related to theory.

Good luck to everyone on the market. I look forward to seeing your names in the 2015 spring jobs post.

## Monday, October 06, 2014

### The Complexity of NIM. Open?

Recall 1-pile NIM:

Let A be a finite set of Naturals. NIM(A) is the following game: There are n stones on the board. Players I and II alternate removing a\in A stones. The first player who can't win loses. Note that if 1\in A then `can't move' means that the other player took the last stone. If (say) 2 is the min elt of A then its possible there is 1 stone on the board and a player can't move.

The following are known and easy to prove:

This raises the following computational problem: How hard is the problem of, given finite set A, find the mod pattern. I would want to know the complexity as a function of the size of the representation of A, or possibly just |A|log_2(max elt of A). Has this been looked at? Some Google searches and asking around did not yield anything. I'm hoping that asking my readers may yield something.

Let A be a finite set of Naturals. NIM(A) is the following game: There are n stones on the board. Players I and II alternate removing a\in A stones. The first player who can't win loses. Note that if 1\in A then `can't move' means that the other player took the last stone. If (say) 2 is the min elt of A then its possible there is 1 stone on the board and a player can't move.

The following are known and easy to prove:

- If A={1,L} and L is even then II wins iff n\equiv 0,2,4,...,L-2 mod L+1
- If A={1,L,L+1} and L is odd then II wins iff n\equiv 0,2,4,...L-1 mod 2L+1
- If A={1,L,L+1} and L is even then II wins iff n\equiv o,2,4,...,L-2 mod 2L
- If A= {L,...,M} then II wins iff n\equiv 0,2,4,...,L-2 mod L+1
- For ANY set A there will be a mod pattern, after a certain point.

This raises the following computational problem: How hard is the problem of, given finite set A, find the mod pattern. I would want to know the complexity as a function of the size of the representation of A, or possibly just |A|log_2(max elt of A). Has this been looked at? Some Google searches and asking around did not yield anything. I'm hoping that asking my readers may yield something.

## Thursday, October 02, 2014

### Favorite Theorems: Multilinear Circuits

In the past decade we have seen a strong program in algebraic circuit complexity. If you just define circuits using multiplication and addition gates, sometimes you can use the algebraic structure to get lower bounds that prove much more difficult in the Boolean case. For October's favorite theorem we highlight a couple of Ran Raz's results.

The main result of the first paper is basically in the title. Raz creates a polynomial function f that can be computed by a polynomial multilinear circuit of depth O(log

Ran Raz followed up with Amir Shpilka and Amir Yehudayoff to show lower bounds for syntactically multilinear circuits and exponential bounds for constant-depth multilinear circuits.

The second paper showed the most well-known of the algebraic functions (permanent and determinant) do not have poly-size multilinear formulas. Raz again starts with the partial derivative matrix, this time combined with random restrictions.

More recent work in algebraic circuit complexity focuses on the VP versus VNP problem, the algebraic version of P v NP. VP = VNP if we can solve the permanent on poly-size algebraic circuits. Proving VP ≠ VNP is a goal of the Geometric Complexity Theory program as well as a consequence of tighter bounds on constant-depth algebraic circuits.

^{2}n) but cannot be computed by any multilinear formula. (A formula, unlike a circuit, cannot use the output of a gate more than once). His proof works by examining the rank of the partial derivative matrix of a function chosen in a specified random way.Ran Raz followed up with Amir Shpilka and Amir Yehudayoff to show lower bounds for syntactically multilinear circuits and exponential bounds for constant-depth multilinear circuits.

The second paper showed the most well-known of the algebraic functions (permanent and determinant) do not have poly-size multilinear formulas. Raz again starts with the partial derivative matrix, this time combined with random restrictions.

More recent work in algebraic circuit complexity focuses on the VP versus VNP problem, the algebraic version of P v NP. VP = VNP if we can solve the permanent on poly-size algebraic circuits. Proving VP ≠ VNP is a goal of the Geometric Complexity Theory program as well as a consequence of tighter bounds on constant-depth algebraic circuits.

Subscribe to:
Posts (Atom)