The cold email that got me into a PhD

When I wanted to do a PhD in the US, I searched for open problems on professors' personal websites and tried to solve them. I found one - on David Eppstein's website - that seemed doable, and managed to solve it with help from Guillem Godoy, the professor I was working for at the time.

I sent him an email with the solution.¹ I didn't hear back until, four months later, someone asked the same question on CS Theory Stack Exchange, which jogged his memory about my email:

He became my PhD advisor.

Sorry for the slow response. This does look like a valid proof. I was reminded of it by a question on cstheory.stackexchange.com asking whether my problem had been solved — I am in the process of leaving an answer there crediting you for the solution. If you're still interested in visiting UCI in Spring 2015, you'd be welcome.²

The problem

The problem was on a slide from one of Eppstein's old courses, listed among project ideas with the note "Should be NP-complete. No proof known."

You're given an n×n matrix of 0's and 1's and a binary sequence, and asked whether there's a path through adjacent cells, visiting each exactly once, whose values spell out the sequence.

To prove it NP-hard, I reduced from Hamilton Path on grid graphs. Here is the original write-up that I emailed him:

📄 Sequence Matching Hamilton Path: NP-hardness proof (PDF)

---

Want to leave a comment? You can post under the linkedin post or the X post.

Footnotes

1. I also remember drafting a letter for a professor whom I thought could be a good match research-wise, before I realized what "emeritus" means 🫣 😆 ↩

2. Yes, he used em dashes in 2014. ↩