Complexity Theory related surveys

Some complexity related survey-ish papers:
A CACM article from September 2009 titled "The status of the P versus NP problem" available here.

Mentioned in the above survey, two more interesting papers:

• an article by Scott Aaronson on the independence of the P vs. NP question
• a paper by Impagliazzo giving a personal view on the average case complexity

I did not have enough time to read more of the cited works in the CACM article, but I'll add more as I have time to read it.

Coalgebraic Logic

Due to recent needs, I looked up some stuff on coalgebraic logic, a generalization of modal logics. If you're unfimiliar with the notion of coalgebras, read the good 'tutorial on coalgebras and coinduction' by Jacobs and Rutten.
I keep extending this post to contain a small collection of useful reading material, staring with this list:

• Moss - Coalgebraic Logic

For modal logics per se, have a look at the handbook of modal logics.

Some pointers to articles

Some pointers to news, papers and interesting announcements:

• Neural responses and consumption behaviour
  How concious are we when deciding about buying stuff?
  
  
• Efficient quantum memory for light
  A solid state quantum memory with higher efficiency than previous memory systems.
  

• Visualizations of the Ulam spiral
  Just some pictures/graphics.
  


• Manufactoria is a rather short but entertaining flash game.
  

Absolutly interesting are the DFG science tv webcasts which report on the DFG (DFG is the german equivalent of the NSF) funded projects.

In some German articles I was pointed to yet another book: The Road to Reality: A Complete Guide to the Laws of the Universe (Vintage) which I might read some time soon.

I finished reading Proust Was a Neuroscientist, a really enjoyable book. The author suggested to read Consilience: The Unity of Knowledge . I reading it currently (only up to page 100 yet) and it's somewhat between enjoyable and frustrating to read.

Search engines and market forces

Friedman claimed that if there's demand for some sort of goods or goods with special attributes (like being produced in an environtment-friedly process, by high paid workers, ...) the market will create adequate products - as long as demand means the willingness of the consumers to pay for that special property they request.

Some rather unknown examples or at least rarely used examples for this are "green" or CO2-neutral servers and online services. For search engines, there are several alternatives:

• Forestle promises to enable its partner, the US based organisation "The Nature Conservancy" to reforest 0.1 m^2 of rain forest for every search.
  
• Ecosia supports the WWF in protecting rain forest in Brasil, on average about 2 m^2 per search
  
  The backend of forestle and ecosia is provided by Bing and Yahoo. The operator for both is a for-profit organisation located in Berlin, Germany, which is bound by contract to invest at least 80% of its earnings in these rain forest projects.
  
  
• znout doesn't support anyone, but buys enough CO2-certificates to green-ify the power used by the servers in the search process. Its also the only search engine that uses google (the custom search provided by google)
  
• GoodSearch offers you to choose a US-based charity to give the money to - on average 0.01 USD per search. It features, among many others, amnesty international and the Richard Dawkins Foundation for Reason and Science. Its again a front-end to Yahoo search technology.
  

All search engine providers generate their money via advertisment on the search pages.

Epigenetics

I recently noticed that my knowledge on epigenetics is close to non-exsistent, so I decided to change that.

For entertainment, there is a documentation by BBC called "The ghost in your genes" which seems to cover the basic findings. I embed the first of 4 parts on youtube:


Moreover, there is an inaugural lecture by Professor Paro at the ETH Zürich.

There is also a bunch of papers in different levels of detail and specialization, I didn't read all of them yet:

• Jablonka, E. und Lamb, MJ. (2002): The Changing Concept of Epigenetics. In: Annals of the New York Academy of Sciences 891
  
• Bradbury, J. (2003): Human Epigenome Project—Up and Running. In: PLoS Biol.

I'll update this post as I discover and read more good resources on this topic.

Recent readings

A few remarks concerning some books I read since my last post:

• Patterns of Democracy: Government Forms and Performance in Thirty-Six Countries presents a board study of democratic governments and classifies them into 'majoritarian' (e.g. UK) and 'consensus' (e.g. Switzerland) systems. He finds 10 items in 2 dimensions (or: the 10 items can be factored in 2 factors which good correlations) which are useful for classification. 36 countries are analysed with respect to this 10 items and the classical prejudices (majoritarian governments can act quicker and thus are better and more decisive, etc) are examined. His conclusion is that most of these turn out to be false; for some, rather the opposite seems to be true.
  
• Qed: The Strange Theory of Light and Matter (Princeton Science Library) is a very good popular science book - in my opinion even better for those who have studied the matter beforehand. It does not contain any formulae - something I would complain about a lot if I didn't already know many of them. Otherwise, if you haven't had contact with quantum mechanics at all, it might be too less to be useful.
• The Elegant Universe: Superstrings, Hidden Dimensions, and the Quest for the Ultimate Theory is one of the very few books on string theory I got my hands on yet. For a math/science orientated person, it gives a very rough but imprecise picture on the possible solutions string theory /might/ offer/s. On the other hand, it skips quite some of the problems string theory actually has (like the validity of the use of pertubation theory) and mostly due to the nature of string theory itself, doesn't offer any formulae. The recapitulation of relativity and quantum mechanics in the beginning of the book is ok, but not the best I read.
• The other one seems to be available in German only: a collection of papers on the topics of globalization and nongovernment organizations: Die Privatisierung der Weltpolitik. It sheds light on the increasing influence of non-governmental organizations in world politics - not necessarily lobbyists from economy and industry, but also public interest organizations like environmental or animal rights activists. Very enjoyable is the neutral attitude, more analyzing than taking any side.

I ordered a bunch of new books on epigenetics and neurosciences.

Some Videos on Physics

Just some simple popular science talks for some spare time in between:

Sean Carroll on the origin of the universe and the arrow of time

Part 1



Part 2



Brian Greene on String Theory