Category Archives: Computer Science and Optimization

Danny Nguyen and Igor Pak: Presburger Arithmetic Problem Solved!

Short Presburger arithmetic is hard! This is a belated report on a remarkable breakthrough from 2017. The paper is Short Presburger arithmetic is hard, by Nguyen and Pak. Danny Nguyen Integer programming in bounded dimension: Lenstra’s Theorem Algorithmic tasks are … Continue reading

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

Bob Sedgewick’s Free Online Courses on Analysis of Algorithms and Analytic Combinatorics.

Philippe Flajolet 1948-2011   I am  happy to forward the announcement on two free online courses (Mooks) by Bob Sedgewick  Analysis of Algorithms and Analytic Combinatorics. Analysis of Algorithms  page provides access to online lectures, lecture slides, and assignments for … Continue reading

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

Jean

Jean Bourgain and Joram Lindenstrauss. I was very sad to hear that Jean Bourgain, among the greatest mathematicians of our time, and a dear friend, passed away.  I first met Jean about forty years ago and later we  became friends … Continue reading

Posted in Analysis, Combinatorics, Computer Science and Optimization, Convexity, Number theory, Obituary | Tagged | 4 Comments

Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant Solved the Mihail-Vazirani Conjecture for Matroids!

  Milena Mihail and Umesh Vazirani I thank Nati Linial, Dan Spielman and Karim Adiprasito for sharing the news with me. The Mihail-Vazirani conjecture for matroids and Feder-Mihail’s theorem Consider a collection of vectors. A basis is a subset of … Continue reading

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

Igor Pak will give the 2018 Erdős Lectures

  Next week Igor Pak will give the 2018 Erdős Lectures (delayed from June) Here is the poster   Combinatorics — Erdos lecture: Igor Pak (UCLA) “Counting linear extensions” Monday December 10  11:00-13:00 Location:  IIAS Hall 130, Feldman building,  Givat Ram     … Continue reading

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

PCP fest, Tel Aviv University, 18-20 December 2018

Conference web site The study of Probabilistically Checkable Proofs, starting with the discovery of the PCP Theorem, is a cornerstone of modern computer science, with impact on complexity theory, algorithms, and cryptography. Born as a purely theoretical notion, mostly used … Continue reading

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

Video of my ICM2018 lecture: Noise Stability, Noise Sensitivity, and the Quantum Computer Puzzle

The Video of my ICM2018 lecture is now on the air Here are the (slightly improved) slides. I made the mistake of trying to improve my slides in the evening before the lecture and in the morning I discovered that … Continue reading

Posted in Combinatorics, Computer Science and Optimization, ICM2018, Quantum, Updates | Tagged | Leave a comment

Igor Pak is Giving the 2018 Erdős Lectures in Discrete Mathematics and Theoretical Computer Science

Update: The lectures this week are cancelled.  They will be given at a later date. Next week Igor Pak will give the 2018 Erdős Lectures   Monday Jun 18 2018 Combinatorics — Erdos lecture: Igor Pak (UCLA) “Counting linear extensions” 11:00am to 12:30pm Location: … Continue reading

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

Cohen, Haeupler, and Schulman: Explicit Binary Tree-Codes & Cancellations

The high-dimensional conference in Jerusalem is running with many exciting talks (and they are videotaped), and today in Tel Aviv there is a conference on Optimization and Discrete Geometry : Theory and Practice. Today in Jerusalem, Leonard Schulman talked (video available!) … Continue reading

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

Conference on High Dimensional Combinatorics, April 22-26 2018

Conference on High Dimensional Combinatorics Conference home-page Dates: April 22-26, 2018 Place: Israel Institute for Advanced Studies, The Hebrew University of Jerusalem Organizers: Alex Lubotzky, Tali Kaufman and Oren Becker Registration form: click here Registration deadline: April 13, 2018 Combinatorics in general and the theory … Continue reading

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