Solution to STOC 2022 cryptic crossword

Original crossword


Across clues

  • Spoke first at STOC, with handouts. (4)
    SAID = S(TOC) + AID (handouts are a visual aid)
  • Laugh at Romanian jail without pa[r]king for Ford, say. (8)
    HARRISON (Ford, an actor) = HA + R + PRISON – P (= parking)
  • Danes maybe cycling for cake. (7)
    ECLAIR = CLAIRE (Danes, an actress) rotated = “cycling”. Difficult clue.
  • Squared dodecahedron contains root. (4)
    EDDO (a plant). Contained in … ED DO…
  • With competence, like Niels Henrik? (4)
    ABLY, wordplay on “like [mathematician Niels Henrik] Abel”.
  • Trouble sounds like beer. (3)
    AIL (vb.), homophone of ALE.
  • L[a]nsky impales most of suricate with tip of yari. (5)
    MEYER (Lansky, a mobster) = ME(Y)ER[CAT]
  • Taster confused desserts. (6)
    TREATS = TASTER*
  • Programmer is a father. (3)
    ADA (Lovelace) = A + DA (= father)
  • Some alternating state. (3)
    ANY = A (as in complexity class AC) + N.Y.
  • Limaye without an almond, say. (3)
    NUT = NUTAN – AN
  • Bullet point keeps her in France. (6)
    PELLET = PT (= point, abbrev.) around ELLE (her, Fr.)
  • Assholes insert Landau symbol into abstracts after second review. (7)
    EGOISTS = E (2nd letter in REVIEW) + G[O]ISTS
  • Logic from the Horn of Africa. (2)
    SO = second order logic, also abbreviation of Somalia
  • Like, with probability 1. (2)
    AS = like = almost surely
  • Complex zero first encountered by lady friend. (7)
    OEDIPAL (a type of complex) = O + E + DI + PAL
  • Partly hesitant at ternary bit. (6)
    TATTER, hidden word.
  • Supporting structure turns semi-liquid. (3)
    GEL = LEG backward (= turned)
  • Everything Arthur left to end of protocol. (3)
    ALL = A[rthur] + L[eft] + [protoco]L
  • Unbounded fan-in polylogarithmic depth circuit model is fake. (3)
    ACT = AC (complexity class) + T (a Ford model)
  • Maybe Tracey’s luxury car runs out of [p]olynomial time. (6)
    ULLMAN (an actress) = PULLMAN – P
  • Pin[k] dress you ordered last Friday initially returned. (5)
    FLOYD (a band), backwards acrostic (“initially”, “returned”)
  • Relationship uncovered travel document. (2-1)
    IS-A (a UML relation) = [v]ISA
  • Be certain about last Pfaffian orientation. (4)
    BENT = BE[N]T
  • Detect conference cost size. (4)
    FEEL = FEE + L
  • Matching for horses? (6)
    STABLE (a type of matching, and where horses stay)
  • Collect information about first woman embracing the state. (8)
    RETRIEVE = RE (= about) + T(he) + RI (= Rhode Island, a US state) + EVE
  • Central to better AI data storage technology. (4)
    RAID, hidden in “…r AI d…”

Down clues

  • Safer testable codes? (4, 4)
    SEAT BELT = TESTABLE* (code is an iffy anagram indicator). Better clue in hindsight would have been “Locally testable codes are a buzzword. (3)” for ECO (hidden).
  • Maybe Arthur without Merlin is even worse … (5)
    ILLER = (Arthur) MILLER – M
  • definition of time than deterministic Arthur–Yaroslav. (3)
    DAY = D + A +Y (a complexity class abbreviations)
  • Cover us about first sign of integrality gap. (6)
    HIATUS = HAT + US around I(ntegrality)
  • Publish, but not ultimately sure about polynomial-time recurrence. (7)
    RELAPSE = RELEASE – (sur)E holding P
  • 49 subsets the setter handles. (6)
    IDEALS = stable subsets = I + DEALS
  • Food at indiscrete algorithms conference held around Yale’s entrance. (4)
    SOYA = SODA – D (SODA without discrete) + Y
  • Revealed no deep confusion. (6)
    OPENED = NODEEP*
  • Not having an arbitrary number of children. (4)
    NARY = N-ARY, double definition
  • In Related Work section, over-inflate scientific contribution of Rabin in data structure. (4)
    BRAG = R (Rabin abbreviated as in RSA) inside BAG
  • Iceland exists. (2)
    IS, double definition
  • Cuckoo hashing incurs five seconds. (3)
    ANI = second letters of “hAshing iNcurs fIve”
  • Function of what is owed, I hear. (3)
    DET = homophone of “debt”.
  • Cut off measure of computer performance, not taking sides. (3)
    LOP = [F]LOP[S]
  • Two sigmas above the mean, or about ten delta. (8)
    TALENTED = TENDELTA* (“about” is the anagram indicator)
  • Coattail at breakfast? (3)
    OAT, tail of COAT, a breakfast cereal.
  • Twisted polygon in tessellation supporting functors. (7)
    TORTILE = TOR (functor) above TILE (a polygon in a tessellation).
  • Tree parent has two left edges. (6)
    MALLEE = MA + L + L (left, twice) + E + E (edge set, twice)
  • Temporary visitor betrays topless arrangement. (6)
    STAYER = [B]ETRAYS*
  • Trigonometric function is pretty dry. (3)
    SEC, double definition
  • Denounce operator in vector analysis and put it away. (6)
    DELETE = DEL + ATE (vb., past tense)
  • 49 litres of sick. (3)
    ILL = IL (roman numerals for 49) + L
  • Turing machine’s second network. (4)
    ALAN = A (second letter in MACHINE) + LAN
  • Academic degree supports unlimited games for simple minds in the US. (5)
    AMEBA (US spelling of AMOEBA) = [G]AME[S] + BA
  • Open access journal rejected final proof in distance estimate. (4)
    AFAR = AJAR – J + F (last letter of PROOF).
  • Conceal often sample space. (4)
    LOFT, sample of “…L OFT…”
  • Objectively, we are American. (2)
    US = objective form of “we”
  • It negates where you drink. (3)
    BAR, double definition, the bar us used to negate a variable

Special instructions

The letters missing from 4 of the clues, indicated by […] above, are K A R P, a homophone of CARP (“sounds like nitpicking”). The answers to those clues are HARRISON, MEYER, ULLMAN, and FLOYD. The six members of the first STOC programme committee were Harrison, Meyer, Ullman, Floyd, Karp, and Hartmanis. The answer to the entire puzzle is therefore HARTMANIS, additionally indicated as “confused with H(ungarian) MARTIANS” = HMARTIANS*.

Assholes insert Landau symbol into abstracts after second review (7)

Themed cryptic crossword I compiled (over two fun evenings) for the STOC 2022 conference. Lots of short words, to make it super-friendly.

Special instructions. Four of six people that form a group related to our meeting appear in the grid, clued for their namesakes. Alas, each of these clues is missing a letter. This sound like nit-picking, but the letters form the name of the fifth person. The sixth person of the group, not to be confused with the Hungarian “Martians,” is the puzzle answer.

Across
1. Spoke first at STOC, with handouts. (4)
4. Laugh at Romanian jail without paking for Ford, say. (8)
10. Danes maybe cycling for cake. (7)
11. Squared dodecahedron contains root. (4)
12. With competence, like Niels Henrik? (4)
14. Trouble sounds like beer. (3)
16. Lnsky impales most of suricate with tip of yari. (5)
17. Taster confused desserts. (6)
19. Programmer is a father. (3)
21. Some alternating state. (3)
22. Limaye without an almond, say. (3)
23. Bullet point keeps her in France. (6)
26. Assholes insert Landau symbol into abstracts after second review. (7)
29. Logic from the Horn of Africa. (2)
31. Like, with probability 1. (2)
34. Complex zero first encountered by lady friend. (7)
38. Partly hesitant at ternary bit. (6)
39. Supporting structure turns semi-liquid. (3)
41. Everything Arthur left to end of protocol. (3)
43. Unbounded fan-in polylogarithmic depth circuit model is fake. (3)
44. Maybe Tracey’s luxury car runs out of olynomial time. (6)
45. Pin dress you ordered last Friday initially returned. (5)
46. Relationship uncovered travel document. (2-1)
47. Be certain about last Pfaffian orientation. (4)
48. Detect conference cost size. (3)
49. Matching for horses? (6)
50. Collect information about first woman embracing the state. (8)
51. Central to better AI data storage technology. (4) 

Down
1. Safer testable codes? (4, 4)
2. Maybe Arthur without Merlin is even worse … (5)
3. … definition of time than deterministic Arthur–Yaroslav. (3)
4. Cover us about first sign of integrality gap. (6)
5. Publish, but not ultimately sure about polynomial-time recurrence. (7)
6. 49 subsets the setter handles. (6)
7. Food at indiscrete algorithms conference held around Yale’s entrance. (4)
8. Revealed no deep confusion. (6)
9. Not having an arbitrary number of children. (4)
13. In Related Work section, over-inflate scientific contribution of Rabin in data structure. (4)
15. Iceland exists. (2)
18. Cuckoo hashing incurs five seconds. (3)
20. Function of what is owed, I hear. (3)
24. Cut off measure of computer performance, not taking sides. (3)
25. Two sigmas above the mean, or about ten delta. (8)
27. Coattail at breakfast? (3)
28. Twisted polygon in tessellation supporting functors. (7)
30. Tree parent has two left edges. (6)
32. Temporary visitor betrays topless arrangement. (6)
33. Trigonometric function is pretty dry. (3)
35. Denounce operator in vector analysis and put it away. (6)
36. 49 litres of sick. (3)
37. Turing machine’s second network. (4)
40. Academic degree supports unlimited games for simple minds in the US. (5)
41. Open access journal rejected final proof in distance estimate. (4)
42. Conceal often sample space. (4)
44. Objectively, we are American. (2)
47. It negates where you drink. (3) 

Digitisation in Higher Education

Summary of my keynote talk on 4 November 2021 at the eponymous Norwegian national conference Nasjonal konferanse: Digitalisering i høyere utdanning 2021, hosted at Bergen University and organised with the Norwegian Directorate for Higher Education and Skills. The summary is somewhat disjointed and includes some of the slides.

1. Digitisation in Higher Education (summary)

The first part of the talk is about the potential use of digital technology to improve learning outcome in specific contexts. When I gave the talk I showed a bunch of ephemeral examples that I had used myself, or which seemed otherwise cool, instructive, useful, or exciting in late 2021. These examples won’s stand the test of time, so I won’t repeat them here. A well-known and old example that everybody knows is the language learning application Duolingo.

Benefits include immediate feedback, scalability, transparency of assessment, accessibility, spaced repetition, and individual pacing or tracking of material. Common to the contexts where digital technology seems to be largely beneficial are

  1. learning outcomes can be validly tracked and assessed,
  2. it makes sense to design a clear progression or scaffolding through the curriculum,
  3. relevant feedback can be provided at scale and automated.

More problematic are assistive technologies, often using machine learning or other forms of decision-making processes collectively known as artificial intelligence, that ensure surface conformity of written material. These have clear benefits for authoring but also equally clear negative consequences for assessment. Modern word processors allow the production of professional-looking prose and automate surface markers of quality (layout, grammar, style, phrasing, vocabulary), which traditionally were used as proxies for content in assessment of learning outcomes; online natural language processing services like Google Translate invalidate traditional forms of language proficiency assessment based on written material. In 2021, a beta version of the programming environment GitHub Copilot automatically solves programming exercises from the task description. The same tools that perform plagiarism checks can also plagiarise very well.

So there is stuff that becomes somewhat easier by digitisation (transmission of knowledge), and where we have many ideas for what to do, and stuff that becomes much harder (valid assessment), and where we have very little idea about what to do.

A third theme is stuff that does become easier, but maybe oughtn’t. This is found under the umbrella education data mining – predicting student performance, retention, success, satisfaction, achievement, or dropout rate from harvested data such as age, gender, demographics, religion, socio-economic status, parents’ occupation, interaction with application platform, login frequency, discussion board entries, spelling mistakes, dental records, social media posts, photos, and everything else. The promise of this field—and in particular, machine-learned predictions based on polygenetic scores—is enormous; and there is an emerging literature of success stories in the educational literature. I strongly dislike this trend, but that’s just, like, my opinion.

This summaries the first part, with the foci

  1. what works?
  2. what fails?
  3. what should we not primarily evaluate along the works/fails axis?

There are of course a ton of other problems, which I expanded on in the full talk:

  1. digitisation favours certain disciplines and traditions of instruction
  2. it systematically undermines the authority of educators
  3. the intellectual property rights issues are ill understood and seem to have very little attention from educational administrators
  4. routine student surveillance

2. What the Hard Part Is

I’m pretty confident about part 1 (digitisation for education), and return to a confident stance in part 3 (education for digitisation). In contrast, part 2 is characterised by epistemic humility. It’s my best current shot at what makes the whole topic hard do think about.

Over the years I have learned a lot about “How to think about digitisation” from the DemTech project at IT University of Copenhagen, which looks at digitisation of democratic processes, in particular election technology. “How to digitise elections” is a priori an easier problem than “How to digitise higher education”, because the former is much more well-defined. Still, many of the same insights and phenomena apply.

These problems include a (largely unhelpful) eagerness of various stakeholders to digitise for the sake of it. An acerbic term for this is “magical IT gravy”:

[…] politicians who still think that you can just drench a problem domain in “magical IT gravy” and then things become perfect.

Poul Henning Kamp, 2021

Briefly put, if you digitise domain X then you will digitise your description of X. (A fancy word for this is reification.) Since (for various reasons, including lack of understanding, deliberate misrepresentation, social biases, status, and political loyalty) the description of X is seldom very good, digitisation reform typically deforms X. Since digitisation is seen as adaptive within organisations, it bypasses the converstations that such transformation would normally merit.

Example: Electronic Elections

My ITU colleague Carsten Schürmann showed me this insightful taxonomy:

Hierarchy of values related to digitisation. Adapted from Carsten Schürmann.

Let’s use voting as a concrete example to talk us through this. At the bottom is Functionality: voting is to increase a counter by 1 every time somebody casts a vote. This is easy to implement, and easy to digitise; any programmer can write an electronic voting system. Above that is Security: making sure the voting process is free (i.e., secret, private, non-coerced, universally accessible, etc.) This involves much harder computer science, for instance, cryptography. You need to have a pretty solid computer science background to get this right. Above that tier is Validity: how do we ensure that the numbers spat out by the election computer have anything to do with what people actually voted? This is even harder, in particular without allowing coercion by violating secrecy. (Google “vote selling” if you’ve never thought about this.) Finally, after thinking long and hard about all these issues (which by now include social choice theory, logic, several branches of mathematics) you arrive at what elections are actually about: Trust. The overarching goal of voting it so convince the loser that they lost. And this requires that the process is transparent.

Applications at the Functionality stage are easy (if you’re a competent programmer), they are mono-disciplinary, and the happen by themselves because geeks just want to see cool stuff work. The higher up you go in the hierarchy, the more disciplines need to be included, so the requirement for inter-disciplinary work increases. An organisational super-structure (such as a university) is needed to incentivise and coördinate the things at the top.

What is Higher Education About?

To translate the above model from voting to Higher Education, the Functionality part is transmission of knowledge: all the cool and exciting ideas I mentioned in part 1. Security corresponds to preserving privacy of learners throughout their educational history; this already conflicts with both educational tracking (e.g., for individualised progression) and reporting (e.g., for credentials). The first steps, probably in the wrong direction, can be seen by universities in Europe reacting to the European GDPR legislation, which already takes up a significant amount of organisational resources. This layer is correctly seen as annoying, depressing, time-consuming and boring, but still outshines in enthusiasm the next layer: Validity. The very features of information technology that make it incredibly useful for transmission of knowledge (speed, universality, faithful copying, depersonalised expression, accessibility, bandwidth) make it incredibly difficult to perform valid assessments, in particular in high-stakes, large-scale exams of universal skills. This is because digital technology makes it it is very easy to misrepresent authorship and originality. (Think of playing the violin, drawing, programming, parallel parking, mathematics, translating between languages—which digital artefacts would constitute proof of proficiency?)

Yet this is all still manageable, and some universities or educational systems may even choose to get this right. For instance, I think I know that to do.

But the really Hard Problem of Digitsation is the one at the top of the hierarchy: What is higher education even about?

I don’t know the answer to that.

Here are some possible answers. Maybe they’re all correct:

What is higher education about?

The narrative I tell myself is very much the first one, the capital-E Enlightenment story of knowledge transmission, critical thinking, and a marketplace of ideas. We can call this the Faculty view, or Researcher’s, or Teacher’s. The Economist’s view in the 2nd row is, thankfully, largely consistent with that; it’s no mystery that the labour market in knowledge economies pays a premium for knowledgeable graduates—the two incentives are somewhat aligned. (It does, however, make a big difference in how important transmission of knowledge and validity of assessment are in relation to each other. Again, “why not both?” and there is no conflict. Critical thinking versus conformity is a much more difficult tension to resolve.)

Still, the question whether Higher Education creates human capital (such as knowledge) or selects for human capital is (and remains) very hard to talk about among educators. Very few teachers, including myself, are comfortable with the idea that education favours the ability to happily and unquestioningly perform meaningless, boring, and difficult tasks exactly like the boss/teacher wanted (but was unable/unwilling to specify honestly or clearly) in dysfunctional group, and that it selects for these traits by attrition. Mind you, it may very well be true, but let’s not digitise that. (I strongly recommend Bryan Caplan’s excellent, though-provoking, and disturbing book The Case Against Education to everybody in education.)

The two other perspectives on what Higher Education is about (Experiental, Social, both are Student perspectives) are much more difficult to align with the others. Students-as-consumers-of-an-experience (“University is Live Role Playing”) and students-as-social-primates (“University is a Meet Market”) have very different utility functions than both Faculty and Economists.

The point is: if we digitise the phenomenon of Higher Education, we need to understand what it’s about. (Or maybe what we want it to be about.) Currently, Higher Education seems to do a passable job of honouring all four explanations. I guess my position is largely consistent with Chesterton’s Fence:

In the matter of reforming things, as distinct from deforming them, there is one plain and simple principle; a principle which will probably be called a paradox. There exists in such a case a certain institution or law; let us say, for the sake of simplicity, a fence or gate erected across a road. The more modern type of reformer goes gaily up to it and says, “I don’t see the use of this; let us clear it away.” To which the more intelligent type of reformer will do well to answer: “If you don’t see the use of it, I certainly won’t let you clear it away. Go away and think. Then, when you can come back and tell me that you do see the use of it, I may allow you to destroy it.”

G.K. Chesterton, The Thing (1929)
Typical slate fencing on the Talyllyn Railway, Wales, Wikimedia Commons, Public Domain.

Even if we (as educators and educational managers) were to understand what education is about, and even if we were agree on good ideas for how to proceed, none of us lives in a world where good decisions are just made. We have to communicate with stakeholders who are themselves beholden to other stakeholders, and need to understand that these individuals live in a complicated social or organisational space where they are evaluated on their individual, institutional, or ideological loyalty. Not on the quality of their decisions.

We must expect most organisations, including most universities, to make decisions about digitisation in higher education that are based on much more important factors (to the stakeholders) than “whether it works”. Given the choice between trusting the advice of a starry-eyed snake-oil salesman (or, in our case, a magical IT gravy salesman) and a reasonable, competent, experienced, responsible, and careful teacher, most responsible organisations will choose the former.(!) The feedback loops in education are simply too long to incentivise any other behaviour.

3. Educating for Digitisation

The last part of the talk—about how to prepare higher education for digitisation—is really short. Because (I believe) I know what to do. I consider it a solved problem.

Here is the list of things to do:

  1. Do teach basic programming.

That’s it.

Basic programming is teachable, it is mostly learnable by the higher education target demographic, is easily diagnosed at scale, works extremely well with digitisation-as-a-tool, is extremely useful now (in 2021), applies to many domains, will likely be even more useful in future, and in more domains, is highly compatible with labour market demands, and an enabling tool in all academic disciplines.

If you’re on board with this, my best advice for anyone with the ambition to teach basic programming is to adopt the following curriculum:

  1. Basic programming
  2. Nothing else

Point 2 is really important. In particular, my advice is to not add contents like applications, history of computing, ethics, societal aspects, reflection, software design, project management, machine learning, app development, human–computer interaction, etc. Mind you, these topics are extremely interesting, and I love many of them dearly. (And they should all be taught!) But unless you are a much better teacher than me, you will not be able to make the basic programming part work.

That’s it. The full talk had better flow, included some hands-on demonstrations of cool applications, and had more jokes. I am really grateful to the organisers for giving me the chance to think somewhat coherently about these issues, and had a bunch of very fruitful and illuminating conversations with colleagues both before and after the talk. I learned a lot.

Algoritmer og informationssøgning

Presentation on 1 November 2021 at the annual meeting of the Danish Gymnasiernes, Akademiernes og Erhvervsskolernes Biblioteksforening, GAEB in Vejle, Denmark.

I had the pleasure of giving a series of lectures on algorithms for information search on the internet to the association of Danish librarians. This is a highly educated crowd with a lot of background knowledge, so we could fast-forward through some of the basic stuff.

I am, however, quite happy with the historic overview slide that I created for this occasion:

Here’s an English translation:

ObjectiveSubjectiveSocial
1991199820042009
What do we expect from the search engine?SearchingRankingRankingRecommendation
What’s searching about?Which information exists?What has high quality?What is relevant for me?What ought I consume?
FokusFind informationFind informationFind informationMaintain my status, prevent or curate information
Core technology to be explainedCrawlers, keyword search, categoriesReference network topologyImplicit user profiles, nearest neighbour search, cookies Like, retweet
Example companyYahooGoogleAcxiomTwitter, Facebook
Source of profitAdvertisingUser dataAttention, interaction
Worry narrativePrivacy, filter bubblesMisinformation, tribalism, bias
Rough overview of the historical development of information search on the internet


Particularly cute is the row about “what is to be explained”. I’ve given talks on “how searching on the internet works” regularly since the 90s. and it’s interesting that the content and focus of what people care about and what people worry about (for various interpretations of “people”) changes so much.

  1. Here is the let 2000s version. How google works (in Danish). Really nice production values. I still have hair. Google is about network topology, finding stuff, and the quality measure is objectively defined by network topology and the Pagerank algorithm.
  2. In 2011, I was instrumental in placing the filter bubble narrative in Danish and Swedish media (Weekendavisen, Svenska dagbladet.) Suddenly it’s about subjective information targeting. I gave a lot of popular science talks about filter bubble. The algorithmic aspect is mainly about clustering.
  3. Today, most attention is about curation and manipulation, and the algorithmic aspect is different again.

I briefly spoke about digital education (digital dannelse), social media, and desinformation, but it’s complicated. A good part of this was informed by Hugo Mercier’s Not Born Yesterday and Jonathan Rauch’s The Constitution of Knowledge, which (I think) get this right.

The bulk of the presentation was based on somewhat tailored versions of my current Algorithms, explained talk, and an introduction to various notions of group fairness in algorithmic fairness, which can be found elsewhere in slightly different form.

There was a lot of room for audience interaction, which was really satisfying.

Surveillance paternalism

At a conference in Norway last week I learned new word coined by Tore Burheim, IT Director at Bergen University: overvåkningsomsorg. It’s a variation of Shoshana Zuboff’s brilliant word, overvåkningskapitalism, surveillance capitalism.

There is no perfect translation into English: omsorg is care, so the direct translation would be surveillance care, but that doesn’t quite work. Health care is “taking care of health”. Surveillance care would be “taking care of surveillance”. That’s not what is meant. Overvåkningsomsorg is the use of surveillance for ostensibly benevolent reaons, it is surveillance-for-care: A Huxleyan or Benthamian society where the system puts you under surveillance because it cares for you. Where Zuboff’s dystopia is easy to dislike (who likes surveillance? who actually likes capitalism?), overvåkningsomsorg is a delicious oxymoron.

I propose surveillance paternalism as the English translation, even though it’s not perfect. (“Paternalism” is not as warm as “care”.) Surveillance benevolence? “The age of benevolent surveillance”?) Danish overvågningsomsorg and Swedish övervakningsomsorg, are easy. For German, I propose Überwachungsfürsorge or maybe even Überwachungsbarmherzigkeit or something like Wohlfahrtsüberwachung.

Anyway, great word and great book title. Somebody should write this.

EATCS Council 2021 Election Statement

I am delighted to be nominated for the EATCS Council, on which I have served for a full term now.

ICALP

Looking back at my election statement from 2017, it is dominated by my ambition to increase the quality of ICALP, primarily by giving ICALP a steering committee.

I am happy that I can just write DONE next to this action point, see https://eatcs.org/index.php/committees. The ICALP steering committee turned out to be a complete success. I am extremely proud of what we’ve done with ICALP, including reacting very quickly to the COVID pandemic in 2019–2020. Mostly the success is due to the incredibly competent and pleasant people working inside the committee (ably headed by Anca Muscholl), and the amazing atmosphere that continues to permeate the entire TCS community.

Publication models

I worry about the publication and review model in the sciences, including in TCS, and have spent a lot of time involved in the advisory board of TheoretiCS, tirelessly headed by Thomas Schwentick. TheoretiCS will be an open access journal of very high quality covering all of TCS; having the journal tightly integrated into the community is a core value, and I serve as the representative of ICALP.

This has been very long process that I am extremely excited about, and I’m proud of what we’ve done so far.

TCS and the sciences

My 2017 election statement includes a passage about “ how the mathematical discipline of theoretical computer science can interact with its surroundings”.

This remains a central question for me, but a much harder one than helping to build steering committees or journals. I had the honour of serving as chair of the Swedish Research Council’s panel for (all of) computer science in 2019, 2020, and 2021, which has solidified by understanding of both CS and the role of TCS inside CS.

Core principles

I am a signatory of the open letter to CACM about core principles of scientific inquiry and stand by the values elucidated therein. I am cognisant of the fact that academia, including TCS, are divided on this issue (see the excellent rebuttal of our position by David Karger), and want to make my position clear as part of this election statement.

False Friends in Your Algorithms Course

Your first algorithms course is not easy.

The words are not the hardest part, but from years of teaching this material we have learned that words do sometimes invite enormous misunderstandings. You can be led down a garden path by a fancy word that you learned, only to discover that it means something else this week.

Luckily, the terminological issue is relatively easy to remedy by just writing it down and raising awareness. Here are some of the false friends I am aware of. (Do contact me with more examples, in particular ones that actually confused you.)

stack

A stack is a specific abstract data type, see Stack (abstract data type). When we say “stack” in an algorithms course, we almost always mean the data type.

However, the word “stack” is also a specific data structure in the runtime system of an active computer programme, see Call stack, also called execution stack, program stack, control stack, run-time stack, or machine stack, and is often shortened to just “the stack”.

When we talk about recursion and its implementation in our course, some people may say “the stack,” rather than “the call stack” or some more unambigous term. For instance, you may overhear “in your graph exploration programme, you wouldn’t have run out of stack space if you had used a stack.” The first stack is the recursion stack, the other isn’t.

The (call) stack is a stack (abstract data type), but not vice versa.

heap

A heap is a specific data structure that implements the abstract data type priority queue, see Heap (data structure). When we say “heap” in an algorithms course, we almost always mean the data type.

Howver, the word “heap” is also used to refer to a specific chunk of dynamically allocated memory, see Dynamic memory allocation.
We almost never use that term in the present course, but you may come across it in relation to data structures in other material, for instance about allocating linked lists and other dynamic data structures.

The (memory) heap is not a heap data structure.

map

In mathematics, a map is a “function,” a something that connects (“maps”) things from one set to another, see Map (mathematics)). The Danish word is afbildning.

Some programming languages use term to refer to what we call “symbol table” in this course: a something that maps “keys” to “values”, see Map (computer science).
Other words are associative array or dictionary.
An example is Java’s interface java.util.Map that describes an abstract data type for a symbol table, and is famously implemented in the data structures java.util.HashMap.

However, in other programming languages, map is used for the application of a function to a sequence, see Map (higher order function)) This is true for Python. (Python instead used “dictionary”, dict, for its symbol tables.)

So in Python, map is a higher-order function, in Java, Map it is an interface. These things have nothing to do with each other.

One can try to stick to the term symbol table for the abstract data type.

running time / runtime

Running time is the time to execute an algorithm, synonymous with Time complexity.
It is given as a growth rate in terms of a size measure, using some asympototic notation. We can say “the running time of merge sort is O(n log n)”.

We may also use it to refer to the actual execution time (in seconds) of a concrete piece of code.
We can then say “the execution time for ex8.cpp was 2.4 seconds on input 002-huge-43.in”.

In contrast, the runtime system is the environment in which a programme is executed, and runtime) as part of a program’s life cycle. We talk about runtime errors if a programme fails during execution, and may want to distinguish between checking array index-out-of-bounds error at runtime or compile-time.
Neither of these concepts have to do with running time.

graph

Graph means two things in algorithms and discrete mathematics; they have nothing in common.

Most of the time we mean a combinatorial structure that models a pairwise relation, see
Graph (discrete mathematics))
In this context, “graph” is a synonym of “network”.

It may also mean graph of a function, which is what you have learned in school. Such a graph is either a set of points or the drawing of these points. This is what we mean when we say “graph of a function,” or “draw the running time as a graph.”

random

“Random” means two different things: stochastic (as in throwing dice or drawing lots) or unpredictable (as in arbitrary). These are very different and your instructor will be very cross with you if should mix them up.

When, for instance, we pick the split element in quicksort randomly, we mean “uniformly at random and independently from previous random choices.” It’s very important that you don’t misread this as “arbitrary”: if the split element in quicksort is picked arbitrarily (say, by your worst enemy), the analysis breaks down and quicksort becomes slowsort.

Of course, when we talk about the very important random access model of computation (RAM), the word “random” means arbitrary/unconstrained/unpredictable. Here, it is important that accessing memory location M[i] takes constant time, no matter how i was chosen. Even your worst enemy wouldn’t be able to make the RAM spend more than constant time. So: the word random does not mean that the constant-time bound holds only for random-in-the-stochastic sense access, or (God forbid) that the result of M[i] is random or even arbitrary.

I believe that “random” only means “decidedly nonrandom” when we’re talking about the random access machine, so you’re probably safe in interpreting it as “taken from a probability distribution, probably uniformly and independently unless something else is said” in all other contexts.

node

A node is a localised swelling in a network, it is a synonym of “knot,” both from the Latin nodus.
Think of a fisherman’s net.

In an algorithms course, node means “basic unit of a data structure”, see Node computer science).
It often appears explicitly in an implementation, typically as an object of class Node, and sometimes only implictly as a useful abstraction.

We will also use node for the fundamental unit of a graph, see
Vertex). We will try to stick to “vertex” for such nodes, but the terms are synonyms and you will meet node-as-vertex in many places.
Another good word for node-as-vertex is point.

Perhaps confusingly, when you construct the data structure to solve a basic graph problem, typically you don’t use a node (data structure) for a node (combinatorial object).

linear

Linear means at least two, completely unrelated things.
In “linear programming”, the word is used as in calculus (linear function), to highlight the fact that the variable has degree 1 (rather than appearing squared.)

In “linear probing,” a collosion strategy employed by hash tables, it just means “one-after-the-other”.

programming

In “introduction to programming,” or “computer programming” or “Java programming,” the word programming means “writing instructions”, typically using a programming language.
In “linear programming,” “quadratic programming,” or “dynamic programming,” the word programming just means planning or scheduling, as in “TV programming” or “theatre programming,” and could be usefully replaced with scheduling or optimisation almost everywhere it occurs.
As a particular confusion, constructing a linear program (or “programme” if you’re fancy), means setting up a bunch of constraints (these constraints are linear functions), but does not involve writing the (computer program) to solve those constraints. You can write a Java program to solve a linear program.

dynamic

Dynamic means “the entries or instance can change” or “the entries are never recomputed”.
In the former sense, it is used in dynamic array (an array whose length can change – all arrays are mutable, so in that sense they’re all dynamic) or dynamic graph algorithm (an algorithm for a graph that undergoes changes.) In the latter sense it is used in dynamic programming, a specific algorithmic optimisation strategy, where the whole points was that functions without side effects never change, so we might as well store them is a static table and never change them.

The history of the term “dynamic programming” is documented by Bellman and quite entertaining.

asymptotic

Asymptotic means “never falling together”, and the term draws attention to the fact that one function is the asymptote of another by virtue of the two never touching. This is typically a topic of high school maths, see asymptote. In the analysis of algorithms, “asymptotic” almost always just means “for large values of the input size” and has nothing to do with “not touching” or even approaching each other. In particular, a function is asymptotically itself, and 2 is 1 in asymptotic notation; see Big O notation. There is an intermediate concept of asymptotic analysis which somewhat explains how the two terms related.

Lindsay, Pluckrose, Horkheimer, Marcuse unlocked in Secret Sartre

For immediate release. To celebrate the publication of Cynical Theories in the middle of the exciting cultural and academic climate of 2020, Helen Pluckrose, James Lindsay, Herbert Marcuse, and Max Horkheimer are now playable characters in Secret Sartre, the social deduction game of academic intrigue and ideological infighting.

“The intellectual corruption of sense-making institutions, in particular academia, that we have been witnessing in the past few decades is increasingly credited to the post-marxist ideas of Critical Theory in the Frankfurt school, rather than only the traditions of French postmodernism. Players of Secret Sartre have expressed their desire to acknowledge this perceptual shift – to allow different voices to be heard in the game, to open the shared experience to a different narrative – and Max Horkheimer has long been a favourite request among both devoted and casual players,” says game designer Thore Husfeldt.

Print and cut into four cards using the traditional, legitimising norm of rectangle. Use the card backs that come with the basic Secret Sartre game. The secret allegiance of Marcuse and Horkheimer is Postmodernism. The secret allegiance of Pluckrose and Lindsay is Science.

“To complete the Critical Theory faction, we’ve added Herbert Marcuse, father of the New Left, and another central Frankfurt school thinker. Through his advisor Heidegger, he also connects Secret Sartre to that other large totalitarian tradition of the 20th century, Fascism. This also allows us to acknowledge our ludic, ideological, and intellectual debt to the original game.”

To balance the new expansion offering, both Helen Pluckrose and James Lindsay join the quixotic Science faction, championing values such as truth, humanism, evidence, conversation, honesty, and enlightenment. Pluckrose and Lindsay are the authors of Cynical Theories (Pitchstone, 2020) became famous through the Grievance studies affair.

The current expansion to the original 2015 game follows a previous expansion from 2017, which added Jordan B. Peterson and Bret Weinstein to the forces of the Enlightenment.

The game expansion is available as a free download immediately. To unlock Horkheimer for actual play in Secret Sartre requires purchase of Cynical Theories in hardcover or a sizeable donation to New Discourses.

Hjælp til projektopgave om kunstig intelligens, overvågning, science fiction, algoritmer og det digitale samfund

Kære projektgruppe af elever på skole X.

I har været så søde at spørge mig om hjælp til en projektopgave, og har sendt mig en masse gode og relevante spørgsmål om noget, jeg faktisk ved noget om. Dejligt.

Undskyld

Desværre har jeg ikke tid til at svare jer. Det er der mindst tre grunde til.

  1. Jeres spørgsmål er alt for brede. »Hvad er problemerne med…« eller lignende vil, når I spørger en akademiker af en vis lødighed, afføde en alenlang redegørelse. Det ville tage mig 1 år og 500 sider at svare ordentligt på den slags spørgsmål. Ganske rigtigt er det netop indholdet til den bog, jeg altid gerne ville have skrevet. Men jeg har altså ikke skrevet den.
    Hvis I spurgte en politiker, så ville vedkommende have et færdig, kort og forberedt svar. Men jeg er ikke politiker. Det er deres opgave. Min er en anden.
    Journalister kan forresten heller ikke stille gode spørgsmål til akademikere, så I er i meget godt selskab.
  2. Jeg kender ikke jeres baggrund. Jeg er god til at forklare, men jeg kan ikke forklare noget potentielt teknisk uden at vide, hvad I forstår. Bør jeg begynde med 50 sider om grundlæggende it eller ej? Kan I programmere? Ved I, hvad en algoritme er? Jeg aner det ikke, og hvis jeg skal svare ordentligt, skal jeg først få grundlaget på plads.
    Journalister kan heller ikke finde ud af dette.
  3. Selv hvis I var i stand til at formulere klare og præcise spørgsmål, som jeg kunne svare på ved blot at bruge en time eller to, så ville jeg stadig ikke have tid til det. I er nemlig rigtig mange og skriver tydeligvis projektopgaver på de samme tidspunkter af året.

Information

Hvad kan I så gøre?

Sommetider deltager jeg i offentligheden i samtaler eller holder foredrag om de emner, som I spørger om. Dem er I meget velkomne til at kigge på, og citere mig for det sagte. Kig især på de lange samtaler på Cast IT.

Der er meget mere, inklusive debatartikler i dagblade, på https://thorehusfeldt.com/appearances/ .

ITU at NCPC 2019 (5 October)

This page summarises the preparation for ITU students for the Nordic Collegiate Programming Competition (»Danmarksmesterskaberne i Programmering«) for 2019

The Nordic Collegiate Programming Competition (NCPC) is a programming and problem solving event held every year. Teams of 3 programmers try to solve as many problems as they can (from a list of a dozen or so tasks) in five hours. The NCPC is open to all, but in order to compete in the “official” part (placing in the national championship or proceeding to the European or world finals), you need to be a university student, and you need to register in advance and participate on site. That is also the most fun and satisfying experience.

How difficult is this?

This is for you. If you have programming skills corresponding to a single ITU introductory programming course, you should be able to solve 1–2 problems. You should feel very good about that. If you have even taken an introductory algorithms class (or other problem solving class) then maybe 3–4 questions are within reach, which puts you very high on the list. You can look at last years’ standing for all of Denmark; as you can see this event is highly welcoming of newcomers. (Don’t get distracted by the monstrous performances of the top participants; think of it like running the Berlin marathon — you don’t feel bad about being slower than the world record holder in the same race).

The event (»Danmarksmesterskaberne i programmering«)

The Danish events label themselves Danish Championships, and typically take place in Aarhus, Odense, and Copenhagen. ITU Students are encouraged to participate in the Copenhagen event hosted at KU, and supported by NetCompany and JobIndex.

If you want some inspiration, here is a hyggelig film about the 2016 event:

You can also look at the

  • web site for NCPC 2018 (last year), where you can see the team names and how well they did (under Final standings), read the problems, and look at the slides explaining their solutions. As you can see, there were 0 ITU teams. We want to change this.

Preparation at ITU

You should totally participate. If you’re on your 2nd year of studies and enjoy programming, problem solving, and collaborating, this is a brilliant, engaging, and intellectually and socially satisfying way to improve your skills – it is also great team building. And boy, does it look good on your cv.

  • Create a team. You want to create a team, maximally (and preferably) of 3 people, and find a suitably painful team name. If you don’t yet have a team, we will probably be able to create some during September. If you want to seriously compete, you need to read the rules for participating in the official championships, see the event web site. Or you can be like me and just participate for the fun of it. Align your expectations with your friends.
  • Chat channel: https://talk.itu.dk/channel/dmprog-ncpc-2019 : a chat channel at talk.itu.dk for this event. If you’re an ITU student, you already have an account. We’ll use this to communicate about pizza, problems, teams formation, news, etc.
  • NCPC Coaching Fridays at ITU at 15: Most Fridays at 15–16, starting 30 August, one of the ITU teachers will be available (room to be announced) for some coaching. Among other things, we’ll go through last year’s NCPC problems, point to other good material, discuss strategy and preparation. See the bottom of this page for an overview.
  • Bjarki’s course. Bjarki Ágúst Guðmundsson maintains a very ambitious course about competitive programming at https://algo.is. Includes links to relevant open Kattis exercises. No matter where you are in your skill development, there should be a module or two for you that makes you better.
  • Johan’s book. Johan Sannemo, Principles of algorithmic problem solving. Similar to Bjarki’s course, slightly different format and focus.
  • Grind. Log on to open.kattis.com. Sort the problems by difficulty and solve them from the top. Or search for NCPC to find old contest problems.
  • Teambuild. Do some programming in your team in order to understand your group’s dynamics. (The contest is with a single computer, so only one person at a time is typically typing.) Agree on one or two languages. (Python 2 and Java both are good choices.)
  • Select written material. You can bring any written material. So: Learn not to rely on on-line material (you can’t google stackoverflow during the contests) and find out which written you actually need and can navigate (say, a programming language reference, but not all 4 volumes of the Art of Computer Programming). You can even maintain your own evolving document, with often-forgotten code snippets, standard templates, hints to yourself, your editor configuration, soothing picture of a kitten, etc. Here’s an example from a very experienced partipant (Måns Magnusson), heavily focussing on algorithms: https://github.com/exoji2e/notebook.
  • Three hour warm-up event Friday 20 September 16-19. ITU will host a 3 hour warm-up event two weeks before NCPC at https://open.kattis.com/contests/ne66md. The main goal is to give you a chance to experience a mini-contest as a team (for instance, who does the typing?) Register informally at talk.itu.dk/ncpc , and the Computer Science Department will provide free food (probably sandwiches and soft drinks). Brief intro at 15:45 in 2A03, we’ve reserved the tables on the 2nd floor (2R01, etc.) during event. Last-minute drop-ins welcome.
  • Five hour warm-up event Saturday 28 September 11-16 . Exactly one week before the main event. Hosted by the Kattis people at https://open.kattis.com/contests/ncpc2019warmup.

Coaching/Lectures

I’ll give some extra lectures in various formats. The expected skill set that of 2nd year Software students, but everybody is welcome.

  • 30 Aug, 13-14, repeated at 16-17. 2A08. Repeated at 16-17 same day. (Thore). Welcome. Kattis basics, NCPC basics, tips and tricks, questions and answers. Solution of NCPC 2018 problem B–babybites (where Thore’s team was 1st last year!) and C–codecleanups.
  • 6 Sep, 15-16. 2A08. (Thore) H–houselawn, greedy algorithms, I-intergalactic bidding.
  • 13 Sep, 15-16. 2A08. (Thore) Graph problems. deliverydelays (very hard! we didn’t manage to solve it)
  • (20 Sep): No coaching, since there’s a warm-up event. at 16.
  • 24 Sep, 8–10, Aud5. Dynamic programming I. Part of the MSc Algorithm Design course. Everybody welcome.
  • 1 Oct, 8–10, Aud5. Dynamic programming II. Part of the MSc Algorithm Design course. Everybody welcome.