# GitHub

This is just a quick announcement that we have migrated all our projects like PGSolver, MLSolver, FADecider and so on to GitHub. This allows you to get the newest versions of our software easily and to contribute your own code to our codebase.

Assuming that you might be an avid user of Subversion, you might want to read this tutorial which explains Git from a Subversion-point-of-view.

# Once upon a time in Japan, one year ago

The following is an old blog post from last year that I’ve posted on a different blog that I’ve now closed. In restrospective not much has changed since then in my views. I have to admit, however, that some thoughts are fairly pathetic – I guess I was still overwhelmed by everything when I wrote it.

I’ve spent the first couple of days in Tokyo and went then to Kyoto. Tokyo is an incredibly large city packed with skyscrapers. If you go up one of the high buildings around the center to get a good view, it seems like the city is never ending, like the whole world is covered with skyscrapers. Like the Death Star (without being dramatic here). It’s almost surreal. Let there be no doubt, the skyline of New York is one of the most impressive sceneries, but compared to Tokyo, Manhattan is just a very small district in this gigantic city. It has multilayered streets all over the place. It is also the first city I’ve seen that has cars but no parking spots.

I’ve spent the rest of my time in Kyoto. It is the old royal city south of Tokyo, much smaller and greener than Tokyo. The best way to get around there is to get yourself a bike. My colleague was so friendly to give me one of his bikes which made it perfectly easy for me to visit all the places I was looking for. Japan in general and Kyoto in particular are beautiful. The people devote quite some attention to small little details. Every tree has been brought into perfect shape and each plant’s color is intense. Lime green. Crimson red. It’s just a form of art. It’s like stepping into a science fiction movie. Which sounds cliche and overgeneralizing but to me it was.

As you may know, one of the most important occasions for Japanese people is the so-called cherry blossom season, which is a two weeks long period in which the cherry blossom trees bloom. It usually takes place by the end of March, but this year the trees started to bloom a little later, so I was lucky enough to enjoy the trees at full peak. People are sitting under the trees and have picnics. It is a national celebration called “Hanami”, and most Japanese people get a warm tone in their voice when talking about their cherry blossom trees. You don’t really get it at first, but you start to understand after some time that the Hanami means a lot to them. It also shows you how much of a national tragedy Fukushima was, as they didn’t celebrate the Hanami last year.

When you go by the river in Kyoto, you see many people sitting around just looking at the river or the trees besides the river. They just enjoy the beauty of the moment. We have somehow forgotten how this works; we are always obsessed by using our time as efficiently as possible, even our free time.

For me, life has always been about choosing between hedonism and delayed gratification, and I think that is pretty typical for Western cultures. Hedonism, I always thought, might give you an instant gratification, a good fun, without giving your life any meaning. You’re missing the big picture and you might as well lose yourself in perpetuating meaningless stuff over and over again. Delayed gratification, on the other hand, seems to give you the big picture. It allows you to focus on doing something you might not enjoy too much, but you are promised to be rewarded later on for doing it.

I’ve always interpreted the carpe diems along these lines. Steve Job’s quote “Remembering that I’ll be dead soon is the most important tool I’ve ever encountered to help me make the big choices in life” seems to support this interpretation. You should always have the big picture in mind.

But what I now begin to understand is that delayed gratification tends to build up endless chains of in-order-to-thinking, postponing the gratification possibly infinitely long. “I’ll be dead soon” also means that you might as well be dead without being ever gratified for whatever it is you’re doing. Your big picture might not even work out as you planed it, and then you’re screwed.

Looking at the Japanese culture, I now realize that it is neither necessary nor desirable to choose between hedonism and delayed gratification. You should focus on the big picture, but you should also try to enjoy life every day. There is so much beauty in this world. We just need to relearn how to see and enjoy it. Today might by your last day, so don’t waste it doing stuff that you hate. Don’t waste it following other people’s dreams. I might be completely off the point to identify this as being a Japenese thing. (Edit: I am now pretty sure I was off the point.) Maybe it was just me thinking along these lines when I was there.

Religion in Japan obviously is quite different from ours. The original Japanese religion is Shinto and now coexists with Buddhism. There are many temples for both religions and some of them are even mixed. The Shinto religion is a polytheistic nature religion, where you basically have gods for everything. But instead of going there to just praise a lord, you pray for health or fertility or good luck in an exam. Your relationship with the god is much more demanding from your site. What I found particularly sympathetic were trees that they’ve put in front of the temples on which everybody can attach small papers that you want the god to take care of. If you think of fortune cookies, you basically take the good wishes with you and let the restaurant deal with all the bad stuff. It’s an optimistic and non-fatalistic way to deal with the future.

I probably don’t have to tell you much about the food: it’s incredibly good and fresh, and the Japanese dishes that we get in the Western world are only just ten percent of the different kinds of dishes that you get here. Many of them were exotic but also very tasteful. Be careful when trying Japanese sea cucumber though, which tastes pretty terrible, at least from my point of view. And even some Japanese people admitted that only a small fraction of them actually likes sea cucumber, so I think you’ll be on the safe side if you don’t like it.

In comparison to Japanese dishes, our food looks like it’s prepared by some uncivilized barbaric tribe. Instead of using elegant chop sticks, we get a set of tools to work on the food in order to get the stuff into manageable pieces. Even when you consider Western food like steaks or whatever, it’s a good question to ask why it’s not already cut. It would be much nicer to eat.

Everything, every ritual is carried out with the uttermost perfection. If people hand you stuff, they always turn it around in front of you before giving it you so that you can see the item in the right order. And they always give it you with both hands. This gesture somehow turns a simple action like giving you some stuff into an almost transcendental celebration.

People seem to have a fundamentally different understanding of how people should behave in society. Let me give you two examples. The public places and streets in Kyoto have no trash bins, but there is also no trash lying around. Not a single thing. I first thought that you’re probably going to be punished quite badly when being caught throwing stuff on the ground, but that’s not the thing. People see public places like their own gardens. The public is themselves. So why should they throw garbage on the ground? That just doesn’t make sense. Of course, our society has a completely different take on this. Throwing garbage on the ground in public places? As long as no one sees me, who cares?

Also small-scale stealing seems to be out of the picture. People let their bikes just stand around, leaving bags of stuff that they just bought in the baskets, and go into a shop to buy some other items. They just leave their bags and bikes without attendance. That’s amazing and it seems to just work like that.

People also seem to be generally friendly and kind. Although many do not speak English, people always try to help you, even if it takes them quite some time to accompany you to your desired destination. As a practical advice, you should take any directions that people give you with caution, as people sometimes rather give you a wrong direction than telling you that they don’t know where you should go. From what I’ve understood it’s about not giving you negative feedback. It’s about not losing your face, and that goes for both parties.

So go with the flow and try to be polite and sensitive yourself. I’ll definitely come back soon.

# Metapost Library for drawing Graphs

We use a custom-built library to create all the game graphs that you see in our papers and animations that allows you to specify nodes, edges, annotations among a couple of other things. We have made the library public so people can play around with it as well.

# New paper on Cunningham’s Rule & a new Wiki for TCS

David Avis and myself have just finished a paper on Cunningham’s Rule for solving linear programs, featuring an exponential lower bound. Have a look at the preprint here and let us know what you think.

# Scientific Sermon: Computing Winning Sets From Winning Strategies

[latexpage]
In our last post of the series, we have seen how to obtain winning strategies in polytime if all you can do is compute winning sets (without strategies) in polynomial time. In this post, we’ll try to solve a related problem: given a pair of strategies for both players that are guaranteed to be winning on the winning sets of the game, can we extract these winning sets in polynomial time? The answer is, as we will see, yes.

In order to simplify the problem, let $G$ be a parity game and $\sigma$ be a player 0 strategy. We can define everything accordingly for player 1.
Define the player 0 $\sigma$-winning set as follows:
$W_0(G,\sigma) = \{v \in V \mid \text{all \sigma-conforming plays starting in v are won by pl~0}\}$

It is easy to see that $W_0(G,\sigma) \subseteq W_0(G)$, and $W_0(G,\sigma) = W_0(G)$ iff $\sigma$ is a winning strategy on $W_0(G)$.

Hence, in order to solve our problem, it suffices to compute $W_0(G,\sigma)$.

Now we simplify our problem even more by considering the so-called strategy subgame. Given a game $G=(V,V_0,V_1,E,\Omega)$ and a player 0 strategy $\sigma$, the strategy subgame $G|_\sigma = (V,V_0,V_1,E’,\Omega)$ restricts the set of edges as follows:
$E’ = \{(v,w) \in E \mid v \in V_0 \Rightarrow \sigma(v) = w\}$
In other words all edges of player 1 remain in the game while all player 0 edges chosen by $\sigma$ are removed from the game.

It is not hard to see that $W_0(G,\sigma) = W_0(G|_\sigma)$, because the game on the right-hand side still includes the strategy $\sigma$. So we have a reduced our original problem to computing $W_0(G|_\sigma)$.

Why is that of any help? If you look closely, you’ll see that $W_0(G|_\sigma)$ is a so-called one-player game, i.e. a game in which at most one of the two players (in this case at most player 1) has more than one strategy. So our remaining task can be phrased as follows: How do we solve one-player parity games in polynomial time?

There are a bunch of algorithms that solve one-player parity games in polytime, but let us consider an algorithm very similar to the recursive algorithm that we have described earlier. You can also take a look at the Wikipedia page for an outline of the algorithm.

Our algorithm is recursive in the number of different priorities. If we only have one priority, we can immediately see who wins the whole game. If we have more than one priority, let $p$ be the largest one.

1. Case $p$ is odd: Let $P$ be the set of all nodes with priority $p$. We compute the $1$-attractor $U$ of $P$. It is not too hard to see that $U \subseteq W_1$ with the attractor strategy of player 1 on $U$ as winning strategy. We remove $U$ from the game and continue with the rest.
2. Case $p$ is even: Let $P$ be the set of all nodes with priority $p$. We compute the $0$-attractor $U$ of $P$ and remove it from the game, resulting in a game $G’$. We solve the game $G’$ by recursion and obtain winning sets $W_0’$ and $W_1’$. We compute the $1$-attractor $A$ in $G$ of $W_1’$ and remove it from the game as it is clearly won by player 1. This leaves us with $U \setminus A$ and $W_0′ \setminus A$.
We now claim that $W_0′ \setminus A$ is won by player 0. Assume it’s not. Then, there must be a player 1 escape going through $A \setminus W_0′ \cup U$ reaching $W_1’$. But since $A$ is an attractor and the game is a one-player game, this is impossible. Let $X$ be the player 0 attractor of $W_0′ \setminus A$. Hence, we can remove $X$ as a save win for player 0 from the game.
We are left with $U \setminus (A \cup X)$ with which we continue.

As an exercise, you can check that the algorithm runs in polytime.

In the next post of the series, we consider an assumption that you are allowed to make if you’re trying to find a polytime algorithm for solving parity games: you can assume that one of the two players, say player 0, wins the whole game. All you need to do, is to compute her winning strategy.

# Java Keystore Creation from SSL Certificate

For Java-based servers that use SSL, you are usually required to convert your SSL certificate to a Java Keystore. It took me some time to figure out the right parameters and tools to create it, so here is the shortcut to creating the file.

Requirements:

• Your domain name, i.e. “facebook” (without the top-level domain), which we will denote by [NAME] (we assume top-level domain “com” for the time being)
• A password for the keystore which you will need for the Java server, which we will denote by [PASSWORD]
• A program called keytool which should be part of your Java SDK
• The SSL certificate files “[NAME].com.crt”, “ca.key” and “gd_bundle.crt”

You can then go a head and execute the following to commands which will create the keystore file “[NAME].keystore” for you.

openssl pkcs12 -export -in [NAME].com.crt -inkey ca.key -out [NAME].p12 -name [NAME] -CAfile gd_bundle.crt -caname root -chain

# Applied Engineering: Exhaustive Search

In the last post of the series, we’ve introduced modules, functors and maps. We had ended with realization of the value assignment function that maps a given table assignment to a (ranking) value.

In this post, we will conclude the series and solve the optimal table assignment problem using OCaml. We will implement a function that searches through the space of potential table assignments to find (the) one with best possible value. We will use a very simple exhaustive search algorithm here.

First, we introduce a new module similar to the Map module we’ve already used previously. It models a set of objects and allows to add, remove, and find elements and to iterate over them efficiently. For our purposes, a set will be the right data structure for walking through the search space.

module IntSet = Set.Make(
struct
type t = int
let compare = compare
end
)

let int_list_to_set int_list =
List.fold_left (fun set_acc list_el -> IntSet.add list_el set_acc)
IntSet.empty int_list

As before, we have to specify a compare function, and we use the default one once again. We also add a function int_list_to_set that converts a list of integers to a set of integers by folding the list and adding one element at a time using IntSet.add while starting with the empty set IntSet.empty.

If we want to get the sets of people and seats, we could use the mapping function as follows:

let people_set = int_list_to_set (List.map (fun (x,_) -> x) people)
let seats_set = int_list_to_set (List.map (fun (x,_,_) -> x) table)

Before we can turn to the exhaustive search algorithm, we consider one last type that is particularly useful in functional programs: the option type. It is a box that can contain at most one instance of some other type – in other words, it’s either an empty box or a singleton. It is already defined by OCaml, but it can easily be redefined:

type 'a option = None | Some of 'a

You can use the type as follows:

let x = None
let y = Some 5
match option_variable with
None -> do_something
| Some i -> do_something_else

Back to our initial problem: finding an optimal table assignment. Just for fun, we will also try to find a worst table assignment, so the search algorithm should be given a comparison routine that allows the algorithm to select the more “appropriate” table assignment when comparing two.

We will therefore consider the following two comparison functions:

let better_selector assignment assignment' =
if assignment_value assignment > assignment_value assignment'
then assignment
else assignment'

let worse_selector assignment assignment' =
if assignment_value assignment > assignment_value assignment'
then assignment'
else assignment

Our exhaustive search algorithm will be called find_assignment, and it will be given one of the comparison routines as only parameter. We will then be able to create the following two convenience function searching for either a best or a worst assignment:

let best_assignment = find_assignment better_selector
let worst_assignment = find_assignment worse_selector

The basic idea of our exhaustive search algorithm is as follows. At any point in the algorithm we have four objects:

1. the currently “best” assignment (initially will be None),
2. a partial assignment (initially will be the empty map),
3. the set of empty seats  (initially will be the set of all seats), and
4. the set of persons without a seat (initially will be the set of all persons)

The algorithm will then proceed as follows. If there are no more people without a seat, the partial assignment (which is a full assignment at that point) will be compared with the currently best assignment, and the better one will be returned. If otherwise there are no more seats left, the algorithm will fail, because there are not enough seats for all persons. If there are still seats and persons left, the algorithm will pick the first person unseated and the first unoccupied seat, seat the person there, and recursively find the best assignment. Then, the algorithm will free the seat again, and seat the second person on the same seat and recursively find the best assignment again. This will be done for all persons unseated, so in the end, we’ll find a best assignment.

Here is the code:

let find_assignment selector =
let people_left = int_list_to_set (List.map (fun (x,_) -> x) people) in
let seats_left = int_list_to_set (List.map (fun (x,_,_) -> x) table) in
let rec find reference assignment people_left' seats_left' =
if IntSet.is_empty people_left' then
match reference with
None -> Some assignment
|   Some other_assignment -> Some (selector other_assignment assignment)
else if IntSet.is_empty seats_left' then
failwith "There are not enough seats!"
else
IntSet.fold (fun person reference' ->
let people_left'' = IntSet.remove person people_left' in
let seat = IntSet.choose seats_left' in
let seats_left'' = IntSet.remove seat seats_left' in
let assignment' = IntMap.add person seat assignment in
find reference' assignment' people_left'' seats_left''
) people_left' reference
in
match find None IntMap.empty people_left seats_left with
None -> failwith "There must be one assignment."
|   Some assignment -> assignment

So what do we get in the end? A best seating assignment gets a score of 7.5 and the assignment is:

Hank sits on seat #5
Karen sits on seat #4
Becka sits on seat #1
Mia sits on seat #2
Julian sits on seat #0
Trixi sits on seat #3

A worst seating assignment gets a score of -0.625 and the assignment is:

Hank sits on seat #0
Karen sits on seat #3
Becka sits on seat #1
Mia sits on seat #5
Julian sits on seat #4
Trixi sits on seat #2

Finally, the spammer got back to me again. I already thought I lost him, but there we go again. If you want to recap what happened, here are part 1 and part 2.

Guten Tag,

Wie geht es Ihnen?

Bis jetzt habe ich von Ihnen keine E-Mail bekommen.

bitte erwarte ich eine E-Mail von Sie.
Hoffe,dass alles gut lauft mit der Aanwalt.
Bitte sagen Sie mir mehr über der ablauf.

Mit freundlichen Grüssen
Ferdinand Arendt

Sehr geehrte Herr Arendt,

es geht mir gut, vielen Dank der Nachfrage. Wie geht es Ihnen?

Es verstört mich zu hören, dass Sie von mir keine E-Mail erhalten haben. Ich schrieb Ihnen am 22.01. und anschließend Ihrer Kollegin Frau Smith am 28.01. – offenbar sind einige der E-Mails nicht bei Ihnen eingetroffen. Diese neumodischen Kommunikationsformen sind aber auch unzuverlässig! Früher war alles besser. Selbst wir waren früher besser, nicht wahr? Aber ich schweife ab.

Ich hätte gehofft, dass Sie mir mehr über den Ablauf verraten könnten. Bis jetzt habe ich von Ihnen ja noch keine weiteren Unterlagen in der Angelegenheit erhalten. Wie sollen wir weiter verfahren?

P.S. Bestellen Sie Frau Smith meine besten Grüße.

Hochachtungsvoll,
Ihr Alexander Habicht

Sehr geehrter Herr Habicht,

Ich weiß nicht wie weit Herr Arendt Sie bereits in dem Fall in Kenntnis gesetzt hat und über welche Informationen Sie derzeit verfügen.
Wie bereits erwähnt wird das Erbe vom Nachlassgericht verwaltet. Da niemand Anspruch auf das Erbe erhoben hat, wurde vom Gericht ein Erbenermittler beauftragt einen Erben ausfindig zu machen. Leider haben seine Nachforschungen zu keinem eindeutigen Ergebnis geführt. Daher hat sich der Erbenermittler an Herrn Arendt gewandt.
Laut dem Ermittler gibt es zwischen Ihnen und dem Verstorbenen einen Zusammenhang, jedoch ist dieser nicht so eindeutig, dass er sich mit dem Ergebnis direkt an das Gericht wenden kann. Wie der Zusammenhang zustande kommt und welche Kriterien ausschlaggebend für sein Ergebnis sind, kann ich Ihnen zum jetzigen Zeitpunkt nicht sagen.
Er gab jedoch Herrn Arendt Ihre Kontaktdaten und bat ihn sich mit Ihnen in Verbindung zu setzen.
Wenn Sie das Erbe antreten möchten, wird der Erbenermittler eine Erklärung aufsetzen von der herausgeht, dass Sie der alleinige Erbe des Nachlasses sind und diese an das Gericht weiterleiten. Ich werde Sie in diesem Fall vertreten und beraten und beim Gericht einen Antrag auf einen Erbschein stellen. Da Sie als ein entfernter Verwandter des Erblassers eingetragen werden, benötigen Sie einen Erbschein. Dieser ist eine Urkunde, die Sie als Erben ausweist und mit der die Bank verpflichtet ist das Erbe an Sie freizugeben.
Um den Antrag stellen zu können, möchte ich Ihre Kontaktdaten aktualisieren.
Bitte füllen Sie dazu das Formular im Anhang aus und senden mir dieses zusammen mit Ihrer Geburtsurkunde per E-Mail zurück.
Wenn Sie noch Fragen oder Anliegen haben, kontaktieren Sie mich bitte.
Sie erreichen mich täglich von 9.00 Uhr bis 11.00 Uhr und von 12.00 Uhr bis 14.00 Uhr.
Ansonsten schreiben Sie mir eine E-Mail und ich versuche mich schnellstmöglich zu melden.

Mit freundlichen Grüßen
Jenna Smith

Sehr geehrte Frau Smith,

vielen Dank für Ihre E-Mail. Herr Arendt hat mich bis jetzt nur über die ungefähre Höhe des Erbes und eine befremdliche Verteilung des Erbes informiert. Unter anderem war Herr Arendts Vorschlag, 60% des Erbes an sich selbst zu überweisen. Das erscheint mir, vorsichtig gesprochen, doch eine etwas übertriebene und unübliche Vergütungspraxis zu sein.

Es freut mich zu hören, dass das Erbe bereits von einem Nachlassgericht verwaltet wird. Wären Sie so freundlich, mir die Adresse des Gerichts sowie den mit dem Fall betrauten Sachbearbeiter zu nennen? Ich würde mich dann direkt schriftlich mit dem Gericht ins Benehmen setzen und weitere Unterlagen einfordern.

Ich kann es kaum erwarten mehr über den nicht so eindeutigen – aber offenbar dennoch klar sichtbaren – Zusammenhang zwischen mir und dem Verstorbenen zu erfahren.

Selbstverständlich möchte ich das Erbe antreten, insbesondere natürlich besonders gerne als Alleinerbe. Vielen Dank schon mal dafür, dass der Erbenermittler eine dementsprechende Erklärung aufzusetzen bereit ist.

Leider kann ich kein Formular im Anhang entdecken. Bitte schicken Sie mir ASAP ein neues Formular.

Hochachtungsvoll
Ihr Alexander Habicht

# Setting up a Rails project with Heroku, Eclipse and Domains

I always forget the single steps to create a new rails application that has a staging & production environment, can be deployed to Heroku and has the nameservers properly configured. So here’s the outline (so you and I never forget it):

1) Create Application

rails new $APP cd$APP

2) Create Eclipse ./.project file

<?xml version="1.0" encoding="UTF-8"?>
<projectDescription>
<name>$APP</name> <buildSpec> <buildCommand> <name>com.aptana.ide.core.unifiedBuilder</name> </buildCommand> </buildSpec> <natures> <nature>org.radrails.rails.core.railsnature</nature> <nature>com.aptana.ruby.core.rubynature</nature> </natures> </projectDescription> 3) Update Gemfile source 'https://rubygems.org' gem 'rails' gem 'jquery-rails' gem "jquery-ui-rails" gem "anjlab-bootstrap-rails", "~> 2.0.4.4", :require => "bootstrap-rails" group :assets do gem 'sass-rails' gem 'coffee-rails' gem 'uglifier' end group :development do gem 'sqlite3' end group :production, :staging do gem "pg" gem "therubyracer" end gem "devise", ">= 2.1.2" gem "cancan", ">= 1.6.8" gem "rolify", ">= 3.1.0" 4) Install Bundle bundle install --without production staging 5) Clean Up rm ./README.rdoc rm ./public/index.html rm ./public/favicon.ico rm ./doc/README_FOR_APP rm ./app/assets/images/rails.png 6) Create Root Controller rails generate controller root index 7) Update Routes root :to => 'root#index' 8) Create Git Repository & Init git init git remote add origin$URL

9) Overwrite ./.gitignore

.bundle
db/*.sqlite3*
log/*.log
*.log
/tmp/
doc/
*.swp
*~
.DS_Store

10) Commit

git add .
git commit -a -m "Initial Commit"
git push origin master

11) Create Heroku Endpoints & Push to Heroku

heroku create $APP-staging --remote staging heroku create$APP --remote production
git push staging master
git push production master

12) Prepare Heroku Domain

heroku domains:add --app $APP www.$APP.com

• Domain Forward to http://$APP.herokuapp.com • NameServer Settings: www.$APP.com CNAME \$APP.herokuapp.com