Mathematics and Computation (2019) [pdf]
Postedabout 2 months agoActiveabout 2 months ago
math.ias.eduResearchstory
calmpositive
Debate
20/100
MathematicsComputationComplexity Theory
Key topics
Mathematics
Computation
Complexity Theory
The post shares a PDF of 'Mathematics and Computation' by Avi Wigderson, sparking discussion on the book's content and related topics in complexity theory.
Snapshot generated from the HN discussion
Discussion Activity
Active discussionFirst comment
3h
Peak period
12
0-12h
Avg / period
6.5
Comment distribution13 data points
Loading chart...
Based on 13 loaded comments
Key moments
- 01Story posted
Nov 18, 2025 at 7:35 AM EST
about 2 months ago
Step 01 - 02First comment
Nov 18, 2025 at 10:14 AM EST
3h after posting
Step 02 - 03Peak activity
12 comments in 0-12h
Hottest window of the conversation
Step 03 - 04Latest activity
Nov 23, 2025 at 3:06 PM EST
about 2 months ago
Step 04
Generating AI Summary...
Analyzing up to 500 comments to identify key contributors and discussion patterns
ID: 45964816Type: storyLast synced: 11/20/2025, 1:30:03 PM
Want the full context?
Jump to the original sources
Read the primary article or dive into the live Hacker News thread when you're ready.
The book should be called Mathematics and Theory of computation
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.
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.
https://www.youtube.com/watch?v=HX9i9PL8os0