A very interesting “opinion piece” by Terry Tao. I liked the list of five “hypothetical” ways in which a mathematical field can lose its ways. And the story of Szemeredi’s theorem, used as a case study of good mathematics, is so beautiful that it’s always good to hear it told.
Recent Comments
non-theory
theory
Archives
- May 2013
- April 2013
- March 2013
- November 2012
- August 2012
- July 2012
- June 2012
- May 2012
- February 2012
- January 2012
- December 2011
- November 2011
- September 2011
- June 2011
- May 2011
- April 2011
- March 2011
- February 2011
- January 2011
- December 2010
- November 2010
- October 2010
- September 2010
- August 2010
- July 2010
- June 2010
- May 2010
- April 2010
- March 2010
- February 2010
- January 2010
- December 2009
- November 2009
- October 2009
- September 2009
- July 2009
- June 2009
- May 2009
- April 2009
- March 2009
- February 2009
- January 2009
- December 2008
- November 2008
- October 2008
- September 2008
- August 2008
- July 2008
- June 2008
- May 2008
- April 2008
- March 2008
- February 2008
- January 2008
- December 2007
- November 2007
- October 2007
- September 2007
- August 2007
- July 2007
- June 2007
- May 2007
- April 2007
- March 2007
- February 2007
- January 2007
- December 2006
- November 2006
- October 2006
- September 2006
- August 2006
- July 2006
- June 2006
- May 2006
- April 2006
- March 2006
a
Tags
Additive Combinatorics
Apple
Avi Wigderson
CCA security
circuit lower bounds
Conceptual contributions
cryptography
CS254 2010
eigenvalues
Expanders
Fields Medal
FOCS 2006
FOCS 2010
Hard-Core Sets
ICM 2006
Integrality gap
Leonid Levin
linear programming
Luby-Rackoff
maximum flow
Metric embeddings
Oded Goldreich
Proposition 8
pseudorandom function
Pseudorandomness
pseudorandom permutation
public-key encryption
quadratic residue
Random Oracle Model
Regularity Lemma
RSA
SAT
signature schemes
sparsest cut
Spectral partitioning
STOC and FOCS
Szemeredi Theorem
Tamar Ziegler
Terence Tao
things that are excellent
Tim Gowers
Turing Centennial
unique games
World Cup
Zero Knowledge
10 comments
Comments feed for this article
February 13, 2007 at 8:01 pm
Anonymous
This sort of introspection study of the field is very common in mathematics. In computer science this is not so much the case. I’ve only heard Karp and Chazelle openly question if the field is moving in the right direction.
We researchers in TCS could all benefit from hearing the perspective of some of the best and brightest as to where the think the most fruitful lines of research are.
Last but not least, its amazing the clarity of Terry’s vision of mathematics. Clarity that I might add many famous mathematicians often achieved only until their older, wiser years.
February 16, 2007 at 6:28 pm
Anonymous
Can Anonymous please post a reference to where Chazelle and Karp question whether (theoretical?) CS is moving in the right direction?
Thanks. –Yarden
February 16, 2007 at 11:47 pm
Anonymous
Christos wrote a retrospective paper on P/NP that’s quite good
February 17, 2007 at 2:56 am
Anonymous
I think that anonymous 1 is confused. There were many questions about the direction of TCS a dozen years ago. Karp led the group raising the questions at that time. What transpired in the next few years demonstrated the extraordinary effectiveness of the field.
More recently both Karp and Chazelle have been very effective at pointing out how valuable the work of TCS has been and how the insights of TCS are important to many other disciplines both within CS and outside.
February 17, 2007 at 5:10 pm
Anonymous
Sorry, I did not mean “question” in a critical way. Allow me to rephrase that as “I’ve only head Karp and Chazelle openly ponder if the field is moving in the right direction”.
As anon 4 points out, in STOC 1995 Karp lead a discussion of where the field is going and where it ought to go. Chazelle held a similar session during SoCG 1994.
Over the years I’ve seen several (sub)fields within CS blindly sailing towards the rocky shallows without much question as to the expected outcome. AI during the late 70s and early 80s comes to mind, yet anyone who dared openly question the direction AI was taking was seen as uncollegial. As we know, AI research and funding paid a heavy price during much of the 80s and early 90s from these mistakes.
TCS is nowhere close where AI was. The field as a whole is very healthy. But this is part of my point: we shouldn’t need to be inches from the rocks to ponder what is the best course to take. Terry’s paper is very much in this spirit. He’s not claiming that math is in some state of crisis, he’s simply doing some healthy housekeeping and planning.
February 19, 2007 at 3:17 am
Janos
The TCS community has a tradition of having the “best and brightest” expound on their view of where the field is going or ought to go. STOC, FOCS, and CCC have invited talks, and tutorial sessions that do just that. If you look at the original publication of Kapr’s NP-completeness paper, in the book “Complexity of Computer Computation” (record of a special conference at IBM Yorktown Heights), it concludes with the record of a public discussion on the meaning of these topics.
Moreover, the challenges of Karp et al gave rise to a very spirited, and constructive exchange of ideas: see for example the early ACM Computing Surveys article (Dec 96).
For a more recent version of what Theory should be, see
http://theorymatters.org/pmwiki/pmwiki.php
The point that Tao emphasizes is that the vitality of an area depends on a continuous collaborative story, not on a single point of view, or a single definition of what is “good”.
AI funding didn’t suffer as much from bad directions, as from exagerated, overoptimistic claims of what their techniques could achieve.
I am not sure what anonymous (WHY ANONYMOUS?) saw as Theory sailing towards the rocky shallows–could we have some concrete examples? My impression is that we try to go in the directions where we can push the envelope of knowledge–which is not a bad heuristic.
February 19, 2007 at 5:16 am
Anonymous
You’ve linked to the old version; the new version (didn’t check what’s changed) is here.
February 19, 2007 at 2:44 pm
Anonymous
not on a single point of view, or a single definition of what is “good”.
I do not expect nor seek unanimity in the voices. It’s the dialogue that we should seek: great thinkers pondering aloud “what’s the next big challenge? where can progress, as a field, be made?”.
AI funding didn’t suffer as much from bad directions, as from exagerated, overoptimistic claims of what their techniques could achieve.
Hype is only part of the story. The methods of AI were not conducive to growth. Today, progress in AI subfields is highly correlated to how long ago they adopted hard scientifically reproducible tests (e.g. machine learning, theorem proving).
I am not sure what anonymous (WHY ANONYMOUS?)
Answer by self-quote: “anyone who dare openly question is seen as uncollegial”.
Theory sailing towards the rocky shallows–could we have some concrete examples?
Outside theory: programming languages and software engineering, in which progress seems very weakly correlated to actual needs.
Within theory and to use an example from Karp: PRAM research. The whole field came to screeching halt in the mid 90s, so much so, that SPAA was considering folding a couple of years back. IMHO all of this could have been avoided if PRAM research had been redirected in 1992-1993. By the time the LogP model came out, in an acknowledgment of this drift, it was too late. Today’s resurgence of SPAA proves that there was value in the field, what was needed was a different approach. Since the community could never muster this direction the field went into hibernation.
A more modern example is CC which seems to be drifting a bit after the complexity-classes driven approach of the late 80s. I would love to hear a dialogue, say, between Lance, Christos and Lucca as to where CC ought to go.
February 20, 2007 at 4:28 am
Luca
Anonymous #8: it’s very uncollegial of you to misspell my name.
February 20, 2007 at 4:24 pm
Anonymous
it’s very uncollegial of you to misspell my name.
I read my son every night a story about a kid named “de Lucca” and no sooner had I clicked on “publish your comment” when the thought hit me: last name de Lucca is double c, first name Luca is single c. Sorry.