Last night at 10:30pm, I was clicking through my twitter feed and read a tweet by Lance Fortnow on the apparent proof that P is not equal to NP.  For those of my friends who are not computer scientists – this is the biggest unsolved problem in our field.  The person that can show that P=NP or P!=NP will get a million bucks in the Millenium prize and basically any job they want.  For the layperson, I describe the problem as this:

There are a set of problems that we can solve quickly in a time proportional to the number of things we’re computing. For example, think of sorting a list of numbers or calculating your road trip on Google Maps. Computers can do these problems in “polynomial (P) time”.  Then there are problems where we can only find the solution by going through every possible solution and checking it.  A popular example is the travelling salesman problem: you have a set of cities that you want to visit and want to find the shortest path possible.  The only way to find the optimal solution is to enumerate through every possible path and check it.  These kinds of problems we call “Non-deterministic Polynomial (NP) time”.  The problem is that computer scientists haven’t found a way to show that we either can or cannot solve NP problems in an “easier” P way.  If P=NP, then there should be a way to solve ALL NP problems in P time, creating some fundamental changes in the way we think about computing. Therefore, we usually assume that P is not equal to NP and we have to treat the two classes of problems differently.  However, nobody has shown that P is not equal to NP.

That is, until allegedly now.  A researcher, Vinay Deolalikar, at HP labs claims to have shown that P!=NP. You can read the 98 page proof.  Computational complexity isn’t my specialty, so I can’t vouch for the truthiness (or lack thereof) in the proof. However, I know there are many smart minds out there verifying it as we speak.  This is a very exciting aspect of academia, especially mathematics!

Recently, I have been thinking about education.  Not just pedagogical stuff — how to teach or how students learn — but more general philosophical thoughts about education and the future of education. At Michigan, I took a course on Open Educational Resources with Joseph Hardin. Michigan has a large group of people, including Hardin and James Duderstadt who think and publish about open education related topics.  We even constructed an OER wiki for the course (I wrote a couple of the pages – peer production and open access).  More recently, I read DIY U by Anya Kamenetz, she pitches the case for the changing future of education and I attended the GK12 conference last week where we were paired with a teacher fellow (you can find a picture of me by clicking Graduate Fellows on the linked page!).  This was topped off by reading a startling but inspiring (and I think accurate) graduation speech by a valedictorian, Erica Goldson.  She writes:

When I leave educational institutionalism, will I be successful or forever lost? I have no clue about what I want to do with my life; I have no interests because I saw every subject of study as work, and I excelled at every subject just for the purpose of excelling, not learning. And quite frankly, now I’m scared.

I highly recommend reading the entire graduation speech.

I’ve always had an interest in education, not just because I’d like to be a tenure track professor, which includes teaching, but I would like to know more about how I learn and how I can develop better skills to access and parse information.  I usually did well in school, I always found it easy to jump through hoops.  Almost randomly, I’d find moments of inspiration and I would turn in assignments late because I’d be investigating some tangent or doing some interesting independent research. I had this moment a few times in my undergraduate days at Michigan State and a few more during my Masters program at Michigan.  These moments, which usually had very little to do with formal education, are what inspired me to stay with academia and do original research. Things are more intense here at Northwestern and I’m passing my classes.  However, I find that I can learn phenomenally more independently – with my own self-driven questions to answer.  I feel like I am developing more as a researcher and teacher when I am not in classes then when I am, which on the surface, seems contradictory.

In a few weeks from now, I’ll be working with High School students. Next year, I’ll be back to working with undergraduates, so I have been thinking a lot about how to inspire and motivate others to think critically and be vested in their own education, like I wasn’t most of the time.   I don’t know if I necessarily have an answer yet, though. There are so many resources out there for individuals to do self-driven research but motivating them to do so, from the head of a classroom sounds intimidating.  If I think to my high school or undergraduate self, I can think of two topics that would have self-motivated me:

• Video Games – I always enjoyed playing “sim” games, so when I discovered agent-based modeling in my Masters program, I found all sorts of interesting questions.
• Computers – I’ve been a bit of a geek my entire life but left my undergraduate CS program because the material didn’t inspire me (sitting in the lab writing backgammon programs all night is hardly inspiring).  I found my own way into computer science now and am absolutely happy here.  How can I prevent future smart kids from running away from the field because it looks boring at first?

So, I don’t really necessarily have an end to this post. Hopefully, over the course of the next 12 months, I’ll be able to develop some resources to help others and maybe a few lesson plans or two I can post on here.  I think all of the people I mention earlier make valid points about education and the future of education but I can’t yet distill all of these topics into a single goal or unified plan. This bugs me, so we’ll see how things go.

I just returned from Durham, North Carolina where I was at the Harambee 2010 Social Networks for Educators workshop.* I was there wearing two hats: 1) as someone who is qualified to talk about teaching a social networks course (using this text) and  2) as a teacher interested in using social networks to get high school students interested in social networks.** There were about 40 other academics there interested in using social networks in education, from all sorts of disciplines: computer science, communications, sociology, and education mostly.  The goal of the conference was to assist educators in 1) developing new courses using social networks, 2) finding ways to implement social networks into existing courses and 3) help students develop better critical thinking skills.

I came into the conference with the following thought: the teaching of social networks can be divided into a simplex like below, where a class is somewhere along the boundary.  This leads to classes which are a combination of sociology, mathematics and engineering.  The study of social networks is a discipline in itself and each field has its own approach.

In retrospect, I was thinking too narrowly.  Rather than being a discipline in itself, social networks are a great pedagogical tool to reach some other learning goal. For example, for students early in their CS education, social networks make a great introduction to algorithmic and game theoretic thinking. For sociology students, social networks are a great introduction into statistical analysis and complex systems.  Rather than teaching social networks as an end in itself, there are much broader goals that can be accomplished.  This is definitely a skill I can take into a K-12 classroom in the fall; I conjecture that high school students certainly know about social networks (i.e. Facebook) and are vaguely familiar with the concept of network.  This can be leveraged with good examples to help students develop critical thinking skills: many things can be modeled as networks: economies, ecologies, supply chains, etc.  Recognizing networks is a skill that every person in our modern society should have, they’re so pervasive.

A couple random highlights of the conference:

Ben Shneiderman’s inspirational talk about how the future of CS is modeling computational AND human behavior.  His NodeXL project is really impressive and would work great for an introductory networks class.

Jon Kleinberg‘s keynote talk at the end of the conference.  He concisely summarized what I was trying to say the day before, when I spoke about teaching a course using his book.  It was nice to hear another CS theorist talk at the conference, I felt a little lonely in CS theory-land at times.

That summarizes my Harambee adventure this year. Hopefully, next year, I’ll get invited back to talk about my experience using social networks to encourage high school students.

* – The conference was sponsored by the NSF CNS-0722288. Thanks NSF!

** – I am a NSF GK-12 Fellow, so I will be spending my fall in the classroom with a teacher! Thanks again NSF!

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.

Over the past few weeks (and for the next two weeks) I’ve been captivated by the World Cup. As an American, this is stereotypically unusual; most Americans are pretty apathetic about the most popular sport on the planet.  I’ve even been watching games that don’t involve Team USA.

However, I know I’m not the only American excited about the game; I see the (mostly American) twitterati going wild over game results.  I read an article yesterday about how bars in the big American cities are packed at 9am for Team USA games. People in places like Washington DC, Chicago, New York, Los Angeles, Seattle are excited about the games.  So, I ask – who are these people packing bars at 9am to watch soccer? Do they have jobs? Here in academia, I can spend a few hours in morning in my office or at home with the game on ESPN3 on my computer.  What about everyone else?

I planned on typing up a long blog post about this; making a case for a soccer intelligentsia. I conjecture that the average US soccer fan is white, grew up in the suburbs, works in some creative form (academia, design, etc), drinks microbrews, lives in an urban area, and probably has a graduate degree.  This lead me to some googling and clearly I am the 1,329,401st person to think about this problem.  A better summary of my thoughts about this can be found in an already written article over at Slate.com

I was doing some work today, catching up on some reading about social choice functions.  Most of the literature was written by Kenneth Arrow, for which he won a Nobel Prize (among other work on general equilibrium).  On his wikipedia page, I stumbed up on this 2009 paper Some Developments in Economic Theory since 1940.

Anyone who has taken a PhD-level micro course should read this text. It provides a concise guide to the development of modern thinking about game theory, general equilibrium theory, and mathematical economics along with a pleasantly written autobiography of Dr. Arrow.  I recommend.

My big plans to write a proof of the day already tanked! On day #1. In my defense, I’ve been writing proofs all weekend and didn’t feel like writing another one for the blog. Primarily they have been proofs about linear algebra, algorithmic game theory, and microeconomics.  I think I have a good one on supermodularity coming later this afternoon. This is an econ concept that, for all I can tell, is not used outside of economics.

In other news, there is a really great post on the Lovasz Local Lemma over on Lance Fortnow’s blog.  I have to admit, I have had three different classes and own two books that talk about the local lemma. However, I still have no idea what it means. The blog post is a bit more insightful and I feel like I’m getting closer to full understanding; but still not there yet. The LLL is like this pinnacle of academic achievement for me. If I can understand the lemma, then there is nothing stopping me from conquering all of discrete mathematics.

In another epic fail moment, this blog has started getting hits for the search term “paul milgrom sucks”. For those who don’t know,  Paul Milgrom is a famous economist and researcher of auction theory. He’s one of the fathers of the modern day FCC spectrum auction and wrote much of the auction literature that exists. He was given an award here at Northwestern, which I blogged about at the time.  In a later blog post, I mentioned that “Windows Vista Sucks”. Google’s algorithm connected the terms and now I get hits for that search query.  So, I would like to clear the air here; I don’t think Paul Milgrom sucks, in fact, I own several of his books and think he is an excellent writer. His work on the FCC auctions is phenomenal (I think the companies he consults for probably agree) and he is a good speaker. In fact, I would argue that he is probably a good candidate for a Economics Nobel some day.

This is my very first proof of the day, so the proof is probably wrong (although, I hope not).

Source: Linear Algebra Done Right by Sheldon Axler – p.59 Question #9

Prerequisite: Some advanced linear algebra

Claim: Prove that if is a linear map from to such that , then is surjective.

Idea: In the problem, they give us a very specific null vector of T.  Since we know this, we can derive some information about . Then, we can construct a vector, put it through the function and show that it is surjective by construction by looking at the dimension of of the input and output.

Proof: We know that and that , and want to show that T is surjective.  By definition, for T to be surjective, its range must be equal to the codomain of the linear map. Therefore, if , then is surjective. To show this, let . Then, we know that .  Since and the dimension of the resulting mapping is 2, we have shown that and hence is surjective.

I’m going to try an experiment with this blog. In an effort to develop better proof writing skills, I am going to try to write a proof per day on here. Sometimes, it will be something assigned to me as homework and sometimes, it will be something random that I want to prove. Either way, at this moment, I feel like I am a horrible proof writer. Spending a dedicated amount of time each day (probably each weekday) will help be improve. I should disclose that sometimes my proofs will be really bad (or not even right), so caveat emptor.

At first, I considered starting a separate blog just for the proofs but then I realized that I’d have to reinstall all of my themes and modules that I already configured for this wordpress install. It took me long enough to get this one right that I don’t want to go through the process again. Maybe I’m lazy or maybe WordPress is not very scalable for this kind of thing.  So, I created a wordpress category “POTD” (Proof Of The Day).  I then went through and hacked all of my custom db calls to the wordpress library to separate posts with category=1 (uncategorized) versus category=92 (potd). Hopefully, it won’t be confusing for my readers.

You can view my first Proof of the Day!

One of my colleagues in my lab here sent me a link to this paper, by Sitaram Asur and Bernardo Huberman at HP – Predicting the Future with Social Media (PDF). I’m not sure if this was published in any conference proceeding or a journal. Either way, their findings are really cool.

They take data collected from the Twitter Search API and extract data about 24 big Hollywood films — i.e. how many times people talk about the movie, post a link to the film’s website, etc.  Then, they take this data and compare it to data from the Hollywood Exchange and the box office returns.  They show that Twitter chatter is a tremendously accurate predictor (R^2>.90) for the box office returns. Even better, they show that for the films they selected it is a better predictor than the Hollywood Exchange.  They expand on their findings by considering the “sentiment” of the tweets and show that this is also a significant indicator of week 2 movie success. The twitter chatter is a good analog to traditional word-of-mouth marketing.

This is the first quantitative finding that I’ve seen that shows a social network is a good indicator of some product’s success. There are lots of business books out there claiming that viral and social marketing is going to revolutionize the world.  The general interpretation seems to be: if we plaster our product all over social networks than this automatically equates to higher profit. The above findings show that this is generally not always the case; social networks are more of a conduit for traditional word-of-mouth advertising. Simply just plastering social networks with your promotional material does not appear to be a good predictor of your early performance.  Furthermore, if people think your product sucks, negative sentiment among the social network users does translate to poor performance later on.   So, I guess it still pays to make a good product, rather than unnecessarily spending money advertising your promotional material on social networks.