Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Models versus Proofs

Expand Messages
  • Lance
    The STOC Call for Papers (deadline November 5th) and FOCS Program including the 50th Celebration are now available (FOCS registration info coming soon). Also a
    Message 1 of 1 , Sep 10, 2009
      The STOC Call for Papers (deadline November 5th) and FOCS Program including the 50th Celebration are now available (FOCS registration info coming soon). Also a reminder that the Beijing Innovations in Computer Science conference submission deadline is Tuesday. 

      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.

      Posted By Lance to Computational Complexity at 9/10/2009 05:42:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.