Recent Comments

Recent Posts
 Test Your Intuition about the AlonTarsi Conjecture
 Thilo Weinert: Transfinite Ramsey Numbers
 Timothy Chow Launched Polymath12 on Rota Basis Conjecture and Other News
 Proof By Lice!
 The seventeen camels riddle, and Noga Alon’s camel proof and algorithms
 Edmund Landau and the Early Days of the Hebrew University of Jerusalem
 Boolean Functions: Influence, Threshold, and Noise
 Laci Babai Visits Israel!
 Polymath10 conclusion
Top Posts & Pages
 Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
 A Breakthrough by Maryna Viazovska Leading to the Long Awaited Solutions for the Densest Packing Problem in Dimensions 8 and 24
 Extremal Combinatorics IV: Shifting
 The seventeen camels riddle, and Noga Alon's camel proof and algorithms
 Randomness in Nature
 In how many ways you can chose a committee of three students from a class of ten students?
 Randomness in Nature II
 The Erdős Szekeres polygon problem  Solved asymptotically by Andrew Suk.
 Thilo Weinert: Transfinite Ramsey Numbers
RSS
Category Archives: Computer Science and Optimization
Ryan O’Donnell: Analysis of Boolean Function
Ryan O’Donnell has begun writing a book about Fourier analysis of Boolean functions and he serializes it on a blog entiled Analysis of Boolean Function. New sections appear on Mondays, Wednesdays, and Fridays. Besides covering the basic theory, Ryan intends to describe applications … Continue reading
Cap Sets, Sunflowers, and Matrix Multiplication
This post follows a recent paper On sunflowers and matrix multiplication by Noga Alon, Amir Spilka, and Christopher Umens (ASU11) which rely on an earlier paper Grouptheoretic algorithms for matrix multiplication, by Henry Cohn, Robert Kleinberg, Balasz Szegedy, and Christopher Umans (CKSU05), … Continue reading
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
The AC0 Prime Number Conjecture
Möbius randomness and computational complexity Last spring Peter Sarnak gave a thoughtprovoking lecture in Jerusalem. (Here are the very interesting slides of a similar lecture at I.A.S.) Here is a variation of the type of questions Peter has raised. The Prime … 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
IPAM Remote Blogging: SantosWeibel 25Vertices Prismatoid and Prismatoids with large Width
Here is a web page by Christope Weibel on the improved counterexample. The IPAM webpage contains now slides of some of the lectures. Here are Santos’s slides. The last section contains some recent results on the “width of 5prismatoids” A prismatoid is a polytope … Continue reading
Remote Blogging: Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?
Here are some links and posts related to some of the talks in IPAM’s workshop “Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?” I will be happy to add links to pdf’s of the presentations and to relevant papers. Descriptions and … Continue reading
Is Backgammon in P?
The Complexity of ZeroSum Stochastic Games with Perfect Information Is there a polynomial time algorithm for chess? Well, if we consider the complexity of chess in terms of the board size then it is fair to think that the answer is … Continue reading
To Life, to Science and to Innovations
ICS2011 at ITCS, Tsinghua University, Beijing, China The title of this post “To life, to Science and to Innovations” was Silvio Micali’s toast at the second conference on Innovations in Computer Science and Silvio’s words have a good chance of becomeing the official toast of … Continue reading