Category Archives: Uncategorized

Will Code for Drinks @ Scrollbar 2018

Homemade poster for the event

I am foremost a teacher, and I care a lot about introductory programming, computational thinking, algorithms, and the social environment of a university.

As an experiment in “social coding,” we implemented an event called “Will Code for Drinks @ Scrollbar” in the Friday bar at IT University of Copenhagen on 23 November 2018. The basic idea is to get beginning programmers—this includes 1st semester students and professors—together for a few hours, solve some well-defined programming exercises, and get a drink for each solved exercise.

Preparation

The idea was born over a couple of lunches with colleagues, and thanks to the enthusiasm of Martin Aumüller and Troels Lund it quickly developed momentum.

The platform we used for this is Kattis (open.kattis.com), which is a well-working system developed for programming competitions. Kattis comes with thousands of extremely well-done exercises, a reliable server with an accessible web interface, and very simple procedures for registering individuals, forming teams, and hosting contests.

Preparation included:

  1. Establishing rapport with the ITU Friday bar—a student-run organisation that hosts a social event every Friday afternoon during the semester. They loved the idea, and we were able to find a free date where no other ScrollBar event or theme (Halloween) was already planned, and no other ITU event (Board Game night!) was scheduled elsewhere in the house by one of the many other social committees.
  2. Learning Kattis and solving dozens of exercises there in order to find a selection of the event. The idea was that students with very little programming experience were supposed to at least solve one exercise, possibly with help, during the event. The selection we ended up with were Baby Bites, Spavanac, the lovely Trik, and the somewhat harder Bank Queue. We figured that 3 drinks are enough for anybody, and wanted a more challenging problem to keep everybody engaged during the event.
  3. Spreading the word among first-year programming teachers and their students. During the weeks up the event, our enthusiasm infected several students, who registered on Kattis and started grinding in preparation.
  4. Decisions, decisions… should the event be called “Will Code for Beer” instead? Drink or drinks? How competitive should we make it?
  5. Creating a visual identity. My original plan was to use a lot of images of various people holding cardboard “Will Code for Drinks” signs. In the end, it was too much work (after talking to the communications department about GDPR), and I cobbled together a clean visual identity on my computer in a couple of minutes. Another reason to reject the hobo-theme is that it possibly repels students who are concerned about appearances.
  6. Find some way to pay for the resulting bar tab, and that will be acceptable to the Accounting and Finances section.
  7. Design and order caps so that assistants (Martin, Troels, and myself) would be visible during the contest. Alas, the caps were not delivered on time.
An early experiment in developing a visual identity for the event. In the end, I rejected this direction, despite the great resonance among students and colleagues, for purely aesthetic reasons.

During the event

The event was “just” a contest on the open Kattis server  https://open.kattis.com/contests/f4ktq9

The moment the contest started at 15:30, we had most of the students in the same room adjacent to the bar, so we could help with Kattis registration, logging in, reading from standard input, etc. After that, participants slowly moved into ScrollBar and the ITU Atrium. We kept ourselves visible and available, and helped with programming and problem solving.

After

I spent a few hours writing emails to individual groups that I had talked to during the contest, explaining other approaches to specific tasks. Then I sent a brief thank-you note to all participants that I could identify and invited feed-back and suggestions for improvement. This was quite boring, I had to identify partipants  who had registered under their own name on Kattis and had a name I could uniquely find in the ITU student roster.

Evaluation

This was supposed to be a test run, and I had hoped for 5 teams of students. In reality, slightly over 50 teams registered, with 130 participants. Stunning success!

Will Code for Drinks @ ScrollBar 2018 in full activity. Photo by Troels Lund.

Of the participants I was able to identify, 48 are first-semester students. These were the intended target group. More that half of the students are from the educations hosted by the Computer Science department, but all of ITU’s student populations were present. 45 teams solved at least one problem, 35 teams solved three. 10 teams solved all four problems; this includes the teams consisting of faculty members and Ph.D. students. Phew!

In the end, the “damage” was 183 beers, 80 cocktails, and 8 soft drinks. In total, students solved 132 programming exercises in 2.5 hours, and fun was had. As a teacher, I couldn’t be happier.

In just a few weeks, ITU is now the second-largest and second-ranked Danish uni on Kattis. Aarhus is still way ahead.

Future

I would love to make this event even more social and less competitive. An idea that came up during the contest was to have the scoreboard ranked by “most recent solve” rather than “number of solves”. That way, every team gets to be at the top at least once. Removing the scoreboard entirely is another option, but that removes the shared digital forum – in effect, all the teams would exist in their own little bubble.

The best idea we’ve come up with in this vein is to couple the teams with music playlists. Then the current leader (i.e., the team that most recently solved a problem) would decide which music is played in the bar. “Will Code for Drinks and Music” or “Will Code for Drinks and Rick Roll” or something. To make this work, we need a more advanced registration system, and we’d need to scrape the standings off the Kattis server.  All doable.

Another improvement would be to have our own, ITU- or ScrollBar-branded problems instead of relying on (often well-known) problems from the Kattis pool. We could switch to another system than Kattis (or build our own) but that is a lot of work, and there is intrinsic value in incentivising students to register on Kattis.

No matter the form, we will certainly do this again in Spring 2019!

A Glimpse of Algorithmic Fairness

Workshop presentation at Ethical, legal & social consequences of artificial intelligence, Network for Artificial Intelligence and Machine Learning at Lund University (AIML@LU), Lund University, 22 November 2018.

Abstract

Several recent results in algorithms address questions of algorithmic fairness — how can fairness be axiomatised and measured, to which extent can bias in data capture or decision making be identified and remedied, how can different conceptualisations of fairness be aligned, which ones can be simultaneously satisfied. What can be done, and what are the logical and computational limits?

I give a very brief overview of some recent results in the field aimed at an audience assumed to be innocent of algorithmic thinking. The presentation includes a brief description of the location of the field algorithms among other disciplines, and the mindset of algorithmic or computational thinking. The talk includes pretty shapes that move about in order to communicate some intuition about the results, but is otherwise unapologetic about the fact that the arguments are ultimately formal and precise, which is important for addressing fairness in a transparent and accountable fashion.

References

Toon Calders, Sicco Verwer: Three naive Bayes approaches for discrimination-free classification. Data Min. Knowl. Discov. 21(2): 277-292 (2010). [PDF at author web page]

Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. [arXiv 1703.00056]

Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, Richard S. Zemel:
Fairness through awareness. Innovations in Theoretical Computer Science 2012: 214-226. [arXiv 1104:3913]

Michael Feldman, Sorelle A. Friedler, John Moeller, Carlos Scheidegger, Suresh Venkatasubramanian: Certifying and Removing Disparate Impact. Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, August 10-13, 2015. [arXiv 1412.3756]

Sorelle A. Friedler, Carlos Scheidegger, Suresh Venkatasubramanian: On the (im)possibility of fairness. [arXiv:1609.07236]

Úrsula Hébert-Johnson, Michael P. Kim, Omer Reingold, Guy N. Rothblum: Multicalibration: Calibration for the (Computationally-Identifiable) Masses. Int. Conf. Machine Learning 2018: 1944-1953. [Proceedings PDF]

Jon M. Kleinberg, Sendhil Mullainathan, Manish Raghavan: Inherent Trade-Offs in the Fair Determination of Risk Scores. Innovations in Theoretical Computer Science 2017: 43:1-43:23. [arXiv 1609:05807]


(The image at the top, the title slide of my presentation, shows a masterpiece of the early Renaissance, Fra Angelico’s The Last Judgement (ca. 1430), illustrating a binary classifier with perfect data access and unlimited computational power.)

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.

 

Tegmark.001

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.


Collapse

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.

Reversion

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.

Descendants

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.

Zookeeper

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.

Conquerors

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


Oz

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.

 

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.

440px-Karl_Popper

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: 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.

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!

weinson