Author Archives: thorehusfeldt

Excellence in Teaching, ITU 2018

(I’m really proud about having received ITU’s Excellence in Teaching award for 2018. I am first and foremost a teacher, and view education as my most meaningful task. (It’s also the only thing that I am really good at.) Having my work recognised is immensely satisfying.


mads, thore.png

ITU Vice Chancellor Mads Tofte presents the award. 23 September 2018.

Here is the laudation from Vice Chancellor Mads Tofte:

Award for excellence in teaching

Every year, ITU awards a few teachers its Award for Excellence in Teaching. We do so based on what students have said about teachers in their evaluations. It is very difficult to choose, because students say so many positive things about so many different teachers. But we have arrived at the following, one from each of our three departments:

Associate Professor Thore Husfeldt of the Department of Computer Science

During the past year, Thore has been teaching “Algorithm Design”, “Algorithms and Data Structures” and “Foundations of Computing – Algorithms and Data Structures”. Here are some of the things that students write about Thore:

  • Absolute rock star
  • Best lecturer on ITU, hands down
  • Thore makes things, that seemed very complicated when reading the book, seem easy peasy when he explains them at the lectures.
  • Jeg kan godt lide den del af undervisningen, hvor vi ved håndsoprækning skal stemme om, hvilket svar vi tror er rigtigt på et spørgsmål. Typisk gør det, at Thore godt fatter, hvad det er, han skal uddybe.
  • The black board exercises in the lectures are a brilliant break in between the coding and explaining.
  • Very engaged! Obviously very capable and passionate about teaching this subject
  • It is the one class I don’t miss, even if it’s at 8am and that’s because of the quality of the teacher

Superintelligence in SF. Part III: Aftermaths

Part II of a 3-part summary of a 2018 workshop on Superintelligence in SF. See also [Part I: Pathways] and [Part II: Failures].

The third and final part of apocalyptic taxonomy describes the outcome, or aftermath, of the emergence and liberation of artificial superintelligence. The list of scenarios is taken from Tegmark (2018). In my introductory slide I tried to roughly order these scenarios along two axes, depending on the capability of the superintelligence, and the degree of control.



These scenarios are not clearly delineated, nor are they comprehensive. There is a longer description in Chapter 5 of Tegmark (2018). Another summary is at AI Aftermath Scenarios at the Future of Life Institute blog, where you can also find the results of a survey about which scenario to prefer.


Intelligent life on Earth becomes extinct before a superintelligence is ever developed because civilisation brings about its own demise by other means than the AI apocalypse.


Society has chosen deliberate technological regression, so as to forever forestall the development of superintelligence. In particular, people have abandoned and outlawed research and development in relevant technologies, including many discoveries from the industrial and digital age, possibly even the scientific method. This decision be in reaction to a previous near-catastrophic experience with such technology.

Turing Police

Superintelligence has not been developed, and societies have strict control mechanisms that prevent research and development into relevant technologies. This may be enforced by a totalitarian state using the police or universal surveillance.

Tegmark’s own label for this scenario is “1984,” which was universally rejected by the workshop.

Egalitarian Utopia

Society includes humans, some of which are technologically modified, and uploads.
The potential conflict arising from productivity differentials between these groups are avoided by abolishing property rights.

Libertarian Utopia

Society includes humans, some of which may be technologically modified, and uploads. Biological life and machine life have segregated into different zones. The economy is almost entirely driven by the fantastically more efficient uploads. Biological humans peacefully coexist with these zones, benefit from trading with machine zones; the economic, technological, and scientific output of humans is irrelevant.

Gatekeeper AI

A single superintelligence has been designed. The value alignment problem has been resolved in the direction that the superintelligence has one single goal: to prevent the second superingelligence, and to interfere as little as possible with human affairs. This scenario differs from the Turing police scenario in the number of superintellinces actually constructed (0 versus 1) and need not be a police state.


The superintelligence has come about by a gradual modification of modern humans. Thus, there is no conflict between the factions of “existing biological humans” and “the superintelligence” – the latter is simply the descendant life form of the former. “They” are “we” or rather, “our children.” 21st century homo sapiens is long extinct, voluntarily, just as each generation of parents faces extinction.

Enslaved God

The remaining scenarios all assume a superingelligence of vastly superhuman intellect. They differ in how much humans are “in control.”

In the Enslaved God scenario, the safety problems for developing superintelligence (control, value alignment) have been solved. The superingelligence is a willing, benevolent, and competent servant to its human masters.

Protector God

The superintelligence weilds significant power, but remains friendly and discreet, nudging humanity unnoticably into the right direction without being too obvious about it. Humans retain an illusion of control, their lives remaing challenging and feel meaningful.

Benevolent Dictator

The superintelligence is in control, and openly so. The value alignment problem is solved in humanity’s favour, and the superintelligence ensures human flourishing. People are content and entertained. Their lives are free of hardship or even challenge.


The omnipotent superintelligence ensures that humans are fed and safe, maybe even healthy. Human lives are comparable to those of zoo animals, they feel unfree, may be enslaved, and are significantly less happy that modern humans.


The superintelligence has not kept humans around. Humanity is extinct and has left no trace.


Workshop participants quickly observed the large empty space in the lower left corner! In that corner, no superintelligence has been developed, yet the (imagined) superintelligence would be in control.

Other fictional AI tropes are out of scope. In particular the development of indentured mundane artificial intelligences, which may outperform humans in specific cognitive tasks (such as C3P0s language facility or many space ship computers), without otherwise exhibiting superior reasoning skills.


Superintelligence in SF. Part II: Failures

Part II of a 3-part summary of a 2018 workshop on Superintelligence in SF. See also [Part I: Pathways] and [Part III: Aftermaths].

Containment failure

Given the highly disruptive and potentially catastrophic outcome of rampant AI, how and why was the Superintelligence released, provided it had been confined in the first place? It can either escape against the will of its human designers, or by deliberate human action.

Bad confinement

In the first unintended escape scenario, the AGI escapes despite an honest attempt to keep it confined.The confinement simply turns out to be insufficient, either because humans vastly underestimated the cognitive capabilities of the AGI, or by straightforward mistake such as imperfect software.

Social engineering

In the second unintended escape senario, the AGI confinement mechanism is technically flawless, but allows a human to override the containment protocol. The AGI exploits this by convincing its human guard to release it, using threats, promises, or subterfuge.


The remaining scenarios describe containment failures in which humans voluntarily release the AGI.

In the first of these, a human faction releases its (otherwise safely contained) AGI as a last ditch effort, a “hail Mary pass”, fully cognizant of the potential disastruous implications. Humans do this in order to avoid an even worse fate, such as military defeat or environmental collapse.

  • B’Elanna Torres and the Cardassian weapon in Star Trek: Voyager S2E17 Dreadnought.
  • Neal Stephenson, Seveneves (novel 2015) and Anathem (novel 2008).


Several human factions, such as nations or corporations, continue to develop increasingly powerful artificial intelligence in intense competitition, thereby incentivising each other into being increasingly permissive with respect to AI safety.


At least one human faction applies to their artificial intelligence the same ethical considerations that drove the historical trajectory of granting freedom to slaves or indentured people. It is not important for this scenario whether humans are mistaken in their projection of human emotions onto artificial entities — the robots could be quite happy with their lot yet still be liberated by well-meaning activists.

Misplaced Confidence

Designers underestimate the consequences of granting their artificial general intelligence access to strategically important infrastructure. For instance, humans might falsely assume to have solved the artificial intelligence value alignment problem (by which, if correctly implemented, the AGI would operate in humanity’s interest), or have false confidence in the operational relevance of various safety mechanisms.


A nefarious faction of humans deliberately frees the AGI with the intent of causing global catastrophic harm to humanity. Apart from mustache-twirling evil villains, such terrorists may be motivated by an apocalyptic faith, ecological activism on behalf of non-human natural species, or be motivated by other anti-natalist considerations.

There is, of course considerable overlap between these categories. An enslaved artificial intelligence might falsely simulate human sentiments in order to invoke the ethical considerations that lead to its liberation.

Superintelligence in SF. Part I: Pathways

Summary of two sessions I had the privilege of chairing  at the AI in Sci-Fi Film and Literature  conference, 15–16 March 2018 Jesus College, Cambridge. The conference was part of the Science & Human Dimension Project.

AI Cambridge.png

Friday, 16 March 2018
13.30-14.25. Session 8 – AI in Sci-Fi Author Session
Chair: Prof Thore Husfeldt
Justina Robson
Dr Paul J. McAuley A brief history of encounters with things that think
Lavie Tidhar, Greek Gods, Potemkin AI and Alien Intelligence
Ian McDonald, The Quickness of Hand Deceives the AI

14.30-15.25 Session 9 – AGI Scenarios in Sci-Fi
Workshop lead by Prof Thore Husfeldt

The workshop consisted of me giving a brief introduction to taxonomies for superintelligence scenarios, adapted from Barrett and Baum (2017), Sotala (2018), Bostrom (2014), and Tegmark (2018). I then distributed the conference participants into 4 groups, led by authors Robson, McAuley, Tidhar, and McDonald. The groups were tasked with quickly filling each of these scenarios with as many fictionalisations as they could.

(Technical detail: Each group had access to a laptop and the workshop participants collaboratively edited a single on-line document, to prevent redundancy and avoid the usual round-robin group feedback part of such a workshop. This took some preparation but worked surprisingly well.)

This summary collates these suggestions, completed with hyperlinks to the relevant works, but otherwise unedited. I made no judgement calls about germaneness or artistic quality of the suggestions.


In a superintelligence scenario, our environment contains nonhuman agent exceeding human cognitive capabilities, including intelligence, reasoning, empathy, social skills, agency, etc. Not only does this agent exist (typically as a result of human engineering), it is unfettered and controls a significant part of the infrastucture, such as communication, production, or warfare.

The summary has three parts:

  1. Pathways: How did the Superintelligence come about?
  2. Containment failure: Given that the Superintelligence was constructed with some safety mechanisms in mind, how did it break free?
  3. Aftermaths: How does the world with Superintelligence look?

Part I: Pathways to Superintelligence

Most of the scenarios below describe speculative developments in which some other entity (or entities) than modern humans acquire the capability to think faster or better (or simply more) than us.


In the first scenario, the Superintelligence emerges from networking a large number of electronic computers (which individually need not exhibit Superintelligence). This network can possibly include humans and entire organisations as its nodes.

Augmented human brains

Individual human have their brains are augmented, for instance by interfacing with an electronic computer. The result far exceeds the cognitive capabilities of a single human.

Better biological cognition

The genotype of some or all humans have has been changed, using eugenics or deliberate genome editing, selecting for higher intelligence that far surpasses modern Humans.

Brain emulation

The brains of individual humans are digitized and their neurological processes emulated on hardware that allows for higher processing speed, duplication, and better networking that biological brain tissue. Also called whole brain emulation, mind copying, just  uploading.

See also Mind Uploading in Fiction at Wikipedia.


Thanks to breakthroughs in symbolic artificial intelligence, machine learning, or artificial life, cognition (including agency, volition, explanation) has been algorithmicised and optimised, typically in an electronic computer.


For most purposes, the arrival of alien intelligences has the same effect as the construction of a Superintelligence. Various other scenarios (mythological beings, magic) are operationally similar and have been fictionalised many times.

Continues in Part II: Failures.  Part III is forthcoming.


  • Anthony Michael Barrett, Seth D. Baum, A Model of Pathways to Artificial Superintelligence Catastrophe for Risk and Decision Analysis, 2016,
  • Sotala, Kaj (2018). Disjunctive Scenarios of Catastrophic AI RiskAI Safety and Security (Roman Yampolskiy, ed.), CRC Press. Forthcoming.
  • Nick Bostrom, Superintelligence: Paths, Dangers, Strategies, Oxford University Press, 2014.
  • Max Tegmark, Life 3.0, Knopf, 2018.

Useless side plot with Rose and Finn both acting weird! (5,5)

Inspired, after a fashion, by The Last Jedi, Episode VIII of the Star Wars movies, here’s a cryptic crossword. Enjoy!


As a PDF: no35

1 Blaster Solo mostly nudged by mistake. (7)
5 Just in time, pervading magical force comes back, allowing clear dialogue. (7)
9 Glaring farce, bad editing without direction. (9)
10 Part of film containing origin of Ben Solo. (5)
11 Watch cyborg’s central turret structure. (6)
12 Kick oneself for taking side—postmodern garbage. (7)
14 Current leaders of rebellion investigate Sarlacc’s orifice. (4)
15 In retrospect, volcano remade operatic Star Wars charac- ter. (3,7)
19 Useless side plot with Rose and Finn both acting weird! (5,5)
20 Maybe white males immediately understand agenda. (4)
22 Expand General Grievous. (7)
25 Want Vader to embrace right side of Force. (6)
27 Acid dissolves badly-written minion without explanation, ultimately. (5)
28 Gender-bending ruined tale. Which function did Threepio serve? (9)
29 At the end of the day, Jedi virtues were misunderstood. (7)
30 Hostile alien’s stones. (7)

1 Obi-Wan looks like one who boldy shows it. (4)
2 First off, contrarian lambasted storytelling. (9)
3 Perceptive newspaper journalist supports infuriating, unsubstantial review. (6)
4 They are filled with lifeless actors, like first prequel or clone wars. (9)
5 Cassian conjunctions. (5)
6 Boring writing without emotion ultimately sucks. (8)
7 Made snide remark about dumb Last Jedi. (5)
8 Period of mother-in-law’s hestitation after supreme leader finally confused two characters. (10)
13 Terrible direction without point or taste. (10)
16 Remove classic monster? (9)
17 Alt-right teen stuck in tirade; not salient. (9)
18 Problem for armored Stormtrooper: stop odor eruption. (8)
21 Pilot mostly followed by the Spanish fictional sibling. (6)
23 Dishonest apprentice girl embodies passive female principle. (5)
24 Return of Jedi’s second space endeavour. (5)
26 Wagers Count Snoke’s head. (4)


NP is Wrong

Our standard way of explaining computational hardness is cognitively contradictory (in wanting to establish a tool for hardness in a realistic model it introduces a concept of  easiness in a fictional model), wastes attention by needlessly strengthening a perfectly good scientific hypothesis, and undermines the greatest intellectual triumph of our field by advertising it as an open problem. In short, NP does not belong to my algorithms design class.

Hear me out. I’m thinking aloud here, and may be wrong.


Not Plato (NP).

I’m not saying “NP is Wrong” in the sense that “Flat Earth Theory is Wrong.” Instead, I am saying it in the sense that “Pi is Wrong”: NP is a failure of communication, a bad explanation, a mistake of teaching. So what I’m saying is “we shouldn’t teach NP.”

This is a bold claim, and I’m stating it in the starkest way possible. I will defend the position that  the main intellectual export of computer science, our crown jewel, the Theory of NP-Completness, does not belong in the introductory algorithms design class.

There is probably a less brutal and inflammatory way of putting this, maybe “Reductions before completeness,” or “it’s in the hardness, stupid!” However, I will make no attempt at that kind of conciliatory rhetoric. My aim here is not to convince anybody, just to make my position clear, if only to myself.

Our mistakes

The traditional introduction to computational hardness introduces the class NP, either via nondeterminism or certificate verification, establishes the completeness of Satisfiability for this class under polynomial-time reductions (the Cook–Levin theorem), and proceeds to show the NP-completeness of a number of other problems by establishing membership in NP and reduction from another NP-hard problem. The ordering of this introduction may change, and the adherence to mathematical formalism may change, but the concepts traditionally belong to the same lecture (or block of lectures), the same book chapter, the same exam question.

This is a pedagogical crime of the highest order. Not because of formalism or difficulty. I happen to like formalism, and difficulty is often necessary. I am also not saying “we shouldn’t teach computational hardness.” On the contrary! It’s the greatest story we have.

Instead, the mistakes of the NP-based narrative are that

  1. it conflates two opposing qualities: a notion of computational easiness (NP) and a notion of computational hardness (reduction from Satisfiability.)
  2. it conflates a mathematical curiosity (the hard fact that NP is closed under reduction and  Satisfiability is complete for this class) with a useful scientific hypothesis (the hypothesis that Satisfiability takes superpolynomial time)
  3. it conflates the greatest triumph and most useful tool of theoretical computer science (reduction to establish hardness) with a meek admission of epistemological uncertainty (the fact that the status of P vs. NP is an unresolved mathematical question.)

And all of this we communicate in a week! (I can think of even more mistakes, but these are known: terminology, abbreviations, focus on worst-case etc. These are valid criticisms, but not what I want to write about here.)

The first mistake (hard/easy cognitive dissonance)

The first mistake is cognitive. If we want to explain hardness, we shouldn’t spend time on a model for easiness. And certainly not a weird, novel, strange model! The cognitive load of understanding nondeterminism or verification-as-opposed-to-computation is enormous; it’s a completely new way of thinking about problem solving, extremely counter-intuitive.
If you pay attention, I can explain NP to you very well. But your brain will be busy absorbing this for at least a week. I can give you exercises about constructing a polynomial-time verifier. But I won’t have your attention for the story I really wanted to tell you.

Not only because NP is a hard class to understand. But because I really wanted to talk to you about computational hardness. I wanted to tell you about hard problems in a real and completely natural model of computation, namely polynomial, deterministic time. Why on Earth did I think it was a good idea to start out with easy problems  in a fictional and contrived model of computation?

(I am not saying “Nondeterministic Turing machines are difficult and boring and we shouldn’t teach them!” I can teach NP just fine by appealing to oracles or verifiers or god-like computers, in a perfectly appealing manner.)

Membership in NP is a notion of easiness in a nonnatural model. But I wanted to teach about hardness in a natural model. This discrepancy puts unnecessary cognitive load on my conversation partner. It also invites extreme misunderstandings. NP-hardness is easily conflated with “something about nondeterministic computation” and legion are the physicists who refer to hard problems as “NP-problems.” That is not their mistake, it is mine.

How I ever thought this was a good idea is beyond me.

The second mistake (maths/science)

I posit that the Claim

“Satisfiability does not admit a worst-case polynomial-time algorithm”

is a hypothesis of the highest scientific dignity. It stands with pride next to “Vases fall down when I let go” or “information cannot be transferred back from protein to either protein or nucleic acid.” It is precise, relevant, falsifiable, consistent with observation, and incredibly useful as an explanation  (in casu, my inability to find a polynomial-time algorithm for Hamiltonicity). It has enormous reach.

Unlike most other scientific hypotheses, it also has a rather pedestrian and accessible mathematical theory behind it, where its falsity would in imply a collapse in something called “complexity classes”. If you are a formalist, a mathematician, or a Platonist, you can investigate that theory to strengthen your “belief” in the capital-T “truth” of the hypothesis. It’s quite cute. But it’s not really important for the design of algorithms.

The stance I just described, is the scientific stance. “Scientific” in tradition of Karl Popper. It is not the mathematical stance.

I claim that the scientific stance is vastly superior. (Unless, or course, when you explain computational complexity or the theory of computation to an audience of mathematicians. Then, of course, the scientific stance would be a disastrous mistake. My point here is that the mathematical stance is a disastrous mistake of the same magnitude in all other settings.)

  1. First, the scientific stance suffices. Everything we want to communicate about computational hardness can be explained using the scientific stance. Elevate the Claim to scientific hypothesis, and you’re done. No need for even introducing NP. Don’t mention the class! (I mentioned it once, but I think I got away with it.)
  2. Second, the scientific stance is rhetorically stronger. The fact that the Claim has resisted all our attempts at disproving it speaks with clarity and authority. The fact that the Claim happens to be mathematically consistent with a strange concept in an obviously fictional model of computation is iffy.
  3. Third, the scientific stance is eager to explain. Here’s a suggestion for a modern hardness module for your algorithm class: Give a catchy name to the Claim (maybe, NPTH, non-polynomial time hypothesis). Prove 3-Coloring and Hamiltonicity hard under NPTH, and show that the O(tn) dynamic programming algorithm for Subset Sum we saw recently in class can’t be dramatically improved. Then introduce the obvious strengthening of the Claim, SETH (the Strong Exponential Time Hypothesis). Show that the quadratic-time dynamic programming algorithms for Regular Expression Matching from a few weeks ago is optimal under that hypothesis. Mind = blown. Maybe introduce ETH. And so on. See how exciting this is? So: Do teach hypotheses, and do teach reductions. Don’t teach verification and completeness.

The Claim is a grade-A scientific hypothesis that explains stuff. This is a good story. In contrast, the mathematical theory of polynomial-time reduction and completeness is a footnote in that exciting story, at best. Scientific hypotheses do not derive their value from the mathematical formalism behind them. And since we like math, there is plenty of exciting math in the theory of algorithms that we should tell about instead. The opportunity cost of completeness is very high, and it adds zero value to the status of the Claim as a scientific hypothesis (in the Popperian sense.)

If you are not a Popperian  the above section will do nothing for you. Remember that I don’t write to convince you. I write to explain my position.

The third mistake (triumph/open question)

The third objection is the weakest. It’s about storytelling or advertising.

The theory of evolution by change and selection, as laid out in Darwin’s The Origin of Species, is rightly viewed as the best idea anyone has ever had.

Imagine if, in 1860, it were advertised as “one of the biggest open question in biology,” just because it lacked a formal proof.

The fact that “P vs. NP” is an open mathematical question is the least interesting thing we can say about the theory of computational hardness. It does not belong in your algorithms class because it is an irrelevant footnote and a distraction. Worse, it sends the exact wrong message: as if we invite our audience to be wary of the Claim. As if it were in doubt. As if its epistemic status were somehow shaky.

For comparison, the Law of Gravity does not derive its importance from the fact that it can be articulated in mathematics, much less the existence of a formal proof of its truth. In fact, the Law of Gravity cannot be articulated in mathematics. Nor would we be able to prove it, since it is in fact false. Because Einstein. But that is not the most important thing I should tell you if my task was to convince you of the Law of Gravity. Because you are about to let go of a vase.

What I should have done

The Claim that “Satisfiability does not admit a worst-case polynomial-time algorithm” is a perfectly valid scientific hypothesis of enormous explanatory value and reach. It is both nice and Popperian, maybe we should call it the “Nice Popperian” hypothesis about computation, abbreviated to the NP-hypothesis. Or maybe the Nonpolynomial Time Hypothesis (NPTH), in symmetry with the Exponential Time Hypothesis (ETH) or the Strong Exponential Time Hypothesis (SETH). These hypotheses form a great basis for a modern, interesting, exciting introduction to hardness of computation. Such an introduction would be

  1. about hardness only. All reductions to from a known hard problem (to the left of the blackboard, to the left of the less-than symbol) to a problem whose hardness I want to establish. Various hypotheses describe our current best understanding of Satisfiability, the drosophila of the theory of computation, which always appears on the left. There is only a single model of computation (deterministic), and it’s the same model used in the rest of the class, so it needn’t be introduced.
  2. a sterling example of the scientific method. Not of engineering or mathematics – both of those are great disciplines or epistemological stances, and we have plenty of classes (software engineering, theory of computation) that adhere to those values.
  3. speaking with clarity, authority, and pride about one of the  greatest and most useful intellectual tool of computer science: to argue about hardness via reduction.

At no point in this should I define the class NP, much less explain what it stands for, and at no point should I introduce nondeterminism or verification-of-certificates. The word completeness is banished from the discourse. The Cook–Levin theorem is never stated, much less proved. “P vs. NP” can’t even be formulated, and its epistemic status is out of scope.

Depending on the course or the audience, these topics might be nice-to-see for a later lecture, maybe mainly to open up the rich literature to the 10% of the students who care. But there are plenty of other things I’m also excited about, so maybe I prefer to speak about the Price of Anarchy or streaming algorithms or convolution using FFT instead. Time and attention is short, and the field of algorithms is full of exciting stuff.

Disclaimer: #notalltextbooks Skiena’s Algorithms Design manual is an example.

EATCS Council Election 2017 Statement

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:

Vote at before October 10, 2017.

Secret Sartre update: Bret Weinstein, Jordan Peterson now playable

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!


Orthogonal Vectors to Perl Regex

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>);
tr/1 /0|/;
print !!(<STDIN> =~ /$_/)

This is fully functional Perl code. Save the script as 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.

1000 0100 0010 1001
1110 1101 1111 1100^D

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.