Recent Comments

Recent Posts
 Remarkable New Stochastic Methods in ABF: Ronen Eldan and Renan Gross Found a New Proof for KKL and Settled a Conjecture by Talagrand
 Hoi Nguyen and Melanie Wood: Remarkable Formulas for the Probability that Projections of Lattices are Surjective
 Petra! Jordan!
 The largest clique in the Paley Graph: unexpected significant progress and surprising connections.
 Thinking about the people of Wuhan and China
 Ringel Conjecture, Solved! Congratulations to Richard Montgomery, Alexey Pokrovskiy, and Benny Sudakov
 Test your intuition 43: Distribution According to Areas in Top Departments.
 Two talks at HUJI: on the “infamous lower tail” and TOMORROW on recent advances in combinatorics
 Amazing: Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen proved that MIP* = RE and thus disproved Connes 1976 Embedding Conjecture, and provided a negative answer to Tsirelson’s problem.
Top Posts & Pages
 Remarkable New Stochastic Methods in ABF: Ronen Eldan and Renan Gross Found a New Proof for KKL and Settled a Conjecture by Talagrand
 Nati's Influence
 Hoi Nguyen and Melanie Wood: Remarkable Formulas for the Probability that Projections of Lattices are Surjective
 Amazing: Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen proved that MIP* = RE and thus disproved Connes 1976 Embedding Conjecture, and provided a negative answer to Tsirelson's problem.
 Sarkaria's Proof of Tverberg's Theorem 2
 Jeff Kahn and Jinyoung Park: Maximal independent sets and a new isoperimetric inequality for the Hamming cube.
 Amazing: Hao Huang Proved the Sensitivity Conjecture!
 Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
 Ringel Conjecture, Solved! Congratulations to Richard Montgomery, Alexey Pokrovskiy, and Benny Sudakov
RSS
Search Results for: wigderson
Avi Wigderson’s: “Integrating computational modeling, algorithms, and complexity into theories of nature, marks a new scientific revolution!” (An invitation for a discussion.)
The cover of Avi Wigderson’s book “Mathematics and computation” as was first exposed to the public in Avi’s Knuth Prize videotaped lecture. (I had trouble with 3 of the words: What is EGDE L WONK 0? what is GCAAG?GTAACTC … Continue reading
Mustread book by Avi Wigderson
Originally posted on Windows On Theory:
Avi Wigderson is one of the most prolific and creative theoretical computer scientists (in fact, he is one of the most prolific and creative scientists, period). Over the last several years, Avi had worked…
TYI 41: How many steps does it take for a simple random walk on the discrete cube to reach the uniform distribution?
Aeiel Yadin’s homepage contains great lecture notes on harmonic functions on groups and on various other topics. I have a lot of things to discuss and to report; exciting developments in the analysis of Boolean functions; much to report on … Continue reading
Posted in Combinatorics, Probability, Test your intuition
Tagged discrete cube, random walk, Test your intuition
Leave a comment
Starting today: Kazhdan Sunday seminar: “Computation, quantumness, symplectic geometry, and information”
Sunday, 27 October, 2019 – 14:00 to 16:00 Repeats every week every Sunday until Sat Feb 01 2020 Location: Ross 70 See also: Seminar announcement; previous post Symplectic Geometry, Quantization, and Quantum Noise. The Google supremacy claims are discussed (with … Continue reading
Quantum computers: amazing progress (Google & IBM), and extraordinary but probably false supremacy claims (Google).
A 2017 cartoon from this post. After the embargo update (Oct 25): Now that I have some answers from the people involved let me make a quick update: 1) I still find the paper unconvincing, specifically, the verifiable experiments (namely experiments … Continue reading
Posted in Combinatorics, Computer Science and Optimization, Quantum, Updates
Tagged John Martinis
67 Comments
Computer Science and its Impact on our Future
A couple of weeks ago I told you about Avi Wigderson’s vision on the connections between the theory of computing and other areas of mathematics on the one hand and between computer science and other areas of science, technology and … Continue reading
Posted in Academics, Computer Science and Optimization, Quantum, Updates
Tagged computer science
1 Comment
Itai Benjamini and Jeremie Brieussel: Noise Sensitivity Meets Group Theory
The final version of my ICM 2018 paper Three puzzles on mathematics computation and games has been available for some time. (This proceedings’ version, unlike the arXived version has a full list of references.) In this post I would like to … Continue reading
Posted in Algebra, Combinatorics, Probability
Tagged Itai Benjamini, Jeremie Brieussel, Noisesensitivity
1 Comment
Amazing: Hao Huang Proved the Sensitivity Conjecture!
Today’s arXived amazing paper by Hao Huang Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture Contains an amazingly short and beautiful proof of a famous open problem from the theory of computing – the sensitivity conjecture posed … Continue reading
Posted in Combinatorics, Computer Science and Optimization
Tagged Hao Huang, sensitivity conjecture
24 Comments
A sensation in the morning news – Yaroslav Shitov: Counterexamples to Hedetniemi’s conjecture.
Two days ago Nati Linial sent me an email entitled “A sensation in the morning news”. The link was to a new arXived paper by Yaroslav Shitov: Counterexamples to Hedetniemi’s conjecture. Hedetniemi’s 1966 conjecture asserts that if and are two … Continue reading
Posted in Combinatorics, Open problems, Updates
Tagged Hedetniemi's conjecture, Yaroslav Shitov
16 Comments
An Invitation to a Conference: Visions in Mathematics towards 2000
Let me invite you to a conference. The conference took place in 1999 but only recently the 57 videos of the lectures and the discussion sessions are publicly available. (I thank Vitali Milman for telling me about it.) One novel … Continue reading