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

Posted in Academics, Combinatorics, Computer Science and Optimization, Open discussion, Philosophy, What is Mathematics | Tagged | 16 Comments

Must-read 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…

Posted in Combinatorics, Computer Science and Optimization, Updates | Tagged | 4 Comments

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 , , | 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

Posted in Combinatorics, Computer Science and Optimization, Geometry, Physics, Teaching | Tagged , , , | Leave a comment

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 | 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 | 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 , , | 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 , | 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 , | 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

Posted in Conferences, What is Mathematics | Tagged | 1 Comment