Category Archives: Combinatorics

Serge Vlăduţ : Lattices with exponentially large kissing numbers

   (I thank Avi Wigderson for telling me about it.) Serge Vlăduţ just arxived a paper with examples of lattices in such that the kissing number is exponential in . The existence of such a lattice is a very old open … Continue reading

Posted in Combinatorics, Geometry | Tagged | 4 Comments

Peter Keevash and Eoin Long: Forbidden vector-valued intersections

Peter Keevash and Eoin Long arxived some time ago a very nice paper:  Forbidden vector-valued intersections, which settled a problem that was first posed here on the blog. Here is the abstract. We solve a generalised form of a conjecture of Kalai … Continue reading

Posted in Combinatorics | Tagged , | Leave a comment

Peter Keevash: More and Easier Designs!

Peter Keevash just posted on the arxiv a couple of new papers on designs. The first is a rewritten version of his original paper The existence of designs with a much simpler proof. The second paper The existence of designs … Continue reading

Posted in Combinatorics | Tagged | Leave a comment

Monday February 19: Quantum Coding and High Dimensional Expanders

Tonight at 8:00 Israel time TCS+ Dor Misner on 2-to-2 games.    On Monday, February 19, we will have a special day on “Quantum Coding and High Dimensional Expanders” organized by Gilles Zemor. Sandwiches will be served for lunch, alongside … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Conferences, Quantum, Updates | Tagged , | 2 Comments

The Semester Break activities of the High Dimensional Combinatorics and Expanders Special Year

UPDATE: Schedule change! An additional workshop On February 5 and shift in dats of the others. Here is the calendar We have now at HUJI a semester break, but the special semester in High dimensional combinatorics and IIAS leaded by … Continue reading

Posted in Combinatorics, Updates | Tagged | 1 Comment

Hardness of Approximating Vertex Cover, Polytope-Integrality-Gap, the Alswede-Kachatrian theorem, and More.

Lior Silberman asked about applications of the 2-to-2 game theorem to hardness of approximation, and James Lee answered mentioning applications to vertex cover. Let me elaborate a little on vertex cover, and other matters. (Here is the pervious post on … Continue reading

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

Jacob Fox, David Conlon, and Benny Sudakov: Vast Improvement of our Knowledge on Unavoidable Patterns in Words

I heard a lecture by Benny Sudakov on the remarkable paper  Tower-type bounds for unavoidable patterns in words, by David Conlon, Jacob Fox, and Benny Sudakov.  Here are the slides, and let me let the slides speak for themselves. The problem

Posted in Combinatorics | Tagged , , , | Leave a comment

Subhash Khot, Dor Minzer and Muli Safra completed the proof of the 2-to-2 Games Conjecture

Update: A related blog post by Boaz Barak: Unique Games Conjecture – halfway there? The 2-to-2 Games Conjecture is a somewhat weaker form of Khot’s unique game conjecture. The paper is: Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion by Subhash Khot, Dor … Continue reading

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

Interesting Times in Mathematics: Enumeration Without Numbers, Group Theory Without Groups.

Lie Theory without Groups: Enumerative Geometry and Quantization of Symplectic Resolutions Our 21th Midrasha (school) IIAS, January 7 – January 12, 2018 Jerusalem Enumerative Geometry Beyond Numbers MSRI,  January 16, 2018 to May 25, 2018 Abstract for the Midrasha

Posted in Algebra and Number Theory, Combinatorics, Geometry, Updates | Leave a comment

Cody Murray and Ryan Williams’ new ACC breakthrough: Updates from Oded Goldreich’s Choices

Thanks to Irit Dinur for telling me about the following: Oded Goldreich’s recent choice is about the paper: Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP, by Corry Murray and Ryan Williams. Ryan Williams … Continue reading

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