tag:blogger.com,1999:blog-37222332015-01-26T06:52:12.696-06:00Computational ComplexityComputational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill GasarchLance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.comBlogger2244125tag:blogger.com,1999:blog-3722233.post-67419481688014865252015-01-22T07:03:00.002-06:002015-01-22T07:03:55.369-06:00There Should be an AlgorithmMy high school daughter Molly was reading her Kindle and said "You know how you can choose a word and the Kindle will give you a definition. There should be an algorithm that chooses the right definition to display depending on the context". She was reading a book that took place in the 60's that referred to a meter man. This was not, as the first definition of "meter" would indicate, a 39 inch tall male. A meter man is the person who records the electric or gas meter at your house. Today we would use a gender neutral term like "meter reader" if technology hadn't made them obsolete.<br />
<br />
Molly hit upon a very difficult natural language processing challenge known as <a href="http://en.wikipedia.org/wiki/Word-sense_disambiguation">word-sense disambiguation</a> with the most successful approaches using supervised machine learning techniques. If anyone from Amazon is reading this post, the Kindle dictionary would make an excellent application of word-sense disambiguation. You don't need perfection, anything better than choosing the first definition would be welcome. Small tweaks to the user interface where the reader can indicate the appropriate definition would give more labelled data to produce better algorithms.<br />
<br />
And to Molly: Keep saying "There should be an algorithm". Someday there might be. Someday you might be the one to discover it.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com6tag:blogger.com,1999:blog-3722233.post-6345130350309092172015-01-19T08:33:00.003-06:002015-01-19T08:34:39.871-06:00The two defintions of Chomsky Normal FormI have eight textbooks on Formal Lang Theory on my desk. Six of them define a CFG to be in <i>Chomsky Normal Form</i> if every production is of the form either A-->BC or A--> σ (σ a single letter). With that definition one can show that every e-free grammar can be put in Chomsky Normal Form, and using that, show that CFL ⊆ P. There is a very minor issue of what to do if the CFL has e in it.<br />
<br />
Two of the books (Sipers and Floyd-Beigel) define a CFG to be in <i>Chomsky Normal Form </i>if every rule is A-->BC or A--> σ OR S-->e and also that S cannot appear as one of the two nonterminals at the right hand side of a production of the form A-->BC. With this definition you can get that every CFL (even those with e in them) has a grammar in Chomsky Normal Form.<br />
<br />
The definitions are NOT equivalent mathematically, but they are equivalent in spirit and both aim towards the same thing: getting all CFL's in P (That's why I use them for. What did Chomsky used them for?)<br />
<br />
The first definition is correct historically- its what Chomsky used (I am assuming this since it's in the earlier books). The second one could be argued to be better since when you are done you don't have to deal with the e. I still like the first one, but its six of one, half a dozen of the other. One person's floor function is another person's ceiling function.<br />
<br />
I don't have a strong opinion about any of this, but I will say that if you use the second definition then you should at least note that there is another definition that is used for the same purpose. Perhaps make a homework out of this.<br />
<br />
There are many other cases where definitions change and the new one leads to more elegant theorems and a better viewpoint than the old one. There are even cases where the new definition IS equivalent to the old one but is better. IMHO the (∃) definition of NP is better than the definition that uses nondeterministic Poly Time TM's since this leads to the definition of the poly hierarchy. One drawback- if you want to define NL then I think you DO need nondeterministic TM's.<br />
<br />
The only problem I see with changing definitions is if you are reading an old paper and don't quite know which definition they are using. <br />
<br />
What examples of a definition changing (or an equivalent one being more used) do you approve of? Disapprove of?<br />
<br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com3tag:blogger.com,1999:blog-3722233.post-30245621173057663562015-01-15T12:34:00.000-06:002015-01-16T20:39:56.811-06:00The Impact Factor DiseaseThe Institute of Science Information (ISI) was founded in 1960 to help index the ever growing collection of scientific journals. The founder of ISI, Eugene Garfield, developed a simple impact factor to give a rough estimate of quality and help highlight the more important journals. Roughly the <a href="http://en.wikipedia.org/wiki/Impact_factor">impact factor</a> of a journal in year x is the average number of citations each article from years x-1 and x-2 receives in year x.<br />
<br />
Thomson Scientific bought out ISI in 1992 and turned the data collection into a business. Impact factors are not only being used to measure the quality of journals but of authors (i.e. researchers) and institutions as well. In many parts of the world a person's research quality is being measured strongly or sometimes solely by their ability to publish in high impact factor journals.<br />
<br />
This is bad news for computer science since conference proceedings in our field have historically more prestige than journals. We mitigate the ISI factors pretty well in the US but in many other countries this puts computer science at a disadvantage. The need for impact factor publications is one of the reasons conferences are experimenting with a hybrid model.<br />
<br />
In a new trend I get many announcements of journals highlighting their ISI impact factor, mostly very general and previously unknown to me. Our old friends WSEAS say "The ISI Journals (with Impact Factor from Thomson Reuters) that publish the accepted papers from our Conferences are now 32" in the subject line of their email.<br />
<br />
It's the vanity journal with a twist: publish with us and you'll raise your official numerical prestige. So we get a set of journals whose purpose is to raise the value of researchers who should have their value lowered by publishing in these journals.<br />
<br />
Raise your research standing the old fashioned way: Do great research that gets published in the best venues. The numbers will take care of themselves.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com6tag:blogger.com,1999:blog-3722233.post-65731557766089818882015-01-13T07:23:00.002-06:002015-01-13T07:23:31.664-06:00Barrier's for Matrx Mult Lower bound<br />
Matrix Mult:<br />
<br />
The usual algorithm is O(n^3).<br />
<br />
Strassen surprised people by showing an O(n^{2.81}) algorithm. (Now its so well known that its not surprising. I try to teach it to people who don't already know its true so they'll be surprised.)<br />
<br />
Over the years the exponent came down, though there was a long time between Coopersmith and Winograd's exp of 2.3755 and the recent improvements.<br />
<br />
Are these improvements going to lead to the exp 2+epsilon?<br />
<br />
Alas the answer is prob no :-(<br />
<br />
In <a href="http://eccc.hpi-web.de/report/2014/154/">Fast Matrix Mult: Limitations of the Laser Method</a> Ambainis, Filmus, and Le Gall show that the methods that lead to the algorithms above will NOT lead to an exp of 2+epsilon.<br />
<br />
How to react to news like this? Barriers should not make us give up; however, they should make us look for new techniques, perhaps guided by the barrier. I would like to think that if you know where NOT to look then it helps you know where TO look.<br />
<br />
There have been barriers that were broken (IP=PSPACE didn't relativize, the recent 2-prover PIR used techniques NOT covered by the barrier result, and the Erdos distance problem was proven after it was known that the current techniques `wouldn't work'). I am sure there are other examples, feel free to leave some in the comments<br />
<br />
Will this result help guide researchers in the right direction? Lets hope so!<br />
<br />
Of course, its possible that 2+epsilon is false and the barrier result is a first step in that direction.<br />
<br />
Which one am I routing for? Neither- I am routing for finding out!<br />
<br />
bill g.GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com8tag:blogger.com,1999:blog-3722233.post-8500876548183166032015-01-08T07:28:00.000-06:002015-01-08T07:28:08.648-06:00The History of the History of the History of Computer ScienceIn 2007, the science historian Martin Campbell-Kelly wrote an article <a href="http://www.thecorememory.com/THTHS.pdf">The History of the History of Software</a>, where he writes about how he initially wrote histories of the technical aspects of computer software back in the 70's but now he's evolved into writing more about the applications and implications of software technologies. He argues that the whole field of the history of software has moved in the same directions.<br />
<div>
<br /></div>
<div>
Donald Knuth made an emotional argument against this trend last May in his Stanford Kailath lecture <a href="http://kailathlecture.stanford.edu/2014KailathLecture.html">Let's Not Dumb Down the History of Computer Science</a>. If you can find an hour, this is a video well worth watching.<br />
<br /></div>
<!--
<center>
<iframe allowfullscreen="" frameborder="0" height="315" src="//www.youtube.com/embed/gAXdDEQveKw?rel=0" width="420"></iframe></center>
-->
In the January CACM Thomas Haigh gave his thoughts in <a href="http://cacm.acm.org/magazines/2015/1/181633-the-tears-of-donald-knuth/fulltext">The Tears of Donald Knuth</a>. Haigh argues that Knuth conflates the History of Computer Science with the History of Computing. Haigh says that historians focus on the latter and the History of Computer Science doesn't get enough emphasis.<br />
<br />
Let me mention two recent examples in that History of Computing category. <a href="http://www.imdb.com/title/tt2084970/">The Imitation Game</a> give a great, though slightly fictionalized, portrait of the computing and computer science pioneer Alan Turing focusing on his time at Bletchley Park breaking the Enigma code. Walter Isaacson, whose histories of Franklin, Einstein and Jobs I thoroughly enjoyed, writes <a href="http://www.amazon.com/gp/product/147670869X/ref=as_li_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=147670869X&linkCode=as2&tag=computation09-20&linkId=VVJ6OETDXBNQXEKO">The Innovators: How a Group of Hackers, Geniuses, and Geeks Created the Digital Revolution</a> which tells the stories of computers from Ada Lovelace to Google (oddly stopping before social networks).<br />
<br />
But what can we do about the History of Computer Science, particularly for theoretical computer science? We live in a relatively young field where most of the great early researchers still roam among us. We should take this opportunity to learn and record how our field developed. I've dabbled a bit myself, talking to several of the pioneers, writing (with Steve Homer) a <a href="http://people.cs.uchicago.edu/~fortnow/papers/history.pdf">short history</a> of computational complexity in the 20<sup>th</sup> Century and a history chapter in The Golden Ticket.<br />
<br />
But I'm not a historian. How do we collect the stories and memories of the founders of the field and tell their tales while we still have a chance?Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com5tag:blogger.com,1999:blog-3722233.post-10824654589019138582015-01-05T14:38:00.000-06:002015-01-06T10:21:53.686-06:00Why do students do this?Before my midterm in ugrad Theory of Computation I gave the students a sheet of practice problems to do that I would go over before the midterm.<br />
<br />
One of them was: Let L be in DTIME(T(n)). Give an algorithm for L*. Try to make it efficient. What is the time complexity of your algorithm? (I had done that if L is in P then L^* is in P in class earlier in the term.)<br />
<br />
My intention was that they do the Dynamic Programming solution. Since it wasn't being collected I didn't have to worry about what would happen if they did it by brute force. When I went over it in class I did the Dynamic Programming Solution, which is roughly T(n)^3 time.<br />
<br />
I allow my students to bring in a sheet of notes that they make up themselves.<br />
<br />
On the exam was the problem: Let L_1 \in DTIME(T_1(n)) and L_2\in DTIME(T_2(n)).<br />
Give an algorithm for L_1L_2. What is the time complexity of your algorithm?<br />
<br />
Of my 20 students 5 of them gave me, word for word, the dynamic programming solution to the L, L* problem.<br />
<br />
Why would they do this? Speculations:<br />
<ol>
<li>They just copied it off of their cheat sheet with no understanding.</li>
<li>They wanted pity points (they didn't get any and I told the class that if a similar thing happens on the final I will give them LESS THAN zero on the problem).</li>
<li>They so hoped that the L, L* problem would be on the exam (possibly becuase it was on their cheat sheet) that they misread the problem.</li>
<li>They thought `Dr. Gasarch wouldn't have put it on the practice exam unless it was on the real exam' (or something like that), so they misread it. </li>
</ol>
The five students were not very good (they did poorly on other problems as well, and on the HW), so it was not a matter of good students being confused or getting nervous.<br />
<br />
But I ask-- (1) is this kind of thing common? For my Sophomore Dscrete Math yes, but I was very slightly surprised to see it in my senior course. (2) Do you have examples? I am sure that you do, but my point is NOT to do student-bashing, its to ask WHY they do this. GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com6tag:blogger.com,1999:blog-3722233.post-72807164348226903302014-12-29T12:41:00.000-06:002014-12-29T12:41:38.008-06:002014 Complexity Year in ReviewTheorem of the year goes to <a href="http://arxiv.org/abs/1407.6692">2-Server PIR with Sub-polynomial Communication</a> 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 <a href="http://dx.doi.org/10.1145/293347.293350">showed</a> how to use n<sup>1/3</sup> bits of communication with two databases. Razborov and Yekhanin <a href="http://dx.doi.org/10.1109/FOCS.2006.10">proved</a> that using current techniques the bound could not be broken. Dvir and Gopi<br />
developed new techniques to break that barrier using n<sup>O(√(log log n/log n))</sup> bits with two databases, less than n<sup>δ</sup> for any δ. Bill <a href="http://blog.computationalcomplexity.org/2014/08/the-n13-barrier-for-2-server-pirs.html">posted</a> more on this result back in August.<br />
<br />
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 <a href="http://blog.computationalcomplexity.org/2014/12/favorite-theorems-recap.html">favorite theorems</a> for the past decade.<br />
<br />
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.<br />
<br />
We say goodbye to <a href="http://dmatheorynet.blogspot.com/2014/04/gm-adelson-velsky-passed-away.html">G.M. Adelson-Velsky</a>, <a href="http://bertoni.di.unimi.it/InMemoriam.html">Alberto Bertoni</a>, <a href="http://news.usc.edu/#!/article/59206/in-memoriam-edward-blum-90/">Ed Blum</a>, <a href="http://en.wikipedia.org/wiki/Ashok_K._Chandra">Ashok Chandra</a>, <a href="http://www.clrc.rhul.ac.uk/people/chervonenkis/">Alexey Chervonenkis</a>, <a href="http://www.news.cornell.edu/stories/2014/11/mathematician-eugene-dynkin-dies-90">Eugene Dynkin</a>, <a href="http://cs.illinois.edu/news/memory-clarence-ellis-1943-2014">Clarence "Skip" Ellis</a>, <a href="http://www.nytimes.com/2014/11/16/world/europe/alexander-grothendieck-math-enigma-dies-at-86.html">Alexander Grothendieck</a>, <a href="http://ferranhurtado.blogspot.com.es/">Ferran Hurtado</a>, <a href="http://www.cc.gatech.edu/news/georgia-tech-remembers-mike-stilman">Mike Stilman</a>, <a href="http://www.ae-info.org/ae/User/Stojmenovic_Ivan/OtherInformation">Ivan Stojmenovic</a>, <a href="https://agtb.wordpress.com/2014/06/30/berthold-vocking-1967-2014/">Berthold Vöcking</a>, <a href="http://rjlipton.wordpress.com/2014/07/01/remembering-ann-yasuhara/">Ann Yasuhara</a>, <a href="http://windowsontheory.org/2014/09/19/farewell-microsoft-research-silicon-valley-lab/">Microsoft Research-Silicon Valley</a> and <a href="http://en.chessbase.com/post/nyt-chess-column-dies-but-could-be-resurrected">The New York Times Chess Column</a>.<br />
<div>
<br /></div>
<div>
Thanks to our contributors <a href="http://blog.computationalcomplexity.org/2014/12/joint-center-for-quantum-information.html">Andrew Childs</a>, <a href="http://blog.computationalcomplexity.org/2014/11/guest-post-about-barbie-i-can-be.html">Brittany Terese Fasy</a> and <a href="http://blog.computationalcomplexity.org/2014/10/guest-post-by-dr-hajiaghayi-new-way-to.html">MohammadTaghi Hajiaghayi</a>.</div>
<div>
<br /></div>
<div>
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.</div>
Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com7tag:blogger.com,1999:blog-3722233.post-67384087722859873642014-12-22T16:33:00.001-06:002014-12-22T16:33:19.828-06:00Undergraduate ResearchI just received the Cornell Math Matters, dedicated to the memory of <a href="http://en.wikipedia.org/wiki/Eugene_Dynkin">Eugene Dynkin</a> 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.<br />
<br />
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.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com4tag:blogger.com,1999:blog-3722233.post-63755423551645835252014-12-18T06:44:00.000-06:002014-12-18T13:14:52.554-06:00The NIPS ExperimentThe <a href="http://nips.cc/Conferences/2014/">NIPS</a> (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.<br />
<br />
According to an <a href="http://mrtz.org/blog/the-nips-experiment/">analysis</a> 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 <a href="http://inverseprobability.com/2014/12/16/the-nips-experiment/">here</a>.<br />
<br />
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.<br />
<br />
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.<br />
<br />
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.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com12tag:blogger.com,1999:blog-3722233.post-68731554247891076012014-12-15T11:42:00.002-06:002014-12-15T12:11:36.006-06:00Joint Center for Quantum Information and Computer Science(Guest post by Andrew Childs who is now at the Univ of MD at College Park)<br />
<br />
<br />
<br />
We have recently <a href="http://cmns.umd.edu/news-events/features/2563">launched</a> a new <a href="http://quics.umd.edu">Joint Center for Quantum Information and Computer Science</a> (QuICS) at the University of Maryland. This center is a partnership<br />
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.<br />
<br />
We are pleased to announce opportunities for <a href="http://quics.umd.edu/postdocs">Hartree Postdoctoral Fellowships</a> <br />
(deadline: December 30, 2014) and <a href="https://quics.umd.edu/graduate-students">Lanczos Graduate Fellowships</a>. Outstanding postdoctoral and graduate researchers with an interest in quantum information processing are encouraged to apply.<br />
<br />
QuICS complements a strong program in quantum physics research at the <a href="http://jqi.umd.edu">Joint Quantum Institute</a>. Maryland is also home to a new <a href="http://umdrightnow.umd.edu/news/lockheed-martin-umd-partner-quantum-computing">Quantum Engineering Center</a>. <br />
It's an exciting time for quantum information here.<br />
GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com0tag:blogger.com,1999:blog-3722233.post-1220725433551791112014-12-11T07:22:00.000-06:002014-12-11T07:22:58.162-06:00The Ethics of Saving LanguagesThe linguist John McWhorter wrote an NYT opinion piece entitled <a href="http://www.nytimes.com/2014/12/07/opinion/sunday/why-save-a-language.html">Why Save a Language?</a> 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?<br />
<br />
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.<br />
<br />
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.<br />
<br />
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.<br />
<br />
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.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com11tag:blogger.com,1999:blog-3722233.post-20981636860699471672014-12-09T10:38:00.000-06:002014-12-09T10:38:11.338-06:00Godel and Knuth Prize Nominations due soon. Which would you rather win? Or ...(Alg Decision Theory conference in Kentucky: <a href="http://cs.uky.edu/~srsa224/ADT2015/">here.</a>)<br />
<br />
Knuth Prize Nominations are due Jan 20, 2015.<br />
For info on the prize see <a href="http://www.sigact.org/Prizes/Knuth/">here</a>, if you want to nominate someone<br />
go <a href="http://www.sigact.org/Prizes/Knuth/knuth15.pdf">here.</a><br />
<br />
Godel Prize Nominations are due Jan 31, 2015.<br />
For info on the prize see <a href="http://www.sigact.org/Prizes/Godel/">here</a>, if you want to nominate someone<br />
go <a href="http://www.sigact.org/Prizes/Godel/goedel_call15.pdf">here</a><br />
<br />
Would you rather:<br />
<br />
<ol>
<li>Win a Godel Prize</li>
<li>Win a Knuth Prize</li>
<li>Have a prize named after you when you are dead</li>
<li>Have a prize named after you when you are alive</li>
</ol>
I pick 4; however, I doubt I'll have of 1,2,3,4 happen to me.<br />
<br />
How about you?<br />
<br />
GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com4tag:blogger.com,1999:blog-3722233.post-74090557078947701702014-12-04T07:23:00.000-06:002014-12-04T08:10:42.499-06:00Favorite Theorems RecapWe've now completed five decades of favorite theorems.<br />
<ul>
<li><a href="http://blog.computationalcomplexity.org/2005/12/favorite-theorems-first-decade-recap.html">1965-1974</a></li>
<li><a href="http://blog.computationalcomplexity.org/2006/12/favorite-theorems-second-decade-recap.html">1975-1984</a></li>
<li><a href="http://dx.doi.org/10.1007/3-540-58715-2_130">1985-1994</a> (<a href="http://www.cs.uchicago.edu/~fortnow/papers/topten.pdf">PDF</a>)</li>
<li><a href="http://blog.computationalcomplexity.org/2004/12/favorite-theorems-recap.html">1995-2004</a></li>
</ul>
<div>
And to recap the ten we chose this year from 2005-2014</div>
<div>
<ul>
<li><a href="http://blog.computationalcomplexity.org/2014/02/favorite-theorems-connecting-in-log.html">Undirected Connectivity in Log Space</a></li>
<li><a href="http://blog.computationalcomplexity.org/2014/03/favorite-theorems-unique-games.html">Optimal Inapproximability for Max-Cut</a></li>
<li><a href="http://blog.computationalcomplexity.org/2014/04/favorite-theorems-extended-formulations.html">Limitations of linear programming</a></li>
<li><a href="http://blog.computationalcomplexity.org/2014/05/favorite-theorems-equilibrium.html">Complexity of Nash Equilibrium</a></li>
<li><a href="http://blog.computationalcomplexity.org/2014/06/favorite-theorem-pcp-simplified.html">Combinatorial Proof of PCP Theorem</a></li>
<li><a href="http://blog.computationalcomplexity.org/2014/07/favorite-theorems-compressing-local.html">Constructive Proof of the Lovász Local Lemma</a></li>
<li><a href="http://blog.computationalcomplexity.org/2014/08/favorite-theorems-limited-independence.html">Polylogarithmic independence fools AC<sup>0</sup></a></li>
<li><a href="http://blog.computationalcomplexity.org/2014/09/favorite-theorems-quantum-interactive.html">QIP = PSPACE</a></li>
<li><a href="http://blog.computationalcomplexity.org/2014/10/favorite-theorems-multilinear-circuits.html">Lower Bounds on Multilinear Formulas</a></li>
<li><a href="http://blog.computationalcomplexity.org/2014/11/favorite-theorems-circuit-lower-bounds.html">NEXP not in ACC<sup>0</sup></a></li>
</ul>
<div>
Ten more in ten years. </div>
</div>
Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com3tag:blogger.com,1999:blog-3722233.post-85710673825897044442014-12-01T13:33:00.001-06:002014-12-01T13:33:27.276-06:00Cliques are nasty but Cliques are nastierBILL: Today we will show that finding large cliques is likely a nasty problem<br />
<br />
STUDENT: Yes! In my High School the Cliques were usually at most six people and they gossiped about everyone else. They were very nasty.<br />
<br />
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<br />
<br />
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.<br />
<br />
BILL: We might need the Hypergraph version to model your school.<br />
<br />
<br />
Computer Scientists and Graph Theorists call a set of nodes that are all connected to each other a CLIQUE - pronounced CLEEK<br />
<br />
High School Kids call a group of people who hang out together a CLIQUE- pronounced CLICK.<br />
<br />
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?GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com12tag:blogger.com,1999:blog-3722233.post-49002557221203687462014-11-23T22:08:00.003-06:002014-11-24T09:58:36.471-06:00Guest Post about Barbie `I can be an engineer' -- Sounds good but its not.<br />
There is now a <i>I can be an engineer </i>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.<br />
<br />
Guest Blogger Brittany Terese Fasy explains:<br />
<br />
Remember the controversy over the Barbie doll that said<br />
"Math class is tough!"? Well, Barbie strikes again.<br />
<br />
If you haven't heard about <i>II can be a computer engineer </i> 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<a href="http://www.dailydot.com/geek/barbie-engineer-book-girls-game-developers/"> here</a>.<br />
<br />
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 <a href="http://www.thepetitionsite.com/635/734/252/a-petition-to-make-barbie-a-real-computer-engineer/#">here</a>.<br />
<br />
Progress was made as Barbie issued an apology: <a href="http://www.designntrend.com/articles/26477/20141120/mattel-issues-apology-depicting-barbie-incompetent-computer-engineer-receives-backlash.htm">here.</a> 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. <br />
<br />
Until the book is completely off the market we should not stop! And maybe one day, we'll see<br />
<i>Barbie: I can be a Computational Geometer</i> on the shelves.GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com6tag:blogger.com,1999:blog-3722233.post-75012982966762786162014-11-20T07:25:00.001-06:002014-11-20T12:56:02.643-06:00A November to Remember<a href="http://www.imdb.com/title/tt2084970/">The Imitation Game</a> 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, <a href="http://www.imdb.com/title/tt2980516">The Theory of Everything</a> with Eddie Redmayne as Stephen Hawking opened earlier this month. Also this month has the physics-laden <a href="http://www.imdb.com/title/tt0816692/">Interstellar</a> and the nerd-hero robot adventure <a href="http://www.imdb.com/title/tt2245084/">Big Hero 6</a>. Science rules the box office, though likely to be clobbered by a Mockingjay.<br />
<br />
Speaking of Turing, The ACM Turing Award will now come with a $1 million dollar prize, up from $250K, <a href="http://bits.blogs.nytimes.com/2014/11/13/google-lifts-the-turing-award-into-nobel-territory/">now on par with the Nobel Prize</a>. Thanks Google.<br />
<br />
Madhu Sudan will receive the 2014 <a href="http://www.infosys-science-foundation.com/prize/laureates/2014/madhu-sudan.asp">Infosys Prize in Mathematics</a>. Nimrod Megiddo wins the 2014 <a href="https://www.informs.org/Recognize-Excellence/INFORMS-Prizes-Awards/John-von-Neumann-Theory-Prize">John von Neumann Theory Prize</a>.<br />
<div>
<br /></div>
Harvard Computer Science gets <a href="http://bits.blogs.nytimes.com/2014/11/13/gift-from-ballmer-will-expand-computer-science-faculty-at-harvard">12 endowed faculty lines</a> from former Microsoft CEO Steve Ballmer. That's about the number of former Microsoft Research theorists now on the job market. Just saying,<br />
<br />
Sanjeev Arora <a href="http://windowsontheory.org/2014/11/11/sanjeev-arora-potential-changes-to-stocfocs-report-from-special-focs-session/">asks for comments</a> on the potential changes to STOC/FOCS discussed at the recent FOCS. Boaz Barak has set up a new CS Theory <a href="http://cstheory-jobs.org/">jobs site</a>. On that note, the November <a href="http://cra.org/uploads/documents/resources/crndocs/issues/1114.pdf">CRA News</a> has 75 pages of faculty job ads, up from 50 a year ago.<br />
<br />
Terry Tao <a href="http://thecolbertreport.cc.com/videos/6wtwlg/terence-tao">talked twin, cousin and sexy primes</a> on Colbert last week. The new result he quoted is that the Generalized Elliott-Halberstam conjecture <a href="http://michaelnielsen.org/polymath1/index.php?title=Bounded_gaps_between_primes#Current_records">implies</a> that there are infinitely many pairs of primes at most six apart.<br />
<br />
Not all happy news as we <a href="http://www.nytimes.com/2014/11/16/world/europe/alexander-grothendieck-math-enigma-dies-at-86.html">lost the great mathematician Alexander Grothendieck</a>. Tributes by <a href="http://lucatrevisan.wordpresscom/2014/11/14/alexander-grothendieck/">Luca</a> and <a href="http://rjlipton.wordpress.com/2014/11/16/alexander-grothendieck-1928-2014">Ken</a>.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com10tag:blogger.com,1999:blog-3722233.post-66777697870848436072014-11-17T15:51:00.001-06:002014-11-17T15:51:26.125-06:00A Fly on the wall for a Harvard Faculty meeting: Not interesting for Gossip but interesting for a more important reasonI was recently in Boston for Mikefest (which Lance talked about <a href="http://blog.computationalcomplexity.org/2014/10/sipser-symposium.html"> here)</a> 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.<br />
<br />
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<br />
you could tell there were deep seated tensions. It was all very civilized. Plus there was a free lunch.<br />
<br />
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:<br />
<br />
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.)<br />
<br />
What should a non-majors course have in it?<br />
<br />
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).<br />
<br />
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.)<br />
<br />
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 <a href="http://nlpers.blogspot.com/2014/10/machine-learning-is-new-algorithms.html">post</a>. ) What should the categories be anyway? And what about the functors?<br />
<br />
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!)<br />
<br />
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.)<br />
<br />
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?<br />
<br />
When I saw <i>Back to the future 2 </i>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.<br />
<br />
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?<br />
<br />
and is it OKAY if it doesn't?<br />
<br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com6tag:blogger.com,1999:blog-3722233.post-43777157147070851612014-11-13T10:22:00.001-06:002014-11-13T10:22:36.615-06:00From Homework Solution to Research PaperInspired by the <a href="http://blog.computationalcomplexity.org/2014/11/george-dantzig-100.html">Dantzig Story</a> 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.<br />
<br />
Teaching in the early 90's, I showed <a href="http://dx.doi.org/10.1016/0304-3975(79)90044-6">Valiant's proof</a> 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.<br />
<br />
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.<br />
<br />
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.<br />
<br />
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.<br />
<br />
And that's how Viktória Zankó got a <a href="http://dx.doi.org/10.1142/S0129054191000066">research paper</a> from solving a homework problem.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com5tag:blogger.com,1999:blog-3722233.post-65146554773742981912014-11-11T09:49:00.001-06:002014-11-12T10:54:33.170-06:00Non controversial thoughts on rankingsUS News has a ranking of CS depts and various subcategories. Recently MohammadTaghi Hajiaghay and Luca Trevisan have suggested alternative rankings <a href="http://projects.csail.mit.edu/dnd/ranking/">here (Moh)</a> and <a href="http://lucatrevisan.wordpress.com/2014/10/23/an-alternative-to-the-seddighin-hajiaghayi-ranking-methodology/">here (Luca)</a>. These rankings inspire me to record some thoughts about rankings.<br />
<br />
<ol>
<li>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 <a href="http://en.wikipedia.org/wiki/The_100:_A_Ranking_of_the_Most_Influential_Persons_in_History">here</a>), 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 <a href="http://www.amazon.com/View-Year-3000-Michael-Hart/dp/0967107717">here</a>). My own ranking of Bob Dylan satires <a href="https://www.cs.umd.edu/~gasarch/dylan/dylan.html">here</a> was done for my own amusement.</li>
<li>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: <i>When a measure becomes a target is ceases to be a measure</i>. 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. </li>
<li>There have been a variety of rankings of presidents (see <a href="http://en.wikipedia.org/wiki/Historical_rankings_of_Presidents_of_the_United_States#Liberal_and_conservative_raters">here)</a>. 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 <i>Hail to the chiefs </i>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.</li>
<li>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.</li>
<li>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.</li>
<li>Rankings that compare very unlike objects are useless. <a href="http://www.computersciencedegreehub.com/top-30-computer-science-programming-blogs-2014/">Here</a> 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.</li>
<li> 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 <a href="https://www.youtube.com/watch?v=Zyg4_brSFhw">part 1</a>, <a href="https://www.youtube.com/watch?v=53vp2SPaup4">part 2</a>, <a href="https://www.youtube.com/watch?v=-iOKKBt0UqM">Part 3)</a>- 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 <i>Science fiction Folk Songs </i>was mispelled as <i>Science fiction Filk Songs </i>and hence the term was born.)</li>
<li>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.</li>
<li>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). </li>
<li>Finding what you want: I think that <i>Raiders of the lost ark </i>has tone of the best ending-of-a-movie ever. So I Googled <i>best movie ending </i>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 <i>best movie endings Raiders of the lost ark</i> 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. </li>
<li>Steve Skienna and Charlie Ward have written a book <a href="http://www.amazon.com/Whos-Bigger-Historical-Figures-Really/dp/1107041376">Who's bigger: Where historical figures really rank </a> which has a transparent and reasonable way to measure... not clear. Probably fame. For a review see <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/rank.pdf">here</a></li>
</ol>
GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com7tag:blogger.com,1999:blog-3722233.post-91363561520569528962014-11-08T07:34:00.000-06:002014-11-08T07:34:47.034-06:00George Dantzig >= 100We celebrate the 100th anniversary of the birth of George Dantzig today. In his <a href="http://blog.computationalcomplexity.org/2005/05/george-dantzig-1914-2005.html">obituary post</a> we talked about his work on optimization, particularly the simplex method for solving linear programs.<br />
<br />
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.<br />
<br />
What does this have to do with Dantzig? Turns out he is the true source of the legend. From Dantzig's Washington Post <a href="http://www.washingtonpost.com/wp-dyn/content/article/2005/05/18/AR2005051802171.html">obituary</a>:<br />
<blockquote class="tr_bq">
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.</blockquote>
<blockquote class="tr_bq">
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.</blockquote>
<blockquote class="tr_bq">
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. </blockquote>
<blockquote class="tr_bq">
"That was the first inkling I had that there was anything special about them," Dr. Dantzig recalled.</blockquote>
Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com3tag:blogger.com,1999:blog-3722233.post-91783430357809915452014-11-05T16:07:00.000-06:002014-11-05T16:07:19.692-06:00Favorite Theorems: Circuit Lower Bounds My long time blog readers should have no surprise on my final favorite theorem of 2005-2014.<br />
<blockquote class="tr_bq">
<a href="http://dx.doi.org/10.1145/2559903">Nonuniform ACC Circuit Lower Bounds</a> by Ryan Williams (<a href="http://web.stanford.edu/~rrwill/acc-lbs.pdf">PDF</a>)</blockquote>
We saw several exciting circuit lower bound results in the 80's, highlighted heavily in my first <a href="http://people.cs.uchicago.edu/~fortnow/papers/topten.pdf">list of favorite theorems</a> (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.<br />
<br />
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 Mod<sub>6</sub> gates. Williams eliminated that possibility for constant depth circuits with Mod<sub>k</sub> gates for any k.
<br />
<br />
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.<br />
<br />
Ryan Williams' greatest insight though was to find non-trivial satisfiability algorithms for ACC<sub>0</sub> circuits and use them to give lower bounds for NEXP. Recently Ryan has turned that process around, for example getting a <a href="http://dl.acm.org/citation.cfm?id=2591811">faster algorithm for all-pairs shortest path</a> using the techniques from the Razborov-Smolensky circuit lower bounds. Ryan's <a href="http://web.stanford.edu/~rrwill/projects.html">publication page</a> has several new results giving algorithms from lower bounds.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com1tag:blogger.com,1999:blog-3722233.post-58728250901465858812014-11-03T08:43:00.001-06:002014-11-03T13:38:46.504-06:00A few more notes about Sipser and Sipser-60th<br />
While Lance was AT Mikefest (Sipser's 60th Bday conference), helping to organize it, emceeing the personal statements, I was... also there.<br />
A few notes<br />
<br />
<ol>
<li>Aside from his graying hair, Mike still looks like a teenager.</li>
<li>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. </li>
<li>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).</li>
<li>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.</li>
<li>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?</li>
</ol>
And two non-sipers notes (sort of) from Mikefest<br />
<br />
<ol>
<li> 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. </li>
<li>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. </li>
</ol>
GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com4tag:blogger.com,1999:blog-3722233.post-83159728935598674982014-10-30T12:35:00.000-05:002014-10-30T12:35:00.058-05:00Metrics in AcademicsCongratulations 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 <a href="http://online.wsj.com/articles/baseballs-shift-does-it-work-1410304648">infield shift</a>, the process of moving the infielders to different locations for each batter based on where they hit the ball, all based on statistics.<br />
<br />
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.<br />
<br />
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.<br />
<br />
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.<br />
<br />
As you might have guessed this post is motivated by attempts to rank departments based on metrics, such as described in the controversial <a href="http://blog.computationalcomplexity.org/2014/10/guest-post-by-dr-hajiaghayi-new-way-to.html">guest post</a> last week or by <a href="http://www.mybiasedcoin.blogspot.com/2014/10/rankings-everywhere.html">Mitzenmacher</a>. There are so many rankings based on metrics, you just need to find one that makes <a href="http://www.businessinsider.com/smartest-public-colleges-in-america-2014-10">you look good</a>. 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.<br />
<br />
I prefer the US News & World report approach to <a href="http://grad-schools.usnews.rankingsandreviews.com/best-graduate-schools/top-science-schools/computer-science-rankings">ranking CS Departments</a>, 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 <a href="http://grad-schools.usnews.rankingsandreviews.com/best-graduate-schools/top-science-schools/computer-theory-rankings">rank the theory groups</a> but I still prefer the subjective approach.<br />
<br />
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.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com18tag:blogger.com,1999:blog-3722233.post-90259269498942215942014-10-28T11:21:00.000-05:002014-10-29T06:45:18.717-05:00Sipser Symposium<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-XPw1hPHAzdk/VE-ZK3DhnUI/AAAAAAAAzLY/RjXnA_2T15U/s1600/IMG_1295.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-XPw1hPHAzdk/VE-ZK3DhnUI/AAAAAAAAzLY/RjXnA_2T15U/s1600/IMG_1295.JPG" height="300" width="400" /></a></div>
<br />
<br />
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 <a href="http://www.amazon.com/gp/product/113318779X?ie=UTF8&camp=213733&creative=393185&creativeASIN=113318779X&linkCode=shr&tag=computation09-20&linkId=UIBV3YGYPAGFOONH&qid=1414503108&sr=8-1&keywords=sipser+introduction+to+the+theory+of+computation">great textbook</a> and the corresponding popular course he still teaches).<br />
<br />
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.<br />
<br />
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.<br />
<br />
Johan Håstad recounted the early days of circuit complexity. Avi also talked about lower bounds. Shafi talked on her <a href="http://dx.doi.org/10.1145/12130.12137">great paper</a> 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.<br />
<br />
A number of Mike's PhD students also gave talks. Dan Spielman gave a framework for designing quantum algorithms without knowing much quantum.<br />
<br />
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<span class="Apple-tab-span" style="white-space: pre;"> </span>and Yiqun Yin<span class="Apple-tab-span" style="white-space: pre;"> </span>.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com7tag:blogger.com,1999:blog-3722233.post-67008878433560415042014-10-23T10:11:00.000-05:002014-10-24T08:32:51.209-05:00Guest 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.)<br />
<br />
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 <a href="http://projects.csail.mit.edu/dnd/ranking/">here</a>.<br />
<br />
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.<br />
<br />
Please feel free to give us feedback (hajiagha@cs.umd.edu).GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com48