Some Updates

Jeff Kahn was in town: so we worked together also with Ehud Friedgut and Roy Meshulam (and others) quite intensively. Very nice! Stay tuned for a report!

Polynomial Hirsch conjecture (polymath3): While the conjecture remains wide open there are some interesting developments. The conjecture asserts that the diameter of every d-dimensional polytope with n facets is at most polynomial in d and n. Jesus de Loera and Steve Klee described simplicial polytopes which are not  weakly vertex decomposable and the existence of non weakly k-vertex decomposable polytopes for k up to about \sqrt{d} was proved  by Hähnle, Klee, and Pilaud in the paper  Obstructions to weak decomposability for simplicial polytopes. Karim Adiprasito and Bruno Benedetti proved the Hirsch conjecture for flag polytopes (and manifolds) using CAT(0) methods. Karim will write a guest blog post about it. Stay tuned.

Erdos discrepancy problem (polymath5): Tim Gowers and I have a plan to try soon to revive the EDP project at least for a short while. We plan 3 posts about it in the second half of August over Tim’s blog. Update: The first post EDP22 just appeared.

Polymath7 is going strong on the polymath blog.

Quantum computer debate with Aram Harrow: The most recent post was entitled Can you hear the shape of a quantum computer? Quite an interesting discussion, also on the Quantum pontiff.

“Gold open access” new Forum: See the post and extensive discussion over Gowers’s blog (and also on Tao’s blog).

Telling spheres: Joel Hass was in town and gave a talk about a recent work with Greg Kuperberg: Telling if a 3-manifolds  is a sphere is in co-NP (assuming GRH). This extends Greg’s work on telling unknots. Topology, provides remarkable questions in NP and coNP where proving both sides are hard. My claim to fame is replacing Joel in grading an exam in 1986 (or so) when he got married!

High dimensional expander. My course with Alex Lubotzky on high dimensional expanders ended. A lot of nice things to tell about and we learned quite a few new things. Roy Meshulam concluded his course with a crystal clear lecture on Garland’s method. Maybe we will teach it again after a year break. Meanwhile, Ori Parzanchevski promised me to write something about some recent developments over here. Stay tuned for that too.

16th Midrasha Mathematicae: Our yearly midrasha ran by Aner Shalev was devoted to Words and Growth. Delicious approximate groups and word maps were observed!

Interactive quantum lecture: We had an unususal quantum seminar presentation by Michael Ben-Or on the work A multi-prover interactive proof for NEXP sound against entangled provers by Tsuyoshi Ito and Thomas Vidick. Michael ran Vidick’s videotaped recent talk on the matter and from time to time he and Dorit acted as a pair of prover and the other audience as verifier. (Michael was one of the authors of the very first paper introducing multi-prover interactive proofs.) Update (Jan 2020): for some progress on the problem, see this spectacular paper  by Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen, and this, this, this, and this posts. (The new result is related also to the existence of non-sofic groups; see this 2008 post).

Peter Frankl: I plan on meeting Peter on Friday. Will report.

This entry was posted in Updates. Bookmark the permalink.

4 Responses to Some Updates

  1. “high dimensional expanders” – any chance of lecture notes or at least a list of topics and references appearing here?

  2. Pingback: Even if P=NP we might see no benefit « cartesian product

  3. Pingback: 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. | Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s