In string theory, we now have overwhelming evidence that space is an emergent phenomenon. It is not just one of Witten's progressive ideas. Instead, it is an idea that even Brian Greene often explains to his popular audience. The statement means that we should not think about the objects and events to take place on a well-defined background geometry; we should not think about space and time as basic assumptions whose existence is guaranteed before we consider anything else.
General relativity has taught us that space and time should not be thought of as a static arena for other phenomena. Instead, they are dynamical players: the curvature of space and time tells matter how it should move, and matter influences spacetime's curvature. But the lesson of quantum gravity and string theory in particular is more far-reaching: space and time do not have to exist at the very beginning - they are kind of illusions. Moreover, there can be many different illusionary geometries that emerge if we look at the same physical system.
Quantum mechanics guarantees that the concept of a completely smooth geometry is incompatible with quantum mechanics that make things fluctuate. But string theory goes much further. Geometric descriptions, such as general relativity, are only approximations valid at very long distances. At very short distances, comparable to the "length of the string" (string scale) or "the smallest meaningful black hole" (the Planck scale), physics does not admit a simple description in terms of usual geometry. Geometry is generalized to something much more grandiose, and the difference between geometry and matter disappears - this is the content of unification of gravity with other forces and matter.
String theory implies a lot of dualities, i.e. equivalences between seemingly different theories. For example, T-duality shows that a universe with a circular dimension of radius R is physically indistinguishable from another Universe with a circular dimension L^2/R, where L is the constant length associated with the strings (string scale). A radius smaller than L has identical physics as the inverse radius which is greater than L. If one compares these two equivalent universes, she must first create a dictionary: for example, the objects with momentum N/R in the "small" universe map to string that are wound N times around the circle of the large universe, and vice versa.
The momentum is the generator of translations, and you can see above that it behaves physically in the same way as the winding number (how many times a string is wrapped). It is just a matter of convenience whether we call something "momentum" or a "winding number" in these Universes with circular dimensions. Also, mirror symmetry (which is really a triple T-duality performed in a smart way) analogously relates two very different 6-dimensional shapes (Calabi-Yau mirror dual manifolds) which nevertheless lead to identical physics if you use them as the hidden dimensions for a string theory.
The momenta etc. can have the interpretation of winding numbers, electric charges, and so on, in various equivalent descriptions of the reality. Different equivalent descriptions of reality do not agree what the spacetime geometry is. One of them can become much more reasonable than others, but it is only in the case in which the radii and size of this geometry are much greater than the fundamental scale (for example the string scale). In this case, one geometry is much more realistic and convenient description than others. But because I need the size of the geometry to be large, geometry is just an emergent phenomenon. At very short distances comparable to the fundamental scale, geometry is replaced by a generalized, quantum, stringy geometry that contains much more stuff that we don't usually consider to be "geometry".
Geometry becomes unseparable from other physical concepts, objects and phenomena. The notion of topology of the space(time) manifold also makes sense as the approximation in the limit where we study the long-distance behavior only. At very short distances, quantum mechanics guarantees that even the topology is fluctuating (quantum foam) - one can imagine that the geometry at very short distances becomes non-commutative, although one must be ready that the word "non-commutative" in the most general situation must be extended and generalized.
Non-commutative geometry is something that allows one to replace functions on a manifold (that commute with each other, if they are multiplied) by discrete matrices (which do not commute) - the smooth, commutative geometry appears from very large matrices. Much like in the naive discrete approaches to quantum gravity (such as "loop quantum gravity"), the character of the spacetime is very different if we probe it with a very good resolution. However, the effects in string theory do not say simply that "space is made of atoms of space". Instead, there are many new objects, fields, concepts appearing in this regime and all of them are "fuzzy" and mixed up in some way. This fuzziness also allows topology of space to change smoothly once a topologically nontrivial submanifold shrinks to very short, substringy distances.
And what about time?
On the other hand, the mystery of emergent time is a great question - David Gross was exactly mentioning this puzzle in his talk at the KITP.
Special relativity guraantees that if space is emergent, time must be emergent as well. String theory in various formulations is Lorentz-invariant, and therefore it should agree with this principle. However the specific formulations we have are able to show that space is emergent, but time is never emergent in these pictures. Well, if you have operators or wavefunctions or whatever, and even if you want to predict the future from the past, you need a concept of time.
Although I wrote that string theory respects the laws of relativity, but it does not allow time to emerge as easily as space, it's not a contradiction. The manipulations that we are able to make with the space cannot be easily done with time - time is different in details, at the end, for example it can have an arrow (time-like intervals have a universal arrow, past vs. future, while spacelike intervals don't).
If one says that time is emergent, the idea of predicting the future from the past must be approximate and emergent as well. Well, it's not shocking if we study the S-matrix: it is the set of amplitudes between the infinite past and infinite future, and with infinite separation, time becomes sharp and well-defined much like space.
If we look at the gauge-fixed descriptions, such as the light cone gauge ones (Matrix theory, for example), the gauge-fixing always guarantees that there is a well-defined notion of time, and the other operators are simply functions of it. There have been speculations, e.g. by Aharony and Banks, see
http://arxiv.org/abs/hep-th/9812237
that M-theory - and little string theory in particular - had some inherent non-locality in time. But these conclusions have not been universally accepted yet, I would say. A few more comments: if we adopt the formalism of the S-matrix, the questions go away - the only invariant object is the amplitude at infinite separations both in space and time, and these emergent notions are already "emerged fully" once we study the S-matrix.
However, the S-matrix is not enough to study some detailed questions such as those in cosmology. If we want to understand the early cosmology, it seems sort of necessary (or useful) to understand in what sense the time emerges after the Big Bang. It probably does not make sense to ask what was "before the Big Bang" or "before the Universe was Planckian in size" - because before this moment, the concept of time (and the word "before") had not emerged yet. Nevertheless there is a clear feeling that something is missing, and we should be able to say something about "which universes can emerge" from the Big-Bang and which cannot. And the answer about this Planckian super-early cosmology seems to require us to learn HOW time can be emerging and what is it emerging from.
Although the usual framework based on predictions about the future only makes sense once the concept of time emerges fully - i.e. at time intervals longer than the Planck time - the question about physics "without time, without the future, and without the past" continues to seem necessary for very early cosmology. How can we replace time with something more general?