If anyone wants to watch a recent talk by the author (Avi Wigderson) on a similar broad overview: Avi Wigderson, P vs NP. 2025 Clay Research Conference
In my opinion, BPP (one of the major topics of the book) is such a weird complexity class. It seems both an easy and hard class.
Roughly it accepts inputs that have at least 2/3rds of witnesses accepting and rejects inputs that have no more than 1/3 of witnesses accepting. Witness means additional input (usually considered random input). The super nicety is the huge gap between 1/3 and 2/3.
One can simulate a BPP recognizer to a high degree of fidelity. Just try a bunch of random witnesses.
However, we don't yet know how to efficiently perfectly implement a perfect recognizer. Until we have sampled a lot of witnesses we really don't know what fraction the of overall population we are drawing from is accepting.
However (as the book points out) we know the strategy for perfect solution. We can decide BPP perfectly and efficiently if and only if certain very strong efficient pseudo random number generators exist. And the existence of such is very much tied to if certain problems are hard (require large circuits to solve) or not.
is there a more accepted connotation of the lone word "computation" that means something different from "theory of computation" (in the sense of turing machines, computability, decidability, complexity classes, Sipser) etc?
I don't think knuth does modern TCS stuff, the "old guard" (80s-ish) was focused on either classical algorithms / combinatorics, or the start of systems programming (db, network, os). Yes, Knuth did quite a bit of math in TAOCP, but they're very much "old" techniques.
Modern TCS is about unifying a lot of the ad-hoc approaches of old, as well as analyzing different models of computation that better model reality (EMM, streaming, distributed, etc).
If anyone wants to watch a recent talk by the author (Avi Wigderson) on a similar broad overview: Avi Wigderson, P vs NP. 2025 Clay Research Conference
https://www.youtube.com/watch?v=HX9i9PL8os0
In my opinion, BPP (one of the major topics of the book) is such a weird complexity class. It seems both an easy and hard class.
Roughly it accepts inputs that have at least 2/3rds of witnesses accepting and rejects inputs that have no more than 1/3 of witnesses accepting. Witness means additional input (usually considered random input). The super nicety is the huge gap between 1/3 and 2/3.
One can simulate a BPP recognizer to a high degree of fidelity. Just try a bunch of random witnesses.
However, we don't yet know how to efficiently perfectly implement a perfect recognizer. Until we have sampled a lot of witnesses we really don't know what fraction the of overall population we are drawing from is accepting.
However (as the book points out) we know the strategy for perfect solution. We can decide BPP perfectly and efficiently if and only if certain very strong efficient pseudo random number generators exist. And the existence of such is very much tied to if certain problems are hard (require large circuits to solve) or not.
I bought this book and the title is misleading.
The book should be called Mathematics and Theory of computation
is there a more accepted connotation of the lone word "computation" that means something different from "theory of computation" (in the sense of turing machines, computability, decidability, complexity classes, Sipser) etc?
I could see someone interpreting "computation" to be more practical.
Yeah, actually computing things imo
the theory is mainly about uncomputable things tho
the Oxford joint schools degree was called "Mathematics and Computation" for many, many years
I got the impression that they thought computer science was a fad that was going to go away soon.
These days you can have math and real computation; proving theorems through reducing terms in Lean
Looks like an interesting book. I wonder why I saw no references to Donald Knuth in the bibliography. He is mentioned once in the text.
I don't think knuth does modern TCS stuff, the "old guard" (80s-ish) was focused on either classical algorithms / combinatorics, or the start of systems programming (db, network, os). Yes, Knuth did quite a bit of math in TAOCP, but they're very much "old" techniques.
Modern TCS is about unifying a lot of the ad-hoc approaches of old, as well as analyzing different models of computation that better model reality (EMM, streaming, distributed, etc).
I like both.
[flagged]
Thank you