Looking at questions through the algorithmic lens (i.e. from an algorithmic or complexity point of view) has become useful in disciplines outside of the 'standard domain' of computer science. In particular CS has made an impact on biology through computational biology, on physics through quantum information processing, and AI and complexity theory seem to regularly interact with neuroscience. The natural sciences seem relatively comfortable with TCS.

Thus, my question is in regard to the impact of TCS on the social sciences.

What novel and important insights into the social sciences has TCS provided?

I am vaguely aware of the impact of algorithmic thinking on economics (through game theory). In fact algorithmic game theory is now a part of the 'standard domain' of TCS, so lets exclude AGT answers unless they specifically altered existing theories in the social sciences.

Another example I recall is from linguistics in the learnability vs. innateness of grammar (i.e. poverty of the stimulus) debate. Gold's theorem about the unlearnability of context free grammars provided a strong argument for innate-ness and helped convince some skeptics (I am not sure if this is still valid, since SCFG seem to be learnable). I am more interested in examples of this type, where TCS thinking helped change or shape existing theories in the social sciences.

References to books/surveys are appreciated.

  • $\begingroup$ CW ? I'm not sure ... - it's a great question. $\endgroup$ – Suresh Venkat May 4 '11 at 6:35
  • 6
    $\begingroup$ Isn't the term "social sciences" a misnomer? $\endgroup$ – Tegiri Nenashi May 4 '11 at 21:22

Networks, Crowds, and Markets: Reasoning About a Highly Connected World, by Easley and Kleinberg probably should be mentioned here. It is rather elementary, but gives a wide selection of social sciences topics that have been considered from a CS point of view and provides a lot of references. Someone with more experience in the field can perhaps tell us how close the book is to the current state of the art in the field?

As a more particular answer, with the proliferation of various social networking sites, computer science has become quite relevant in analysing the huge social network data sets from such sites.


This example is from social choice theory, and elections in particular. We know that Arrow's theorem (and the Gibbard-Satterthwaite theorem in general) rule out the possibility of elections that are fair, non-manipulatable and without other bizarre consequences. But a seminal paper by Bartholdi, Tovey and Trick showed that finding the desired 'hack' to break a voting scheme was NP-hard, and there's been a large body of work by many researchers on the complexity of problems in the realm of election design. There's a nice survey by Faliszewski, Hemaspaandra, and Hemaspaandra on this topic.



For more modern examples Computational Legal Studies Blog has some great work. They predicted the nomination of U.S. Supreme Court Justice Sotmayor by using graph theory.


Today's cognitive psychology is really based on the "brain as computer" viewpoint. (Although, this may be considered as part of "neuroscience" mentioned in the question.)

  • $\begingroup$ It is a really fascinating area. I have been hoping to read more about this on your blog for sometime, and now that you have turned it into a groups blog even more so. :) $\endgroup$ – Kaveh Jan 16 '12 at 7:26

Some additional references:

In Macgill S M, 1985, "Structural analysis of social data: a guide to Ho's Galois lattice approach and a partial respecification of Q-analysis" Environment and Planning A 17(8) 1089 – 1109.

MacGill highlights how those in the social sciences who might benefit from using Q-analysis are (usually) least well placed to understand the maths and hence the potential of such tools in the humanities. Which must be the case even with increased computerization - algorithmic formulations. (Maths is a fascinating mist to this nurse.)


A great many issues of ERCIM news have considered the social applications of maths - inc. algorithmic:


Another possible avenue to pursue is visualization in the social sciences. There was a major initiative in England in the 1990s:


The combination of the semantic web, conceptual spaces Gärdenfors (2000) may provide new, hybrid avenues:

Gärdenfors, P. (2000). Conceptual Spaces: The Geometry of Thought, Cambridge.

Conference May - 'Conceptual Spaces at Work'


I wish I could get to grips with these subjects - post-grad studies possibly. My spare time efforts include plans to attend the above conference and writing about a specific form of big picture (conceptual framework) Hodges model here: http://hodges-model.blogspot.co.uk/


cake cutting algorithms which are important for fair division. I am sure they play a large part in social science.

  • $\begingroup$ can you cite a reference where cake cutting algorithms were important to social scientists? or somehow changes some theory in social science? $\endgroup$ – Artem Kaznatcheev Apr 9 '12 at 21:32
  • $\begingroup$ Cake cutting algorithm deals with fair division of resources among n parties which is a long standing problem in social science. Wiki link which I gave cites a lot of references about how it pertains to social science. In particular I like this 3quarksdaily.blogs.com/3quarksdaily/2005/04/… $\endgroup$ – Sai Venkat Apr 10 '12 at 3:57
  • $\begingroup$ I think a better reference is the paper "Cake cutting really is not a piece of cake" by Edmonds and Pruhs. $\endgroup$ – Sai Venkat Apr 18 '12 at 4:01

re applications of complexity theory in social science-- scott aaronson has a daring & amusing-at-times essay tying complexity theory to deep century-old questions in philosophy that I ran across recently reading his blog.

Why Philosophers Should Care About Computational Complexity http://arxiv.org/abs/1108.1791


another interesting area of the application of algorithmic theory to social sciences happens in economics such as studying markets or other "complex systems". the idea is that the market is composed of separate actors or "agents" that each attempt to develop algorithms to make money. a darwinian process of selection ensues. similar to genetic algorithms. (and probably now actually quite close to reality of HST, high speed trading, where there are estimates that up to 70% of market trading is due to program trading.) a leading investigator in this area is j doyne farmer


I see you mention biology on your course page. an excellent application of complexity and algorithmic theory and one under intense development is in the cutting edge problem of determining protein folding configurations. for example an early paper proved that a formalized version of the protein folding problem is NP complete.


protein folding problem is NP complete by berger/leighton http://www.brown.edu/Research/Istrail_Lab/papers/1998/p30-berger.pdf

  • 1
    $\begingroup$ Thank you for mentioning Scott's article, but the other two answers you give (AGT/E and Biology) I specifically exclude in the question. $\endgroup$ – Artem Kaznatcheev Jan 13 '12 at 16:52
  • $\begingroup$ do you think all computational approaches to finance are subsumed in AGT? AGT/E==algorithm game theory + economics? not sure I would agree with that or that Farmers work is in that category. you excluded AGT but did not seem to explicitly exclude Economics. $\endgroup$ – vzn Jan 13 '12 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.