This summer, I am in a reading group working through the book Complex Adaptive Systems. I don’t have the book yet but a PDF of the first two chapters and I thought I would post my thoughts here before I go to the talk this afternoon.

I was originally a big fan of complex systems. I took a few courses at Michigan on complex systems and I’m very familiar with statistical techniques for running simulations.  I even have a sample NetLogo widget on my website somewhere of a theoretical model from my adviser.  Running simulations is kind of exciting and sexy – you usually see graphics of how agents in a system interact and plot out the results.  Then, using stats and inference you can make awesome claims about how the system works and try to infer how this relates to things in the real universe.  This is cool and fun and what made me interested in going into academia.

But then I started my PhD program in the theory department at Northwestern. In theory, we try to make much grander claims: we want to show that something is true or false in all cases or for wide ranges of classes, not just a specific instance.  For example, we want to show certain classes of algorithms can be computed in a certain amount of time. As long as we can show an algorithm is in that class of problems, then we instantly know something about it.  Theoretical findings are powerful but hard to reach, they require extensive mathematical proofs and a great deal of intellectual and logical rigor.

Simulation is useful when you’re using it to compare a theoretical finding against some form of empirical data.   In other words, you’re given some actual real world data points.  You can simulate the theoretical models and show that the data fits your theory.   Verifying theory is important however I contend it is not as powerful of a finding as the theoretical result itself.

Where do complex systems come into this? The authors of the aforementioned book argue that some systems are too complex: we can’t break them down into their components. Therefore, this implies that they argue that theoretical results cannot be found for these systems! Perhaps the systems are too complex; there are too many of what accountants call “intangibles”, things that have value but cannot be counted as assets.  I am not yet convinced of this line of argument; theoreticians should seek to develop mathematical models and tools precisely to model these cases, such that we can develop a better understanding of how our world is classified.

Well, hello. I’m sitting here in a hotel in Atlanta currently in the middle of the Foundations of Computer Science (FOCS) conference. I’m not currently in a session, I’m sitting in the lobby of the hotel where the internet is free.  I would be sitting in my room but this hotel (Renaissance Atlanta) charges $13.00 a day for wireless access to the Internet. It irks me when hotels do that.

The content of this conference is very intense and since my theoretical computer science knowledge is limited (but growing), I can usually only follow the first 5 minutes of any given talk. After that, I get overwhelmed by the sheer quantity of discrete math. This morning, I had the chance to catch:

• Linear systems over composite moduli
  Arkadev Chattopadhyay and Avi Wigderson.
• Multiparty Communication Complexity and Threshold Circuit Complexity of AC^0
  Dang-Trinh Huynh-Ngoc and Paul Beame.
• The Communication Complexity of Set-Disjointness with Small Sets and 0-1 Intersection
  Eyal Kushilevitz and Enav Weinreb.

• On Allocating Goods to Maximize Fairness
  Deeparnab Chakrabarty, Julia Chuzhoy and Sanjeev Khanna.
• Online Stochastic Matching: Beating 1-1/e
  Jon Feldman, Aranyak Mehta, Vahab Mirrokni and S. Muthukrishnan.

I enjoyed the latter two more, since they were more applied than some of the other research being presented. The “Online Stochastic Matching” paper was presented by some guys from Google – who are looking to increase the effectiveness of their ad words system. As an applied guy in a theory program, it is refreshing to see an application of theory.

The first couple presentations I had a hard time following, not because of the speaker but because as a neophyte to Linear Programming it is hard to follow along with complex “LPs” (linear programs). I’m taking a course in linear programming at the moment, which is completely overwhelming. Fortunately, I feel like I understand much more linear programming than before but I have an enormous way to go still.