The Yahoo! Groups Product Blog
- Members: 121
- Category: Algorithms
- Founded: Jan 13, 2003
- Language: English
Yahoo! Groups Tips
Did you know...
Hear how Yahoo! Groups has changed the lives of others. Take me there.
Show Message Summaries
Sort by Date
| Now that most of the FCRC
Deadlines have passed, I would again suggest that you post your
papers on a public archive like the Electronic Colloquium on Computational Complexity or the Computing Research
Repository. The world wants to know about your research.
Which one should you choose? You don't have to, you can freely submit
to both ECCC and CoRR. But how do they compare? [Disclosure: I am on
the ECCC Scientific Board.]
- ECCC focuses on computational complexity though often contains
papers across theoretical computer science. CoRR broadly covers all of
computer science (with tags for subfields) and is part of the arXiv project covering physics and math as
- An article has to be approved by an ECCC board member to
meet a minimum standard before it can appear. CoRR only checks for
relatedness to the topic area.
- Both plan to have papers posted forever. ArXiv is currently run by
the Cornell Library that gives stronger backing to this
promise. However every paper on the ECCC and CoRR should later appear
in a conference proceedings and/or journal.
- ECCC takes postscript submissions. CoRR prefers LaTeX submissions
and processes them with hypertex.
- Both systems allow revisions and all versions remain available.
- ECCC has a (not-so-user-friendly) discussion system and email
announcements of new papers. CoRR has RSS feeds for each subject
class. Both systems plan to continually update
their interfaces and features.
Posted by Lance to Computational Complexity at 12/19/2006 07:38:00 AM
| Can a CS degree propel you to a major acting role on a popular new TV
series? Worked for this
I heard a complaint that in the movie Deja Vu they used
face-recognition algorithms to find a suitcase in a large city in a
matter of seconds. Because it's important to keep the computer science
accurate in a time-travel movie.
In the last Numb3rs, Charlie the
mathematician was seen carrying a copy of the SIAM Journal on
Computing, a prominent TCS journal. Was he reading my paper or yours?
At the end of the episode Larry the physicist left on the space
shuttle to spend six months on the International Space Station while
the actor, Peter MacNicol, moves over temporarily to the show 24. Couldn't Larry just have gone on
a normal sabbatical?
On a more serious note we finally got around to watching Al Gore's
documentary An Inconvenient
Truth. Gore seriously impressed me with how he laid out the
arguments and effects of global warming. The movie really affected my
daughters leading to some interesting family discussions
about warming and what we can do. I highly recommend watching the
movie for those who haven't yet done so.
Posted by Lance to Computational Complexity at 12/20/2006 03:30:00 PM
| Last month the University of Chicago faculty received an email from
new president Robert Zimmer and soon-to-be-provost Thomas Rosenbaum
about discussions on creating a program in Molecular Engineering.
The boundary between science (as the study of natural phenomena) and
engineering (as the development and study of man-made artifacts) has
become much more porous and in certain areas has virtually vanished.
Historically, the University of Chicago has had a major international
presence in science, but with a few special exceptions, has not
systematically developed programs in engineering. With this important
and evolving paradigm shift in the relationship between science and
engineering, there are important questions regarding how the University
should respond. These questions arise both because of exciting and
important new areas of investigation at the science/engineering
interface and because a lack of an explicit investment in engineering
may hamper the development of our science.
Does science need engineering because engineering problems lead to
important intellectual scientific questions or because engineering
provides the tools needed by the scientists to carry on their
research? Perhaps a bit of both.
Posted by Lance to Computational Complexity at 12/21/2006 02:49:00 PM
| December 22, 2006
Dear Recruiting Committee:
George Henry is among the top fifty computational complexity theorists
on the market this year and you should consider him for any faculty,
postdoc or janitorial position in your department.
Computational Complexity compares complexity classes representing
different amounts of complexity resources among different
computational models. There are hundreds of complexity classes and
thousands of variations on those classes. Henry's best result shows
that for two of these classes, one of them is not contained in the
other assuming that some third class is not contained in some fourth
class. This work appeared in a theoretical computer science
conference you've never heard of.
For service, George Henry has wasted his money joining the ACM,
IEEE, AMS, MAA, ASL and SIAM. He's even (under duress) refereed a
paper or two.
Henry gave a seminar once and nobody ran out screaming, probably
because they were too busy sleeping. Henry also taught a course
once. He was not actually convicted on any harassment charges.
On the plus side George Henry has no two body problem since he's never
had a relationship last more than three days.
In short, there are several great complexity theorists on the market
this year but since your department has no chance of hiring any of them you might as well look at Henry.
Professor of Computer Science
Posted by Lance to Computational Complexity at 12/22/2006 01:24:00 PM
| From about early December to late January the academic world takes a
little breather as many universities end their fall quarters and start
their spring. Many students and faculty are away, the universities are
ghost towns. A time for rest, a chance to catch up on some of those
tasks we've been putting off for the fall. A chance to get ready for
the next quarter or semester. This week between Christmas and New
Years marks the nadir of activity: Absolutely nothing interesting
should happen this week.
But over recent years this season seems far less quiet. We also work
in a more global society and many countries, like Israel and India,
treat this week not much differently than any other week. We can
access the internet from anywhere and more importantly, we know everyone
else can access the internet from anywhere. Taking time to visit
relatives and friends or even going on vacation for many does not mean
a break from email. Yesterday, Christmas Day, I received several
actionable emails almost at the level of a typical workday.
We need an internet-free week. We should just shut down the whole
network for seven days. Some people would use the time to relax and
take a break knowing they will not be missing anything
important. Others would continue to work finding themselves
surprisingly much more productive than usual.
Posted by Lance to Computational Complexity at 12/26/2006 08:12:00 AM
| As we start thinking about our Theoretical Foundations proposals, a few related items from the theory
Joan Feigenbaum and Michael Mitzenmacher have written a report "Towards
a Theory of Networked Computation" available on the group's web page. The
report is still under revision and Joan welcomes your comments.
SIGACT Chair Richard Ladner writes in the latest SIGACT News about the
importance of the required Broader Impacts criteria in NSF proposals.
One way to think
about the Broader Impacts criterion is that when we receive money from
the people of the United States through NSF, the people would like to
know ahead of time of what benefit the research may or will be to
society. If there is little or no benefit then why should the people
continue to support NSF? When NSF goes to Congress to ask for money,
it is going to the people's representatives, who ask for
justification to spend the people's money on scientific
research. Basically, NSF's funding, and ours indirectly, depend on
the belief by the public that broader impacts come from our research.
Some people have said to me that a focus on Broader Impacts is a move
away from basic research to more mission oriented research, or
research with strings attached. If we look at the ways that we can
satisfy the Broader Impacts criterion, they are very general, and
relate to education, broadening participation by underrepresented
groups, and other benefits to society. Please read the representative
activities for concrete ideas for
how to include Broader Impacts in our proposals.
As SIGACT Chair, I am trying to help increase the funding for computer
science theory research. The best way to increase funding for research
is to convince people it is important to them and the people around
them. There is a difference between "important" and
"useful". Artists are able to convince people to buy art, not
because it is useful, but because it inspires them. Astronomers
convince people to pay them to study the stars, not because they are
useful (except for our own star, the sun), but because the stars are
fascinating in their own right. Understanding the birth and possible
death of the universe is of no practical value, but is just a
All this said, I am a firm believer in
serendipity. Often, research leads to unexpected results and
unanticipated applications. Unfortunately, this phenomenon is quite
rare and probably not common enough to convince people to provide
large amounts of research money. The best approach is to have a great
story about the benefits of theoretical computer science research and
its promise for the future. This will generate enough money for all of
us so that rare serendipitous events will happen naturally in the
course of doing our research.
Posted by Lance to Computational Complexity at 12/27/2006 09:27:00 AM
| The paper of the year goes to Settling
the Complexity of 2-Player Nash-Equilibrium by Xi Chen and Xiaotie
Deng which finished characterizing the complexity of one of the few
problems between P and NP-complete. The paper won best paper award at FOCS.
The story of the year goes to Grigori Perelman, his proof of the
Poincaré Conjecture, his declining of the Fields Medal and
Shing-Tung Yau's portrayal in the New
Yorker and the lawsuit threat
Science magazine named Perelman's proof the Breakthrough
of the Year.
Meanwhile the theory-friendly number theorist Terrence Tao accepted his
Fields medal and CMU cryptographer Luis von Ahn and Tao won MacArthur
My post FOCS
Accepts and a Movie received over 200 comments mostly about the
state of the theory conferences. Sadly the movie
and the rest of the science.tv site have disappeared. I also
finished my favorite complexity theorems,
at least for now.
In 2006 we celebrated the centennials of the births of Kurt
Gödel and Richard
Rado and mourned the early death of Mikhail Alekhnovich.
Thanks to guest blogger Claire Kenyon, guest posters Eldar Fischer,
Jérémy Barbay, Janos Simon and podcast guests Luis
Antunes, Eldar Fischer, Troy Lee and his opponents. The biggest thanks
to Bill Gasarch who did all of the above several times.
Happy New Years to all my readers and let's look forward to an exciting FCRC and a recommitment of
the United States to increased funding in the basic sciences.
Posted by Lance to Computational Complexity at 12/28/2006 11:14:00 AM
| As we begin January so begins the hiring season. In January CS
departments start sifting through candidates deciding whom to bring in
for interviews. Don't wait until you get your interview call, now is
the time to get your job talk ready.
A great job talk by itself won't guarantee you a job, but I've heard
of many an instance where a bad talk has ruined a candidate's chances
despite otherwise stellar credentials. A good job talk should achieve
Fail to do the first two and you will not get the job. We theorists
have a tendency to want to "wow" an audience with our clever
techniques but first you must spend several slides carefully giving an
intuitive description of your research and why those in the audience
should care about the results. Be sure and mention what your own
research is early in the talk and again at the end.
- Explain your results.
- Explain why your results are important.
- Explain how you achieved your results.
Know your audience, usually a broad spectrum of computer
scientists. You give a different talk to them than you would in a
regular theory seminar. Motivation and intuitive explanations of your
research are key.
Repeat the following mantra as you make your slides: Formulas
bad. Pictures good. Formulas bad. Pictures good.
Give a practice talk in your own department. Invite some people from
outside theory. Listen to the comments. Revise your talk. Repeat.
Posted by Lance to Computational Complexity at 1/02/2007 07:29:00 AM
| The New York Times reports
on a possible merger of the two major US satellite radio
companies. This would resolve one of the great dilemmas as XM carries the audio of every Major
game and Sirius has a station
devoted to live and archival broadcasts of the Metropolitan Opera. |
On the face of it, you would expect most baseball fans would rather
watch paint dry than attend an opera and vice versa. But I'm not alone
among the people who fanatically follow both. I can't pin down the
exact connection between opera and baseball and one can make many
philosophical comparisons (e.g. both require large teams but at most fixed
times individuals rule the stage, both require a good attention
span). Most lovers of both that I know are
also scientists though that might just be my lack of a good
sample. And I can't explain the Italians who seem to embrace opera and
In the academic world we get little choices about where we can live,
so I find myself extremely lucky to be in a city with a great
tradition in both baseball and
opera. I've mentioned baseball
more than opera in this weblog, but it was the baseball season tickets
that I gave up once the kids were born.
If you are a great lover of baseball or opera you should give the
other a try. And if you read the title of today's post and thought
about the browser, shame on you.
Posted by Lance to Computational Complexity at 1/03/2007 08:48:00 AM
| An economist, a physicist and a computer scientist were sitting at a
table. A true story, not the beginning of a joke. One of them said
We were solving fundamental problems twenty to thirty years
ago. There is still much we don't understand but today we are only
Any one of them could have said that,
scientific insecurity runs through all fields. A similar set of
scientists probably had a similar discussion twenty years ago as well.
At the end they all concluded that the future of their fields lied not
in the cores of their fields but in the interaction between them and
other fields not represented, like biology. They probably also said
that twenty years ago.
Posted by Lance to Computational Complexity at 1/04/2007 06:14:00 AM
| Jan van Leeuwen runs down many of the anniversaries coming up this
Reading your post 2006 Year in Review, I was reminded of a number of
memorable things that are coming up in 2007.
Are there any commemorative facts to be noted in 2007? Most certainly there
are, although it isn't anything like the Gödel year we just had. I'm not
counting the Robert
A. Heinlein Centennial to be held in Kansas City later this year, undoubtedly a major event for the science fictionists among us.
Staying closer to our field, in 2007 it will be 100 years ago that John
Mauchly was born. Together with Howard Aiken and J. Presper Eckert he
is one of the best known, early computer pioneers from the US. Together
with Eckert he built the ENIAC and later the UNIVAC I (built between 1946
2007 also marks the 100 year anniversary of another computer pioneer, namely
Svoboda from the Czech Republic. He was the main designer of the first Czechoslovak relay automatic computer SAPO (built between 1947 and
1951), working in the Research Institute of Mathematical Machines within
the Czech Academy of Sciences.
From a more theoretical perspective, in 2007 it will be 100 years ago that
Hassler Whitney was born. As a mathematician he made some highly original
contributions to early graph theory, notably on the four color problem and
on planarity (cf. Whitney's planarity criterion). He is also widely credited
as the inventor of matroid theory, of which the foundations were defined in
his 1935 paper On
the Abstract Properties of Linear Dependence.
Other mathematicians whose centennials are coming up include H.M.S.
Coxeter and Harold
But 2007 also marks the 300 year (!) anniversary of the birth of Leonhard Euler. The math
community is celebrating the Tri-Centennial Birthday of Euler in many
Posted by Lance to Computational Complexity at 1/05/2007 08:26:00 AM
| A graduate student asks
What should I wear for an academic job
Most computer scientists won't notice and will completely
forget what you wore when it comes to decision making time. But the
wrong clothes might make a bad impression on some of them and you
might meet administrators or faculty from other department with
different standards of attire. You never want to give the appearance
that you are not taking the interview seriously.
On the other extreme I have seen candidates looking uncomfortable in
suits they clearly borrowed or bought off the rack. My suggestion,
dress as nicely as you feel comfortable. To be specific, I'd suggest
nice pants and a jacket with or without a tie for men. For women the
best I can say is dress professionally.
Don't feel afraid to ask the person hosting your visit about these
kinds of questions. The host generally wants you to succeed and can
tell you about who you will meet and any expectations they may have.
Posted by Lance to Computational Complexity at 1/07/2007 08:27:00 PM
| Suresh and Jeff cover the
currently meeting in New Orleans. Suresh talked
about a lecture given by Luc Devroye giving techniques that might help
determine the actual constant factors in some algorithms. I usually ignore constants even in the exponents. Perhaps that's why
you tend not to see me at SODA conferences.
Many readers pointed to a New York Times article
discussing how the freeze on spending levels for 2007 will affect
science funding, a problem I mentioned
last month. The Times article mostly describes the affect on big
science projects but those of us doing "small science" will
be hit hard as well. The CRA recommends
that you contact your representatives and senators.
Posted by Lance to Computational Complexity at 1/08/2007 06:13:00 PM
| Why do so many scientists wear glasses? Thirty years ago this question
was essentially equivalent to "Why so many scientists have bad
eyesight?" I don't have a good answer to this second riddle,
perhaps some genetic link between scientific ability and eyesight,
perhaps scientists don't have worse eyesight than society in general
and I just have biased beliefs.
But now the question "Why do so many scientists wear
glasses?" has much less to do with eyesight. With advances in
contact lenses and surgery most people can do away with their
glasses. But most scientists seem to keep their glasses, even wearing
them with pride. Is it really a fashion statement? I've asked some of
my colleagues, they worry about the price or the risks, both of which
are quite low once you do the research.
I couldn't wait to get rid of my glasses. I started wearing contacts
in college in the late 80's and had LASIK surgery in 2002. I've had
better than 20/20 vision and haven't needed to worry about my eyesight
since. How do your glasses feel?
Posted by Lance to Computational Complexity at 1/10/2007 10:18:00 AM
| While Luca suffers
in Hong Kong, I am visiting beautiful Columbia, South Carolina. (The
ribs are better here) Next week a day in Bloomington, Indiana and the
following week a couple of days in Ann Arbor, Michigan as I visit the
flagship universities of those states. |
Over my life I have visited the flagship campuses in Arizona, Indiana,
Iowa, Maryland, Massachusetts, Michigan, Minnesota, Nebraska, New
Jersey (Rutgers), North Carolina, Oregon, Pennsylvania (Penn State),
South Carolina, Texas, Vermont, Virginia, Washington, West Virginia
and Wisconsin. (Illinois is conspicuously absent). I have also visited several campuses of the California
and New York systems which don't have a specific flagship. I
can more locations of flagship campuses than I can state capitals.
universities got a strong push from the Morrill Land Grant
Act passed during the Lincoln administration after the southern
states that objected (like South Carolina) had left the union.
One of the great strengths of the US higher education system are these
state universities, independent and competing, instead of a system of
nationalized universities that you find in many other countries.
Posted by Lance to Computational Complexity at 1/11/2007 08:13:00 AM
| A cute problem that I got off Steve Fenner's door that he got from FOM. |
Let x and y be two integers with 1<x<y and x+y≤100.
Sally is given only their sum x+y and Paul is given only their product
xy. Sally and Paul are honest and all this is commonly known to both
conversation now takes place:
What are the numbers?
- Paul: I do not know the two numbers.
- Sally: I knew that already.
- Paul: Now I know the two numbers.
- Sally: Now I know them also.
Posted by Lance to Computational Complexity at 1/12/2007 05:44:00 AM
| Richard Ladner wants me to remind my readers about the SIGACT student
research competition. From his chair letter in the last SIGACT news.
There will be a new event at STOC 2007, the Student Research
Competition, which will be a poster and short presentation competition
for undergraduates. The deadline for submissions is February 23rd,
2007. If you are working with an undergraduate on research, please
encourage him or her to submit to this competition. Accepted students
are provided up to $500 for travel to the conference. This competition
is an excellent way to engage the next generation of theory
researchers in our conference. I want to thank Brent Heeringa for
chairing this new activity for SIGACT.
(Theoretical Aspects of Rationality and Knowledge) conference meets
this year in Brussels in June mixing computer
scientists, economists and philosophers discussing knowledge,
rationality and how it all plays in CS and economic models. And I'm on
the PC this year. Submission deadline is January 30.
The 27th Crypto
conference will be held August in Santa Barbara, one of the few
conferences held in the same location each year. Submission deadline
February 19th. For those who feel Crypto focuses too much on applied
research, the Theory of Cryptography
Conference (TCC) meets next month in Amsterdam.
ICALP, the granddaddy of
European theory conferences, meets in Poland in July. Submissions by
Princeton in August. Deadline April 7. MFCS (Eastern European
Theory) in Czech Republic in August, deadline April 2.
There are many many more. DMANET
will keep you on top on what's going on.
Posted by Lance to Computational Complexity at 1/15/2007 07:16:00 AM
| It is a conference ritual as far back as I remember. Your arrive at
the conference and receive the proceedings, all the papers to be
presented at the conference many of which you are seeing for the very
first time. I would take the proceedings to my room, smell that new
proceedings smell and open it up, first checking that my papers looked
fine, not that I could do anything if they weren't. Using the
proceedings I would plan what talks I would attend the first day. |
The proceedings would never leave my room until after the
conference. I just hated lugging the heavy proceedings
around. Sometimes when a speaker said something that didn't make sense
to me, I would simply borrow a proceedings from someone sitting next
When I returned home I would put the proceedings in its proper place
on my office shelf, marveling at my complete collection of STOC, FOCS
and Complexity proceedings back to 1986, incredibly useful for looking
up recent papers.
How has technology changed how I use a proceedings? Not much during
the conference, but I now rarely use proceedings to look up papers and no longer have complete collections of STOC and FOCS.
Other people use proceedings during a conference in different
ways. Some never open them up. Some follow along in the proceedings
during a talk. Some read the paper before or after the talk.
That's the important point to keep in mind when we have our debates on
whether to eliminate proceedings, or put them on the web or on CD-ROMs. We all use proceedings in different ways and no single
solution will address everyone's needs.
Posted by Lance to Computational Complexity at 1/16/2007 06:56:00 AM
| My daughter learned about square roots and she did her homework taking
those roots using a calculator. She asked me how to compute the square
root without using a calculator.
I actually learned this procedure
in the mid-70's, probably the last generation to do so. But unlike
long division or Euclid's Algorithm, I quickly forgot how to compute
square roots since the process was quite cumbersome, one didn't have
to take square roots that often and reasonably priced calculators appeared
soon thereafter. Almost no one even 50 years ago used
the manual method for square roots, using slide rules or log
I rarely even use calculators today. I find square roots like I find out
anything else, praying to the
Posted by Lance to Computational Complexity at 1/17/2007 05:04:00 AM
| Jason Teutsch is an Indiana Math Ph.D. student who has been working
with me via the CIC Traveling Scholars
program. Tomorrow he defends his thesis so today I'm
driving Jason and another faculty member and graduate student down to
Bloomington. Road Trip!
In graduate school we took these trips quite often. Many conferences
meet in the Northeast and we would pile into cars and drive out. A
good chance to bond with your fellow students.
Fewer conference meet in the Midwest and in Chicago you tend to fly to
travel. But we do have the occasional reason to take the long drive.
We will be in a closed environment with no internet (assuming everyone
stays off their cell phones). We'll actually have to talk to each
other, maybe even try and prove a theorem. How quaint.
Posted by Lance to Computational Complexity at 1/18/2007 08:10:00 AM
| Grant Schoenebeck asked this question for the Q&A Podcast but we
didn't get to it.
In proceedings, papers are printed in a hard-to-read two column format
and are artificially cut off at (usually) 10 pages. Personally, I
look for a more readable/extended format on-line before suffering
through the conference format. However, if we no longer have printed
proceeding (or even if we did, but also had on-line proceedings) then
these restrictions would no longer need to apply. We could print
things is a way that would be much easy to read and could have
original versions of the papers that we not oddly missing some proofs
We have the two-column format in proceedings because it saves space, a
paper typically drops 30-40% by moving to a two-column format. Less
Is this a good idea? Why don't we start doing this now?
But I would go further than Grant and suggest that every author should
have a complete version of their paper available on their web pages
and/or an archive site before the conference. I hate the phrase
"A full proof will be available in the full paper" when one
doesn't exist. But I don't want to require the extra version or we
may end up discouraging people from writing up their results properly
with yet another deadline.
Posted by Lance to Computational Complexity at 1/19/2007 08:30:00 AM
| Last week Chicago Cosmologist Michael Turner gave a talk "Trends
in Science Funding: From NSF to the ACI". Turner was head of the
Mathematical and Physical Sciences, NSF's largest directorate, from 2003 until
last summer (computer
science is mostly funded from the CISE directorate).
describe the state and process of science funding in the
US and argues for the importance of physical science funding. |
In his position, Turner played a role in helping to push the American
Competitive Initiative Bush presented at the State of the Union last
year that would have, among other things, doubled
the NSF budget over ten years, about a 7% increase a year. The ACI was
"stillborn" with the continuing resolution that froze most
of the government's budgets at last year's level. The continuing
resolution has put a very tight squeeze at NSF and other governmental
Still Turner has some reason for optimism. He expects the president to
push for ACI again, if not in tonight's State of the Union, then in
his budget for FY08 and has hopes congress will support ACI or a similar plan. Also several congressmen have signed a Dear
requesting to add funding to the NSF for this fiscal year,
though Turner was pessimistic that this request would be fulfilled.
Posted by Lance to Computational Complexity at 1/23/2007 05:45:00 AM
Hanging in the Indiana University Mathematics Lounge is a letter
dated November 16, 1948 written to Max Zorn from Nicolas Bourbaki and
cc'd to André Weil.
I am glad to be able to inform you that the American Consulate in Paris has now
granted me a visa, and that I have booked passages, for my wife and
myself, which should just enable us to reach Columbus, Ohio, in time
for my scheduled talk to the Association for Symbolic Logic.
Perhaps the AMS rejected his application on the technicality that
Bourbaki did not actually exist as a person, he was just a pseudonym
for a collection of French mathematicians writing a series of books on modern
At the same time, I must say that I have learnt with no little
surprise the rejection, on technical grounds which I do not
understand, of my application for membership in the American
Mathematical Society. Under such circumstances, it will be clear to
you that I cannot but decline your kind invitation to attend a dinner
which, I believe, is chiefly sponsored by that Society.
Bourbaki did have an invited paper
presented at the ASL Meeting in Columbus on December 31. Weil, one of
the founders of the Bourbaki group, presented the paper at the conference.
If the same kind of story happened today would we hang a framed email on the wall?
Posted by Lance to Computational Complexity at 1/24/2007 06:24:00 AM
| A conversation I heard about several years ago.
Physicist: Computer scientists have done nothing for quantum computing.
This becomes a self-fulfilling prophesy. Once computer scientists have
done something physicists care about they cease to be computer
scientists and are now physicists.
Computer Scientist: What about Shor's quantum factoring algorithm?
Physicist: Peter Shor is a physicist.
This view has changed a bit, now we do see a number of physicists
(though certainly not all of them) seeing value in many of the tools,
techniques and results from computer science. We are also making
headway in other fields like economics and biology.
If we want computer science to continue to prosper we need to continue
to reach out to other fields and do our best to make them understand
the role computer science can play in helping understand their basic
Posted by Lance to Computational Complexity at 1/25/2007 09:38:00 PM
| Suzanne Zeitman, associate editor of AMS Mathematical
Reviews (and on the web), would like to get
suggestions from the TCS community on how MR "can do a better job at
covering the literature (wherever it is) in theoretical computer
Looking at a random sampling of papers, the reviews seem to give a
short description of the main results of the paper without much or any
opinion on the quality of the paper though the fact the paper has a
review indicates some positive view of the paper. Other than that the
review doesn't seem to give more information than a well-written
As comments on this weblog show, many people will give more honest
views if they don't have to reveal their identities. Anonymous
reviews of papers might prove equally fruitful.
On this topic, David Bacon created a Digg-like
site scirate.com for quant-ph. Kudos
to Dave for bringing some Web 2.0 tools to highlight important
Still researchers looks at papers more like movies—we like
different genres and then have different preferences within these
genres. Could some sort of recommender system for
academic papers help us find good papers to read?
Posted by Lance to Computational Complexity at 1/28/2007 07:59:00 PM
| Life is just a big Markov chain, whose stationary distribution is death. |
Posted by Lance to Computational Complexity at 1/29/2007 05:00:00 PM
| Having looked at the applications of several theoretical computer science job
candidates, I notice some interesting differences from even one year
The last two points are not completely uncorrelated.
- Last year many of the stronger candidates were coming off of
postdocs looking for tenure-track jobs. This year we see more strength
from the fresh Ph.D.s.
- Last year there were a large number of outstanding cryptography
candidates. This year no particular field dominates.
- Last year the strongest candidates were heavily weighted with MIT
Ph.D.s. The degrees of this year's candidates are much more spread
There are some notable exceptions to the above and the differences are
easily explained by statistical variations on small sample spaces. But
still worthy to note how much variation we see in the theory market
from one year to the next.
Posted by Lance to Computational Complexity at 1/31/2007 09:52:00 AM
Just address an email to email@example.com
Jump to a particular message