Recent Comments

Recent Posts
 Updates (belated) Between New Haven, Jerusalem, and TelAviv
 Oded Goldreich Fest
 The Race to Quantum Technologies and Quantum Computers (Useful Links)
 Around the GarsiaStanley’s Partitioning Conjecture
 My Answer to TYI 28
 Test your intuition 28: What is the most striking common feature to all these remarkable individuals
 R(5,5) ≤ 48
 Test Your Intuition (27) about the AlonTarsi Conjecture
 Thilo Weinert: Transfinite Ramsey Numbers
Top Posts & Pages
 Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
 Borsuk's Conjecture
 A Breakthrough by Maryna Viazovska Leading to the Long Awaited Solutions for the Densest Packing Problem in Dimensions 8 and 24
 Is Mathematics a Science?
 Oded Goldreich Fest
 The Race to Quantum Technologies and Quantum Computers (Useful Links)
 Two Math Riddles
 Why Quantum Computers Cannot Work: The Movie!
 Polymath10: The Erdos Rado Delta System Conjecture
RSS
Category Archives: Computer Science and Optimization
Real Analysis Introductory Minicourses at Simons Institute
The Real Analysis ‘Boot Camp’ included three excellent minicourses. Inapproximability of Constraint Satisfaction Problems (5 lectures) Johan Håstad (KTH Royal Institute of Technology) (Lecture I, Lecture II, Lecture III, Lecture IV, Lecture V) Unlike more traditional ‘boot camps’ Johan rewarded answers and questions … Continue reading
Analysis of Boolean Functions – week 4
Lecture 6 Last week we discussed two applications of the FourierWalsh plus hypercontractivity method and in this lecture we will discuss one additional application: The lecture was based on a 5pages paper by Ehud Friedgut and Jeff Kahn: On the number … Continue reading
Analysis of Boolean Functions – Week 3
Lecture 4 In the third week we moved directly to the course’s “punchline” – the use of FourierWalsh expansion of Boolean functions and the use of Hypercontractivity. Before that we started with a very nice discrete isoperimetric question on a … Continue reading
Analysis of Boolean functions – week 2
Post on week 1; home page of the course analysis of Boolean functions Lecture II: We discussed two important examples that were introduced by BenOr and Linial: Recursive majority and tribes. Recursive majority (RM): is a Boolean function with variables … Continue reading
Posted in Combinatorics, Computer Science and Optimization, Probability, Teaching
Tagged Boolean functions, Tribes
Leave a comment
Analysis of Boolean Functions – week 1
Home page of the course. In the first lecture I defined the discrete ndimensional cube and Boolean functions. Then I moved to discuss five problems in extremal combinatorics dealing with intersecting families of sets. 1) The largest possible intersecting family … Continue reading
BosonSampling and (BKS) Noise Sensitivity
Update (Nov 2014): Noise sensitivity of BosonSampling and computational complexity of noisy BosonSampling are studied in this paper by Guy Kindler and me. Some of my predictions from this post turned out to be false. In particular the noisy BosonSampling … Continue reading
Posted in Computer Science and Optimization, Physics, Probability
Tagged BosonSampling, Noise, Noisesensitivity, Quantum computation
8 Comments
LawlerKozdronRichardsStroock’s combined Proof for the MatrixTree theorem and Wilson’s Theorem
David Wilson and a cover of Shlomo’s recent book “Curvature in mathematics and physics” A few weeks ago, in David Kazhdan’s basic notion seminar, Shlomo Sternberg gave a lovely presentation Kirchhoff and Wilson via Kozdron and Stroock. The lecture is based on … Continue reading
Posted in Combinatorics, Computer Science and Optimization, Probability
Tagged David Wilson, Gustav Kirchhoff, Trees
4 Comments
The KadisonSinger Conjecture has beed Proved by Adam Marcus, Dan Spielman, and Nikhil Srivastava
…while we keep discussing why mathematics is possible… The news Adam Marcus, Dan Spielman, and Nikhil Srivastava posted a paper entitled “Interlacing Families II: Mixed Characteristic Polynomials and the KadisonSinger Problem,” where they prove the 1959 KadisonSinger conjecture. (We discussed part … Continue reading
Why is mathematics possible?
Spectacular advances in number theory Last weeks we heard about two spectacular results in number theory. As announced in Nature, Yitang Zhang proved that there are infinitely many pairs of consecutive primes which are at most 70 million apart! This is a sensational achievement. … Continue reading
QSTART
Physics, Computer Science, Mathematics, and Foundations’ views on quantum information Inauguration conference for the Quantum Information Science Center (QISC), Hebrew university of Jerusalem Update: The news of our conference have made it to a bigleague blog. Update (July 2013): QStart … Continue reading