[HN Gopher] Mathematics and Computation (2019) [pdf]
___________________________________________________________________
Mathematics and Computation (2019) [pdf]
Author : nill0
Score : 66 points
Date : 2025-11-18 12:35 UTC (10 hours ago)
(HTM) web link (www.math.ias.edu)
(TXT) w3m dump (www.math.ias.edu)
| marcofloriano wrote:
| Thank you
| vatsachak wrote:
| I bought this book and the title is misleading.
|
| The book should be called Mathematics and Theory of computation
| xdavidliu wrote:
| 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?
| j2kun wrote:
| I could see someone interpreting "computation" to be more
| practical.
| vatsachak wrote:
| Yeah, actually computing things imo
| jlarcombe wrote:
| the Oxford joint schools degree was called "Mathematics and
| Computation" for many, many years
| chihuahua wrote:
| I got the impression that they thought computer science was a
| fad that was going to go away soon.
| vatsachak wrote:
| These days you can have math and real computation; proving
| theorems through reducing terms in Lean
| GeoffKnauth wrote:
| 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.
| sigbottle wrote:
| 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.
| ks2048 wrote:
| 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
| jmount wrote:
| 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.
| alan-jordan13 wrote:
| Great read--Mathematics and Computation (2019) offers a clear,
| insightful look at how math underpins modern computational
| thinking. Concise, rigorous, and thought-provoking.
___________________________________________________________________
(page generated 2025-11-18 23:01 UTC)