Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
CW ? I'm not sure ... - it's a great question. –  Suresh Venkat May 4 '11 at 6:35
6  
Isn't the term "social sciences" a misnomer? –  Tegiri Nenashi May 4 '11 at 21:22
    
+1 for Community wiking. –  Sai Venkat Apr 9 '12 at 14:01
add comment

7 Answers

up vote 16 down vote accepted

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.

share|improve this answer
1  
thanks! That looks like a fun book, do you know of any similar books or surveys that are at a graduate or research level? A skim on Easley and Kleinberg suggests that it is targeted as an intro for undergrads. –  Artem Kaznatcheev May 5 '11 at 4:48
    
Unfortunately, no, I don't. In fact, I'd love to see such a book or survey myself. –  Janne Korhonen May 5 '11 at 6:36
    
Not sure if anyone still follows the topic, but the other excellent books include Social and Economic Network by Matthew O. Jackson and Network: An Introduction by Mark Newman. [1]: amazon.com/Social-Economic-Networks-Matthew-Jackson/dp/… [2]: amazon.com/Networks-An-Introduction-Mark-Newman/dp/0199206651 –  Thang Dinh Sep 24 '13 at 3:06
add comment

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.

share|improve this answer
    
thanks! A bit more about the current state of social choice is in this question: cstheory.stackexchange.com/questions/2711/… –  Artem Kaznatcheev May 5 '11 at 4:51
    
Ah thanks. I had forgotten my own answer from there :) –  Suresh Venkat May 5 '11 at 4:53
add comment

Chomsky?

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.

share|improve this answer
add comment

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.)

share|improve this answer
    
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. :) –  Kaveh Jan 16 '12 at 7:26
add comment

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.)

www.envplan.com/abstract.cgi?id=a171089

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

http://ercim-news.ercim.eu/back-issues-online

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

www.agocg.ac.uk/train/review/toc.htm

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'

www.fil.lu.se/conferences/conference.asp?id=46&lang=se

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/

share|improve this answer
add comment

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

share|improve this answer
    
can you cite a reference where cake cutting algorithms were important to social scientists? or somehow changes some theory in social science? –  Artem Kaznatcheev Apr 9 '12 at 21:32
    
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/… –  Sai Venkat Apr 10 '12 at 3:57
    
I think a better reference is the paper "Cake cutting really is not a piece of cake" by Edmonds and Pruhs. –  Sai Venkat Apr 18 '12 at 4:01
add comment

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

http://www.scottaaronson.com/blog/


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

http://tuvalu.santafe.edu/~jdf/SFI%20Template/About%20Me.html


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.

http://en.wikipedia.org/wiki/Protein_folding

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

share|improve this answer
1  
Thank you for mentioning Scott's article, but the other two answers you give (AGT/E and Biology) I specifically exclude in the question. –  Artem Kaznatcheev Jan 13 '12 at 16:52
    
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. –  vzn Jan 13 '12 at 17:22
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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