Recent Comments

Recent Posts
 Test Your Intuition about the AlonTarsi Conjecture
 Thilo Weinert: Transfinite Ramsey Numbers
 Timothy Chow Launched Polymath12 on Rota Basis Conjecture and Other News
 Proof By Lice!
 The seventeen camels riddle, and Noga Alon’s camel proof and algorithms
 Edmund Landau and the Early Days of the Hebrew University of Jerusalem
 Boolean Functions: Influence, Threshold, and Noise
 Laci Babai Visits Israel!
 Polymath10 conclusion
Top Posts & Pages
 Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
 A Breakthrough by Maryna Viazovska Leading to the Long Awaited Solutions for the Densest Packing Problem in Dimensions 8 and 24
 Extremal Combinatorics IV: Shifting
 Greg Kuperberg: It is in NP to Tell if a Knot is Knotted! (under GRH!)
 Polymath 10 Emergency Post 5: The ErdosSzemeredi Sunflower Conjecture is Now Proven.
 Test Your Intuition about the AlonTarsi Conjecture
 Can Category Theory Serve as the Foundation of Mathematics?
 Polymath10, Post 2: Homological Approach
 Updates and plans III.
RSS
Category Archives: Computer Science and Optimization
Influence, Threshold, and Noise
My dear friend Itai Benjamini told me that he won’t be able to make it to my Tuesday talk on influence, threshold, and noise, and asked if I already have the slides. So it occurred to me that perhaps … Continue reading
NavierStokes Fluid Computers
Smart fluid Terry Tao posted a very intriguing post on the NavierStokes equation, based on a recently uploaded paper Finite time blowup for an averaged threedimensional NavierStokes equation. The paper proved a remarkable negative answer for the regularity conjecture for a certain … Continue reading
NatiFest is Coming
The conference Poster as designed by Rotem Linial A conference celebrating Nati Linial’s 60th birthday will take place in Jerusalem December 1618. Here is the conference’s webpage. To celebrate the event, I will reblog my very early 2008 post “Nati’s … Continue reading
Posted in Combinatorics, Computer Science and Optimization, Conferences, Updates
Tagged Nati Linial
2 Comments
Analysis of Boolean Functions – Week 7
Lecture 11 The Cap Set problem We presented Meshulam’s bound for the maximum number of elements in a subset A of not containing a triple x,y,x of distinct elements whose sum is 0. The theorem is analogous to Roth’s theorem … Continue reading
Posted in Combinatorics, Computer Science and Optimization, Teaching
Tagged Cap set problem, Codes, Linearity testing
Leave a comment
Analysis of Boolean Functions week 5 and 6
Lecture 7 First passage percolation 1) Models of percolation. We talked about percolation introduced by Broadbent and Hammersley in 1957. The basic model is a model of random subgraphs of a grid in ndimensional space. (Other graphs were considered later as … Continue reading
Posted in Combinatorics, Computer Science and Optimization, Probability, Teaching
Tagged Arrow's theorem, Percolation
Leave a comment
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