Open Problems in High Dimension Geometry

Open problems on the structure of convex bodies in high dimensions

Santosh Vempala is one of world’s leading researchers in computational complexity in general, and especially in the subarea of high dimensional computational geometry. Since coming to Georgia Tech, he has created the ARC, which stands for Algorithms and Randomness Center. His center has been extremely successful in creating cross cultural connections between theorists and other researchers with real problems.

Today I want to discuss some of the problems that he is working on in the area of high dimension convex bodies. There are many interesting open problems in this area, and I thought it would be fun to list those that his group is working on right now. I want to thank Luis Rademacher, one of his postdoc’s, for helping me.

Santosh, besides his terrific research agenda in high dimension geometry and in computational complexity, is involved in an area that he calls Computing for Good. This work consists of Santosh and his students, often undergraduates, working on problems that have social good attached to them. He ran an entire course this spring with Ellen Zegura on this topic.

For example, Santosh has recently worked closely with the Centers for Disease Control (CDC) in Atlanta on systems to track blood supply. In many countries blood supply and hospital blood requirements are tracked by pencil and paper, which causes errors: blood is misplaced, it is sent late to hospitals, or it is delivered in the wrong amount. Santosh’s team has worked on creating a web based system, that will replace the old pencil and paper methods.

A web system sounds like an obvious, if straightforward solution to the blood supply problem. It is not. The challenge is that such a systems must work in places were there is often poor connections to the Internet. The connections are usually both slow and have low availability. Slow and unavailable internet connections is not a firm basis on which to build a system that manages life-saving blood.

Santosh’s clever insight is that web services for these situations raise fundamental new computer science questions. Further he and his students have solved these problems, with new techniques. Thus, besides helping get blood to the people that need it, when they need it, Santosh’s team has done basic research in the construction of web services. Pretty cool.

Convex Bodies in High Dimensions

All these results and questions concern the behavior and structure of high dimension convex bodies. The motivation is clear: convexity is a powerful restriction on a set in high dimensions. Moreover, the restriction is often satisfied in actual applications. So understanding the behavior of convex bodies is of great importance. The other reason is the problems are fun: they are relatively easy to state, but are often very hard to solve.

Convexity is a nice restriction on a body, and in low dimensions our intuition is usually right. As the dimension grows my intuition decays exponentially, and one of two things happens: either the “obvious result” becomes false, or the “obvious result” becomes hard to prove. That is what makes the study of fundamental problems concerning convex bodies so wonderful.

A famous example of this is the Borsuk Conjecture that Karol Borsuk asked in 1932: Can every convex body in be cut into pieces of smaller diameter? A series of positive results followed, first in low dimensions, and then for special types of convex bodies. Then, after years of these partial results, in 1993, Jeff Kahn and Gil Kalai, proved that the conjecture was not even close for general convex bodies. They showed that in general there is a so that

pieces are needed for large enough. Their paper is a classic: it is short and extremely clever. It shows that the conventional wisdom was not even close. I love when this happens–as you know.

Results and Problems

Here are some of the main problems Santosh’s group is currently working on:

Slicing Problem: Is there a universal constant so that every dimensional convex body of volume has a dimensional section of area at least ? This is one of the main open questions in convex geometry. The key is that the area is believed to be a constant part of the volume of the body. The best known depends on the dimension and is due to Jean Bourgain and Bo’az Klartag,

This is an important result because a simple expectation argument would give a bound of order . Thus, they broke through this barrier, but it is a far distance from the conjectured constant bound.

Sylvester’s Problem: The following conjecture implies the slicing conjecture: For a convex body in , let be the expected volume of a random simplex obtained by picking random points from . Then, it is conjectured, that for every the only maximizers of among convex bodies of volume are the -dimensional simplexes.

This is known to be true for due to Wilhelm Blaschke, and is open for higher . The reason it is called Sylvester’s Problem is that Joseph Sylvester asked the following question: if points are chosen at random in the plane, what is the probability that they form a convex quadrilateral? Of course the question is ill-posed because he did not specify a distribution. Actually, there are multiple answers depending on how “random points” in the plane is defined, since the plane is infinite one cannot say that the points come from the uniform distribution.

Reconstruction Problems: Given a dimensional convex body, how many random points from it are needed to reconstruct approximately:

• The body, the best known is due to Luis Rademacher and Navin Goyal.
• The volume, the best known is due to Ronen Eldan.
• The centroid, the best known is which seems to be folklore.
• The covariance, the best known is due to Mark Rudelson.

Recall that if is random in a convex body and is its centroid, then the covariance matrix of is the by matrix having entry equal to the expectation of .

Containment Problem: Let and be two non-empty dimensional convex bodies, with contained in . Suppose further that for every halfspace ,

is small. Then, is it true that is also small? Note, without the containment , the conjecture is known to be false.

Testing Convexity Problem: Suppose that is an arbitrary body in dimensional space. Further, assume with high probability that the span of three random points from the body has a convex intersection with the body. Then, the conjecture is: Is the body is “close” to being convex. This is known to be false for two points.

Open Problems

I have already mentioned several open problems. I guess the open problem is to solve them. The most interesting one to me is the slicing question. Can there really be a constant size slice found for any convex body?

The reason this question seems so interesting is that the normal technology for proving the existence of cuts would be to rely on randomization. But, as I already pointed out that seems to only yield weak bounds. Thus, the exciting possibility is that a solution to the slicing problem would yield new technical methods for understanding convex bodies.

About these ads