2016
07.05

Subset sum made faster

Konstantinos and Chao have a new version of their subset sum paper on the arxiv.  They speed up  the classical subset sum algorithm by a factor of sqrt(n)  using clever divide and conquer strategy.  This version is reasonably well written and is quite elegant. A nice paper!

2016
06.25

“I do not understand why the British government needs until October to decide whether to send the divorce letter to Brussels,” Jean-Claude Juncker, the president of the European Commission, told German television.

http://nyti.ms/293Hp1m

2016
06.24

We shall never stay

Whatever the cost may be, we shall leave on the beaches, we shall leave on the landing grounds, we shall leave in the fields and in the streets, we shall leave in the hills; we shall never stay, and even if, which I do not for a moment believe, this Island or a large part of it were bored and without internet connection, then our Empire beyond the seas, armed and guarded by the British Fleet, would carry on the leaving, until, in God’s good time, the New World, with all its power and might, steps forth to the rescue and the liberation of the old.

2016
06.19

Quote from The Norman Conquest

Naturally everyone answered in the affirmative, shouting out in their respective tongues, but, unfortunately, says Poitiers, the guards outside the church thought that this loud clamour was some sort of last-minute English treachery, and responded by setting fire to the nearby houses.

2016
05.29

Quote from Emperor of Japan: Meiji and His World, 1852’1912

Describing his unhappiness over the shogunate’s signing treaties with barbarians, a development for which he had no excuse to offer the gods or his ancestors, he mentioned his reluctance to send Kazunomiya, the daughter of an emperor, to a part of Japan where foreigners roamed.

2016
05.02

Men reading tweets insulting women to their faces….

Men reading tweets insulting women to their faces. m.youtube.com/watch?v=9tU-D-…

2016
05.01

Exciting news on the Erdos-Szekeres convex polygon…

Exciting news on the Erdos-Szekeres convex polygon problem. arxiv.org/abs/1604.08657

2016
04.26

Sanders to declare victory and withdraw from the Democratic party.

2016
04.20

Not creepy at all… https://t.co/H47HQa48el

Not creepy at all… twitter.com/ABC/status/722…

2016
04.18

“Your lie in April” https://t.co/c8UM39EHGS

“Your lie in April” en.wikipedia.org/wiki/Your_Lie_…

2016
04.18

Michigan governor to fly over Flint and inspect th…

Michigan governor to fly over Flint and inspect the devastation through the window. twitter.com/nytimes/status…

2016
04.17

Bottle ready.

Bottle ready.

2016
04.16

Numberwang https://t.co/Z3u9craZBs

Numberwang youtu.be/qjOZtWZ56lc

2016
04.10

Via reddit. North Korea is a horrible dictatorship…

Via reddit. North Korea is a horrible dictatorship where you only get to pick one person as a leader, not like the US where we get two.

2016
04.06

Student that got into all ivies. I suggest a real…

Student that got into all ivies. I suggest a reality show “the Bachelorette” following her as she choses the one.
nyti.ms/1MSRmPp

2016
04.03

Had we reach peak Trump?

Had we reach peak Trump?

2016
04.03

12 days early.

12 days early.

2016
03.31

The way of the bash…

So, after 20 years I decided to jump from tcsh to bash. Happy I did – the way of bash is strange, but everything is answered in stack-exchange (to the point that I don’t even try to figure out how to do simple things – just search the web for it). Furthermore, it is a way better scripting language with functions and stuff, and also clearly it is more complete. Oh, and it is even coming to windows 10, natively, any day now.

2016
03.31

14% of Hispanics view Trump favorably. That sound…

14% of Hispanics view Trump favorably. That sounds too high to me… washingtonpost.com/blogs/plum-lin…

2016
01.20

Beyond planarity…

I put my talk from SODA 16 on youtube (the audio quality is not great, but whatever):

  1. Part I: The circle packing theorem.
  2. Part II: The planar separator theorem — the movie.
  3. Part III: Low-density and polynomial expansion graphs.
  4. Part IV: Local search and approximation algorithms.
  5. Part V: Hardness, thesis and open problems.

The slides are available here.

Yalla, bye.

2016
01.17

The art and glory of vector figures/animations…

Poly polypolgon

So, creating a vector animation for talks, once you have a pdf with each page being a frame of the animation is not hard, see here for details.

The question remain, how do we generate such a pdf to begin with? One way is by using a drawing program. Ipe is a good candidate, but creating such figures can be tedious, to put it mildly. In some cases (and you might want to sit before reading the rest of this sentence) there is really no better alternative to… doing some real programming!

Luckily, there is a light graphics library, specifically Cairo, that is happy to output directly to pdf (or svg) files, generating true vector drawings – which are both small, and of higher quality than the “standard” bitmap output (yuck).

Of course, you might want to have an interactive program, with a window and stuff, and output to pdf/svg only when you are happy with the results. Cairo is happy to let you do that – the same drawing code can be used to output to the screen, or to a pdf (or svg). Once you have a pdf, you can easily convert the figure to ipe, and edit the figure directly (using pdftoipe).

As a demonstration of the above, here is the source code of an interactive program I wrote (that I used to generate the above figure). Its a C++ program for linux, using gtk, cairo, and CGAL (because life is too short to implement 2d point class yet again). If this sounds like many libraries one needs, on Debian/Ubiuntu this just requires installing the relevant packages (you would also need the pkg-config package — a nice programming tool). The program is self explanatory as far as what keys do.

And a final comment — to force cairo to output the current image to a new page in the pdf file, one need to use cairo_show_page.

2016
01.11

SODA talk slides

Slides…

You would need acrobat reader to see the animations.

2015
12.13

Word of the day: Trilateration. https://t.co/9V8fC…

Word of the day: Trilateration.
en.wikipedia.org/wiki/Trilatera…

2015
12.12

Kung Fu fight between a man and a cow… https://t…

Kung Fu fight between a man and a cow… youtube.com/watch?v=LxXjsQ…

2015
12.08

How could the ancient Greek mathematicians be so smart, and yet so stupid?

mathpages.com/home/kmath066/…

2015
11.26

Drinking the kool-aid… https://t.co/Z2JpDowwg4

Drinking the kool-aid… en.m.wikipedia.org/wiki/Drinking_…

2015
11.26

The Serial Swatter… https://t.co/Dcixl4yxox

The Serial Swatter… mobile.nytimes.com/2015/11/29/mag…

2015
11.24

who would take away their license to kill?

who would take away their license to kill?

2015
11.19

Red mercury – the WMD every self respecting terror…

Red mercury – the WMD every self respecting terrorist should have. nytimes.com/2015/11/22/mag…

2015
11.15

Conference in Memory of Jiří Matoušek

The conference will be held in the very centre of Prague, Czech Republic, in the historical building Karolinum of Charles University. The date is 23-28th July 2016, which is immediately after European Congress of Mathematics.

More details here.