"Let me tell you a story..."

Draft of the paper

Notes:

I think this is my favourite paper on this list at the moment. When first defining this model, I just thought it was kinda a cute story, but thinking more about it felt like it gave more intuition about catalytic space than I was expecting. Also, I was just really delighted to find applications of fun graph theory tools where I wasn’t expecting them. This was done with William Wang, mentored by Ted Pyne.

Motivating Fable:

Theo is locked in the depths of the royal dungeons, on suspicion of intentionally sabotaging the king’s dinner party. The guards have been trying to determine whether he and his second-in-command, Cora Larry, have a consistent alibi.

Which they do. At least, Theo thinks they do: they’d agreed on a detailed lie long in advance. However, as a bizarre interrogation technique, a witch has placed a hex of forgetfulness on both suspects, preventing them from forming more than a couple bits worth of new long-term memories. Now, Theo’s concerned the hex may have scrambled some existing memories as a side-effect, possibly making the two stories inconsistent. What he’d love to do is leave some message for Cora in the interrogation room, listing his whole story and asking her to confirm it matches hers — but there doesn’t seem to be anywhere to hide such a message.

Anywhere, that is, except the Head of the Guard’s chessboard. He left a game partway in progress, and the rank-and-file guards won’t notice if it’s tampered with. The issue, of course, is that when the Head of the Guard returns, if the board isn’t exactly as he left it, he’ll know it was used to pass information.

Fortunately, the two conspirators have a plan. When the guards aren’t looking, Cora carefuly shuffles the pieces on the board, making sure to preserve all the information of the original position so that she can reset it in her next session. When Theo is brought in, he looks at the board, and commits to memory a small but crucial fact about the position. At his next interrogation, he glances at the pieces, now returned to their original state, and breaks into a confident smirk.

“I’m ready to talk.”

Draft of the paper

Notes:

This work was done at the Duluth REU program. I think I believe this conjecture is more likely than not false, but I have no idea how to show it — there’s a couple potential counterexamples noted at the end of the paper, but it seems unlikely that it’s tractable to actually compute extremal numbers for those guys. It’s actually kinda crazy how little we know about extremal numbers in general; maybe I will blog post about this in the future.

Motivating Fable:

Fact 1: The king has asked Theo to send invitations to some of the kingdom’s nobility for a feast at the palace.

Fact 2: Theo is not feeling particularly pleased with the king (as a result of being made to fulfill too many such errands), and would like to ensure this feast is a disaster.

The issue is, most of the nobles in the land are too polite (read: too afraid of being beheaded) to cause a scene. So it’ll take a careful choice of people to make sure there’s enough beef to make this exciting. Theo Rem sees two main options:

Option 1: Make sure that everyone on one side of the table is bitter enemies with everyone on the other side of the table. This is sure to be enough to incite an all-out-brawl.

Option 2: Failing that, try to recreate exactly the same friend and enemy relationships that faciliated the notorious Food Fight Incident of 1072. In order to make sure that the right sort of alliances form, Theo would not only have to make sure specific pairs of guests are enemies, but also make sure that specific other pairs are not enemies.

The question is, does there exist enough animosity in the kingdom to let Theo construct such a malicious guest list?

Link to the paper

Notes:

I have no idea if these results are interesting to anyone else, but Alek and I had been trying to figure out the optimal competitive ratios here for like 2 years, so it was really exciting to finally beat 2 (even if we still didn’t quite make it all the way to ϕ). Incidentally, this problem is the reason the site logo is golden ratio.

Motivating Fable:

“Many hands make light work”, goes the old adage. Or maybe it’s “too many cooks spoil the broth”? While Theo Rem has been unusually aware of the fine line between maxims of late, now is probably his maxim minding maximum for this particular pair. The reason: he and his adventuring party have been running boring errands for the king all week, and now, as if they didn’t already have enough work, he’s recieved a royal decree asking them to deep clean the throne chamber.

It’s a difficult position to be in. He could assign one of his crew to do the job on their own — but then it would take quite a while. Alternatively, he could ask multiple people to do it, in which case they’d probably step on each other’s toes a little bit and be overall less efficient, but at least they’d get it done quickly.

He’d better decide correctly though, because his crew is already pretty unhappy — if they discover they’d been stuck there for much longer than necessary just because of Theo’s bad decisions, there might be mutiny. Given that he has no clue what, if anything, the capricious monarch will demand of him next, what should Theo do?

Link to the paper

Notes:

This one came out of a problem suggested in Erik Demaine’s ‘‘Fun with Hardness’’ class, which I worked on with Brian Liu and Alek Westover. I actually initially thought we weren’t going to get tight answers, but then as I wrote it up figured out how to close the gaps — this is notable as my only experience thus far having something end up more clean than expected when I wrote it down :)

Motivating Fable:

“Out of sight, out of mind”, goes the old adage. Or maybe it’s “familiarity breeds contempt”? Never has Theo Rem been so aware of the fine line between these maxims as now, leading the king’s diplomatic party through the burrows of the pig-gnomes.

In order to set up any kind of lasting relations with a particular gnome clan, one has to pay at least three visits to their village, somewhere in the depths of this twisted network of tunnels. However, the milk of porcine kindness is easily strained should one overstay one’s welcome: trying to travel through the same village more than five times is a sure way to sow ill-feelings. Far from bringing home the bacon, an unwelcome guest is lucky to bring home their own head.

Looking at the branching (but not too branching) map of tunnels boared between villages, Theo begins to wallow in despair: even if the route he seeks does exist, is it possible to find it?

Link to the paper

Notes:

I worked on this with Alek Westover; supervised by William Kuszmaul and Martin Farach-Colton. I think it’s a neat problem, and probably believe it should be possible to beat this algorithm (maybe even getting polylog(1/ε)-competitive), so you should think about it. Especially if you’re really good at subset sums or something.

Motivating Fable:

Captain Rem encouraged people to look on the bright side — shouldn’t one be grateful to be so saturated with gold? — but there was still grumbling. The problem was, while the loot their seaward plundering accrued was substantial, the long skinny cargo hold they used to stow said loot was somewhat less so.

Before the hold was completely full, they always made sure to stop at a port and offload — but even when there was technically enough room, it often took a fair amount of heaving around heavy chests before the crew could find a spot for even a relatively small artifact. If only there was a smarter way to arrange things…

Link to the paper

Notes:

This project was done at SPUR (a summer program at MIT) alongside Divya Shyamal, mentored by Anna Brandenburger and Byron Chin. The techniques are very standard, but it was a fun first TCS project.

Motivating Fable:

When he’d set out to recruit an adventuring party, Theo had been imagining a process a little more snappy and Gandalf-esque, not these hours upon hours of interviews. However, it had quickly become apparent that the coarse-grained information in the “Heroism and Questing” personal ads just wouldn’t be enough to pick people.

Take this fellow, for instance. Theo could’ve predicted, based on the “23 M, half-orc, barbarian, passionate about skull-cracking and menacing” description, that he’d likely be a better fit for one of the more… hands-on parts of the team. But it was a total roll of the dice whether he’d end up being a qualified Chief Dragon Slayer — a roll which, upon receiving the response “deathly afraid of serpents, Mr. Rem” to the question of “what’s your biggest weakness”, Theo was disappointed to learn had come up snake-eyes. “You seem like you’d make a great Junior Axe-Wielding Goon,” Theo acceded, “but unfortunately we filled that position last week. I don’t think we’ll be able to make you an offer at this point in time.”

Theo glanced resignedly at his list of unfilled positions: 14 openings for fighters, 9 for negotiations/logistics, 6 for skullduggery and subterfuge, and 7 for magic experts. How many interviews would it take to fill them all? With the sort of decisions he’d been making thus far, it seemed likely to be quite a few — early in the process, he made the mistake of hiring a competent sorcerer as a dungeon cartographer, not realizing quite how few-and-far-between magic users were, and now no amount of cajoling could convince her to give up her maps. He had to figure out how to avoid making that kind of blunder again…