Wednesday, December 9, 2015

ELS: latency based load balancer

You might have noticed that the Spotify back-end has been faster by about 0.47 milliseconds in the last 6 months. Read about my new algorithm in two posts:
  1. The first one is simpler, has a lot of pictures, graphs and even three animations.
  2. The second one has all the necessary math.

Tuesday, November 24, 2015

Swedish summer 2015

People said this was the rainiest Swedish summer ever, but I disagree. I slept 5 times in the Stockholm archipelago and each time without a tent. This is how we usually slept.

The best hotel in the Stockholm area. Cost: 0 SEK. Experience: priceless. At Angödrommen.
Maybe the weather was nice to me, since this was my last summer in Sweden. Stockholm archipelago, I'm going to miss you!

There is not much to write about all the trips I made, so let the photos speak instead. Don't continue if you are scared of swans, seals, mushrooms, spiders, snakes or dragonflies! A link to a full album is at the end of the post.

Finally getting dark at 11 pm
Swan family chose a vacation by the sea
Snake hiding in blueberries
Unknown water creature with many small legs
We thought we wouldn't be able to pass through at first. It turned out to be a channel made for kayaks.
Mirror sunset at Kolkböte
Happy people and happy sheep at Fjärdlång
Lonely mushroom
Dragonfly
We saw seals!
If you want to see even more wild animals, check the full album made from multiple cameras on Google Photos or a small selection of my photos on Flickr.

Monday, November 2, 2015

Nordic championships in programming 2015: behind the scenes

Nordic championships in programming 2015 (NCPC 2015) took place three weeks ago and I was the head of the jury for the third time in a row, together with Markus Dregi from University of Bergen. Last year I’ve written my impressions from behind the scenes and I’d like to continue with the tradition. Let me first mention 2 problems that I liked.

H – Hero Power

Hero Power involved a simplified Guitar Hero game. On Tuesday September 29, about 10 days before the contest, the task still hasn’t been solved by anyone from the jury. Not even Björn had solved it, the author of the task who worked on it for a couple of months. In addition to many rules that were also present in the final problem statement, at the time there was an additional rule that the SP meter charges by extra 5 seconds at the end of every SP phrase (the so-called 5-second rule).

The contest was near, so me, Björn and Oskar decided to have a meeting on the sunny roof of Spotify’s office. We wanted to simplify the problem but it wasn’t clear how. I claimed that combining continuous charging with 5-second bonuses makes it hard to solve: when you draw the content of the SP meter as a function of time, you get a non-continuous function and such functions are hard to grasp. In this version, it’s not enough to charge in continuous chunks, because taking breaks allows you to collect just the right amount of 5-second bonuses. This complicated the solution greatly.

I suggested removing the 5-second rule but keeping everything else as it is. Björn disagreed. It was getting colder on the roof and we had music to stream, so we agreed to disagree. I wanted to ask the rest of the jury for opinions and also write a solution myself. Perhaps my modification wasn’t that elegant anyway.

After dinner I sat down to write a solution. It was an obvious dynamic programming problem, but the update step turned out to be very tricky. After about 30 minutes of thinking I finally got it and wrote a super-short solution. It felt too short for such a hard problem, so I proved its correctness 2 more times to convince myself.

I mostly liked lines between 41 and 50, which contain dynamic programming, greedy strategy and amortized complexity on a very small space. Even the preprocessing step is non-trivial and uses the ‘resize’ function in C++ ‘vector’ in an elegant way.

I had one of those rare moments when you are taken aback by a beautiful computer program. It was even more rare, since the code was mine. The problem version without the 5-second rule turned out to be awesome on many levels, so I went to defend it on our mailing list.
I've just implemented a solution for the version without the 5-second rule and I'm stunned. This is pure poetry! 
The task is a beautiful mix of dynamic programming, greedy, amortized complexity and clever data structures (just arrays and hash maps, but clever still). All the steps are non-trivial to make it run in O(np).
My excited e-mail was enough to convince everyone to remove the 5-second rule. In the end it was still very hard and only 2 teams solved the problem.

I – iCar

In this task you have an iCar with only one button – when pressed, the car accelerates with the rate of 1 meter per second per second. Once you release the button, the car stops immediately. (Side note: we have considered adding braking instead of immediate stop, but the problem was already too hard.)

This is yet another task that was shaped greatly with time and with the help of the rest of the jury (thanks a lot, Marc!). Andreas Lundblad sent us a suggestion already in May and it was basically the same problem as it appeared in the contest. He could only solve it for one semaphore, though. I managed to figure out all the cases needed to solve it for 2 semaphores, so I told him we’ll take the problem and figure out the details later. At worst we have the 2-semaphore version, but I was curious about extending it to 5 or even 100 semaphores.

In the end we went with 20-semaphore It was a lot of work and it took us a more than a month to get it right. First, Marc generated test cases, but my code was able to find a shorter route to the finish. Later, Marc found the nasty case shown below that broke my solution instead.

The crucial step in solving the problem is choosing the right visualization. There are two important parameters, the position of the car given in kilometers from the start and time since the start. The third interesting parameter is speed, but you can actually skip that and infer it instead.

Two parameters can be visualized in 2D: the picture below has time rising from bottom to the top and position from left to right. It contains a solution that illustrates all the different cases a correct solution needs to handle. Red vertical lines denote red lights on semaphores. Blue parabolas and dots denote a car that is accelerating and stopped respectively.
Solution to 000-random-seed-144.in. Marc also created visualizations for all test cases that you can download from the contest webpage
The second parabola is passing the 5th semaphore at the last moment of a green light and then passing the 10th semaphore at the earliest moment of a green light. We could have passed the 5th earlier, but we’d have to have lower speed to avoid hitting a red light on the 10th. This strategy allows us to pass the 10th semaphore with the highest speed possible.

While this might sound complicated, we're still not done and it's only enough to solve the 2-semaphore version. To solve the problem with 20 semaphores, you also need to handle two more cases, which are the last two parabolas in the picture.

The very high speed we acquired allows us to be at the 12th semaphore during a red light. We could stop at the semaphore and wait there for a green light, but a better strategy is stop earlier, so that we can start accelerating earlier and have higher speed when the 12th semaphore turns green.

Finally, we stop before the 13th semaphore and start accelerating, so that we pass it at the last moment of a green light. Such waiting strategy paradoxically improves the time in the finish. A little bit of calculus can prove that.

In the end no one solved the problem and I kind of expected that. One could argue that this problem should have been saved for a more difficult stage like NWERC or World Finals, but I’m not sure. Even small contests like NCPC need hard problems to stop the best teams from solving everything.

Overall this is one of the top problems I helped preparing for a contest, because quadratic geometry is very unusual in programming contests.

The bad

Apart from fun problems, a couple of things didn't pan out so well. Problem G was solvable with brute force if you managed to optimize it well. Problems D and E were too similar. Too many pproblems were dealing with time events.

We knew about these issue before the contest, but it was too late to change things. We already skipped some problems and were down to 10 when we discovered issues with G. Skipping one more problem felt like a worse decision than keeping it.

We could have prevented it if we received more problem suggestions and more people were helping out. If you would like to prevent similar situation from happening, please send problem suggestions next year. Don’t hesitate even if you aren’t skilled in preparing competition problems, because there’s always other jury members that can help you out. For example, Hero Power and iCar were suggested by people with little jury experience and then received a lot of help from the rest of the jury.

Conclusion

If you like the stories from behind the scenes, don’t hesitate to get involved next year! You can mail me at [polacek (at) kth dot se] and I’ll add you to the right mailing lists.

I’ve now left Scandinavia and after 3 years as a head of jury I’ve quit. I’d like to be involved though and contribute a problem or two next year. I hope the quality of NCPC stays very high!

Saturday, August 29, 2015

Underflow bug

Sometimes code needs to be executed 100 000 000 000 000 (100 trillion) times to hit a bug. Read my blog post for Spotify to learn more.

As usual, Reddit users were there to brighten my day:
  • "Really surprised such a successful tech company produced such shoddy code."
  • "This is remarkably shitty code. I would criticize pretty harshly anyone who wrote it. I would fire anyone who wrote a public blog post about it exactly like this post."
  • "So basic edge case failure. Not even a corner case."
  • "Yeah, not surprised that someone that thinks they invented the term underflow and used it wrongly got something like this wrong."
  • "[the code] is, pretty obviously, broken at a glance"

Wednesday, June 24, 2015

Efficient Use of Exponential Size Linear Programs

After being sick on and off for a couple of years, I decided not to finish my PhD. I did write a small thesis, though. Thus on March 20, 2015, there were two big cosmic events: a partial solar eclipse and I defended a licentiate degree. It was cloudy in Stockholm, so the eclipse was a disappointment, but my defense wasn't and I successfully defended.

I've tried to make the thesis introduction easy to understand and you can now read it here on my blog.

What is the thesis about?

Computer Science is no more about computers than astronomy is about telescopes. – (probably) Edsger Wybe Dijkstra
When Santa Claus needs to find a route around the Earth to distribute all the gifts to children in the shortest possible time, it might take millions of years to compute even if he used all the supercomputers that are currently on Earth. This is an example of a problem in computer science that is not known to be solvable fast even after decades of research.

Maybe we have just not been intelligent enough to find the right approach for this problem. However, if you ask a complexity theorist, they would most likely tell you that it will never be possible. Right now we are not completely sure about this fact, but the evidence is piling up (see the excellent essay The Scientific Case for P≠NP by Scott Aaronson).

If it really is impossible for Santa Claus to find the shortest route to distribute all gifts, what other options does he have? Instead of insisting on finding the shortest route, he might try to find a route that is at most 50% longer than the shortest one. Arguably, this should be an easier task and traveling a 50% longer route could still allow him to distribute all presents in time.

First Attempt

The problem that Santa Claus needs to solve is called the Traveling Salesman Problem (TSP). The famous algorithm by Christophides [Chr76] finds a solution to TSP within an error of 50% from the optimal solution. This is an example of an approximation algorithm, since it does not solve a problem optimally but only approximately, that is within a certain error from the optimal solution.

The time complexity of this algorithm is n2.373 operations [MS04] where n is the number of stops that Santa makes. So a computer running the algorithm makes at most about n2.373 operations.

To get the value of n we need to estimate the number of families with children. According to Gap Minder [Gap11], there are about 1.9 billion children on Earth. The average number of children per family has been estimated to be almost three [Fam06], so we can estimate that Santa Claus will need to make at most 650 million stops. Not all children expect to be visited by Santa Claus but a large fraction does, so this estimate is good enough for our purposes.

If Santa Claus had access to the fastest supercomputer Tianhe-2 (as of November 2014) with the speed of 33.86-petaflops, which is about 3 ⋅ 1016 operations per second, it should take a couple of minutes or hours to finish the computation. We note that the theoretically optimal subroutine taking about n2.373 [MS04] operations might in this case be slower than a subroutine that uses Edmond’s algorithm [Edm65] that needs at most n2.5 operations. In any case, such an algorithm will finish its execution in a couple of days.

A possible problem is the high memory consumption of these algorithms, but for the sake of simplicity of this text let us ignore this problem. A bigger problem might be the 50% error, because a tour that is 50% longer than the shortest one might be too long to distribute all the presents in time.

Improving the Error

The celebrated algorithm by Arora and Mitchell [Aro98Mit99] can find a solution to TSP within an error of say 20, 10 or 5% from the optimal solution. We can pick any error margin we like, but the smaller the error the longer the running time will be. The algorithm works provided that the problem is situated in a Euclidean space. For the purpose of this text, we only need to know that the well-known 2-dimensional (2D) plane or 3-dimensional (3D) space are both Euclidean.

We could pretend that the Earth is flat by using one of the many map projections. Unfortunately, map projections do not preserve an important geometric property, namely that the space is Euclidean and thus cannot be used by the algorithm.

Let us then try using 3 dimensions. The Arora-Mitchell algorithm assumes that the shortest path between two points is the straight line connecting them, but this is a problem for Santa, since he cannot travel under the ground. As it turns out, it is not such a big problem in the end.

Santa Claus can run the Arora-Mitchell algorithm on all positions of children on Earth as if they were simple points in a 3-dimensional space. Then he follows the route returned by the algorithm with the important change that he flies over the Earth’s surface instead of following the straight line under ground. How much longer is the route when flying over the Earth’s surface?

The most remote inhabited place on Earth, Tristan da Cunha, is about 2000 kilometers from the nearest inhabited land. However, the direct distance through the Earth is about 11.5 kilometers shorter, which is only about 0.5% smaller. The situation is shown on the picture below.

The distance between Tristan da Cunha and the nearest inhabited place Saint Helen is about 2000 kilometers. The direct distance through the Earth is about 11.5 kilometers shorter, which is only about 0.5% smaller.
Of course we cannot be sure that 2000 kilometers will be the longest distance between two stops found by the algorithm, however it will most likely not happen very often in the optimal tour. Human settlements are fairly spread out over the Earth’s surface and intuitively an optimal tour should not make a lot of long jumps—it is likely more efficient to first distribute all gifts in Asia and then go to Europe rather than flying 2000 kilometers back and forth all the time.

We thus have a strong reason to be optimistic, so let us hope that the Arora-Mitchell algorithm returns a tour such that Santa travels only about 0.5% longer route compared the one following straight lines under ground. The Arora-Mitchell algorithm is able to return a solution within x% of the optimal tour for any error x we choose. How big should x be if we want to get a 10% error?

If your answer is 9.5%, you are close but not completely right. We want to have 1.005 (1 + x) = 1.1, so x 9.45%. Let us now estimate how long the algorithm will run. The number of operations performed by the algorithm in 3 dimensions is at least
where n is the number of families to visit and a is a number that is at least 9 [RS98]. We note that the exact value of a is higher than 9, but for our purposes this information is enough.

Even if Santa Claus had access to the fastest supercomputer Tianhe-2, it would take about 101250 years to run the algorithm (101250 is a number with 1250 zeros at the end). Or equivalently about 101240 times the age of the universe. Even if each person on Earth had such supercomputer and we ran the algorithm in parallel on all the supercomputers, the running time would still be 101230 times the age of the universe.

For comparison, the Held-Karp algorithm [HK62] that makes about n22n operations is the fastest known exact algorithm that finds the optimal route. It would run 10100000000 times the age of the universe. The running time of the Arora-Mitchell algorithm is tiny compared to this one.

Heuristics

Even though the problem that Santa Claus faces may sound artificial, it appears in real life for companies that distribute goods. Instead of approximation algorithms, they often use heuristics, which are computer programs that try to solve a problem but only weak guarantees are known about the quality of their output.

For an approximation algorithm, we always have a guarantee that the output will be of a certain quality, but we might have to pay for this guarantee with slower running time, as in the case of the Arora-Mitchell algorithm. Heuristics, on the other hand, are usually very fast but we might be unlucky and receive a solution that is not good enough.

In 1947, Dantzig [Dan51] developed the simplex method that became one of the most important algorithms of the 20th century. It performs very fast in practice but for many years its theoretical speed was unknown. In 1970, Klee and Minty [KM72] found some examples where the algorithm became very slow. The algorithm continued to be used in practice and still is until today. It used to have a similar status as heuristics, since we did not know when and why it performs well.

In 1977, Borgwardt [Bor86] found a class of linear programs that are provably solved quickly by the simplex method. Subsequently, other people have found cases where the simplex method performs well. Finally, in 2001—five decades after the algorithm was discovered—Spielman and Teng developed a powerful tool called smoothed analysis [ST04] that explained why the simplex method works fast in practice while there are rare cases where it is very slow.

For many real-world problems, heuristics are both faster and better performing than approximation algorithms and we do not know why, as used to be the case for the simplex method. It is not unheard of that heuristics achieve 1% error as well as they are very fast, while the best-known approximation algorithm only achieves an error in the order of tens of percents (see for example [JM07]). Some people use this fact to argue against the use of complexity theory, but we would argue the exact opposite. Since some heuristics seem to perform well, we should study them more and try to figure out why they perform so well or find cases where they do not, as we did in the case of the simplex method. If anything, this is an argument for more research in complexity theory, not less.

What Should Complexity Theorists do?

There are several interesting research directions that help us. For example, we can try to find faster approximation algorithms for which we do not have to wait 101250 years to finish. We can also try to prove that some heuristics used in practice perform very well, hence turning a heuristic into an approximation algorithm. The hardest alternative of all is to prove that there will never be an algorithm that finds good solutions and is fast at the same time. Such negative results are called hardness results, because they prove that a problem is hard to solve fast.

History has shown that it is important to be both optimistic and skeptical at the same time. Some problems were thought to be hard but an algorithm was found in the end; while for other problems, a very simple and naive algorithm turned out to be the best we can hope for. However, for most of the problems, their complexity is still not well established. The best-known algorithms are often very far from the best-known hardness results and the truth can lie anywhere in between.

What is the Contribution of this Thesis?

In the past decades, linear programming (LP) has been successfully used to develop approximation algorithms for various optimization problems. The simplex method mentioned earlier is used to solve linear programs and is considered to be one of the most important algorithms of the twentieth century, which underlines the importance of linear programming in computer science.

The so-called assignment LP lead to substantial progress for various allocation problems, where items are allocated to players or machines. An example of such problem is scheduling unrelated parallel machines, where computer tasks are to be scheduled on a number of machines such that the last one is finished as soon as possible. Unfortunately, we know that the best-known approximation algorithms for this problem already have the best approximation ratio that any algorithm using the assignment LP can achieve. The bound on the achievable approximation ratio by an LP is called the integrality gap of the LP.

We have thus reached the limits of the assignment LP. The natural question is then whether a different LP formulation can lead to better algorithms. We answer this question positively for variants of two allocation problems: max-min fair allocation and maximum budgeted allocation, which we define in later chapters. This is achieved by using a more powerful LP formulation called the configuration LP that has exponential size. Exponential size is considered inefficient, but configuration LP can be approximated efficiently. This is where the title of the thesis comes from, since we use exponential linear programs in an efficient way.

The restricted max-min fair allocation, also known as the restricted Santa Claus problem, is one of few problems that has a better polynomial estimation algorithm than approximation algorithm. An estimation algorithm estimates the value of the optimal solution, but is not necessarily able to find the optimal solution. The configuration LP can be used to estimate the optimal value within a factor of 1/(4 + ε) for any ε > 0, but it is not known how to efficiently find a solution achieving this value. We give an approximation algorithm with the same approximation guarantee but improve the running time to nO(log n). Our techniques also have the interesting property that although we use the rather complex configuration LP in the analysis, we never actually solve it and therefore the resulting algorithm is purely combinatorial.

For the maximum budgeted allocation (MBA) we prove that the integrality gap of the configuration LP is strictly better than 3/4 and provide corresponding polynomial time rounding algorithms for two variants of the problem: the restricted MBA and the graph MBA. Finally, we improve the best-known upper bound on the integrality gap for the general case from 5/6 ≈ 0.833 to 2√2 − 2 ≈ 0.828 and also show hardness of approximation results for both variants studied.

Further reading

The full thesis is available for download and you can also have a look at my slides, which contain plenty of additional pictures.

Bibliography


[Aro98]    Sanjeev Arora. Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. J. ACM, 45(5):753–782, 1998.
[Bor86]    Karl Heinz Borgwardt. A Probabilistic Analysis of the Simplex Method. Springer-Verlag New York, Inc., New York, NY, USA, 1986.
[Chr76]    Nicos Christofides. Worst-case analysis of a new heuristic for the traveling salesman problem. Technical report, CMU, 1976.
[Dan51]    George B Dantzig. Maximization of a linear function of variables subject to linear inequalities, in activity analysis of production and allocation. 1951.
[Edm65]    Jack Edmonds. Paths, trees, and flowers. Canadian Journal of mathematics, 17(3):449–467, 1965.
[Fam06]    Number of people in a family. http://web.archive.org/web/20140819085940/http://hypertextbook.com/facts/2006/StaceyJohnson.shtml, 2006. Accessed: 2014-08-19.
[Gap11]    The world has reached peak number of children! http://web.archive.org/web/20141120230405/http://www.gapminder.org/news/world-_peak-_number-_of-_children-_is-_now/, 2011. Accessed: 2014-11-20.
[HK62]    Michael Held and Richard M Karp. A dynamic programming approach to sequencing problems. Journal of the Society for Industrial & Applied Mathematics, 10(1):196–210, 1962.
[JM07]    David S Johnson and Lyle A McGeoch. Experimental analysis of heuristics for the stsp. In The traveling salesman problem and its variations, pages 369–443. Springer, 2007.
[KM72]    Victor Klee and George J Minty. How good is the simplex algorithm? 1972.
[KMN+14]   Christos Kalaitzis, Aleksander Madry, Alantha Newman, Lukas Polacek, and Ola Svensson. On the configuration lp for maximum budgeted allocation. In IPCO, pages 333–344, 2014.
[Mit99]    Joseph S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric tsp, k-mst, and related problems. SIAM J. Comput., 28(4):1298–1309, 1999.
[MS04]    M. Mucha and P. Sankowski. Maximum matchings via gaussian elimination. In Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on, pages 248–255, Oct 2004.
[PS12]    Lukas Polacek and Ola Svensson. Quasi-polynomial local search for restricted max-min fair allocation. In ICALP, pages 726–737, 2012.
[RS98]    Satish B Rao and Warren D Smith. Approximating geometrical graphs via “spanners” and “banyans”. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 540–550. ACM, 1998.
[ST04]    Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM, 51(3):385–463, 2004.

Monday, April 13, 2015

High-fat diet in the Arctic

Arctic explorers carry a couple of kilograms of butter, because it contains many calories per gram. Some of them eat a stick of butter for breakfast as well as dinner. Me and Martin also bet on fat when we went to Kebnekaise: we brought butter, goose fat, coconut oil, sausages, bacon, frozen meatballs and almonds. I counted at least 3 kilograms of fat but we probably had more. You have to do this if you want to be considered cool in the Arctic circles.

Kebnekaise is a mountain area located beyond the Arctic Circle and Kebnekaise is also the name of the highest mountain in Sweden. I have been there two years ago and wanted to come back as soon as possible, despite the horrible weather we have experienced. There is something about the Kebnekaise area that draws me there and it's hard to explain.

Sunday

After arriving to Kebnekaise fjällstation, we went for a short ski ride just above the hut. The snow was horrible, as is normal for the very windy Láddjuvággi valley. It was then easy to convince Martin to go to Tarfala valley in search for better snow. It turned out to be the right call.

Monday

In the morning we went up to Tarfala mountain hut in sunny weather.

Tarfala valley, Storglaciär and Isfallsglaciär
Martin took a nap in the afternoon, so I went alone for a ski ride just above the hut. The snow was much better than yesterday but still very tricky. Thanks to a lot of wind, icy parts mixed with deep pockets of powder. I fell because of this in the bottom flat part and later learned that the whole hut watched me fall through the window. I'm always happy to provide entertainment.

After dinner, the whole hut gathered again at the windows to watch a group of guys skiing with headlamps. I told Martin: "They are either complete idiots or professionals".

There is no water or electricity in the hut and you have to fetch water and wood from the outside in −15 degrees Celsius. After the arrival of the group with headlamps, the hut was packed to the last bed and had the right Arctic atmosphere. The fat in our stomachs also only amplified it.

The Moon and a hairy mountain. My best guess is that wind is blowing snow over the mountain and creating an illusion of hair.

Tuesday

Two years ago me and Kolo unsuccessfully tried to climb Kaskasatjåkka (2076 m), the 4th highest mountain in Sweden. We turned around because of high winds. Me and Martin made a second attempt and the weather was much better this time with clear blue sky. However, it was very windy and cold, so we had to cover our faces regularly to avoid frostbites. We were rewarded with a view that is even better than from Kebnekaise sydtopp, the highest mountain in Sweden.

Western panorama includes 3 of the top 5 highest mountains in Sweden: Kebnekaise sydtopp, Kebnekaise nordtopp and Kaskasapakte. And it's taken from the 4th highest mountain, Kaskasatjåkka.

Wednesday

We woke up to a typical Tarfala weather: very low visibility, snow and strong wind. No wonder this is the most windy place in Sweden.



Luckily for us, the wind was blowing into our backs and it was actually making moving easier. We wanted to go back to the Kebnekaise fjällstation, but also check out the glacier cave inside Pallins halvjökel.

You can make a couple of ski turns in the glacier cave

The glacier cave provided a nice shelter, but we had to leave it and enter the white world.

Man on the Moon

We arrived at Kebnekaise fjällstation just before noon and then didn't do anything for the rest of the day.

Thursday

Two years ago I have been ogling Tuolpagorni a lot but we didn't have time to ski it, so I made it my main goal of this vacation.

Tuolpagorni has a bowl on the top, a very unusual formation

The conditions looked awesome: clear blue sky, no wind and a lot of powder snow. Our only worry were avalanches, but a snow pit only showed a dangerous layer more than a meter deep.

It felt very strange to be in Tuolpagorni's flat bowl up in the air. We went up to a saddle below the top, enjoyed the view and then skied down the obvious path.

Our downhill route

It was our first time skiing such a narrow and steep couloir (38 to 40 degreees), but in the end it was easier than expected. The deep snow was very forgiving and the couloir wider than it looks at first.

Our piece of work in the couloir

Wow, what a day! No wind is a once-in-a-lifetime experience in this area and skiing Tuolpagorni is also something we won't forget. Watch Martin's video summarizing the whole day.

Friday

I woke up feeling bad, so I stayed in the hut while Martin went for a short ride near Jökelbäcken. It was time to leave Kebnekaise and head home. I'm sure we'll be back soon.

As usual, a small selection of my photos is on Flickr and a full album from multiple cameras is on Google+. Martin also made a video from the whole trip.

Sunday, March 15, 2015

Evolutionary psychology: understand culture and improve your life

Why do cultures in Europe differ a lot from north to south, but much less from east to west? Does it have something to do with temperature? Why are societies that are surrounded by more bacteria and viruses less tolerant and more xenophobic? And why are symmetric objects considered beautiful all over the world?

To answer these questions, we need to look into our evolutionary makeup. The mind is not just a product of culture, but also a product of evolution and environmental factors other than culture.

Massive modularity of our brains

Many families have children as well as pets, for example a dog or a cat. Even though the pets and children live in the same environment, only one species learns the language spoken in the family. Some people claim that it's because of an all-purpose learning device in our brains, but that is false (see here and here). We have pre-programmed mechanisms (also called modules) in our brains that are designed to learn a language.

We can think of the brain as a computer that is loaded with many useful programs and libraries that learn from the environment. We have mechanisms for face recognition, short-term memory, naive physics, cheater detection, incest avoidance, naive psychology, food disgust, general intelligence, etc. If you lack a module in your brain, you can't circumvent it by learning; the same way you can't fly or breathe under water, because you lack important body parts. Cats and dogs won't be able to talk to us unless their brain evolves and after a stroke you might lose the ability to talk coherently. Malfunctioning brain mechanisms are also the root causes of disorders like Down syndrome, Asperger syndrome and prosopagnosia.

Rider on a elephant

A very useful metaphor about our brains comes from Jonathan Haidt's excellent book Happiness Hypothesis. Our brains consist of a rider controlling an elephant (Daniel Kahneman uses System 1 and System 2 for essentially the same thing). The elephant is responsible for our emotions, intuition, bodily functions, etc. The rider is responsible for rational thought, self-control, etc. The elephant has very old parts that we inherited from reptiles and mammals, while the rider is very young and is also present in higher mammals.

Ironically, the rational and younger rider thinks that he has full control, while it's often the elephant who makes the big decisions. The rider has only a limited power against the strong elephant. Imagine you heard about an excellent work opportunity, but later decided that commuting 10 more minutes to work is not worth more salary and better work conditions. The elephant was very scared and wasn't going anywhere, so the rider came up with his own story where he has everything under control.
The first principle is that you must not fool yourself—and you are the easiest person to fool. – Richard P. Feynman

Nature versus together with nurture (and randomness)

You know the classic question: is behavior X determined by biology or is it determined by the environment? This question gives the impression of there being only two alternatives, a notion now recognized as a false dichotomy. Robert Sapolsky said it well.
To an overwhelming extent, the age-old “nature versus nurture” debate is silly. The action of genes is completely intertwined with the environment in which they function; in a sense, it is pointless to even discuss what gene X does, and we should consider instead only what gene X does in environment Y. – Robert Sapolsky in Peace Among Primates
An important, but often overlooked, factor is randomness. We have chemical processes running in our bodies that are inherently random and those random events affect our behavior. There is also randomness in people's lives—two people will never go through the same experiences. Randomness is one of the reasons why identical twins raised by the same parents in the same environment end up being slightly different. Another overlooked factor is prenatal environment. What your mom ate and whether she was stressed out during pregnancy affects your behavior forever.

An example of how all this plays out is our status-seeking behavior. We all have a brain mechanism that scans the environment around us, measures our own social status and tries to increase it. Entrepreneurs improve status by starting a successful company, professors by getting their papers published and a hunter-gatherer perhaps by killing a big animal. A basic behavior is provided by nature and then culture and environment shape it into its final form. Note that there are also gender differences, men and women on average seek status differently.

Many people have small jaws these days and therefore problems with teeth not fitting in. It is unlikely that this is caused by bad genes, since only 10 000 years ago people had bigger jaws with better teeth. Scientists theorize that it was because they chewed harder food, while these days it's mostly soft food, so the jaw doesn't develop properly. Our brain is much like the jaw. Overprotected kids suffer a deficit of play and they grow into less creative, less social and less happy adults. Even if a behavior is influenced by genes, the genes need input from the environment for the behavior to develop properly. Nature and nurture are truly inseparable.

Evoked and transmitted culture

Have you ever wondered why nations in colder areas have tasteless food? The classic explanation attributes this to cultural differences. This politically correct answer is completely useless: cultures are different because they are different (although it would be appreciated in the tautology club).

People in warmer regions used spices, because they had to. The commonly used spices have very good antimicrobial properties, so they protect food from spoiling when it's too warm.

Let's now move on to a much more difficult topic than food, namely xenophobia. What you read next might be upsetting, so watch a video of a cute duck first.


Our brains are also pre-programmed to be xenophobic and intolerant, but it seems to be very dependent on the environment around us. Suppose you are a hunter-gatherer living in the mountains. The spring and summer were surprisingly cold and the food is scarce, so you descend from the mountains where you meet another tribe. The tribe has been living in an environment with different pathogens (bacteria, viruses, parasites), so you are not immune to them but they are. Exposure to those pathogens might harm you and even kill you. What might evolution do? It makes you avoid strangers, because they might carry dangerous pathogens. It also makes you avoid new things and be more conservative, because your old ways of living are proven to be safe. Remember that evolution is an amoral process that only cares about transmission of genes, so it sometimes leads to such unpleasant results.

There is also good news, though. People living in areas with fewer pathogens are less xenophobic, more tolerant and open to new experiences. If you live in a safe environment, it's less likely that a contact with a stranger or a new experience will harm you. Rather than avoiding strangers, it's more beneficial to meet them and perhaps trade goods with them.

All of this sounds reasonable, but did we really evolved to be this way? One can do experiments to confirm the theory. In one experiment, people that heard news about a recent disease outbreak were less open to immigration. Unfortunately, it's hard to do experiments with whole cultures, but we can wait for a natural experiment: different parts of the world get rid of pathogens quicker than others, so we can compare how their levels of xenophobia change over time.

Wait, there is more! Countries with lower prevalence of pathogens also value physical beauty less, have puberty earlier, are more individualistic, have higher IQ, are less violent, are more democratic, have fewer kids, etc. The list is never-ending and it remains true even after controlling for factors like wealth and temperature. Prevalence of pathogens might be the most important factor behind cultural differences. It will take decades to prove causality and not just correlation, but it's very intriguing nevertheless.

In the last 100 years, humanity made a lot of progress; many countries ended racial segregation, gave voting rights to women and are now even considering gay marriage. What if this increased tolerance happened due to progress in medicine, vaccination and better hygiene? This social change is often attributed to our rational selves, but perhaps we only tamed the elephants in our brains.

Other environmental factors that correlate strongly with cultural differences include: temperature, abundance of resources, ratio of men and women, whether they have a nomadic lifestyle, etc. When elements of culture are shaped by the environment, they are called evoked.

People in warmer cultures don't need to use spices anymore, because they have fridges, but such recipes are still used by new generations. Old information is being transmitted, so we call it transmitted culture. It is unclear what elements of culture are evoked and which are transmitted, though. The understanding of our brains is limited, so anyone claiming they completely understand culture is lying.

Improve your personal life

We could apply evolutionary theories to social problems, but I like to use them to improve my own life. Most people who tried public speaking felt nervous about it. Someone then told them to just relax and not think about it. However, this well-intentioned advice only focuses on the rider and completely ignores the elephant in the brain.

What if I told you that a better strategy is to stand straight instead? Your body will lower the level of stress hormones, the elephant will feel less scared and the rider will calm it down easily.

Other life improvements are about the new media: celebrity tabloids, video games, TV, novels, movies and porn. Recall that our genes react to the environment around us. What happens if you spend your free time fighting fictional creatures or watching lives of attractive people that are 5 000 kilometers away? Your behavior in the actual culture you live in will be inappropriate and suboptimal.
From Stuff No One Told Me

I'm not saying you should avoid all the new media completely. For example I read novels and watch movies from time to time, but I try to pick the more realistic ones. However, you should avoid porn and celebrity gossip like the plague. On the other hand, feel free to gossip about the people around you or have sex with them—science has shown that both behaviors are beneficial.

There are plenty of other ways to apply evolutionary theories to your life and if you want to know more, see the reading list at the end of this post. The possibilities are truly endless: you can improve your happiness, make better decisions, lower your stress, become a better writer, become healthier, be more efficient or understand your own gender better.

New theories

Evolutionary psychologists have come up with interesting theories that try to explain many facts of human existence.
  • Why people gossip.
  • Why socialism works in a family or a small community, but ends in a disaster when applied to a whole nation. As E. O. Wilson said, "Marxism: wonderful theory, wrong species".
  • Why toddlers are almost indistinguishable from each other.
  • Why women put on make-up and why men take large risks.
  • Why parenting style has almost no effect on a child's personality (parents affect child's personality through their genes instead).
  • Why a small fraction of people is born left-handed.
What if some of the theories turn out wrong? We move on and try to find better explanations. However, some of the theories have already amassed substantial evidence, so they are very likely to be correct.

Interestingly, scientists have failed to provide good evolutionary explanations for humor, male homosexuality, female orgasm and music. Music might be just a by-product of evolution that presses the right buttons all over the brain. Think of it as a pleasurable drug.

Some (flawed) arguments against evolutionary psychology

If behaviors like aggression, psychopathy and xenophobia are encoded in our genes, people think this will give others excuses. You can't kill a person, blame it on your genes and skip going to jail. Since the science can be misused, some people try to stop this line of research. Their flawed reasoning reminds me of my favorite quote.
Numerous studies have shown that at least 98% of murderers were born after a heterosexual intercourse. That's why the European Union should ban people from having sex. – Martin Malý
We could ban sex to end all human suffering, but it would come with at a big price: all the good things human would be gone too.

Mentioning evolutionary psychology or neuroscience often leads to very heated discussions, comparable to those about politics and religion. The new scientific findings affect every single mainstream ideology; it doesn't matter whether you are on the political left or right, an anarchist, a feminist, a Christian or even a vegetarian. Each ideology got something wrong about our minds and bodies.

Some people devoted their lives to an ideology, built their whole identity around it and it's hard for them to admit they were wrong the whole time. Cognitive dissonance then kicks in and people get upset. Many arguments against evolutionary psychology have more to do with emotions rather than objective facts.
Rationality is costly. It prevents us from believing what we want to believe. – Michael Huemer in The Irrationality of Politics

Conclusion

It has been 150 years since Charles Darwin's book On the Origin of Species and people are slowly accepting that evolution is real. However, most people have still trouble accepting that evolution affects our brains too. Many religions have accepted evolution and it's time for the rest of the world to do the same.

I would like to end the post on a positive note, so let me quote Daniel Dennett.
Every living thing is, from the cosmic perspective, incredibly lucky simply to be alive. Most, 90 percent and more, of all the organisms that have ever lived have died without viable offspring, but not a single one of your ancestors, going back to the dawn of life on Earth, suffered that normal misfortune. You spring from an unbroken line of winners going back millions of generations, and those winners were, in every generation, the luckiest of the lucky, one out of a thousand or even a million. So however unlucky you may be on some occasion today, your presence on the planet testifies to the role luck has played in your past. – Daniel Dennett in Freedom Evolves

Further reading and watching


Videos and lectures

The easiest way to start with evolutionary psychology is by watching videos and lectures. It's possible to watch them 25% faster by using the gear button on YouTube.

Books

These books take into account evolutionary psychology and neuroscience. Many of them aren't solely about evolution, but they are based on the newest research.

Some interesting papers

If you feel adventurous, you can read some scientific papers.

Sunday, February 15, 2015

How to be happy and build socialism (for real this time)

Recently a couple of friends started a mail discussion on where to live. Some people like to choose places with interesting work opportunities but I think that approach maximizes the wrong thing. I think that happiness should be the ultimate factor. When it comes to happiness the more important question is how to live instead of where to live.

So how should you live? I think science, namely psychology, can now offer an excellent answer. In the last couple of decades psychology evolved from a "quackery" into a solid science. The Happiness Hypothesis book by Jonathan Haidt does an excellent job of presenting the latest research on happiness. I particularly like Haidt's thorough scrutiny of known facts. For example, it is known that married people are happier. But are they happier because they are married or are they married, because they are happy and thus more attractive to others?

Here is my short summary of the book.
  • Perhaps the most important factor is how well socially connected you are—your family, friends or local community are very important. When it comes to a local community, I have been a member of various sport clubs or volunteering groups and many of my happiest memories come from these communities. And don't let me started on all the memories with friends.
  • Some people mistakenly equal comfort and pleasure with happiness, but it doesn't work that way. If you derive happiness from drinking wine, after a while it wears off and you would need to upgrade to a more expensive wine or find something else instead (see hedonic treadmill). Stoics and Buddhists were right: go ahead and take a cold bath!
  • Nietzsche was right when he said "That which does not kill us makes us stronger". In the last 4 years I have struggled with health problems, but I think I'm happier as a result. I really appreciate ordinary things like a good friend or a day without pain. Also, lack of adversity is one of the reasons why overprotected kids end up being less happy adults.
  • Money only buys you happiness until a certain level of income and then they don't matter anymore. If you want to use money to increase happiness, use them on other people or buy experiences instead. There is also new evidence that saving might be the best option.
  • Altruism is a great source of happiness. Giving a gift is more beneficial to the person giving the gift rather than the one receiving it.
  • Work is not as important as most people think, but it has a measurable effect particularly if you have some autonomy in your work. Also, many people experience flow when they are immersed in a challenging exercise. I remember countless nights when I barely drank or ate until a particular math or programming problem was done.
  • Genes and early environment are an important factor in happiness but they are the thing of the past, so there is little you can do.
  • The place where you live is not as important as people think. You'll be as happy in sunny California as in cold and dark Tromsø. Although there are some environmental factors that stress you out and make you less happy, like commuting or high noise levels. Stress in general is a bad thing and not just for happiness.
  • Some sense of morality and meaning of life are important too. Traditionally these have been provided by religions but atheists also need them to be happy.
If I were to sum up the book in one sentence, it would be "Relationships matter the most and career, money and comfort are overrated." Your grandma would probably tell you the same thing, but it's good when scientific findings agree with reality for once.

Live like my parents

My parents have lived their life as preached by Happiness Hypothesis even though they haven't read it. They have very strong social ties, spend money mostly on travelling and don't work a lot.

For example, my father is a doctor but he is better known as the head of an orienteering club. He doesn't have an impressive professional career but he has a spectacular career as a volunteer. Did you know that Pezinok once hosted the World School Orienteering Championships? Alright, you have probably never heard of the small town Pezinok, but still...

When it comes to money, they spend most of it on experiences. My brother and I didn't have a lot of fancy things while growing up, but by the time I was 10 years old I have been to half of Europe. They still travel a lot with their small community of 20–30 people, doing things like biking for a week in the Alps. Most people my age wouldn't dare to go on the bike tours these almost retired people manage to do.

Economic systems

Do you know what is absolutely essential in capitalism? Reputation and trust. When you buy a meal in a restaurant, you trust the employees that they will not serve you spoiled food that makes you sick. If they did that, you wouldn't come back and you would tell all your friends to stay away from the restaurant. The reputation of the restaurant would get damaged, people would trust them less and the restaurant would get fewer customers. They might lower their prices as a result.

If this happened repeatedly, you would mistrust restaurants altogether and stop eating out. This would then lead to an inefficient outcome: you could be doing your normal job instead, get a higher salary for that and then use it to buy an excellent meal. Instead you forgo your salary and cook a mediocre meal at home, while the restaurant decreases its revenue. When people don't trust companies, everyone is worse off—the regular people as well as the companies. By the way, high level of trust (and capitalism) is one of the secrets behind the Scandinavian success.

Sometimes capitalism doesn't lead to good outcomes. People near a major tourist attraction just come and go, so the owner of a restaurant might not care about reputation and serve bad food (word of advice: don't shop near tourist attractions). In a closely knit community you can't afford cheating like that, because people would gossip about you and maybe even exclude you from the community. Evolutionary psychologists theorize that our obsession with gossip makes a community well-functioning. Gossip is a great tool, you quickly get to know who's a cheater and who's honest.

When you are doing transactions in a community, you rarely pay the market price, if you pay at all. When you help a friend move, you might get a lunch as a reward. Even a friendly outing to a bar is a transaction: you trade your time and company in exchange for theirs.

Being a member of a community gives you access to goods that capitalism is bad at providing. Only a friend's hug feels like a friend's hug. Only your grandma can cook a pork knee exactly like your grandma. Only your friend can plan a vacation tailored for your small gang taking into account everyone's preferences. No company can ever do those things, although the Japanese would disagree.

The economic system I just described is very similar to socialism. Socialism and capitalism have both its place in a society and both have advantages and disadvantages. Once you start applying them where they don't belong, you'll get into trouble. If you charge your partner each time you have sex, your relationship won't last long. If you make a whole country use socialism, it will also end in a disaster, because it takes enormous brain power and gossip to track reputation in a huge community. The people who founded the Soviet Union overestimated the capacity of our brains by a factor of about one million.

A small community has a cultural advantage in addition to an economical one. You can ignore your country's culture, since you spend most of your time in your own subculture. You can also ignore politics to a large extent. When a politician messes up unemploymeent benefits, you stay calm, because you have 10 people who would help you if needed.

Work is less important

Apart from work not being the main factor in happiness, I see many other problems with prioritizing work over everything else. For example, if you move to a different place solely for work, you severely cut your social ties. Most people think they will find new friends in the new place, but that rarely works out. Most expats end up befriending other expats and only integrate with the locals very slowly. If you really want to prioritize work, choose a place with more expats.

I also realized that where and what I work with doesn't matter that much. I like to do many things and most of them can be done almost anywhere.
  • I really enjoy writing and people seem to enjoy reading my articles. My most successful post I wrote for Spotify has been viewed 49 000 times until now.
  • I also like to organize vacations for my friends and they trust me that I pick good places. In the summer I can barely focus on regular work and I often procrastinate by planning vacations.
  • From the jobs I have actually been paid to do, I have enjoyed teaching the most. That is another option that can be done almost anywhere.
All jobs mentioned above—writer, travel guide and teacher—usually don't offer high salary, but that is not an issue if you don't care about money, as I explain below.

Early retirement

My life turned around by 900 degrees (that's 360 + 360 + 180 for the mathematically inclined) when I started reading about saving, investing and early retirement. Did you know that you can retire in 17 years if you manage to save half your salary every month?

What happens when I save enough to retire? I won't start laying around doing nothing! I might just do something else than before, like starting a travel agency specializing in bathing in ice-cold lakes all over the world. Perhaps I could write books or teach courses about bathing in those ice-cold lakes. These ideas might not be very profitable but that doesn't matter, since my investments would provide enough income anyway. Interestingly, I achieve flow more often when working on hobby projects than in regular jobs, so doing this should also increase my happiness. And I would also like to work less than 40 hours a week to have times for activities and people that make me more happy.

You might think that saving 50% is impossible, especially in this economy. This is nuts, because you have it 10 times easier than your great-great-grandmother. People in the US spend less than 13% of their income on food, while in 1950 it was 30% and I bet similar development has happened all over the world. A couple of centuries ago sometimes even 100% of your income wasn't enough during a famine. People are so poor that whenever I go to a shopping mall in any modern country, it's always full of people. With such enormous economic prosperity and wealth people still have trouble surviving from paycheck to paycheck and happiness is not increasing. Everything is amazing right now and nobody is happy.


Buying expensive things doesn't make you happy, so why would you waste money on them? If you imagine yourself retiring in 15 years and having more time to do things that make you truly happy, getting rid of your expensive habits becomes a piece of cake.

The rise of the robots and artificial intelligence is also a very good reason to save as much as possible, because we will all lose jobs sooner or later.

Conclusion

The message of all the knowledge about economics, stock market and the science of happiness is crystal clear to me. Use capitalism to get wealthy, retire early, embrace the power of socialism and increase your happiness in the process. Marxists used to say that socialism is the next step after capitalism and I guess they were right. I still think that Marxism is a dangerous ideology that killed at least 100 million people, but deep inside of it lies a bit of truth.
A good place to look for wisdom is where you least expect to find it: in the minds of your opponents. – Jonathan Haidt in Happiness Hypothesis

Monday, January 19, 2015

Ski mountaineering in Veľká Studená dolina

After 5 years of ski touring me and Martin finally mustered some courage to try High Tatras in Slovakia, our highest mountain range. Their unpredictable weather and rough terrain make them very dangerous. To top it off, a couple of days before our planned arrival the weather was awful—freezing rain followed by snow and very strong wind. Thanks to an icy base layer, there was very little snow but high avalanche danger. Our plan was to go up to Zbojnícka chata chalet and assess the local avalanche danger ourselves. There must be at least one good slope to ski!

Wednesday

Poprad in –21 degrees Celsius.
We went up to Zbojnícka chata as planned. Suprisingly, the amount of snow was decreasing with increasing altitude. The last bit below the hut was very icy and we both hated it, because we took our skis off at least 5 times. After a short nap at the hut we went outside to exercise avalanche rescue and dig some snow pits. The first snow pit was completely safe which we couldn't believe, so we dug another one in less deep snow. A column of snow failed before we even started an avalanche test.

A snow column fell even before we started executing a test.
I jokingly said that I'm staying in the hut tomorrow, but I was hoping we would find a safe slope the next day. It started snowing in the evening and I was really happy. At least the annoying ice will be covered by snow.

Thursday

The safest slope in the valley was below Svišťové sedlo (marmot saddle). I was expecting a cloudy day but the sky opened as we approached the saddle.

The Sun finally reached us. Or did we reach the Sun?
When the slope exceeded 30 degrees, we decided to dig a snow pit and make another avalanche test. The snow was deep and the slope safe! The conditions in this particular valley looked perfect and nobody has been here for a couple of days. We left the skis and climbed the last meters with ice axes.

Martin climbing the last few meters.
Rovienková dolina
Happy to be in the saddle.
The view was great and the Sun was shining. Time to ski down.

Safe route choice. All other routes were either steeper or more wind-loaded.
We skied down to Zbojnícky spád which had a lot of blown-in snow. Perfect! After skinning back to the hut, Martin sweared that he'll either end with ski touring or buy new skis, because his skins were slipping a lot on a steep slope. It was still only about 1pm, so why not practice self-arrest? This is a useful technique to stop a fall on a slippery slope with your ice axe. We survived even this exercise.

Friday

The weather forecast predicted high winds on Friday. Some parts of High Tatras got winds of speed 100 km/h, but the valley was calmer. This is no weather for ski touring, so we decided to head back to civilization early in the morning.

High winds up in the mountains
It was mostly alright, although sometimes we had to stop to let the wind gusts disappear.



All in all, it was a great trip. It turned out to be very educational besides all the skiing and climbing. For the first time I saw a snow pit test failing and we also did some useful avalanche and mountaineering exercises.

Small selection of my photos is on Flickr and an album merged from 2 cameras including some videos is on Google+. Martin also made a YouTube video in Slovak from the trip (just don't take inspiration from the first avalanche test, it was poorly performed).