I am delighted to be nominated for the EATCS Council.

My main focus in the EATCS’s flagship conference ICALP. I bring to the table some experience from interacting with the council as the General Chair of ICALP 2014 (in Copenhagen). I have also served on the ICALP PC, served as a keynote speaker, and received a Best Paper award.

My main ambition is to increase the quality of ICALP, and the main instrument would be to

recognise that the goals of ICALP and the goals of the EATCS are not always aligned.

In my experience, these misaligned goals lead to value conflicts that the EATCS Council has difficulties in confronting.

If elected to the council, I would like to investigate the possibilities to

give ICALP a Steering Committee.

Outside of ICALP-related matters, my main areas of interest are how the mathematical discipline of theoretical computer science can interact with its surroundings using a stance of  intellectual honesty, curiosity, and confidence. This context includes intellectually challenging questions from empirical considerations, the other sciences, industry, society, and the public—these questions inform my position on outreach and science communication.

Full list of nominees, brilliant and decent people all: http://eatcs.org/index.php/component/content/article/1-news/2534-nomination-of-candidates-for-the-eatcs-council-election-2017

Vote at http://eatcs.org before October 10, 2017.

The long awaited update for Secret Sartre, the deconstructive social deduction game of postmodernism on campus is finally here! Reality has managed to unlock Jordan Peterson and Bret Weinstein as fully playable characters.

To use them, remove any of Darwin, Dennett, Dawkins, Russel, or Chomsky (but not Curie, who is token) from the original Science decks, and add the Peterson and Weinstein cards.

You can now recreate a faculty meeting at Evergreen State College in the safe confines of your home!

The Orthogonal Vectors problem is given two sets of d-dimensional 01-vectors to decide if there is an orthogonal pair: two vectors, one from each set, with zero dot product. Obviously, the problem can be decided in time O(n²d) by trying all pairs.

Here’s the a complete reduction from the Orthogonal Vectors problem to evaluation of Perl regular expressions.

chomp($_ = <STDIN>);
s/0/\\d/g;
tr/1 /0|/;
print !!(<STDIN> =~ /$_/)

This is fully functional Perl code. Save the script as ov.pl and run it. The process expects two lines on standard input, each describing a set of vectors (as 01-sequences, separated by space). The script returns “1” if and only if the two sets contain an orthogonal pair of vectors.

>perl ov.pl
1000 0100 0010 1001
1110 1101 1111 1100^D
1

This construction shows that matching an n-character string against an n-character regular expression requires quadratic time under the Strong Exponential Time Hypothesis. So, the obvious quadratic-time dynamic programming algorithm for regex matching is in some sense optimal.

As to the Perl code, the first line eats the trailing newline of standard input. The next two lines contain the main part of the reduction, replacing “0” by “\d” (any digit), “1” by “0”, and “ ” by “|” to build a regex. The last line of the code attempts to match the second line from standard input to the regex. Oh, the double exclamation points? They are a perlism to enforce Boolean context, so that the output is “1” (true) exactly if the regex matches. The reduction is so obviously linear that it hurts.

Tell me this isn’t cute.

The core of the construction underlies the celebrated recent results of Backus and Indyk, Bringmann and Künnemann, and Abboud et al. that show similar bounds for various string edit distances. This particular example is just very concrete version of the NFA-acceptance reduction that appears on Karl Bringmann and Sebastian Krinninger’s slides for an MPI course on Complexity Theory of Polynomial-Time Problems (Summer 2016), there attributed to Russell Impagliazzo. I find that reduction very teachable. The step from NFA acceptance to a concrete Perl script is minimal, but makes it even more concrete (executable code!).

• Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams: Tight Hardness Results for LCS and Other Sequence Similarity Measures. IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pp. 59-78.
• Arturs Backurs, Piotr Indyk: Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false). Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015. pp. 51-58.
• Karl Bringmann, Marvin Künnemann: Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015. pp. 79-97.

Explained using only the ten hundred words people use most often.

What is a good way of figuring out a problem?

First: it must be so simple and clear that we can explain it to a computer. (Or a Human. That’s not so different.)

Second: it must be fast enough so that it is done before lunch. (Or before the sun burns out. that’s not so different.)

Since people started using computers, lots of people get paid to think about ways to figure out problems. that’s what i’m doing.  Today we understand that some problems are hard, and others are pretty easy.

I want to help us becoming better at talking about what makes a problem hard.

So far, most of the people who think about this stuff look only at the size of the problem.

But some of us feel that you can think more clearly about problems when you not only look at their size, but at some other things as well. Sometimes, this way of thinking even helps us to come up with better ways to figure out problems!

Two other people and myself have come up with a way to finish the game for all five-letter words — as long as you are forced to visit only around ten words. Or maybe twenty. So we found out that the number of words all-in-all was not so important. instead, what makes the problem hard is how many you are forced to visit. We can even find the shortest such path!

Read more here: Another man, myself, and a woman, ‘Shortest path through stuff you didn’t choose’, place where people who care about this kind of question meet each year (the name sounds like a soft drink),  year twenty-hundred and ten and two.

Appendix

The above is a summary of a poster I made for a research sharing day at ITU.

hard-problems-poster (draft) in pdf (designed for printing in A0)

I loathe poster sessions, partly because of the unclear concept of who the audience is, and mainly because the social interaction exhausts me.

But to motivate me I gave myself the challenge to design a poster in the style of  Randall Munroe’s Up-Goer Five: Use only the 1000 most used words of English, be concrete, whimsical, accessible, and informative. Munroe has since made a whole book in this style: Thing Explainer, which is quite lovely.

I did the whole thing in Omnigraffle Professional 5, which is hard pressed to handle a document with almost 6000 elements. Drawings are free-hand in Keynote (basically because I don’t have a good way of digitising my free-hand drawings — I am a competent artist, but Munroe’s style is sufficiently simple.) The font is xkcd-font from the iPython project, licensed under CCANC 3.0.

As a starting point I used a 2012 paper of Andreas, Nina, and myself that presents an efficient FPT-algorithm for shortest Steiner cycle. That’s as accessible a result as I have. The big drawing at the end shows a path from TEARS to SMILE passing through seven intervening emotions (WORRY, SPITE, etc.) This is a highly nontrivial result and a cute story that I’m insanely happy with, I haven’t found a good way of expressing this fact in only 1000 words.

Andreas Björklund, Thore Husfeldt, and Nina Taslaman, Shortest cycle through specified elements, Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms (SODA 2012),  January 17–19, 2012, Kyoto, Japan, SIAM, pages 1747-1753. [PDF].

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