At NDC London, Jon chatted with Rob Conery about his presentation on how Rob got fired for misunderstanding complexity theory, what you need to know, lambda calculus, and The Impostor’s Handbook.
Download / Listen: Herding Code 221: Rob Conery on How Complexity Theory Can Save Your Job
Show Notes:
- (00:30) Jon asks Rob about his presentation at NDC London. Rob’s talk started by describing how he got fired from a job by trying to do something that was NP-Hard. This past year he dug into understand complexity theory, mostly from the point of view of just recognizing the pitfalls. He once wrote a co-occurrence query for just two products (two products that are bought together frequently), and that worked just fine. However, trying to write a co-occurrence query for three or four products doesn’t work because it’s exponentially hard.
- (02:23) Jon asks about the different classes of problems. Rob explains the terms, starting with polynomial time (P) problems, then talking about exponential and factorial complexity.
- (04:10) Jon talks about how Rob’s co-occurrence query was exponentially hard, but for just two products it worked fine. Rob continues with his example from his talk about finding the best place for a group of people to go – that’s NP-Hard. But if there are only two people, you can handle it. You can get into solving some harder problems using concurrency and throwing machines at the problem, but you should understand it.
- (5:10) Rob explains how ideas like page rank fit in, by using authority as a heuristic. Heuristics can be use used for other problems, like the travelling salesman – they won’t give you the provably best solution, but they will reliably give you a very good answer.
- (7:45) Jon asks about the difference between decisions and optimizations. Rob explains that decision problems are NP-Complete problems – if you can represent a problem as a long boolean statement, it’s a boolean satisfiability problem. He describes how optimization problems
- (10:12) Jon asks about Rob’s recent book, The Impostor’s Handbook. Rob explains why he wrote it, and the current audio / video updates he’s making for it.
- (11:40) Jon mentions how there’s a lot more to the book than complexity theory, and Rob explains how it’s all related – complexity theory, foundations of computing, lambda calculus, etc. Jon asks Rob why he likes lambda calculus so much, and Rob talks about a presentation he really liked by Jim Weirich in which he built a y combinator, and he talks about some examples from his book using a y combinator in ES6 to do things like fibbonaci series.
- (14:00) Rob’s book, The Impostor’s Handbook, is available at bigmachine.io.
Links: