Category Archives: Combinatorics

Game Theory – on-line Course at IDC, Herzliya

Game theory, a graduate course at IDC, Herzliya; Lecturer: Gil Kalai; TA: Einat Wigderson,  ZOOM mentor: Ethan. Starting Tuesday March 31, I am giving an on-line course (in Hebrew) on Game theory at IDC, Herzliya (IDC English site; IDC Chinese … Continue reading

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

Kelman, Kindler, Lifshitz, Minzer, and Safra: Towards the Entropy-Influence Conjecture

Let me briefly report on a remarkable new paper by Esty Kelman, Guy Kindler, Noam Lifshitz, Dor Minzer, and Muli Safra, Revisiting Bourgain-Kalai and Fourier Entropies. The paper describes substantial progress towards the Entropy-Influence conjecture, posed by Ehud Friedgut and … Continue reading

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

Or Ordentlich, Oded Regev and Barak Weiss: New bounds for Covering Density!

Barak Weiss lectured about his breakthrough results with Or Ordentlich, and Oded Regev, at a Simons Institute workshop: Lattices: Geometry, Algorithms and Hardness. It is a famous problem what is the densest (or, most efficient) packing of unit balls in Euclidean … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Geometry | Tagged , , | 2 Comments

To cheer you up in complicated times – A book proof by Rom Pinchasi and Alexandr Polyanskii for a 1978 Conjecture by Erdős and Purdy!

Things do not look that good, and these are difficult times. But here on the blog we have plenty of things to cheer you up and assure you. And today we point to two book proofs — two book proofs … Continue reading

Posted in Combinatorics, Geometry, What is Mathematics | Tagged , | 8 Comments

A new PolyTCS blog!

A new PolyTCS blog The PolyTCS Project is a new blog to run collaborative Theoretical Computer Science projects. The initiative is by two graduate students Rupei Xu and Chloe Yang. The logo was designed by Grigory Yaroslavtsev. At this stage … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Mathematics over the Internet | Tagged , , | Leave a comment

Remarkable New Stochastic Methods in ABF: Ronen Eldan and Renan Gross Found a New Proof for KKL and Settled a Conjecture by Talagrand

  The main conjecture from Talagrand’s paper on boundaries and influences was settled by Ronen Eldan and Renan Gross. Their paper introduces a new powerful method to the field of analysis of Boolean functions (ABF). This post is devoted to … Continue reading

Posted in Analysis, Combinatorics, Probability | Tagged , , | 5 Comments

Hoi Nguyen and Melanie Wood: Remarkable Formulas for the Probability that Projections of Lattices are Surjective

Following a lecture by Hoi Nguyen at Oberwolfach, I would like to tell you a little about the paper: Random integral matrices: universality of surjectivity and the cokernel by Hoi Nguyen and Melanie Wood. Two background questions: Hoi started with … Continue reading

Posted in Algebra, Combinatorics, Number theory, Probability | Tagged , | 6 Comments

The largest clique in the Paley Graph: unexpected significant progress and surprising connections.

The result on Paley Graphs by Hanson and Petridis On May 2019, Brandon Hanson and Giorgis Petridis posed a paper on the arXive: Refined Estimates Concerning Sumsets Contained in the Roots of Unity. The abstract was almost as short as … Continue reading

Posted in Combinatorics, Number theory | Tagged , , , , , | 2 Comments

Ringel Conjecture, Solved! Congratulations to Richard Montgomery, Alexey Pokrovskiy, and Benny Sudakov

Ringel’s conjecture solved (for sufficiently large n) A couple weeks ago and a few days after I heard an excellent lecture about it by Alexey Pokrovskiy in Oberwolfach, the paper A proof of Ringel’s Conjecture by Richard Montgomery, Alexey Pokrovskiy, … Continue reading

Posted in Combinatorics, Open problems, Updates | Tagged , , | 3 Comments

Test your intuition 43: Distribution According to Areas in Top Departments.

  In the community of mamathetitians in a certain country there are mamathetitians in two areas: Anabra (fraction p of the mamathetitians) and Algasis (fraction 1-p of  mamathetitians.) There are ten universities with 50 faculty members in each mamathetics department … Continue reading

Posted in Combinatorics, Open problems, Probability, Test your intuition | Tagged | 9 Comments