Monday, December 29, 2014

2014 Complexity Year in Review

Theorem of the year goes to 2-Server PIR with Sub-polynomial Communication by Zeev Dvir and Sivakanth Gopi. In Private Information Retrieval you want to access information copied in multiple databases in a way so that no database knows what question you asked. In 1995 Chor, Kushilevits, Goldreich and Sudan showed how to use n1/3 bits of communication with two databases. Razborov and Yekhanin proved that using current techniques the bound could not be broken.  Dvir and Gopi
developed new techniques to break that barrier using nO(√(log log n/log n)) bits with two databases, less than nδ for any δ. Bill posted more on this result back in August.

And of course lots of other great work on extended formulations, circuits, algorithms, communication complexity and many other topics. We also had another round of favorite theorems for the past decade.

2014 will go down as the year computer science exploded. With a big convergence of machine learning/big data, the connectedness of everything, the sharing economy, automation and the move to mobile, we have a great demand for computer scientists and a great demand from students to become computer scientists or have enough computing education to succeed in whatever job they get. Enrollments are booming, CS departments are hiring and demand far outstrips the supply. A great time for computer science and a challenging one as well.

We say goodbye to G.M. Adelson-VelskyAlberto Bertoni, Ed Blum, Ashok Chandra, Alexey Chervonenkis, Eugene DynkinClarence "Skip" Ellis, Alexander Grothendieck, Ferran Hurtado, Mike Stilman, Ivan Stojmenovic, Berthold VöckingAnn Yasuhara, Microsoft Research-Silicon Valley and The New York Times Chess Column.

Thanks to our contributors Andrew ChildsBrittany Terese Fasy and MohammadTaghi Hajiaghayi.

Looking ahead 2015 brings the centenary of the man we know for balls and distance and the fiftieth anniversary of the paper that brought us the title of this blog. Have a great New Years and remember, in a complex world best to keep it simple.

Monday, December 22, 2014

Undergraduate Research

I just received the Cornell Math Matters, dedicated to the memory of  Eugene Dynkin who passed away on November 14 at the age of 90. In my freshman year at Cornell, Dynkin recruited me into his undergraduate research seminar building on the success he had with a similar seminar he ran when in Russia. I didn't last long, making the conscious choice not to work on research as an undergrad but to focus on enjoying the college experience. I missed out on a great opportunity but I don't regret that decision.

Reluctantly I wouldn't give that advice to today's undergrads. Getting into a good graduate program has become much more competitive and even a small amount of research experience may make a large difference in your application. I encourage any undergrad who may consider a PhD in their future to talk to some professors and get started in a research program. But don't let it run your life, make sure you enjoy your time at college. You'll have plenty of time to spend every waking moment on research once you start graduate school.

Thursday, December 18, 2014

The NIPS Experiment

The NIPS (machine learning) conference ran an interesting experiment this year. They had two separate and disjoint program committees with the submissions split between them. 10% (166) of the submissions were given to both committees. If either committee accepted one of those papers it was accepted to NIPS.

According to an analysis by Eric Price, of those 166, about 16 (about 10%) were accepted by both committees, 43 (26%) by exactly one of the committees and 107 (64%) rejected by both committees. Price notes that of the accepted papers, over half (57%) of them would not have been accepted with a different PC. On the flip side 83% of the rejected papers would still be rejected. More details of the experiment here.

No one who has ever served on a program committee should be surprised by these results. Nor is there anything really wrong or bad going on here. A PC will almost always accept the great papers and almost always reject the mediocre ones, but the middle ground are at a similar quality level and personal tastes come into play. There is no objective perfect ordering of the papers and that's why we task a program committee to make those tough choices. The only completely fair committees would either accept all the papers or reject all the papers.

These results can lead to a false sense of self worth. If your paper is accepted you might think you had a great submission, more likely you had a good submission and got lucky. If your paper was rejected, you might think you had a good submission and was unlucky, more likely you had a mediocre paper that would never get in.

In the few days since NIPS announced these results, I've already seen people try to use them not only to trash program committees but for many other subjective decision making. In the end we have to make choices on who to hire, who to promote and who to give grants. We need to make subjective decisions and those done by our peers aren't always consistent but they work much better than the alternatives. Even the machine learning conference doesn't use machine learning to choose which papers to accept.

Monday, December 15, 2014

Joint Center for Quantum Information and Computer Science

(Guest post by Andrew Childs who is now at the Univ of MD at College Park)

We have recently launched a new Joint Center for Quantum Information and Computer Science (QuICS) at the University of Maryland. This center is a partnership
with the National Institute of Standards and Technology, with the support and participation of the Research Directorate of the National Security Agency/Central Security Service. QuICS will foster research on quantum information and computation.

We are pleased to announce opportunities for Hartree Postdoctoral Fellowships
(deadline: December 30, 2014) and Lanczos Graduate Fellowships. Outstanding postdoctoral and graduate researchers with an interest in quantum information processing are encouraged to apply.

QuICS complements a strong program in quantum physics research at the Joint Quantum Institute. Maryland is also home to a new Quantum Engineering Center.
It's an exciting time for quantum information here.

Thursday, December 11, 2014

The Ethics of Saving Languages

The linguist John McWhorter wrote an NYT opinion piece entitled Why Save a Language? where he argues why we should care about saving dying languages, basically that language gives us a window into culture. As a computer scientist I appreciate the scientific value of studying languages but perhaps the question is not whether we should care but is it ethical to save languages?

Languages developed on geographical and geopolitical boundaries. Even as new methods of communication came along such as postal mail, the printing press, the telephone and television there never was a strong reason to learn multiple languages save for some small European nations and some professions such as academics and politics.

Then came the Internet and location mattered less but language barriers still persist. I've certainly noticed a marked increase in the number of young people around the world who know basic conversational English, much from the content they consume online. There's also a sizable amount of content in all the major languages.

But if you speak a small language where all the other native speakers are geographically very close to you, you lose this networked connection to the rest of humanity. Your only hope is to learn a second language and that second language might become a first language and so many of these small languages start to disappear.

I understand the desire of linguists and social scientists to want to keep these languages active, but to do so may make it harder for them to take advantage of our networked society. Linguists should study languages but they shouldn't interfere with the natural progression. Every time a language dies, the world gets more connected and that's not a bad thing.

Tuesday, December 09, 2014

Godel and Knuth Prize Nominations due soon. Which would you rather win? Or ...

(Alg Decision Theory conference in Kentucky: here.)

Knuth Prize Nominations are due Jan 20, 2015.
For info on the prize see here, if you want to nominate someone
go here.

Godel Prize Nominations are due Jan 31, 2015.
For info on the prize see here, if you want to nominate someone
go here

Would you rather:

  1. Win a Godel Prize
  2. Win a Knuth Prize
  3. Have a prize named after you when you are dead
  4. Have a prize named after you when you are alive
I pick 4; however, I doubt I'll have of 1,2,3,4 happen to me.

How about you?

Monday, December 01, 2014

Cliques are nasty but Cliques are nastier

BILL: Today we will show that finding large cliques is likely a nasty problem

STUDENT: Yes! In my High School the Cliques were usually at most six people and they gossiped about everyone else. They were very nasty.

BILL: Um, yes, picture in your school that everyone is a node in a graph and that two nodes are connected if they are friends. In your school a clique of size 6 would be 6 people who all liked each other

STUDENT: Actually, the people in a clique secretly hated each other and sometimes belonged to other cliques that would gossip about people in the first clique.

BILL: We might need  the Hypergraph version to model your school.

Computer Scientists and Graph Theorists call a set of nodes that are all connected to each other a CLIQUE - pronounced CLEEK

High School Kids call a group of people who hang out together a CLIQUE- pronounced CLICK.

Which term came first? Why are they pronounced differently when they are quite related to each other? Do the members of a high school clique really hate each other?

Sunday, November 23, 2014

Guest Post about Barbie `I can be an engineer' -- Sounds good but its not.

There is now a I can be an engineer Barbie. That sounds good! It's not. Imagine how this could be turned around and made sexist. What you are imagining might not be as bad as the reality. Depends on your imagination.

Guest Blogger Brittany Terese Fasy explains:

Remember the controversy over the Barbie doll that said
"Math class is tough!"?  Well, Barbie strikes again.

If you haven't heard about II can be a computer engineer  it is a story about how Barbie, as a "computer engineer" designs a game, but cannot code it herself.  She enlists the help of her two friends, Steven and Brian, to do it for her.  Then, she gets a computer virus and naively shares it with hersister.  Again, Steven and Brian must come to the rescue.  Somehow, in the end, she takes credit for all of their work and says that she can be a computer engineer.  Gender issues aside, she does not embody a computer engineer in this book. For more details, please see here.

Children need role models.  Naturally, parents are their first role models.  And, not everyone's parent is a computer engineer / computer scientist.  So, books exploring different career choices to children provides the much-needed opportunity for them to learn about something new, to have a role model (even if if that role model is fictional).  In principle, this book is fantastic; however, it fails to convey the right message.  That is why I started a petition to Random House to pull this book off the market.The petition is here.

Progress was made as Barbie issued an apology: here. And Amazon and Barnes and Nobles  removed the book from its catalog. However, neither Random House, nor the author of the book have issued a statement, and it is still available at Walmart.

Until the book is completely off the market we should not stop! And maybe one day, we'll see
Barbie: I can be a Computational Geometer on the shelves.

Thursday, November 20, 2014

A November to Remember

The Imitation Game starring Benedict Cumberbatch as Alan Turing opens in the US on November 28. If you read this blog you should see that movie. If one challenged British scientist biograph is not enough for you, The Theory of Everything with Eddie Redmayne as Stephen Hawking opened earlier this month. Also this month has the physics-laden Interstellar and the nerd-hero robot adventure Big Hero 6. Science rules the box office, though likely to be clobbered by a Mockingjay.

Speaking of Turing, The ACM Turing Award will now come with a $1 million dollar prize, up from $250K, now on par with the Nobel Prize. Thanks Google.

Madhu Sudan will receive the 2014 Infosys Prize in Mathematics. Nimrod Megiddo wins the 2014 John von Neumann Theory Prize.

Harvard Computer Science gets 12 endowed faculty lines from former Microsoft CEO Steve Ballmer. That's about the number of former Microsoft Research theorists now on the job market. Just saying,

Sanjeev Arora asks for comments on the potential changes to STOC/FOCS discussed at the recent FOCS. Boaz Barak has set up a new CS Theory jobs site. On that note, the November CRA News has 75 pages of faculty job ads, up from 50 a year ago.

Terry Tao talked twin, cousin and sexy primes on Colbert last week. The new result he quoted is that the Generalized Elliott-Halberstam conjecture implies that there are infinitely many pairs of primes at most six apart.

Not all happy news as we lost the great mathematician Alexander Grothendieck. Tributes by Luca and Ken.

Monday, November 17, 2014

A Fly on the wall for a Harvard Faculty meeting: Not interesting for Gossip but interesting for a more important reason

I was recently in Boston for Mikefest (which Lance talked about  here)  and found time to talk to  my adviser Harry Lewis at Harvard (adviser? Gee, I already finished my PhD. Former-Advisor? that doesn't quite sound right. I'll stick with Adviser, kind of like when they refer to Romney as Governor Romney, or Palin as half-governor Palin). He also invited me to goto a Harvard Faculty meeting.

NO, I didn't see anything worth gossiping about. NO I am not going to quote Kissinger ``Academic battles are so fierce because the stakes were so low'' NO I am not going to say that under the veneer or cordiality
you could tell there were deep seated tensions. It was all very civilized. Plus there was a free lunch.

The topic was (roughly) which courses count in which categories incomputer science for which requirements.  Why is this interesting? (hmmm- IS it interesting? You'd prob rather hear that Harry Lewis stabbed Les Valiant with a fork in a dispute about whether there should be an ugrad learning theory course). Because ALL Comp sci depts face these problems.  At Mikefest and other conferences I've heard the following issues brought up:

Should CS become a service department?  Math did that with Calculus many years ago. PRO: They get to tell the dean `we need to hire more tenure track faculty to teach calculus', CON: They have to have their tenure track faculty teach calculus. (I know its more complicated than that.)

What should a non-majors course have in it?

What should CS1,CS2,CS3 have in it (often misconstrued by the question ``what is a good first language'' which misses the point of what you are trying to accomplish). For that matter, should it be a 3-long intro sequence (it is at UMCP).

Can our majors take the non-majors courses?  (At UMCP our non majors course on web design has material in it that is NOT in any majors course.)

When new courses come about (comp-bio, programming hand-held devices, Computational flavor-of-the-month) what categories to they fit into? (For an argument in favor of Machine Learning see Daume's post. ) What should the categories be anyway? And what about the functors?

Which courses were at one point important but aren't any more? UMCP no longer requires a Hardware course-- is that bad?  (Yes- when I tell my students that PARITY can't be solved by a constant depth poly sized circuit, they don't know what a circuit is!)

I don't have strong opinions to any of these questions (except that, despite my best efforts, we do not require all students to learn Ramsey Theory), but I note that all depts face these questions (or need to- I wonder if some depts are still teaching FORTRAN and COBOL- and even that's not quite a bad thing since there is so much legacy code out there.)

I have this notion (perhaps `grass is always greener on the other side') that MATH (and most other majors) don't have these problems.  AT UMCP there have only been TWO new math courses introduced on the ugrad level since 1985 :Crypto (which is cross-listed with CS), and Chaos Theory. CS has new courses, new emphasis, new requirements every few years. Oddly enough when I tell this to Math Profs they ENVY that we CAN change our courses so much. What is better chaos or stability?

When I saw Back to the future 2   in 1989 I noticed that their depiction of academic computer science in 2015 was that  Comp Sci Depts across the country agreed on what was important and be similar (as I imagine math is). Instead the opposite has happened- these things are still in flux. (If you can't trust a Science Fiction movie staring Michael J Fox what can you trust?) As a sign of that, the advanced GRE in CS never really worked and has now been discontinued.

So- will CS settle down by 2015? We still have a year to go, but I doubt it.  2025? Before P vs NP is solved?

and is it OKAY if it doesn't?

Thursday, November 13, 2014

From Homework Solution to Research Paper

Inspired by the Dantzig Story  I occasionally put an open problem on a class assignment. Never worked, though I did have a student get a research paper from solving a homework question the hard way.

Teaching in the early 90's, I showed Valiant's proof that computing the permanent of a 0-1 matrix was #P-complete, including showing that the 0-1 permanent was in #P, the class of functions representable as the number of accepting paths of a nondeterministic polynomial-time Turing machine.

I gave a homework assignment to show that the permanent of a matrix with non-negative integer entries was in #P. The answer I expected was to construct an appropriate NP machine whose number of accepting paths equalled the permanent and some students came up with such a proof.

One of the students Viktória Zankó took a different approach, creating a reduction that mapped an integer matrix A to a 0-1 matrix B such that permanent(A) = permanent(B). A fine solution reducing the problem to a previously solved case.

So what's the rub? Such a reduction was an open problem and simplified Valiant's paper. Valiant only had the reduction for integer matrices A with small entries and needed a mod trick to show the 0-1 permanent is #P-complete. Zankó's construction eliminated the need for the mod trick.

And that's how Viktória Zankó got a research paper from solving a homework problem.

Tuesday, November 11, 2014

Non controversial thoughts on rankings

US News has a ranking of CS depts and various subcategories. Recently MohammadTaghi Hajiaghay and Luca Trevisan have suggested alternative rankings here (Moh) and here (Luca). These rankings inspire me to record some thoughts about rankings.

  1. When making a ranking one must ask: What is it for? For Academic depts it may be to help guide potential ugrads or grads in their choice of where to go. Rankings of the most influential people of all time (Michael Harts book here), or in a given year (Time magazine does this) are made to (I think) organize our thoughts and start debates. Michael Hart also did a book about the most influential people as soon from the year 3000 (so half are fictional) as a way to speculate (see here). My own ranking of Bob Dylan satires here was done for my own amusement.
  2. Transparency sounds like a plus. But if a ranking is too transparent, and is considered important, than organizations might game the system. Recall Goodhart's law: When a measure becomes a target is ceases to be a measure. On the other hand, if the measure really is good then it may be okay if it becomes a target. Some measures are hard to game- like surveys of what people think.
  3. There have been a variety of rankings of presidents (see here).  These ranking say something about the times they were  done. Studying how they change over time could itself be a historical project of interest.  Another thought:  the book Hail to the chiefs it notes that James Buchanan and Andrew Johnson usually rank as the worst presidents, while Lincoln ranks as one of the best--- but this is unfair!--- Buchanan could not stop the civil war (but nobody really could) and Johnson had to clean up the mess after it (but nobody really could). The Lincoln presidency was almost entirely the civil war which Ameican won, so he gets the credit. More to the point--- ranking presidents is odd since it may depend very much on the times they govern.
  4. Bill James (KEY Baseball statistician who I think should go into the Hall of Fame for changing the way we think about Baseball) has tried to have lists of GREAT TEAMS. But there is a problem (which he fully notes)- some teams are GREAT in terms of having great players, but didn't win the world series, or have only one  pennant. Less than the sum of its parts.
  5. Numerical ratings may be odd in that they lump different items together. GPA is a bit odd--- do you prefer a student who got an A in Theory and a C in Operations Systems, or a student who got a B in both? I don't know the answer, but GPA wipes out the distinction.
  6. Rankings that compare very unlike objects are useless. Here is a ranking of CS blogs--- the criteria seems to be just one guys opinion. I  disagree with his ranking, but  I have no idea what he cares about. Also, he includes Harry Lewis's fine blog BITS AND PIECES,  which is often  about academic stuff, and also Terry Tao's fine blog WHATS NEW which is really a math blog. Very hard to compare those two to each other or to others.
  7.  The tigher the focus the more useful a ranking can be. Ranking the best novelty songs of all time would be impossible (Number one is PDQ Bach's Classical Rap) but if you restrict to, say, best science fiction  Satires I(Luke Ski's Grease Wars part 1, part 2, Part 3)- then its easier (Trivia note- Science fiction satire songs are often called FILK SONGS--- the urban legend is that at an early Science Fiction Convention  Science fiction Folk Songs was mispelled as Science fiction Filk Songs and hence the term was born.)
  8. SO, what really would help potential CS Grad Students in theory? Perhaps a grid where for every department is listed the theory faculty, and for each one the number of pubs in top tier confs, second tier confs, and journals in the last 5 years, and their area, and a pointer to their website. Then RESIST the urge to boil it down to one number.
  9. I"m reminded of being on the Grad Admissions committee. I get to look at the transcript (much more informative than the GPA), letters, possibly papers. Fortunately I don't have to boil it down to one number--- there are very few categories (accept, wait list of some sort, reject, but there can be a few others involving scholarships, but VERY few categories really).
  10. Finding what you want: I think that  Raiders of the lost ark has tone of the best ending-of-a-movie ever.  So I Googled best movie ending and  variants of it, and alas, Raiders did not do well. One of the rankings didn't have it in the top 50. So I then Googled best movie endings Raiders of the lost ark and I found a ranking that had Raider in the top 10. Yeah! But this is all silly- I found some person who agrees with me.
  11. Steve Skienna and Charlie Ward have written a book Who's bigger: Where historical figures really rank   which has a transparent and reasonable  way to measure... not clear. Probably fame.  For a review see here

Saturday, November 08, 2014

George Dantzig >= 100

We celebrate the 100th anniversary of the birth of George Dantzig today. In his obituary post we talked about his work on optimization, particularly the simplex method for solving linear programs.

For this centenary let's recall the urban legend of the famous mathematician (I heard it as John von Neumann) who as a student wasn't paying close attention in class. The professor wrote down four of the major open problems in the field. von Neumann wrote them down thinking they were homework problems. The next day he went back to the professor, ashamed that he could only solve two of them.

What does this have to do with Dantzig? Turns out he is the true source of the legend. From Dantzig's Washington Post obituary:
In 1939, Dantzig resumed his studies at the University of California at Berkeley, studying statistics under mathematician Jerzy Neyman. An incident during his first year at Berkeley became a math-world legend.
As Dr. Dantzig recalled years later, he arrived late for class one day and saw two problems on the blackboard that he assumed were homework assignments. He copied them down, took them home and solved them after a few days. "The problems seemed to be a little harder to do than usual," he said.
On a Sunday morning six weeks later, an excited Neyman banged on his student's front door, eager to tell him that the homework problems he had solved were two of the most famous unsolved problems in statistics. 
"That was the first inkling I had that there was anything special about them," Dr. Dantzig recalled.

Wednesday, November 05, 2014

Favorite Theorems: Circuit Lower Bounds

My long time blog readers should have no surprise on my final favorite theorem of 2005-2014.
Nonuniform ACC Circuit Lower Bounds by Ryan Williams (PDF)
We saw several exciting circuit lower bound results in the 80's, highlighted heavily in my first list of favorite theorems (1985-1994 sections 2.2 and 2.3). Progress happened so fast that many expected a proof that an NP-complete problem didn't have polynomial-size circuits, and thus P ≠ NP, was just around the corner. But after 1987 that progress came to a sudden stop. We saw some lower bounds for algebraic circuits or circuits of very small depth but no general lower bounds until the work of Ryan Williams.

For years I would point out that our limited knowledge of lower bounds allowed that possibility that NEXP could be computed by constant depth circuits with Mod6 gates. Williams eliminated that possibility for constant depth circuits with Modk gates for any k.

One could take the techniques and results that Williams uses in his paper and build a whole graduate computational complexity course on them. Dick Lipton did exactly that at Georgia Tech a couple years back.

Ryan Williams' greatest insight though was to find non-trivial satisfiability algorithms for ACC0 circuits and use them to give lower bounds for NEXP. Recently Ryan has turned that process around, for example getting a faster algorithm for all-pairs shortest path using the techniques from the Razborov-Smolensky circuit lower bounds. Ryan's publication page has several new results giving algorithms from lower bounds.

Monday, November 03, 2014

A few more notes about Sipser and Sipser-60th

While Lance was AT Mikefest (Sipser's 60th Bday conference), helping to organize it, emceeing the personal statements, I was... also there.
A few notes

  1. Aside from his graying hair, Mike still looks like a teenager.
  2. In 1985 Mike was one of the few people who thought P=BPP. He wrote a paper about how a certain kind of expander implies what we would now call a hard vs randomness result and presented it at the 1986 CCC (called STRUCTURES then). After the Nisan-Wigderson Hard vs Rand results most everyone thought P=BPP. But Mike was there first.
  3. I took his grad complexity class in the early 1980's. I remember him proving results that either he or someone else had JUST proven the last week. He did a good job too!  What struck me then and now is how vibrant CS is as a field that material taught LAST WEEK can be in an INTRO grad course (that's not as true anymore).
  4. After PARITY not in AC_0, and the monotone circuit results, Sipser and others were OPTIMISTIC that P vs NP would be solved ``soon''.  Oh, to be in a field in the early days when people were optimistic. But see next point.
  5. Mike claims he STILL thinks P vs NP will be solved in 20 years. I don't quite know if he REALLY thinks this or wants to make the point that we should be optmistic. Similar to Lipton thinking P=NP--- does he really think that or does he want to make the point that we shouldn't all be so sure of ourselves?
And two non-sipers notes (sort of) from Mikefest

  1.  Steve Rudich told me that I misquoted him in a blog post and people often say `Steve, do you really think we are 6 months from an independence result'. I am not surprised that I made a MISTAKE in a blog post. I am surprised that people read it, remembered it, and asked him about it. In any case I have edited that post to SAY it was a mistake and I re-iterate it now: STEVE RUDICH DOES NOT THINK WE ARE SIX MONTHS AWAY FROM AN IND PROOF FOR P VS NP.
  2. I spoke to Mauricio Karchmer who, with Avi W and others, had an approach to P vs NC^1 via comm. comp which at the time I thought was very promising--- since we really can prove things in comm. comp. Alas it still has not panned out. However, Mauricio  now thinks that (1) We can't prove lower bounds because they are false, and (2) we can't prove upper bounds because we are stupid.

Thursday, October 30, 2014

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.

Tuesday, October 28, 2014

Sipser Symposium

On Sunday we had the Symposium on Theoretical Computer Science on the Occasion of Michael Sipser's 60th birthday to celebrate what Mike has brought to research (seminal work on the complexity of randomness and circuits), service (ten years leading the MIT math department before recently becoming Dean of Science) and education (his great textbook and the corresponding popular course he still teaches).

We had an incredible turnout for the symposium and banquet that followed. I counted five Turing Award Winners (Mike's advisor Manuel Blum, Leslie Valiant, Shafi Goldwasser, Silvio Micali and Ron Rivest), five of the nine Nevanlinna Prize winners (Mike's student Daniel Spielman, Avi Wigderson, Valiant, Peter Shor and Madhu Sudan) and nine Gödel Prize winners.

Manuel Blum talked about his work with Jeremiah Blocki, Anupam Datta, and Santosh Vempala about a human computable hash function to create different passwords for every website. I've seen Manuel and Santosh produce passwords from arbitrary words and I'm impressed.

Johan Håstad recounted the early days of circuit complexity. Avi also talked about lower bounds. Shafi talked on her great paper with Mike showing public and private coin interactive proofs have the same power and a recent application of that result by Moni Naor et al showing how a defendant can convince the police his DNA doesn't match without revealing his DNA.

A number of Mike's PhD students also gave talks. Dan Spielman gave a framework for designing quantum algorithms without knowing much quantum.

The banquet included several stories, thanks and toasts. Nearly all of Mike's students participated in some way, a great collection of men and women I'm proud to be part of: David Barrington, Ravi Boppana, Jonathan Buss, Andrew Chou, Aditi Dhagat, Lance Fortnow, David Gillman, Michelangelo Grigni, Christos Kapoutsis, Marcos Kiwi, Mary (Bruzzese) O'Connor, Sofya Raskhodnikova, Zack Remscrim (current), Alexander Russell, Leonard Schulman, Daniel Spielman, Ravi Sundaram, Andrew Sutherland and Yiqun Yin .

Thursday, October 23, 2014

Guest Post by Dr. Hajiaghayi: A new way to rank departments

(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 (

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

  1.  The Life of Martin Gardner
  2.  Contribute to the Gardner Centennial
  3.  Another Post on Martin Gardner
  4. 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?

  1. He was not the first person to write on recreational mathematics, but he was certainly early and did it for a long time.
  2. 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.
  3. 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. 
  4. 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.
  5. 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.
  6. 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. 
  7. 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?)
  8. 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 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).
This is not an immediate contradiction since i.o. inclusion is not transitive, even though those i.o.'s happen at about the same length. You can't combine these relativizable statements to prove NEXP is not in i.o.-NP.

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.

  1. 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 work better with pen and paper on hand. This may change if the way to mark up pdf and other documents gets better.
  1. (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?)
  2. Of course, the blog reading issue  is MY fault for being distracted.
  3. 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.
  4. 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.
  1. We still don't have Netflix. We watch less TV this way? Worse TV this way? Not clear how this one goes.
  2. I used to write things out before typing them in, now I type them in directly. I wonder if that's good or bad.
  3. 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.
  4. 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.
  5. This is a DUH-comment- I hate technology that does not work. One of the 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 - and not a single comment accused me of being a Luddite. In short- I hate technology that doesn't work. Duh.
So- your thoughts? Some Luddite things may not be Luddite, but just better. And technology will change yet again, making us all Luddites.

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.

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:
  1. If A={1,L} and L is even then II wins iff n\equiv 0,2,4,...,L-2 mod L+1
  2. If A={1,L,L+1} and L is odd then II wins iff n\equiv 0,2,4,...L-1 mod 2L+1
  3. If  A={1,L,L+1} and L is even then II wins iff n\equiv o,2,4,...,L-2 mod 2L
  4. If A= {L,...,M} then II wins iff n\equiv 0,2,4,...,L-2 mod L+1
  5. For ANY set A there will be a mod pattern, after a certain point.
(I think that if 1\in A then the mod pattern goes from the beginning, but if 1\notin A then its possible that it does not start for a while.)

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(log2 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

Tuesday, September 30, 2014

Dagstuhl on Algebra in Computational Complexity

(Reminder- Theory day at UMCP: here is the link. )

There was a Dagstuhl on Algebra in Computational Complexity Sept 22-26.
I learned stuff in the talks, over meals, and even in my room alone at night.

1) Recall that a while back Ryan Williams (the theorist, not the American-Football player) showed that NEXP is not in ACC. His proof involved MANY things but one of the core things was an ALGORITHM for a version of  SAT (I think Succinct-SAT) that was ever-so-slightly better than brute force. So one lesson is that people in complexity theory should know some algorithms. At Dagstuhl Ryan presented work that shows that people in algorithms should know complexity. He used some old results about circuits to obtain  algorithm for all-pairs shortest path that has complexity n^3/X where X=2^{\Omega(log n)^{1/2}. The ultimate goal is to either prove or disproof that all-pairs... has n^{3-ep} algorithms or not. On the NOT side he has (with other people, including Virginia Williams) a large class of problems , including APSP, that either all have n^{3=ep} or none of them do.

2)  There were two (possibly three) talks on VP and VNP. Both are circuit classes defined by Valiant. Meena Mahajan has some natural problems that are complete for VNP (if you consider looking at Homomorphic polynomials natural) and Eric Allennder had a dual notion to VP and VNP. A sequence of polynomials is in VP  if there is an arithmetic circuit  family of polynomial bounded size and degree that computes the sequence. (Circuit C_n computes poly f_n). VNP is if there is a sequence C_n of poly bounded size and degree such that f_n(x) = sum as y\in {0,1}^p(n) C_n(x,y).

This is usually discussed over a finite field. Eric's result depended on which field it was.

3)  Stephen Fenner talked about some combinatorial games that were PSPACE complete. The black-white-poset-game is as follows: there is a poset where every node is colored white or black. One player is called black, the other is called white. Players alternate removing nodes of their color, and if they remove a node they remove all nodes above it. Either player can go first, so you may have a game where if B goes first he wins, but if he goes second he does not. Fenner and his co-authors have shown that the general problem of, given a Black-whie Poset and who goes first, determining who wins, is PSPACE complete. They showed that other versions are in P.

4)  In the 1990's Karchmar and Wigderson had an approach to NC^1 vs NC^2 and P vs NC^1 that looked promising--- they defined problems in communication complexity (where we actually DO have results!) that would imply some separations. This lead to monotone circuit results, but not to real circuit results. Or Meir spoke on some problems in that realm which can now be approaced with information complexity. Are we closer to a true separation? Next Dagstuhl!

5)  David Zuckerman gave a nice talk on Malleable codes. I was intrigued by some of the math that he did. The Sum-Product theorems are along the lines of: If A, B are large sets of reals (or other domains) then either A+A or AA is large. Or one could say that if A,B,C are all large than AB+C is large. David used an entropy version of this--- if A,B,C have large min-entropy, then so does AB+C.

6)  Kopparty showed that Polynomial Id Testing and Polynomail Factoring are related and may be equivalent.

7)  Over Lunch Jacobo Toran told me the following rather odd result.

a) Imagine the following GI algorithm: given two graphs look at the degree sequence, then the degrees of the degress, then... (this goes on n times). Two graphs are isom if they are never found to be non-isom. DOESN"T WORK-  Cai-First-Immerman showed that. Even so, we'll call that FOCSI-isom. Note that FOCS-isom is in P.

b) Recall that G (as a matrix) and H (as a matrix) are isom if there exists a Perm Matrix P such that GP = PH. We can expand what P can be- say to doubly-stocastic (every row and every column adds to 1) We call two graphs G,H STOC-isom if there exists a Double stocastic matrix P such that GP=PH. This is in Poly Time by Linera Programming.

c) FOCS-isom and STOC-isom are the same! Too bad, I thought that STOC-isom might be a way to get GI in P.

8) Sometimes at a conference I find a book in the library and read it at night and learn something out of nowhere. This happened with Mitzenmacher-Upfal book on Prob. and Computing (It could be called ``The Alice book'' as there is a picture of Alice from Alice in Wonderland on the cover. For the longest time a famous compiler book was called The Dragon Book). I read parts of it and even made up notes that I may use in an ugrad course:  the coupon collector problem: A cereal company puts coupons labeled 1,2,...,n at random in boxes. If you mail in one of each you get a free box of cereal. You are DETERMINED to get that box of cereal. What is the expected number of boxes of cereal you must buy? It turns out to be nln(n), and is very tight around that.

9) I learned more from the talks, more from the meals, and more from my own alone time, but what is above is a good sampling.

10) More chalk-talks then I would have thought. Either chalk or slides can be done well or poorly.

11) Looking forward to the next Dagstuhl!

Saturday, September 27, 2014


I rarely highlight individual events on the blog, but one's advisor only turns sixty once. We will honor Michael Sipser at MIT on Sunday, October 26 with a one-day symposium full of great speakers in complexity. As one of Sipser's PhD students, I'm helping to organize the event and serving as emcee for the dinner speeches. Please send me any funny or embarrassing stories or pictures of Sipser through the decades.

Many of you know Sipser from his popular textbook Introduction to the Theory of Computation. Sipser was one of the driving forces in complexity in the 70's and 80's. Sipser initiated the program of using circuit complexity to separate complexity classes and, with Merrick Furst and James Saxe, showed parity could not be computed by poly-size constant-depth circuits. His research includes how to simulate randomness by alternation, was the first to explore hardness vs randomness, made great advances in the complexity of interactive proofs, and much more. Sipser led the MIT Mathematics department for the last ten years and was recently appointed Dean of Science.

Join us in Cambridge for this great day to celebrate an extraordinary man.


P.S. STOC call posted, Deadline November 4

Wednesday, September 24, 2014

Typecasting in Dagstuhl

After this pre-recorded typecast, we learned of the tragic death of Alexey Chervonenkis, the C of VC dimension, a huge loss to the learning community. We’ll have a proper obit soon. Now onto the typecast.

Lance: Hello and welcome to Dagstuhl for our first typecast since the 2014 Complexity Conference. Howdy Bill.

Bill: Hi Lance. Are you enjoying Dagstuhl?

Lance: I always have fun at Dagstuhl especially when you are here Bill.

Bill: I have not seen you at many talks.

Lance: So maybe you should go to more talks Bill.

Bill: Never mind. As you told me Scott is writing a blog book. Should we too?

Lance: Something we discussed many times.

Bill: How about a slightly different idea? At the end of this year you will have had FIVE lists of TEN best theorems. (Doing math in his head) That’s FIFTY theorems. There’s a book with a unified theme.

Lance: And I’m glad you’re going to write it.

Bill: That’s not exactly what I had in mind. But I’m happy to help you write it?

Lance: Do you think there are people who would want to buy this book?

Bill: I need your help BLOG AUDIENCE. Leave a comment to say if you would read this book. Would you read the book if you have to pay for it?

Lance: I certainly wouldn’t.

Bill: You don’t count. But they (points to the audience) do. [Bill leaves to get ice cream and comes back] I’m sure it will sell well in Silicon Valley.

Lance: Speaking of Silicon Valley, that was one tough post to write on MSR-SVC, basically an obituary post for a research lab.

Bill: Isn’t rather grim calling it an obituary?

Lance: Exactly.

Bill: Do you always give one word answers?

Lance: No.

Bill: You are man of few words.

Lance: You are a man of a few words too many.

Bill: Yes, I like to keep conversations flowing.

Lance: Indeed you are of the few extroverts in complexity. Introverts like me think deeply of what to say before we say it.

Bill: Did you just insult me? How did an introvert like you become a department chair?

Lance: I fake it well. [Quickly changing topic] I hear there’s exciting news out of Maryland. And I’m not talking about the Orioles.

Bill: We’re getting a new building, The Brendan Iribe Center for Computer Science and Innovation.

Lance: Because there’s no innovation in computer science. Brendan who?

Bill: He co-founded Oculus which was sold to Facebook for Ackerman of O(1) dollars.

Lance: Sounds exciting. It is one pretty ugly building you are in now.

Bill: Moving on, how the Complexity Conference in Vancouver?

Lance: You didn’t read my blog post?

Bill: [Reading blog post] Wow, no best paper and only 66 participants. Seems a bit lower than last year.

Lance: We were correlated with STOC last year and next year at FCRC as well. Though not with the IEEE anymore.

Bill: Is complexity theory dying?

Lance: The talks at this Dagstuhl alone prove otherwise.

Bill: I particularly liked David Zuckerman’s talk about using statistical sum-product theorems to create non-malleable codes. Why is it so empty in here?

Lance: It’s a rare sunny day at Dagstuhl and we’re inside doing this typecast. What other topics are exciting you at Dagstuhl?

Bill: There’s a resurgence of interest in VP and VNP, Valiant’s algebraic analogues of P and NP and genuine optimism that VP <> VNP might be provable in the near future.

Lance: There is some great work there but let’s wrap this up while we have still have some daylight.

Bill: You know what to say Lance.

Lance: In a complex world, best to keep it simple.