Friday, November 19, 2010

Complexity Theory

If you're a student thinking of going into complexity theory, take a good look around and ask yourself: "Do I really want to be in a field with this amount of groupthink?" [1,2,3,4,5, and last but certainly not least 6]


Back in the day, I was myself saved from a career in complexity by Omer Reingold's logspace connectivity.

57 comments:

Anonymous said...

You don't like Ryan's result? It actually seems right up your alley; it is very much based on "real" algorithmics.

Mihai said...

I have nothing against Ryan's result, as I had nothing against Omer's (I actually found it very elegant). I am simply disgusted by the group dynamics.

Anonymous said...

What do you mean when you say that Omer's result saved you from a career in complexity?

Anonymous said...

I agree, complexity theory has too many spokespeople (and any clown can get a blog).

But ... most complexity theorists don't have blogs, and some of these guys are the cleverest in computer science. I know some of them who understand everything going on in all current theory research: approximation algorithms, learning theory, sublinear algorithms, geometric algorithms, metric embeddings, game theory, data structures.
Yet they are very very humble.
Such broad understanding and polymathness you don't find in other subareas of theory.

I haven't met an approximation algorithmist who knows why BPP is in Sigma_2, or even what its conceptual content is.

alex said...

You shouldn't go into physics either. Too many people think the earth revolves around the sun.

Anonymous said...

to Previous anonymous: I am an approximation algorithmicist, and the conceptual content of BPP contained in Sigma_2 is you guess a hard function, check that it is hard and can use a PRG.

On a side note, I find it very hard to believe that you have never met an approximation algorithmicist that can say at least something about that proof. My only conclusion is that you are exaggerating, which is exactly the reason it is so hard to get excited every 2 months when there is a new, earth-shattering breakthrough about mod 5.5 gates with at most 4 gates.

I actually would love to hear more about Ryan's result just due to my own intellectual curiosity, if it weren't so off-putting dealing with the arrogance of so many complexity theorists.

Micha said...

I'm pretty new to the complexity field, and I think of myself of a normal social animal. In particular, I think I'm apt to notice arrogance. But I'm pretty lost there: I never thought of one of the big figure to have any kind of arrogance. Is there something I'm missing there?

Anonymous said...

I feel all research areas with more than a few persons involved are like that. Do you know of counter examples?

Anonymous said...

If you're a student thinking of going into data structures, take a good look at Mihai's blog posts and ask yourself: "Do I really want to be in a field with this arrogant guy playing god?

Anonymous said...

Mihai, I think your read is incorrect. It is politics, not groupthink.

Anonymous said...

Can you clarify what you mean?

If I understand correctly what "groupthink" means, I don't think that betting money against one colleague, like Aaronson did, is groupthinking.

Mihai said...

If you're a student thinking of going into data structures, take a good look at Mihai's blog posts and ask yourself: "Do I really want to be in a field with this arrogant guy playing god?

Hey, hey, hey! I take issue with the word "playing".

Anonymous said...

I like Mihai's bluntness, I'm quite tired of the "omg omg these guyz are soooo smart AND YET SO HUMBLE!!!!".

Anonymous said...

I don't think that betting money against one colleague, like Aaronson did, is groupthinking.

Well, Aaronson will never consider Deolalikar a colleague! To him he is an outsider.

UpNext:TC_Zero said...

I have worked in complexity theory and have a good idea of the significance of Williams' result, and appreciate the elegance of the proof as well.

But I do agree with Mihai about the painful groupthink expressed by complexity theorists across the various blogs.

For example, none of the bloggers say why we should even think of ACC as a robust and interesting complexity class. I think only Luca talks about the fact that Ryan Williams' result is actually that a superclass of ACC is shown to be different from NEXP. In many ways, this superclass, although somewhat technical to define, is more natural and interesting than shallow-depth circuits with Mod_p gates (functions computable by circuits depth-two, polylog-fanin AND gates feeding into a symmetric gate). Seriously, other than pure mathematical curiosity, Mod_p gates have been an unwelcome distraction in complexity theory.

Unfortunately, none of the complexity bloggers say why we should consider ACC a real/serious complexity class (other than saying that it was easy to separate P from AC0, but add arbitrary Mod_p gates, and we can't even separate it from NEXP). Perhaps we were mucking with a class that just doesn't have any mathematical structure, a good sign of its being uninteresting. Fortunately, due to work of Yao/Beigel--Tarui and Williams, ACC has been put to rest.

Eleanor Roosevelt said...

Great minds discuss ideas. Average minds discuss events. Small minds discuss people.

Anonymous said...

mihai, you are married, rite ?
are you living with your wife ? is she a cs too ?

Unknown said...

I don't know if Mihai is arrogant or not. As a researcher, I see that he delivers results and that he can explain them in a way that you need a small or no background to understand it.

However, I believe this time Mihai has underestimated the importance of this result. I mean as noted in those blogs, it's the first result over 23 years. Furthermore, it uses techniques that could solve the P=NP question.

It's not self-promotion of complexity, but rather excitement of the people involved. But while in the 1900s you would have to be the Director of the Post Office to know this level of interaction, now it's on the Web.

Anonymous said...

LOL
Congrats Mihai!
At last you got back to your sensationalistic style!
(Seriously.)

Anonymous said...

Refreshing post, comme d'habitude.

I agree groupthink is disturbing on its own, but some groups tend to make it even more disturbing. It's very ironic to see this exemplfied in some of the comments here.

Anon: It's so... umm... invigorating of you to bring M's wife into the discussion. Strong move right there!

Eleanor: One could argue you got it all backwards. But hey, did you look into doing complexity?

Anon 101 said...

Just because a group of people share an opinion does not make that opinion the result of groupthink. On the other hand, it's likely that, if someone out there were to be less excited by Ryan's result, they would be unlikely to be so vocal about it (except perhaps anonymously, but AFAIK there are no anonymous TCS bloggers). So I think what you're seeing is less groupthink and more self-selection bias... Unless you have other reasons to believe it's groupthink, which I'd be interested to hear.

Anonymous said...

I thought it was purely a reaction to the recent heavily publicized P/NP attempt?

I.e they are trying to say, HERE is what a result we take seriously looks like.

Anonymous said...

UpNext:TC_Zero said: For example, none of the bloggers say why we should even think of ACC as a robust and interesting complexity class. I think only Luca talks about the fact that Ryan Williams' result is actually that a superclass of ACC is shown to be different from NEXP. In many ways, this superclass, although somewhat technical to define, is more natural and interesting than shallow-depth circuits with Mod_p gates (functions computable by circuits depth-two, polylog-fanin AND gates feeding into a symmetric gate).

You should read the paper again. For the algorithm one needs the class of circuits to be closed under ORs: that's why it works for ACC but not for depth-two, polylog-fanin AND gates feeding into a symmetric gate. The author himself makes that point in the paper.

GASARCH said...

In order to show that a community has GROUPTHINK you need to show that there is an X such that
(1) everyone (or most people,
or the leaders or something)
have the same opinion about X, and
(2) that opinion is wrong.

If X=Ryan Williams result is GREAT

then
you have shown that several blogs
liked it. In order to complete your argument you must show
(1) The blogs are indicative,
and
(2) X is not so great.

Judging on the comments on the blogs the opinion that Ryan's result is so great IS being challenged by some in the community.

I am not saying you are incorrect,
only that your argument has several gaps you need to fill in.

GASARCH

Anonymous said...

From Wikipedia: "Groupthink is a type of thought within a deeply cohesive in-group whose members try to minimize conflict and reach consensus without critically testing, analyzing, and evaluating ideas. [...]".

When I read the cited blog posts on Ryan's result, I don't see any evidence that this is happening.

It seems, however, that Mihai thinks that the mere presence of consensus is sufficient for groupthink to be happening. Interestingly enough, when Mihai presents this hypothesis (and others) he makes exactly the mistakes he accuses the complexity theorists of: He presents a thought that generates conflict and avoids consensus, but he does so without critically testing, analyzing, or evaluating ideas.

Anonymous said...

I don't think Mihai is interested in formally proving his claim that the complexity blogs and/or community exhibits groupthink. He was merely expressing an opinion. To an outside observer, that opinion appears to be two-fold:

(1) While Ryan Williams' result is certainly a nice advance, the amount of fuss being generated by the complexity community is vastly out of proportion with the greatness of the result. This is a result of the complexity community's lack of perspective with regards to what constitutes a great result -- similar or even more profound advances in algorithms or data structures do not garner this much attention, due to the lack of a bunch of blogs dedicated to self-promotion of their field.

(2) This is consistent with a pattern of "crying wolf" behavior in the complexity community. Every new epsilon advancement in proving a lowerbound for mod 3.7 gates of depth 4 and polylog*ackermann fan-in is trumpeted over and over on the blogosphere as the best thing to ever happen in the history of science. Many of the amazingly awesome results in complexity are not so impressive when one takes the time to really look at them, and this leads to a loss of credibility.

Anonymous said...

Every new epsilon advancement in proving a lowerbound for mod 3.7 gates of depth 4 and polylog*ackermann fan-in is trumpeted over and over on the blogosphere as the best thing to ever happen in the history of science.

I haven't seen weak partial results remotely akin to what you are making fun of, trumpeted on any blogs. (They definitely exist in the literature, though.) Can you cite any reasonable example?

Mihai said...

Groupthink is perhaps not the best word, but I was trying to express a sentiment, which is often hard to do in words :)

I am bothered by the choir; it makes me think that I entered the wrong church. And yes, the choir does show up regularly. I distinctly recall the time of Omer's logspace result, or the time of Sergey's locally decodable code.

Of course, not everybody shares these sensibilities. If you are not bothered by the choir, and complexity theory is something you enjoy, then what can I say? Live long and prosper!

Anonymous said...

I work in complexity theory.

I do not like the choir.

But I like complexity theory.

Google said...

Groupthink:

http://www.boingboing.net/2010/11/21/turkey-groupthink.html


Seriously though, is complexity any different than other areas in this respect? Why is it different?

Anonymous said...

Complexity is different in that it touts its achievements so effectively, so as to drown out the superior achievements in related fields such as algorithms. Much like a child who keeps screaming until his mother gives in and grants him more cake than his siblings. I can't count the number of times where a complexity result won best paper in STOC/FOCS in lieu of a far more impressive result in algorithms -- simply because the complexity theorists do not shut up until everyone else gives in to their claims of superiority.

Mihai said...

Seriously though, is complexity any different than other areas in this respect? Why is it different?

Yes, it is different, though there's probably no easy explanation. But there is a lot of feel-good effort in the field (including the emphasis on barriers, and people repeating to each other that these problems are so hard).

Ryan Williams said...

Hi Mihai,

You might like to know that these lower bounds initially arose from an attempt to prove that CNF SAT on n variables and poly(n) clauses has a 1.9^n time algorithm (the subject of our joint SODA'10 paper). So from some perspective, you could say that I failed to refute Strong ETH, and "merely" could prove NEXP is not in ACC instead.

However, I think these "algorithms vs complexity" wars are short-sighted and unproductive. Both are useful for each other (as you know). I hoped that the current work would indicate this, if anything.

Mihai said...

Ryan, there is no war between the scientific fields of complexity and algorithms. (If some of my readers want to start one, it's their call.) I can and do say bad things about algorithms people with some regularity :)

Now, I don't find it particularly hard to entertain the position that I could be annoyed by the ceremonial beating of the drums on the complexity turf without passing judgement on the value of complexity research or any specific result inside it.

PS: If you want advice from someone who's been writing text for the blog crowd for a while, I suggest you take the quotes out from "merely".

Anonymous said...

If there were a big, but incremental, breakthrough in algorithms, such as a O(n^2.2) algorithm for matrix multiplication, I'm sure there would be an equal number of blogs praising the result in exactly the same way. (In fact, I would guess that some of the complexity blogs you linked to would also praise the algorithms result.)

Anonymous said...

to the last anonymous, your comment looks reasonable initially, but after a while I realize it is perhaps the "point" of Mahai's post: in order for an algorithmic result to get the same mentioning in blogs, you need to improve the running time of the matrix multiplication algorithm, which has immediate impact for so many problems, and if it is simple it would also be a real contribution to practice as well. probably you are just giving an example to say that algorithm results will also be appreciated, but this particular example really makes me wonder whether it was the point of Mahai's.

Anonymous said...

my point was: any computer scientist, engineer, or mathematician can understand how important is the matrix multiplication problem. only this kind of results is as good as these complexity results? i know i am off the point but can't help to point it out.

Anonymous said...

Note tha the following has nothing to do with Ryan's result, which I think is fantastic and fully deserves all the attention and praise it is receiving.

But I agree with Mihai's larger point (and he should correct me if I am misinterpreting).

The point is that complexity gets a huge amount of attention and "prestige" in TCS. A heuristic measure of this could be number of STOC/FOCS papers, number of prize-winning publications and theses, centers (IAS, CCI) etc...

I personally love complexity (I work in a very closely related area) and am very happy with this.

That being said, I do often wonder why, as computer scientists, we get so excited about some of the results we see in complexity that are really breakthroughs in combinatorics or some other minor sub-field of complexity. Often these results have little to nothing to do with computer science but we seem to praise them simply because they use "deep" math. And we do this at the expense of other results which are much more important from a CS point of view.

Anonymous said...

I agree with the above Anon. I don't think this criticism really applies to Ryan's result, which after all is a proof-of-concept for a technique aimed at an important programme in computer science.

But off the top of my head, why were we so excited about Dvir's proof of the finite field Kakeya conjecture? Sure, this was a great piece of mathematics (and his techniques have led to several recent breakthroughs in mathematics that have received well deserved attention). But while it had some applications to some subfields of complexity, I don't think from a CS perspective it was a very important result.

Anonymous said...

But off the top of my head, why were we so excited about Dvir's proof of the finite field Kakeya conjecture?

As far as I can tell, it was primarily due to transitivity: a lot of people were very happy to be able to think to themselves "Dvir could do what Terry Tao couldn't; my publication record is better than Dvir's [not that it was a fair comparison when Dvir was just starting out]; therefore I and my field are the greatest!"

Not that there's anything special about this case. The same sort of feelings come up whenever anyone contributes to another field.

Anonymous said...

For the last comment : Finally, someone said it. Bulls Eye!!

TCS people grow out of complexes and work. All work is good right now - start thinking of high level questions, what is important and what not, years later - 500 maybe .. a weird enough complexity result is as good as a
$n^{\epsilon^{-O(1)}}$ PTAS for a graph problem nobody cares about, in a paper that nobody understands, using techniques nobody would like to ask their enemies to implement.

Anonymous said...

Hi,
In this issue, I agree with Mihai. For example, Raecke's result and Bartal's result to me seem much more important than recent complexity results on circuit lower bounds, undirected connectivity in log-space, and unique-game hardness. If you work on algorithms you will know how important and general (and sometime very practical) is that you an solve your problem on trees instead of general graphs and only pay a little bit, O(log n) factor in the worst case, in terms of the quality of the solution. I could name more in algorithms of course.

arnab said...

Mihai, since you already have a well-read blog and are a good communicator, why don't you "hype" algorithmic results that you find important and ground-breaking? By "hype", I mean convey the excitement about what makes particular results exciting to you.

I understand that this activity might not accord with your personal style, but still, it would be more productive (and interesting) than complaining about others' opinions on breakthrough results.

Anonymous said...

arnab, I think the comment just before your comment gives such examples.

Anonymous said...

I think a problem is that there are no algorithms/data structure blogs of similar quality as the complexity blogs. Most algorithms/data structure blogs (including this one) don't emphasize on other's peoples results, but rather on the blog writer's results. They seem in general more self-centered.

GASARCH said...

A though experiment and a challenge for Mihai:

If Ryan had proven SAT not in DTIME(n^2)
and the blogs all cheered, would that be group think?

For what values of x would the result
SAT not in DTIME(n^x) not be worthy of all the blogs applauding.

Why was Omer's result not worth of the attention that it got?

How many results can you point to that the complexity is more impressed with than they should be. (I would guess
one or two a year tops.)

Also note that the blogs have had plenty of people disagreeing with the importance of the results, and Lance and Scott have taken them seriously in
intelligent debate. That hardly seems like a group-think.

Also- some commenter said that Complexity gets more than its deserved share of best paper awards. This is the kind of statement for which one can gather
evidence. Commenter- please do so or retract your comment.

Anonymous said...

The following link is a nice example of what, I think, Mihai wanted to point out.

The first sentence of the abstract of Lance Fortnow's talk:

"P versus NP: An Epic Struggle": It is the most important open question in computer science if not all of mathematics.

Despite the fact that P!=NP is a very important problem, I still think that P!=NP folk are the only scientists I know that are 'bold' enough to claim that the central problem of their area is 'the most important' one in computer science.

And, honestly, I could find plenty of adjectives describing their 'struggle', but none among them would be even remotely close to 'epic'.

Anonymous said...

Man, I am so utterly confused about all this. Is there actually an issue with complexity people? like blowing things out of proportion and going gaga over it when they shouldn't? From the comments it does look like there is :)

I would say this though: if complexity theory attracts you, go work in that area and enjoy! Don't care about issues not related to science ;-) ("group-think", "financial support", "hard math", etc.)

Anonymous said...

Meanwhile, over on Lance's blog, there has been another breakthrough!

Anonymous said...

From all these frequent breakthroughs, it appears to me that complexity theory is an easy field. After all, how hard can the problems be if there is a breakthrough every year? :-)

Anonymous said...

Previous Anonymous, you misunderstand! The problems are insanely hard, they just have so many breakthroughs because they are so much smarter than everyone else.

Anonymous said...

@ anonymous #5
" to Previous anonymous: I am an approximation algorithmicist, and the conceptual content of BPP contained in Sigma_2 is you guess a hard function, check that it is hard and can use a PRG."

That is not at all the conceptual content of BPP in Sigma_2. It is not known to be possible to efficiently check that something is hard in the way that you are describing, or that the pseudorandom object that you want actually exists. What you are talking about is much closer to more recent hardness vs. randomness tradeoff type results.

You should review the proof, it is much simpler than that. The idea is just that you can use error amplification until for any input almost all strings cause the program to act correctly, and then essentially just run a " set lower bound protocol", a two round interactive proof which verifies that indeed, the set of yes strings is very large.

Anonymous said...

They must believe it is important, otherwise, they would have to admit to themselves that the complexity people live in vain. http://en.wikipedia.org/wiki/Scanners_Live_in_Vain

Anonymous said...

Mihai, not a complexity theory comment, but just need your answer on this:

is this a Romanian English poet you know?

http://www.corpse.org/index.php?option=com_content&task=blogcategory&id=13&Itemid=32

I think she is in one of your pictures, if I am correct about her identity. Where is she, what happened to her. Her writing is so compelling...

Thank you for any info you can volunteer.

A fan.

Mihai said...

Anon, yes, I do know the person, but I have no current contact information. What's the point of asking such a random question in a blog comment as opposed to email?

Anonymous said...

Mihai, hello, hope all is well with you and your work. As a reader of your blog since its very inception, I cannot help noticing the dwindling number of entries per year. So much so, in fact, that 'informatics weekly' has gone into 'quarterly?' -i mean its been a good four month since ur last post. What's the state of complexity theory these days, especially as reflected in your blog --no more news from the 'western front,' or is it just no more news from the Patrascu post?
I am mostly saying this because, as a reader, I have certain expectations of constancy in an author's output, especially if they're announcing periodical contributions.

Anonymous said...

Happy 2011, Mihai. Mebs' time you started us off on this new year with a new blog post...although 2012 is ok, too...take your time. ;)