Løsning til min danske kryptokryds nr. 32

Definitioner er understregede.
* angiver omkastning, < angiver omvending.

Vandret

2 Retsforfølge og lede efter vrøvl igen. (7)
SAGSØGE. SØGE (=lede) efter GAS (vrøvl) retur (=igen)

7 Lyd fra endetarm i avlssvin. (4)
MIAV. Gemt i endetarMIAVlssvin

10 Anret sumak-arrangement fra vestafrikansk land. (10)
MAURETANSK. ANRETSUMAK*

11 To kilo i vinen gør beruset. (7)
DRUKKET. KK (to kilo) i DRUEN

13 Afsætning af glas går tilbage. (4)
SALG. GLAS<

14 Propagere for EU? Bed DR om skrivelse. (7)
UDBREDE. EUBEDDR*

15 Stagnation i Liechtenstein er tidsbegrænset. (6)
INTERTI. liechtensteINERTIdsbregrænset

16 Lige fra regnvejr til robåd. (4)
ENER. Hvert andet bogstav fra REGNVEJR

17 Svovl-ledning har forskinket hvad der blev afsat seks dage til. (9)
SKABELSEN. S(vovl) + KABEL + SEN

21 Vi pirater til søs, hvor offentlighed er uønsket. (9)
PIRATERI. VIPIRATER*

25 Storme fra gale aser. (4)
RASE. ASER*.

27 Skinger tuba afbryder stilhed uden at holde tempoet. (6)
RUBATO. TUBA* i (afbryder) RO (stilhed).

29 Gøre hastværk når man restaurerer voliere. (7)
OVERILE. VOLIERE*

30 Dyr fadæse leverer indhold. (4)
ÆSEL. fadÆSELeverer

31 Var fx Finland under den kolde krig et område med god akustik? (7)
LYDLAND. Kryptisk definition, indikeret ved “?”.

32 Besvær i knoglerne, de er slemt betændte! (10)
LEDSMERTER. DEERSLEMT*

33 Klokken er forkert. (4)
URET. Dobbelt definition.

34 Dekanen, efter omorganisation, er den, der genoptager sagen. (7)
ANKENDE. DEKANEN*.

Lodret

1 Gid prishop skaber en vred kunde, fx. (10)
HIDSIGPROP. GIDPRISHOP*

2 Svagt fra sangerinder fra sjællandsk akademi. (7)
SORANER. SOPRANER uden P (“svagt”).

3 At mule over magisk smykke. (6)
AMULET. ATMULE*.

4 Overførselsindkomst til husdyr i form af tørret frugt. (5)
SUKAT. SU + KAT.

5 Finde på nyt navn til agenda: køber flås. (7)
GENDØBE. aGENDa kØBEr flået (dvs. uden det yderste lag.)

6 Opret selvstændighedsbevægelse og Belgien griner. (7)
ETABLER. ETA + B + LER.

7 Malker forbløffende fisk. (6)
MAKREL. MALKER*

8 Medrivende og ophidsende tennis. (6)
INTENS. TENNIS*.

9 Gav kærtegn, omkring et sekund, men anstrengte sig. (5)
ASEDE. AEDE omkring S.

12 Dejlig forvirret om skingert horn er lavet stål, fx. (10)
JERNHOLDIG. DEJLIG* omkring HORN*

18 Hinduistisk princip om kulde og udstråling. (7)
KARISMA. KARMA om IS.

19 Lot vendte sig godt en halv meter omkring for at se øen. (7)
ATOLLEN. ALEN omkring LOT<

20 To gange en tønde efter aftale. (7)
ENTENTE. EN T(ønde) (to gange) E(efter)

22 Denise, efter et par øl, forbliver meget kølig. (6)
ISENDE. DENISE*

23 Vitser om Puccini, fx. (6)
VERIST. VITSER*.

24 Hård på den gamle måde, indeholder lille risiko. (6)
HASARD. HAARD omkring S (small)

26 Fiskerihavn erhverver delvist skaller. (5)
AVNER. fiskerihAVNERhverver

28 Syntes at nogen fortjente grundtemaets kerne. (5)
UNDTE. grUNDTEmaets.

Mit fjerde forsøg på en dansk kryptisk krydsogtværs i den engelske »bjælkede« stil. Nogle nøgler er udmærkede, andre lidt kluntede.

Som PDF: no32.  Løsning til nr. 32

Vandret
2 Retsforfølge og lede efter vrøvl igen. (7)
7 Lyd fra endetarm i avlssvin. (4)
10 Anret sumak-arrangement fra vestafrikansk land. (10)
11 To kilo i vinen gør beruset. (7)
13 Afsætning af glas går tilbage. (4)
14 Propagere for EU? Bed DR om skrivelse. (7)
15 Stagnation i Liechtenstein er tidsbegrænset. (6)
16 Lige fra regnvejr til robåd. (4)
17 Svovl-ledning har forskinket hvad der blev afsat seks dage til. (9)
21 Vi pirater til søs, hvor offentlighed er uønsket. (9)
25 Storme fra gale aser. (4)
27 Skinger tuba afbryder stilhed uden at holde tempoet. (6)
29 Gøre hastværk når man restaurerer voliere. (7)
30 Dyr fadæse leverer indhold. (4)
31 Var fx Finland under den kolde krig et område med god akustik? (7)
32 Besvær i knoglerne, de er slemt betændte! (10)
33 Klokken er forkert. (4)
34 Dekanen, efter omorganisation, er den, der genoptager sagen. (7)

Lodret
1 Gid prishop skaber en vred kunde, fx. (10)
2 Svagt fra sangerinder fra sjællandsk akademi. (7)
3 At mule over magisk smykke. (6)
4 Overførselsindkomst til husdyr i form af tørret frugt. (5)
5 Finde på nyt navn til agenda: køber flås. (7)
6 Opret selvstændighedsbevægelse og Belgien griner. (7)
7 Malker forbløffende fisk. (6)
8 Medrivende og ophidsende tennis. (6)
9 Gav kærtegn, omkring et sekund, men anstrengte sig. (5)
12 Dejlig forvirret om skingert horn er lavet stål, fx. (10)
18 Hinduistisk princip om kulde og udstråling. (7)
19 Lot vendte sig godt en halv meter omkring for at se øen. (7)
20 To gange en tønde efter aftale. (7)
22 Denise, efter et par øl, forbliver meget kølig. (6)
23 Vitser om Puccini, fx. (6)
24 Hård på den gamle måde, indeholder lille risiko. (6)
26 Fiskerihavn erhverver delvist skaller. (5)
28 Syntes at nogen fortjente grundtemaets kerne. (5)

The occasion of this cryptic crossword was the workshop Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms (Nov. 2 – Nov. 6, 2015, Simons Institute for the Theory of Computing, Berkeley, California, United States) that I had the pleasure of co-organising.

The grid is a bit more difficult than usual, with several entries less than 50% checked, and two 15-letter words. Some of the clues (and jokes) make little sense if you’re not the in target group of theoretical computer scientists.

Across

9 School on a graph isomorphism base. (9)
10 Who does the grading in Greek? (5)
11 Maybe a forest is better. (7)
12 Bizarre airlines ignoring N. Alon, say. (7)
13 Indian author of assumption about finding 14 across fast. (4)
14 Idiot workers take gin cocktail to first job. (10)
16 They fight to restore Rosamond’s section. (7)
17 Matrix transform vanishes when v → 0. (7)
19 Circuit complexity, typically, sounds like a religious habit (10)
22 Father of parameterised and polynomial-space algorithms, originally. (4)
24 Two-player game about encrypted mail token. (7)
25 Free variable turns leading proof assistant around. (7)
26 Additional seconds of Keynote experiments stymie brilliant talk. (5)
27 Compute |A ∪ B| as |A| + |B| like Dracula’s former girlfriend? (9)

Down

1 Maybe 20 down is a hammer made of carbon fibre? (9,6)
2 Beethoven wrote one functor in homological algebra; maybe addition. (8)
3 English statistician is positive to a degree. (5)
4 Introduces P.I.T. problem in linearly independent sets. (8)
5 Family of degree |C|. (6)
6 Tree decompostion of Sat is near. (4,5)
7 Letters from Nerode let Erdös blank out. (6)
8 Laugh at an optimal hint solving a problem. (11,4)
15 Maybe a² + b² + c² challenge keeps Naor up. (9)
17 Optimal scheduler spent day and performed many tasks. (8)
18 Where identity is unique, altogether. (2,1,5)
20 More than 64 kilobyte Nintendo retro characters. (6)
21 Neglected flow algorithm starts confusingly. (6)
23 Threaten unruly spy with hierarchy. (5)

Annotated solution

Løsning til kryptokryds nr. 31.

Vandret

2 Småfed kvinde, travlt besat.
KVABSET (=småfed)
Ordspil: KV (fork. for kvinde), anagram (travlt) av BESAT

7 Drej knækket krus. (4)
SKRU (= drej)
Ordspil: anagram (drej) af KRUS

10 Tilpasning af dato: Patina ændres. (10)
ADAPTATION ( = tilpasning)
Ordspil: anagram (ændring) af DATOPATINA

11 Anarkistisk junta tilbageholder strøm d. 24. december. (7)
JULENAT (= d. 24. december)
Ordspil: Anagram (anarkistisk) af JUNTA  omkring LE (strøm “el”, omvendt)

13 Atter skjult i lykkelig ensomhed. (4)
IGEN (= atter)
Ordspil: Skjult i lykkelIGENsomhed

14 Ungt rådyr går frem og tilbage efter plante. (7)
KIDDIKE (en plante i korsblomstfamiljen)
Ordspil: KID (ungt rådyr) + DIK (KID baglæns, ordet “går frem og tilbage”) + E (“efter”)

15 Nu ses vrede efter Cæsars første folketælling. (6)
CENSUS (= folketælling)
C (Cæsars første bogstaf) + anagram (vrede) af NU SES

16 Eremit vaskede spejlet. (4)
ENER (= eremit)
Ordspil: RENE (= vaskede, adj.) baglæns

17 Omorganiseret natolager bruges til kommunikation. (9)
TALEORGAN (bruges til kommunikation)
Anagram (omorganiseret) af NATOLAGER

21 Oprørt generer de dem, der bestemmer. (9)
REGERENDE (= dem, der bestemmer)
Anagram af (oprørt) GENERER DE

25 En klovn tilbage til landet. (4)
IRAN (et land)
I (en) + NAR (= klovn) baglæns

27 Handles kort efter dyrket mark. (6)
AGERES ( = handles)
AGER (dyrket mark) + ES (et kort)

29 Betragt i fuglekæbe en del af skelettet. (7)
NÆSEBEN (del af skelettet)
SE (betragt) indeholdt i NÆB (fuglekæbe) + EN

30 Hvor man kan mødes omkring sagnvæsen. (4)
CAFE (hvor man kan mødes)
CA (omkring) + FE (et sagnvæsen)

31 Hvad siger det lille lam i skrift til europæer. (7)
RUMÆNER (europæer)
MÆ (hvad det lille lam siger) i RUNER (skrift)

32 Omdanne sær, opdyrket jordart. (10)
MORÆNESAND (jordart)
Anagram (opdyrket) af OMDANNESÆR

33 Angrib rent ud. (4)
ENTR (angrib)
Anagram (ud) af RENT

34 Tømt glas for hastig dukkert. (7)
DRUKKET (tømt glas)
Anagram (hastig) af DUKKERT

Lodret

1 Afvisning af smykke efter skaldyr på tog. (10)
REJICERING (= afvisning)
RING (smykke) efter IC (tog) i REJE (skaldyr)

2 Tænk nu gedens indvolde klemte. (7)
KNUGEDE (=klemte)
Indeholdt (“indvolde” af) tænKNUGEDEn

3 Slagmarken tabes i begyndelsen passivt. (6)
VALENT (= passiv)
VALEN (asernes slagmark) + T (første bogstav af “tabes”)

4 Fx zulu, beta, alfa, november, tango, uniform. (5)
BANTU (en gruppe af sprog som indeholder zulu)
B + A + N + T + U (ifølge i det internationale flyveralfabet)

5 Måske Gråbøl returnerer en frokost. (7)
ETTIDEN (frokost)
DITTE (Gråbøl) bagfra (“returnerer”) + EN

6 Julemad i kristendommen fx, den sidder fast i munden. (7)
TANDROD (sidder fast i munden)
AND (julemad) i TRO (kristendommen, fx) + D (den, fork.)

7 Station lever af større byer. (6)
STÆDER (større byer)
ST (station, fork.) + ÆDER (= lever af)

8 Se rundt om min horisont. (6)
KIMING (= horisont)
KIG (= se) omkring MIN

9 Flytte bruskfisk. (5)
ROKKE (= flytte) (en bruskfisk)

12 Åbner udstilling: Firserne er misforstået. (10)
FERNISERER = åbner udstilling
Anagram (misforstået) af FIRSERNE ER

18 Bredt stykke stof gør din barm gyngende. (7)
ARMBIND (bredt stykke stof)
Anagram (gyngende) af DINBARM

19 Organ findes og yder. (7)
LEVERER (= yder)
LEVER (organ) + ER (findes)

20 Lincoln, mellem venner, pruttede til vildt gilde. (7)
ABEFEST (vildt gilde)
ABE (Abraham Lincoln) + FES (pruttede) + T (til, fork.)

22 Gammelt ømtåleligt helium fx. (6)
GASART (helium, fx)
GA (gammelt, fork.) + SART (= ømtåleligt)

23 Bære en rådden frugt. (6)
ENEBÆR (frugt)
Anagram (rådden) af BÆRE EN

24 Promovere dansk kulturradikal uden ende. (6)
BRANDE (= promovere)
(Georg) BRANDES (dansk kulturradikal) uden sidste bogstav

26 Fornuft er mærkelig baglæns på engelsk. (5)
RÆSON (= fornuft)
SÆR (= mærkelig) baglæns + ON (på, engelsk)

28 Mesterskaber i vanvid i soveværelse fx. (5)
GEMAK (soveværelse, fx)
EM (mesterskaber) i GAK (vanvid)

Exam time again. I’ve tried to produce exam questions for my current algorithms design class themed after Blizzard’s collectible card game Hearthstone. For a variety of reasons I decided to abandon the idea for the exam, but the ideas are cute enough for a blog post. Here are the first three. The target audience are algorithms design students struggling with Chapters 1–8 of Kleinberg and Tardos’s Algorithms Design book (so: graph traversal, greedy, divide and conquer, dynamic programming, network flow, NP-hardness). Enjoy!

Hearthstone Basics

Each card in the game Hearthstone depicts a minion. Each minion has 3 values: Attack, Health and Cost, given as integers a, h, and c. Here’s a minion with Attack 3, Health 2, and Cost 4:

For the purpose of these exercises, these values are unbounded, positive integers. During the game, both players have a number of minions in play. In a turn of Heartstone, the player assigns his minions to fight enemy minions. Each minion gets to target a single enemy minion, initiating a fight between the two minions. When a minion with Attack A fights a minion with Health H, the other minion’s Health is reduced to max{0,H-A}. Note that both minions fight, and each deals damage to the other, regardless of who initiated the fight. Also note that an enemy minion can be involved in many fights each turn, when it is repeatedly targeted. When a minion’s Health is reduced to 0, it is removed from play.

For each of the problems below, state which algorithmic design technique should be used, or if the problem is NP-hard. Also give the best asymptotic worst-case running time.

Cleanup

You and ZombieMage02 both have the same number of minions in play. It is your turn. Can you take them all the enemy minions in one sweep?

Input:
The enemy minions (a₁,h₁),…,(a_n,h_n) ∈ N² and your minions (a₁′,h₁′),…,(a_n′,h_n′) ∈ N²

Output: “Yes,” if your minions can take out all enemy minions this turn. “No,” otherwise.

Tanks

TwoOrcsOneCup has two minions in play. Both completely overpowered and powerful enough to wipe out your hero when it becomes TwoOrcsOneCup’s turn again. You have n minions in play. Can you take out both minions this turn?

Input: The enemy minions (a₁,h₁),(a₂,h₂) ∈ N² and your minions (a₁′,h₁′),…,(a_n′,h_n′) ∈ N²

Output: “Yes” if your minions can take out both enemy minions this turn.

Charge!

Showdown time. Your hero has almost no Health left and OprahWindfury’s mage keeps pummeling you with fireballs. This has been going on for hours—time to end this! Luckily your hand is full of high-powered cards with Charge, which can attack immediately.
Get out as many of these guys as you can afford!

Input Your available mana K. The minions with Charge on your hand, (a₁,h₁,c₁),…,(a_n,h_n,c_n) ∈ N².

Output: The total number of Attack points you can play this round.

Cards generated using achievementgen.com

Foredrag om Turings virke ved forpremieren til filmen The Imitation Game i Grand Teatret, København, d. 22. januar 2015.

Foredraget omhandler de dele af Turings virke, som kun nævnes i forbifarten i filmen. Hovedvægten ligger på at forklare vigtigheden af Turings konceptuelle bidrag, nemlig idéen om «universalitet af beregning» i form af universalmaskinen – ofte kaldt den universelle turingmaskine.
Der er også lidt om kunstig intelligens og moderne biologi.

Videre læsning:

• Alan Turing: The Enigma af Andrew Hodges (1983).
• The Universal Computer: The Road from Leibniz to Turing af Martin David (2000).
  

This is the annotated solution to my A Song and Ice and Fire-themed cryptic crossword I Sent Letters About Cersei’s First Sexual Relationship.

Definitions are underlined, anagrams are starred, reversals are indicated by <.

Across

1 Heathen ironborn plundered plowed field. (7)
INFIDEL. I(ronborn)N FIELD*.

5 Behaviour of a cruel and terrifying person—I therefore left leaders of Sorrowful Men. (7)
OGREISM. (I ERGO)< S(orrowful) M(en).

9 Sellsword captain carried goods, having a change of heart towards early retirement. (5)
CAGGO, known as Corpsekiller, captain of the Windblown in A Dance of Dragons LX. CARGO (= carried goods) with central letter G changed to R(etirement). Not the best clue in the set.

10 Rev. Spooner escorted laggard to a guardsman sworn to House Lannister. (3,6)
RED LESTER, guardsman of Tywin Lannister, posted outside the Hand’s solar in A Storm of Swords LXXVII. Spoonerism of “led rester”. Arguably, the Spoonerism should be indicated by “According to Spooner” or something like that. The “a” is superfluous.

11 Short moments filled with endless lay for relatives. (6,4)
SECOND SONS, among the oldest of the free sellsword companies. SECONDS around SON(g).

12 Wants to sell daughter’s maidenhead and partially redeem maester. (4)
EMMA, old server at the Quill and Tankard tavern of Oldtown, mother of Rosey. Hidden in redeEM MAester. According to some schools, the definition ought to be “She wants to sell…”.

14 Ned heard two manoeuvres in despair. (11)
DOWNHEARTED. NEDHEARDTWO*.

17 Reward tenth sworn brother of the Night’s Watch. (6,5)
ENDREW TARTH, master-at-arms at Castle Black after Ser Alliser Thorne. REWARDTENTH*, with “sworn” (in the sense of “cursed” etc.) as the anagram indicator.

19 Leave out central promise to Targaryen leader. (4)
OMIT. prOMIse T(argaryen).

20 A few groats and pennies holding unit back before first ride for Ser Duncan at Ashford Meadow, say. (10)
CHALLENGER, which was the role of Ser Duncan in said tournament in The Hedge Knight. CHANGE around ELL< followed by R(ide).

23 Dwarf returned cup-shaped metal object to unknown artisan. (9)
IRONBELLY, master smith at King’s Landing charged with chain-construction by Lord Tyrion in A Clash of Kings XV. NORI (a dwarf in JRR Tolkien’s The Hobbit) reversed, followed by BELL and Y. I am very pleased with this clue: the unknown is well-hidden, the surface makes you think of an irrelevant situation (pointing towards the wrong dwarf and the wrong cup) at the purple wedding of A Storm of Swords.

24 Eyrie facing the French is situated in a sheltered position. (7)
NESTLES. NEST + LES.

25 Hedge knight’s coat of ice is surrounded by expression of surprise. (7)
LORIMER, known as the Belly, a fat hedge knight in the service of Leo Lefford, attended by Podrick Payne, see A Feast for Crows XIV. RIME in LOR

Down

1 I sent letters about Cersei’s first sexual relationship! (6)
INCEST. ISENT* about Cersei. Another clue I’m very happy with.

2 Initially festive, until Gwyneth and Cletus Yronwood’s banishment. (6)
FUCAGY. Acrostic in “F(estive)… Y(ronwood)”.

3 Return command to Eddard before soldiers become priests. (7,3)
DROWNED MEN, priests of the Ironborn. WORD< NED MEN. “Soldiers” for MEN is not really cryptic enough in my book.

4 Solar remodelled for knight of the Kingsguard. (5)
LORAS. SOLAR*.

5 Honor-clad, destroyed seat of a noble house in the Vale of Arryn. (3,6)
OLD ANCHOR, seat of House Melcolm . HONORCLAD*.

6 Noble house: A stag rampant. (4)
REED. DEER<.

7 At home, Tangletongue consumed close friend. (8)
INTIMATE (as a noun). IN TIM  ATE. Tim Tangletongue is a steward at Castle Black, defending the Wall in A Storm of Swords LXIX.

8 Sam mired in a mess, attending the Drowned God. (8)
MERMAIDS. SAMMIRED*. Again, some schools don’t like the grammar of the definition.

13 Atop Reek, he jerked Jaime’s junk. (10)
OATHKEEPER, Valyrian steel sword of Ser Jaime Lannister, discarded in A Storm of Swords LXXII by giving it to Brienne of Tarth. ATOPREEKHE*. Irresistible surface.

15 Fails to disclose how an area can be fortified? (9)
WITHHOLDS. An area can be fortified WITH HOLDS.

16 Maesters and the King’s Hand, for example, cover the face after short announcement. (8)
ADVISORS. AD VISORS

18 House Mallister’s heraldic beast, beheaded in the morning, catches sunlight. (6)
AGLEAM. (e)AGLE AM.

21 Staunch and kingly, after change of allegiance. (5)
LOYAL. ROYAL after changing directions (Left for Right).

22 Bard sounds talented. (4)
ABEL, bardic alter ego of Mance Rayder attending a feast in Winterfell. Homophone of ABLE.

Unclued

The unclued entries solve as PIETY, PRAYER, and DEVOTION, the three ships of the unfortunate Lord Sunglass seized by King Stannis for the attack on King’s Landing.

I’ve been quite busy writing up a survey of graph colouring algorithms. As an experiment, I’ve put up a draft of the manuscript on Bitbucket, including the source files.

The draft is available as a PDF document.
The sources can be inspected at the Bitbucket Git repository thusfeldt/graph-colouring-algorithms.

Even though the literature on graph colouring algorithms is vast, I was unable to find an earlier comprehensive survey. (In fact, the Wikipedia page Graph colouring, to which I have contributed quite a bit, is in pretty good shape.) Thus, I’ve found myself surveying results and techniques that are somewhat outside of my comfort zone, and made editorial choices about issues where I speak with little authority.

Thus, by making this draft available, I strongly invite comments of all kinds. Errors, miscalculations, sources of confusion, misunderstandings, criminal omissions of results or tacit assumptions, undue weight: Please tell me. Here or via email. If you’re really cool, use the issue tracker or fork the git repository, edit your change, and send me a pull request. (I dream of a distant future where all papers can be crowd-sourced and the original author just juggles diffs. I also dream of rolling pavements and flying cars, of course.)

I would especially like to hear comments from mathematicians and other researchers outside of theoretical computer science (what tacit assumptions have I forgotten to make explicit?), algorithms students at the beginning graduate level (is it understandable?), and graph colouring researchers (what favourite result of yours did I misunderstand or omit?).

The Grötzsch graph is the smallest graph without triangles that cannot be 3-coloured.

I’ve played around with various drawings of it and found the following, which I’m quite happy with:

It’s not the obvious layout; the articles at Mathworld and Wikipedia contain drawings that are more standard and arguably do a better job at visualising the structure of the Grötzsch graph. Another drawing, due to David Eppstein is at at Wikimedia commons.

“My” embedding is a projection on the plane of an embedding of the Grötzsch Graph on the unit sphere:

(I really need to make an animation of this.)

The central vertex of the 2D drawing sits at the top of the sphere; the pentagram-like group of 5 vertices sit slightly above the equator, and the last five vertices (placed no the outer rim in the 2D drawing) are on the southern hemisphere. It turns out that in this embedding, the unit vectors defined by these points are at internal angles of more than 120 degrees, so the embedding describes a vector 3-colouring in the sense of [David R. Karger, Rajeev Motwani, Madhu Sudan: Approximate Graph Coloring by Semidefinite Programming. J. ACM 45(2): 246-265 (1998)]. This shows that the Grötzsch graph (which is 4-chromatic) can be vector 3-coloured.

I find this quite neat.

I found the 3D embedding by actually running an semidefinite programming solver to find a solution to the vector colouring problem. The output of such a program is of course just a bunch of vectors (in 11 dimensions), but it turned out that the solver was friendly enough to only use the first 3 dimensions. After some headscratching and bumbling attempts at visualising the vectors in various mathematical software packages that I understand only feebly, I managed to make sense of the embedding so that I can now draw it neatly.

(I did a similar thing for the Chvátal graph, but I can’t make any sense of the resulting vector 3 colouring.)

I had an extremely active year 2012 in terms of popular science. To a large extent that is because it was Alan Turing’s centenary.

Here’s a summary of what I did:

1. The first event was in April 2012 as part of a yearly Danish science festival (forsk.dk). I give a talk on representations of Alan Turing in contemporary art, Alan Turing i samtidskunst, at the art school ignatius.dk in Copenhagen. Most of the material was based on a previous lecture from 2011 Alan Turing: Man as Machine lecture at Malmö Konsthall in connection with an exhibition of Danish artist Henrik Olesen.
2. In June, I was honoured to be invited by the good people in Bergen to give the opening lecture on occasion of Turing’s birthday in a lecture series arranged by Bergen University for the Turing centenary. Let us Calculate! – From Leibniz to Turing. The nice Turing film “Codebreaker” (turingfilm.com) was shown right before my talk, so I focussed on Alan Turing’s contribution to our intellectual history instead of the biographical material and Bletchley park. Other speakers in the series were Christos Papadimitriou, Kenneth W. Regan, and Luc Steels; illustrious company indeed!
3. The Bergen people managed to put a full-page article about Turing in the local paper, and I quickly stole their best idea: explain the idea behind the halting problem in terms of phone applications. This led to a quick blog entry: The Freeze App does not Exist.
4. A few days later, Danish radio broadcast a long montage (about 40 min) about Alan Turing based on long interviews with me and with Hans Hüttel (Aalborg University). Archived at Radio 24syv. I thought this came out really well.
5. Lund has a long tradition of weekly public science lectures, the “Technology and Science Circle”. I’m in the steering committee and we agreed to devote the fall to Turing, “Datorernas Darwin: Alan Turing 100 år”. This led to 10 public lectures with a total of 30 appearances (physics, CS, systems biology, gender studies, etc.). Pretty cool. I gave one myself, about the algorithmic lens on information curation (Pagerank, Filterbubble).
6. In December, Swedish radio broadcast Alan Turing ville bygga en hjärna. Another montage based on an interview with me. This, too, came out well. (Though I find my Swedish toe-curling.) Both radio appearances were very pleasant experiences and were produced by excellent, well-prepared journalists. Swedish Public Radio P1, Vetandes Värld. The interview itself was conducted in early Fall.
7. Just before year’s end, Danish science webzine videnskab.dk published my reviews of three books related to Turing.

At the very least, there were welcome incentives to read up on Turing. Collective thanks to everybody who turned up, tuned in, emailed, commented, or staid for a chat or beer afterwards.

What’s next? Leibniz year 2016?