Monthly Archives: September 2013

Real Analysis Introductory Mini-courses at Simons Institute

Posted on September 30, 2013 by Gil Kalai

The Real Analysis ‘Boot Camp’ included three excellent mini-courses. 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 →

Posted in Analysis, Computer Science and Optimization, Conferences | Tagged , , | Leave a comment

Analysis of Boolean Functions – week 4

Posted on September 24, 2013 by Gil Kalai

Lecture 6 Last week we discussed two applications of the Fourier-Walsh plus hypercontractivity method and in this lecture we will discuss one additional application: The lecture was based on a 5-pages paper by Ehud Friedgut and Jeff Kahn: On the number … Continue reading →

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

Polymath 8 – a Success!

Posted on September 20, 2013 by Gil Kalai

Yitang Zhang Update (July 22, ’14). The polymath8b paper “Variants of the Selberg sieve, and bounded intervals containing many primes“, is now on the arXiv. See also this post on Terry Tao’s blog. Since the last update, we also had here … Continue reading →

Posted in Mathematics over the Internet, Number theory, Open problems | Tagged , , , , | 11 Comments

Analysis of Boolean Functions – Week 3

Posted on September 18, 2013 by Gil Kalai

Lecture 4 In the third week we moved directly to the course’s “punchline” – the use of Fourier-Walsh expansion of Boolean functions and the use of Hypercontractivity. Before that we  started with  a very nice discrete isoperimetric question on a … Continue reading →

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

Richard Stanley: How the Proof of the Upper Bound Theorem (for spheres) was Found

Posted on September 10, 2013 by Gil Kalai

The upper bound theorem asserts that among all d-dimensional polytopes with n vertices, the cyclic polytope maximizes the number of facets (and k-faces for every k). It was proved by McMullen for polytopes in 1970, and by Stanley for general triangulations … Continue reading →

Posted in Combinatorics, Convex polytopes | Tagged , | 5 Comments

Simons@UCBerkeley

Posted on September 9, 2013 by Gil Kalai

Raghu Meka talking at the workshop  I spend the semester in Berkeley at the newly founded Simons Institute for the Theory of Computing. The first two programs demonstrate well the scope of the center and why it is needed. One program … Continue reading →

Posted in Conferences, Updates | 1 Comment

Analysis of Boolean functions – week 2

Posted on September 8, 2013 by Gil Kalai

Post on week 1; home page of the course analysis of Boolean functions Lecture II: We discussed two important examples that were introduced by Ben-Or 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 , | Leave a comment

Around Borsuk’s Conjecture 3: How to Save Borsuk’s conjecture

Posted on September 4, 2013 by Gil Kalai

Borsuk asked in 1933 if every bounded set K of diameter 1 in can be covered by d+1 sets of smaller diameter. A positive answer was referred to as the “Borsuk Conjecture,” and it was disproved by Jeff Kahn and me in 1993. … Continue reading →

Posted in Combinatorics, Convexity, Geometry, Open problems | Tagged , , , | 2 Comments

Analysis of Boolean Functions – week 1

Posted on September 3, 2013 by Gil Kalai

Home page of the course. In the first lecture I defined the discrete n-dimensional 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 →

Posted in Combinatorics, Computer Science and Optimization, Teaching | Tagged , , , | 1 Comment