Paper by Erik D. Demaine

Reference:

MIT Hardness Grp., Josh Brunner, Andy Tockman, Frederick Stock, Della Hendrickson, Hayashi Layers, Timothy Gomez, Erik D. Demaine, and Jenny Diomidova, “Hardness Table Layout Hardness Table”, in Proceedings of SIGTBD (SIGTBD 2025), April 18, 2025.

Abstract:

We analyze the complexity of summarizing given results into a table, organized by various parameters possibly constrained in order, to optimize various objectives. Our results include polynomial-, pseudopolynomial-, constant-, and zero-time algorithms; and NP- and coNP-hardness.

Comments:

Authors are ordered by number of vowels. See an open-source interactive web app, which can generate the tables from this paper.

Length:

The paper is 9 pages.

Availability:

The paper is available in PDF (2356k).

See information on file formats.

[Google Scholar search]