Recent Comments

Recent Posts
 To cheer you up in difficult times 21: Giles Gardam lecture and new result on Kaplansky’s conjectures
 Nostalgia corner: John Riordan’s referee report of my first paper
 At the Movies III: Picture a Scientist
 At the Movies II: Kobi Mizrahi’s short movie White Eye makes it to the Oscar’s short list.
 And the Oscar goes to: Meir Feder, Zvi Reznic, Guy Dorman, and Ron Yogev
 Thomas Vidick: What it is that we do
 To cheer you up in difficult times 20: Ben Green presents superpolynomial lower bounds for offdiagonal van der Waerden numbers W(3,k)
 To cheer you up in difficult times 19: Nati Linial and Adi Shraibman construct larger cornerfree sets from better numbersontheforehead protocols
 Possible future Polymath projects (2009, 2021)
Top Posts & Pages
 To Cheer You Up in Difficult Times 15: Yuansi Chen Achieved a Major Breakthrough on Bourgain's Slicing Problem and the Kannan, Lovász and Simonovits Conjecture
 To cheer you up in difficult times 21: Giles Gardam lecture and new result on Kaplansky's conjectures
 TYI 30: Expected number of Dice throws
 8866128975287528³+(8778405442862239)³+(2736111468807040)³
 The Argument Against Quantum Computers  A Very Short Introduction
 Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
 Amazing: Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen proved that MIP* = RE and thus disproved Connes 1976 Embedding Conjecture, and provided a negative answer to Tsirelson's problem.
 Possible future Polymath projects (2009, 2021)
 Photonic Huge Quantum Advantage ???
RSS
Tag Archives: Linear programming
Projections to the TSP Polytope
Michael Ben Or told me about the following great paper Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds by Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary and Ronald de Wolf. The paper solves an old conjecture … Continue reading
IPAM remote blogging: The Many Facets of Linear Programming
The many facets of Linear Programming Here is an extremely nice paper by Michael Todd from 2001. It gives useful background for many lectures and it can serve as a good base point to examine last decade’s progress. Background post for … Continue reading
Günter Ziegler: 1000$ from Beverly Hills for a Math Problem. (IPAM remote blogging.)
Scanned letter by Zadeh. (c) Günter M. Ziegler lefttoright: David Avis, Norman Zadeh, Oliver Friedmann, and Russ Caflish (IPAM director). Photo courtesy Eddie Kim. Update: The slides for Friedmann’s talk are now available. The conference schedule page contains now the slides for … Continue reading
Posted in Computer Science and Optimization, Conferences, Guest blogger
Tagged Linear programming
4 Comments
Subexponential Lower Bound for Randomized Pivot Rules!
Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick have managed to prove subexponential lower bounds of the form for the following two basic randomized pivot rules for the simplex algorithm! This is the first result of its kind and deciding … Continue reading
The Polynomial Hirsch Conjecture: A proposal for Polymath3
This post is continued here. Eddie Kim and Francisco Santos have just uploaded a survey article on the Hirsch Conjecture. The Hirsch conjecture: The graph of a dpolytope with n vertices facets has diameter at most nd. We devoted several … Continue reading
A Diameter problem (7): The Best Known Bound
Our Diameter problem for families of sets Consider a family of subsets of size d of the set N={1,2,…,n}. Associate to a graph as follows: The vertices of are simply the sets in . Two vertices and are adjacent if . … Continue reading
A Diameter Problem (6): Abstract Objective Functions
George Dantzig and Leonid Khachyan In this part we will not progress on the diameter problem that we discussed in the earlier posts but will rather describe a closely related problem for directed graphs associated with ordered families of sets. The role models for … Continue reading
Posted in Combinatorics, Convex polytopes, Open problems
Tagged Hirsch conjecture, Linear programming
7 Comments
Diameter Problem (3)
3. What we will do in this post and and in future posts We will now try all sorts of ideas to give good upper bounds for the abstract diameter problem that we described. As we explained, such bounds apply … Continue reading
Posted in Combinatorics, Convex polytopes, Open problems
Tagged Hirsch conjecture, Linear programming, Quasiautomated proofs
1 Comment