Category: Computer Science

Posted on

Rush Science

It looks like QIP talk accepts and rejects are out.  Sadly a piece of work I’ve been hacking on for a while didn’t make the cut (eventually it will make it’s way to the arXiv.)  But I did get one of the more amusing reviews sentences I’ve seen:

However, working this idea out seems to a require a protocol which is rather involved and, in some places, subtle.  Consequently, I was not able to work through and understand the construction in the time available.

Which is, perhaps, one of the best condemnations of the computer science conference system I’ve ever seen!

All rush and no play makes science something something.

Posted on

Doing My Part

Ryan Williams ACC. Which reminds me the other day a student of mine accidentally called coNP, coCP. Yep, turns out CP is a class. So the question is: will P versus NP be resolved before or after all two alphabetic symbol complexity labels are used up?

Posted on

Uniquity Symposium on "What is Computation?"

Readers of the Pontiff might be interested in a series of articles coming out in the ACMs Ubiquity publication concerning the question: “What is Computation?” Over the next 15 weeks the following articles will come out on this subject including one by a jokester:

The following articles will appear on Ubiquity once a week, beginning in November 2010.
1. What is Computation? [opening statement], by Peter J. Denning
2. Evolution of Computation, by Peter Wegner
3. Computation is Symbol Manipulation, by John Conery
4. Computation is Process, by Dennis J. Frailey
5. Computing and Computation, by Paul Rosenbloom
6. Computation and Information, by Ruzena Bajcsy
7. Computation and Fundamental Physics, by Dave Bacon
8. The Enduring Legacy of the Turing Machine, by Lance Fortnow
9. Computation and Computational Thinking, by Al Aho
10. What is the Right Computational Abstraction for Continuous Scientific Problems? by Joseph Traub
11. Computation, Uncertainty, and Risk, by Jeffrey P. Buzen
12. Natural Computation, by Erol Gelenbe
13. Biological Computation, by Melanie Mitchell
14. Is the Symposium Question Harmful? by Peter Freeman
15. Wrapping it Up [closing statement], by Peter J. Denning

I suppose this is a paper dance of some sort, but I’m guessing its one with me dancing around saying “One of these kids is not like the others.”

Posted on

It's the QIP Final Countdown

QIP 2011 submissions due October 14, 2010, lah. (Dear readers from Singapore, is there a comma before “lah”?)
Not to be confused with the final sponge down.

===========================
QIP 2011 – Call for submissions
14th workshop on Quantum Information Processing
Tutorials January 8-9, NUS, Singapore
Workshop January 10-14, The Capella, Sentosa Singapore
Conference Website: http://qip2011.quantumlah.org
Paper Submission: http://www.easychair.org/conferences/?conf=qip2011
Quantum Information Processing (QIP) is a rapidly developing field of research spanning both physics and computer science. As the name implies, the field extends information processing (including computing and cryptography) to physical regimes where quantum effects become significant.
QIP 2011 is the fourteenth workshop on theoretical aspects of quantum computing, quantum cryptography, and quantum information theory in a series that started in Aarhus in 1998 and was held last year in Zurich. QIP 2011 will feature plenary talks (called invited talks at previous QIP workshops), featured papers (previously called long contributed talks), contributed papers, and a poster session.
Submissions of abstracts for contributed papers are sought in research areas related to quantum information science and quantum information processing. A small number of contributed paper submissions will be selected as featured papers. The submission to QIP should consist of 2-3 pages, containing a non-technical, clear and insightful description of the results and main ideas, their impact, and their importance to quantum information and computation. In addition, the submission should direct the reader to a technical version of the work (this should preferably be online but otherwise can be provided as an attachment). The submission should not consist of a compressed version of the technical exposition of the paper, but instead should facilitate the reading of the technical version and help the program committee assess its importance. In exceptional cases, submissions without technical versions may be accepted.
The 2-3 page abstracts of the accepted contributed papers and featured papers will be posted on the QIP 2011 website. More details will be provided in the acceptance notices.
Submission deadlines
Contributed papers: October 14
Posters: December 1
Notifications of acceptance
Contributed talks: November 17
Posters submitted by November 10: November 17
Posters submitted after November 10: December 8
Programme Committee:
Andris AMBAINIS (University of Latvia)
Steve BARTLETT (University of Sydney)
Sergey BRAVYI (IBM)
Wim van DAM (UC Santa Barbara)
Daniel GOTTESMAN (Perimeter Institute) (chair)
Pawel HORODECKI (Gdansk University of Technology)
Iordanis KERENIDIS (Universite Paris-Sud)
Hirotada KOBAYASHI (National Institute of Informatics)
Robert KOENIG (Caltech)
Barbara KRAUS (University of Innsbruck)
Mio MURAO (University of Tokyo)
Peter SHOR (MIT)
Graeme SMITH (IBM)
Frank VERSTRAETE (University of Vienna)
Michael WOLF (Niels Bohr Institute)
Steering Committee:
Dorit AHARONOV (Hebrew University of Jerusalem)
Ignacio CIRAC (MPQ, Garching)
Eddie FARHI (MIT)
Renato RENNER (ETH Zurich)
Louis SALVAIL (Universite de Montreal)
Barbara M. TERHAL (IBM T J Watson)
John WATROUS (University of Waterloo)
Andreas WINTER (University of Bristol / CQT, NUS) (chair)
Andrew Chi-Chih YAO (Tsinghua University)
Local Organisers:
Cedric BENY (Poster Session)
Rahul JAIN (Local Arrangement and Social Events)
Hartmut KLAUCK (Tutorials)
KWEK Leong Chuan (Sponsorship)
Darwin GOSAL (Webmaster)
Markus GRASSL (Outreach and Publicity)
Ethan LIM (Webmaster)
Tomasz PATEREK (Rump Session)
Stephanie WEHNER
Andreas WINTER (Coordinator)
Miklos SANTHA (Advisor)

Posted on

2010 MacArthur Awards

The 2010 MacArthur Fellows have been announced. Among them are a physics teacher, a quantum astrophysicist, an optical physicist, a biophysicist, and a computer security expert:

  • Amir Abo-Shaeer Physics Teacher inspiring and preparing public high school students for careers in science and mathematics through an innovative curriculum that integrates applied physics, engineering, and robotics.
  • John Dabiri Biophysicist investigating the hydrodynamics of jellyfish propulsion, which has profound implications for our understanding of evolutionary adaptation and such related issues in fluid dynamics as blood flow in the human heart.
  • Michal Lipson Optical Physicist working at the intersection of fundamental photonics and nanofabrication engineering to design silicon-based photonic circuits that are paving the way for practical optical computing devices.
  • Nergis Mavalvala
    Quantum Astrophysicist linking optics, condensed matter, and quantum mechanics in research that enhances our ability to detect and quantify gravitational radiation.
  • Dawn Song Computer Security Specialist exploring the deep interactions among software, hardware, and networks to increase the stability of computer systems vulnerable to remote attack or interference.

A good year for physics…well if you want to buck the feelings of the old codgers and insist physics does not just equal particle physics. I guess it no longer takes a genius to do particle theory (just a context free grammar generator?) Just kidding fellows 🙂

Posted on

NRC (not really correct?) Graduate School Rankings

The NRC graduate school ranks are due out tomorrow, September 29. For those who don’t know, the last NRC ranking was in 1995 and the latest is much delayed (I.e. the “data” such as it is is already out of date.) Departments have been given access to the data for a week now but have been under embargo. As a blogger it is a moral imperative to search the inter tubes for leaks of this data. Surprisingly there has been little leaked, but today I’m proud to say that my own UW, while not technically breaking the embargo (okay maybe they have :)) has some info out about their forthcoming rankings. Now I’m probably definitely biased but I can pretty safely say that the UW CS ranking is off by a bit:

The NRC assessment of UW Computer Science & Engineering is based on clearly erroneous data. The assessment is meaningless, and in no way representative of the accomplishments of UW CSE. Errors in the data affect (at least) UW CSE, many other computer science programs nationally, and many programs in other fields at the University of Washington.
During the week of September 19th, NRC provided pre-release access to its long-delayed “Data-Based Assessment of Research-Doctorate Programs in the United States,” scheduled for public release during the week of September 26th.
We, along with colleagues in other computer science programs nationally and colleagues in programs in other fields at the University of Washington, quickly discovered significant flaws of three types in NRC’s data:

  • Instances in which the data reported by NRC is demonstrably incorrect, sometimes by very substantial margins.
  • Instances in which the accuracy of the data cannot easily be checked, but it does not pass even a rudimentary sanity check.
  • Instances in which institutions interpreted NRC’s data reporting guidelines differently, yielding major inconsistencies.

Here are three specific examples affecting UW CSE:

  • Due to difficulty in interpreting NRC’s instructions, NRC was provided with an incorrect faculty list for our program – essentially, a list that included anyone who had served as a member of a Ph.D. committee. In 2006 (the reporting year), UW CSE had roughly 40 faculty members by any reasonable definition. In the NRC study, our “total faculty” size is listed as 91 and our “allocated faculty size” (roughly, full time equivalent) as 62.5. A large number of these “additional faculty” were industrial colleagues – whose “academic records” (including grants, publications, and awards) were quantitatively evaluated by NRC as if these individuals were full members of our faculty. Since faculty size is the denominator in many measures computed by NRC, you can imagine the result – clearly erroneous.
  • NRC reports UW CSE with 0% of graduate students “having academic plans” for 2001-05 (the reporting period for this measure). In fact, 40% of our graduating Ph.D. students took full-time faculty positions during this period. We are one of the top programs nationally in producing faculty members for major departments; in recent years our graduates have taken faculty positions at Berkeley, CMU, MIT, Princeton, Cornell, Wisconsin, Illinois, Michigan, Penn, Waterloo, Toronto, WashU, UCSD, Northwestern, UCLA, UBC, Maryland, Georgia Tech, UMass-Amherst, and many other outstanding programs. NRC obtained this number from an outside data provider; it’s clearly erroneous.
  • NRC reports UW CSE as having 0.09 “awards per allocated faculty member.” The erroneous faculty count is not sufficient to explain this, given that our faculty includes 14 ACM Fellows, 10 IEEE Fellows, 3 AAAI Fellows, 14 Sloan Research Fellowship recipients, a MacArthur Award winner, two NAE members, 27 NSF CAREER Award winners, etc. We don’t know where NRC obtained this data, but it’s clearly erroneous.
    The University of Washington reported these issues to NRC when the pre-release data was made available, and asked NRC to make corrections prior to public release. NRC declined to do so. We and others have detected and reported many other anomalies and inaccuracies in the data during the pre-release week.

The widespread availability of the badly flawed pre-release data within the academic community, and NRC’s apparent resolve to move forward with the public release of this badly flawed data, have caused us and others to take action – hence this statement. Garbage In, Garbage Out – this assessment is based on clearly erroneous data. For our program – and surely for many others – the results are meaningless.

Posted on

CS Theory Q&A Site in Public Beta

The “Theoretical Computer Science” Q&A site, aka TheoryOverflow, is now in public beta.  Now you can ask all those theoretical computer science questions that you’ve been putting off working on while you were watching the saga that has been…the Next Food Network Star.  What you thought I was going to say the supposed proof of P versus NP?

Posted on

More P vs NP

The Gray Lady on P vs NP with, crazily, a mention of this here blog. Totally not deserving of said mention, but the article is fun.

Posted on

PNP Hype

One of the most interesting things about the recent claim of a proof that P does not equal NP (see this post on the ice tea blog for a list of problems people are having with the proof, as well as this page hosted on the polymath project) is the amount of interest this paper has drawn. Certainly a large part of this has to do wit the fact that current there are (a) more computer science bloggers than ever before and (b) so many tweeters tweeting the night away. Also, of course, Slashdot can cause all hell to break lose.
But I wonder if there isn’t something else going on here. Privately I have spoken to colleagues who are much more qualified to understand this proof and they are generally skeptical of the claim. This seems completely rational to me, considering the long list of claims that either P=NP or P does not equal NP that have been shot down over the years (a fascinating list at the P-versus-NP page.) That their priors are well tilted toward skepticism seems fairly natural. So, my guess is that for the hard-core complexity theorists their really isn’t that much interest in taking time out of what they are working on understanding the paper…unless someone who they really respect tells them they should do so (I think the Optimizer’s post is a good example of this. Plus, please, people, stop emailing Scott, he needs to get some work done 😉 )
Yet still there is a lot of interest. I’d like to suggest that the reason for this is that the paper involves an unusual diversity of topics in attempting to make a proof. Indeed the paper (an updated version is available here) consists mostly of a lot of review of the fields which are claimed to be needed to understand the proof. These include work on random instances of k SAT, finite model theory, Hammersly-Clifford theorem, and more. Now there are people in theoretical computer science who have enough breadth to skip these review chapters, but I would say that they are in the minority. And even more interestingly there are people who probably are experts in just one of these areas who can read and nod their head at section of the proof, but don’t know the other sections. Okay well maybe I am projecting here, but I know when a group of AI people heard about the paper they were very interested that it used some of the concepts they use everyday. So maybe the reason that this particular P not equal to NP paper has grabbed this much attention is that it samples from a wide group of people who see parts they understand and therefore gets these people to try to understand the full proof. Okay that and the fact that the paper isn’t really “cranky.”
Now as to whether or not the proof is actually correct, well I’m not as rich as Scott, but I would bet that some of the points raised in objection are actually problems, so I’d need some pretty stellar odds before I’d bet that the proof is correct.
Oh and one other thought: it seems that the paper was actually “leaked” after Deolalikar sent the paper to a group of respected complexity theorists. I sure hope that whoever leaked the paper consulted the NyTimes ethicist before leaking it. Or maybe it was WikiLeaks who leaked the paper? Have they no shame?!?!
update:. Note that some people did ask the author for permission before posting about it. See this comment