Montag, 19. Juli 2010

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.

Dienstag, 6. Juli 2010

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:

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

Mittwoch, 30. Juni 2010

Some pointers to articles

Some pointers to news, papers and interesting announcements:

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.

Sonntag, 23. Mai 2010


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:

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

Samstag, 22. Mai 2010

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.

Freitag, 9. April 2010

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

Sonntag, 14. März 2010

Writing systems and non-linearity

Some time ago I posted some links, one of them pointing to a non-linear, graph like writing system called Ouwi; meanwhile I spent some time reading up on the topic of writing systems and have some more pointers:

Pinuyo is a pictorial language which indicates grammatical function of the ideograms by placement and surrounding symbols.

I also found a long, but sometimes deviating thread on 2-dimensional writing systems on the conlang mailing list archive. Unfortunatelly many of the links are now dead, the thread is from 2005.

Omniglot is a nice website about alphabets, writing systems and languages. It contains some constructed systems, like block script, a sylabic alphabet for the english language which combines letters to blocks (like the korean script for example). Most of them are linear ones.

I'm still wondering if there are some languages/alphabets optimized for reading speed. Most are either evolved, natural languages, which certainly are a compromise between reading and writing and the constructed ones optimized for speed like the morse code or shorthand.

In an edit, let me just add a few more links, somewhat related:

Láadan, a feminist language designed for countering male-centering of natural languages.
The gripping language, not spoken but transmitted by touching of the hands.

Dienstag, 2. März 2010

Random Numbers and Certified Randomness

A rather recent edition of the ACM TechNews contained a short report/link on a German team which developed a hardware random number generator [1], that

uses an extra layer of randomness by making a computer memory element, a flip-flop, twitch randomly between its two states 1 or 0. Immediately prior to the switch, the flip-flop is in a "metastable state" where its behaviour cannot be predicted. At the end of the metastable state, the contents of the memory are purely random.

Whereas this device gives me more security, it does not solve the problem of someone sending me supposedly "random numbers" which he might have prepared in advance to even pass statistical tests. A neat solution is provided by quantum mechanics which allows to check randomness of numbers via the violation of the Bell inequality [2] using entangled states.

[1] "A meta-level true random number generator" in Int. J. Critical Computer-Based Systems, 2010, 1, 267-279

[2] Random Numbers Certified by Bell's Theorem

Enthusiasm for Science

I just wanted to point out to a project called 'the symphony of science', available at

It consists of a series of music videos, aiming to

"bring scientific knowledge and philosophy to the public, in a novel way, through the medium of music. Science and music are two passions of mine that I aim to combine in a way that is intended to bring a meaningful message to listeners, while simultaneously providing an enjoyable musical experience."
I embed only one of those here:

I really like what the project is aiming for. In my opinion, there is a severe lack of easy accessible material for the general public regarding all fields of science. Publishing in journals and proceedings is good, but doesn't help the non-scientific population at all. Unfortunatelly, writing popular science books isnt' valued in the scientific community at all.

Montag, 15. Februar 2010

Some results in quantum computing

Just some points to (rather) recent results in complexity theory with regard to quantum computing:

  • Quantum Interative Proofs equals Polynomial Space class: QIP = PSPACE
  • On the relation of the BQP class to the PH class; furthermore a separating decision problem would follow from the Generalized Linial-Nisan Conjecture: BQP vs PH

The Rise of the Creative Class

I purchased a new book, The Rise of the Creative Class: And How It's Transforming Work, Leisure, Community and Everyday Life by Richard Florida.

According to this book, the creative class consists of those people who primarily create, combine, modify and extend ideas. This includes artists and musicians, but also ranges to scientists and engineers even some managers are included. Taking a look at the class and its composition, Florida argues how companies and countries can react to the growing importance and influence of creative workers. It turns out that there is a strong correlation between places with many gays, artists, cultural/ethic mixture and a strong creative industry/economy.
Furthermore he argues that people tend to cluster at places they like rather than to prefer places the industry chooses to build their factories. Consequently cities and counties should take measures to ensure those people will cluster.

Reading it (and not having finished it yet) I get the feeling that all that needs to be done is to follow the arguments M. Friedman made: let the free market decide. Deregulation should allow people to cluster whereever they like to and due to democratic systems form their environment according to their likings. The creative class contains up to one third of all employees - being not a minority at all, special rules, laws and regulations can be supported by the class itself if necessary. With respect to the backward, conservative US laws, the abolishment of quite some laws seems to be the better alternative.

Freitag, 8. Januar 2010

Cognitive Sciences and unfinished readings

I got the recommendation to read some chapters titled Structures, Learning and Ergosystems (available here) due to its heavy use of mathematical examples and outlined processes of thinking in mathematics. I got kind of upset with reading during the first 40 pages because of some imcomprehensible claims - at least I cannot see the validity of those, maybe it is just my limited and inadequate knowledge of cognitives sciences. It's a collection of facts without stating clear connections between them.
I found a cognitive scientist to whom I can relay questions, so I might post some questions with his answers later.

Meanwhile, I'm not done with the ealier mentioned book about Quantum Non-Locality and Relativity. I was slowed down by a Greman book about philosophy of science and Peter Singer's Practical Ethics.

I will write a short book review for the Quantum Non-Locality book as soon as I finish reading it.

Some pointers to articles

Some pointers to articles, already old:

The Ouwi writing system (

This describes, besides an artistic invented language, a non-linear, two-dimensional writing system. It has ten letters made up of four different atomar symbols. The only relevace for identifying a letter is the order of the atomar symbols they're made of, meaning letters can be flipped, rotated or bent at the joints. Letter cannot only be connected horizontally or vertically like in Roman, Arabic and Chinese systems, but also be intersected or be the source of radiation of letters in different directions. It reminded me of the Ilkash writing system which also uses a non-linear 2d system to add more information into symbols and the flow of text (in Ithkuil, the probably non-speakable 'predecessor' of Ilkash, even characters can morph). In contrast to the last two mentioned systems, the Ouwi system is ment to be easily learnt and remembered.

Google's go programming language ( and concurrency in go (
for a quick overview, in case you don't already have an overview.