Talk given at the GoCAS workshop Existential Risk to Humanity, Gothenburg, 7 Sep 2017.
Video recording of presentation at YouTube
Slides:
Talk given at the GoCAS workshop Existential Risk to Humanity, Gothenburg, 7 Sep 2017.
Video recording of presentation at YouTube
Slides:
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(n2d) 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!).
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.
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].
Föredrag den 20 september 2016 i Sällskapet Heimdall, Malmö.
Föredrag den 28 februari 2017, arrangerad av Lund Sustainable Engineers and Code@LTH, 12.15–13.00, LTH, Lunds Universitet, E-huset, E:A (eller E:B).
Sammanfattning: Nej.
Under föredraget hoppas jag att bl a kunna förklara hur olika former för artificiell intelligens fungerar – hur bygger man en schackdator och hur en pratbot, hur fungerar maskininlärning i motsättning till god, gammaldags symbolisk AI, hur fungerar maskinöversättning baserad på stora datamängder, vad är ett artificiellt neuronnät, etc.
Är några av dessa tekniker en bit på vägen till artificiell generell intelligens? Och hur ser en värld med artificiell superintelligens ut? Kan och bör vi skydda os? Hur?
Lite AI-historia blir det nog också, så både Ada Lovelace, Jon von Neumann och Alan Turing kommer at nämnas.
Perspektivet är algoritmteoretisk och kunskapsoptimistiskt.
Referenser:
Løsning til min danske kryptokryds nr. 32
Definitioner er understregede.
* angiver omkastning, < angiver omvending.
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*.
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 a2 + b2 + c2 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)
(Trigger warning: this is satire intended to lampoon the two cultures currently dividing academic politics. It is also a fully playable social deduction game in the tradition of Werewolf, Mafia, The Resistance, and Avalon. In fact, Secret Sartre is a straighforward re-theming of the upcoming game Secret Hitler by Max Temkin (2016). Re-theming is a euphemism for theft, but no infringement of intellectual property is intended. Since this satire is about postmodernsim, intent is all that matters. The print-and-play edition of the original, including the rules, is available on-line; Secret Hitler is an extremely well-designed game with brilliant mechanics and a splendid theme.)
In Secret Sartre, the faculty members of an unnamed university department battle for ideological supremacy. A fragile alliance of upstanding rationalists, logical positivists, empiricists, liberal humanists, scientists and other fetishizers of the Enlightenment must work together to stem the rising tide of postmodernism. Watch out, though – there are closet postmodernists among you, and someone is Secret Sartre.
At the beginning of the game, each player is secretly assigned to one of three roles: Science, Postmodernism, or Sartre. Sartre plays for the postmodern team, and the postmodernists know who Sartre is, but most of the time Sartre does not know who his fellow postmodernists are. The Scientists are far out on the autism spectrum and don’t know who anyone is.
The scientists win by enacting five rational policies or having Sartre fired. The postmodernists win by enacting six postmodernist policies, or if Sartre is elected Head of Studies late in the game. As postmodernist policies are enacted, the Department Chair gains new powers. Even scientists may find themselves tempted to enact postmodernist policies that help them control the table and fire their enemies. At the same time, the postmodernists conspire to construct a shared narrative space in which the social construction of their allegiance becomes the perceived Truth. Language is a weapon!
Give each player a pair of cards, one identity and one allegiance. Both of these cards are secret and may never be shown to any other player, except (i) if Sartre is fired he immediately reveals it, ending the game in victory for the scientists, or (ii) if the Department Head investigates the loyality of a faculty member enacting the Diversity Training postmodern policy.
The composition of faculty is given by the following table:
Players | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|
Science | 3 | 4 | 4 | 5 | 5 | 6 |
Po-mo | 1+S | 1+S | 2+S | 2+S | 3+S | 3+S |
Here are the faculty members’s identities. Except for Sartre, none of the names have any bearing on the game.
You also need an allegience card for each player. This is the cards that you show when you’re under ideological investigation from the Department Chair. You need 4 po-mo cards (for Derrida, Foucault, Rorty, and Sartre), and 6 science cards (for the rest).
Put each pair of cards in a separate envelope, shuffle, and deal.
Each player looks at their identities, making sure that nobody else sees it. The player with the highest academic degree in real life is the first Department Chair candidate. If several players hold the same degree, spend some time discussing the merits of the degree-granting institutions, possibly using a recent ranking of universities. If this does not resolve the issue, another player with an MBA can break the tie using the player’s h-index.
The Department Chair candidate now enacts the following ritual. For 5–10 players:
Everybody close your eyes. Postmodernist and Sartre, open your eyes and acknowledge each other. [Take a long pause.] Everyone close your eyes. Everyone can open your eyes. If anyone is confused or something went wrong, please tell the group now.
For 7–10 players:
Everybody close your eyes and extend your hand into a fist in front of you. Sartre, keep your eyes closed but put your thumb out into a thumbs-up gesture. All postmodernists who are not Sartre, open your eyes and acknowledge each other. Postmodernists, take note of who has extended their thumb – that player is Sartre. Think about the relationship between the signifier and the signified. [Take a long pause] Everyone close your eyes and put your hands down. Everyone can open your eyes. If anyone is confused or something went wrong, please tell the group now.
Secret Sartre is played in rounds. Each round has an Election of new faculty leardership, a Faculty Meeting to enact a new policy, and an Executive Action where the Department Chair exercises his or her power.
Each round, faculty members elect a new Department Chair and Head of Studies. These are shown as two placards (cut them out and fold as shown.)
If more than 50% of the group votes yes, the candidates become Department Chair and Head of Studies, respectively. If three or more postmodernist policies have already been enacted, ask the new Head of Studies if he is Sartre; if he is Sartre, he must reveal himself and the game immediately ends in a postmodernist victory. Otherwise, proceed to the Faculty Meeting.
If the vote is a tie, or if most players vote no, the Department Chair placard moves clockwise to the next player and the election tracker is advanced by one election. (The election tracker is at the bottom of the Science policy board, see below. Use a coin or something similar.)
If faculty rejects three proposals in a row, the student representatives take matters into their own hands. Student policies are completely random: Reveal the policy on top of the Policy Draw Deck and enact it. Any power granted by this policy is ignored, but all players become eligible for Head of Studies for the next Election. Reset the Election Tracker after a policy is enacted by the populace or a government is successfully elected.
You need 6 rational policy cards and 11 postmodernist policy cards. These are shuffled and placed face-down as the Policy deck.
The Department Chair draws the top three cards from the Policy deck,
looks at them in secret, and discards one Policy face down into the discard pile. The Chair passes the remaining two cards to the Head of Studies who looks in secret, discards one Policy card face down, and enacts the remaining Policy card by placing it face up on the corresponding track.
This is the track for the scientist’s policies:
None of these policies has any effects on game play or real life, their role is only to mantain the status quo of male white dominance of Academia (includig Marie Curie as a token woman). The scientists win after enacting the fifth rational policy.
Depending on the number of players, one of three boards is used for postmodernist policies:
Postmodern policies may have effects on game play, see below.
The sanctity of the faculty meeting is of the utmost importance! Once it begins with the Head drawing three Policy cards, faculty members stay silent until a policy has been enacted. Discarded policy cards may never be revealed; you must rely on the word of faculty leadership, who are allowed to lie.
If there are fewer than three cards remaining in the Policy deck at the end of a legislative session, shuffle them with the discard pile to create a new Policy deck. Unused policies should never be revealed, nor may they simply placed on top of the new Policy deck. If the government enacts a rational policy or a postmodernist policy that grants no power, begin a new round with a new Election. If the government enacts a postmodernist policy that grants power to the Department Chair, proceed to the Executive Action.
Whether by fate or choice, the faculty meeting may have adopted a postmodernist policy, moving the department away from excessive reductionism and granting the Deparmental Chair new powers to enforce collectivist fidelity. The Departmental Chair must enact the power granted in this round. Look at the Postmodernism policy track to determine which power, if any, has been granted.