On a not entirely unrelated note, even if you have no interest in economics, be sure and read Noam Nisan's post on the differences in the theoretical CS and Econ communities.
Economists and game theorists take their models much more seriously and literally than computer scientists do. While an economists’ model should correspond to some real phenomena, a CS model should correspond to a host of unknown future situations. A CS reader is more willing to take the leap of imagination between the model as stated and various unknown future scenarios. In compensation, the CS reader expects a take-away that transcends the model, often found in the form of mathematical depth. An economics reader is much more skeptical of a model and demands specific justification, but on the other hand, mathematical depth is not seen as a feature but rather as a nuisance to be buried in the appendix.I made a similar point in a question during the panel session at the Cornell Workshop last week, that proofs dominate most CS theory talks but Econ theory talks rarely mention them. The micro-economists quickly claimed they care just as much about proofs but Noam does capture a major difference of emphasis between our communities. But I disagree with Noam on the importance of the proof over the model.
Our focus on proofs is not inherent in theoretical computer science. CS theory grew initially out of the logic community and initially focused more on models and results than deeper mathematical proofs in the first couple of decades of the field. As the field started drawing more diverse mathematicians (particularly with the combinatorialists in the 80's) we slowly started to see a trend towards using proofs as a major yardstick in measuring the quality of a paper. Our conference systems exacerbates this process: With so many strong submissions to major conferences, it's easier to find faults in new models than in deep mathematical proofs.
We have more sophisticated mathematical techniques in TCS because we reward these techniques causing a feed-back loop. Doesn't make us any more forward looking just less relevant.
My talk at the workshop described a new model for handling complexity in games, and described a theorem without giving a proof. The actual proof (with Rahul Santhanam, write-up in progress) is messy but not technically deep. Muthu called the presentation a "quintessential" theory talk, a code-word for "old-fashioned". I'll take that as a compliment.
Panos Ipeirotis and Rakesh Vohra also have takes on the difference between econ and CS.
It's interesting that for me the title "models versus proofs" meant something completely different, until I read the post. Automatic theorem provers (e.g., SMT provers) eat a first-order logic formula and either say that it's a unsatisfiable (and perhaps give you a proof tree) or give you back a probable model.
ReplyDelete... I guess that's another "cultural" difference between communities.
ReplyDeleteI agree that we should pay more attention to asking the right questions (includes models) and a bit less attention to answering every question we see (proofs).
ReplyDeleteSeveral Turing awards and Nobel prizes have been given for asking non-obvious questions with relatively straightforward answers. Special relativity is the answer to the question what follows from assuming that all inertial frames of reference are equally valid? The theory of NP-completeness is the answer to the question (from abstract of Cooke's paper) [Is it the case that] any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be “reduced” to the problem of determining whether a given propositional formula is a tautology [?] Turing's seminal paper was also a lengthy but relatively routine answer to an innovative question (as noted in fake review on Scott's blog).
The answers to these questions look completely trivial today since everyone has learned the techniques used. I suspect that at the time these proofs were innovative but most top researchers could have invented those techniques if they had tried to solve those problems.
It seems rather strange for our field to give asking and answering questions similar weight when choosing Turing awards while valuing answering questions far more highly when choosing conference programs.
At the end of the day, economic theories need to match real-world data. That's why the model is so important.
ReplyDeleteIn TCS, many of our models have become completely divorced from reality (because the realistic models are too hard to analyze). This is not a good thing.
A quote from this short article by Paul Krugman: So by all means let’s have math in economics — but as our servant, not our master.
ReplyDeleteIsn't a good part of your own research (namely the oracle stuff) well on the proof side?
ReplyDelete