What is background independence and how important is it? 
*

*What is background independence and how important is it?

*In order to be a theory of everything, will the final string-theory/m-theory have to be background independent? 

*Does the current lack of background independence show string theory is currently NOT a theory of everything? 
My understanding from Wikipedia is that the ADS/CFT shows hopeful hints. Are there any recent papers that have made progress in this direction?
I've tried google but get haven't been able to get a definitive answer to this question.
I found this  interesting post by Lubos Motl, but it is from 2005.
 A: *

*Background independence is generally the independence of the equations defining a theory on all the allowed values of its degrees of freedom, especially values of spacetime fields, especially the metric tensor. However, this concept has various levels that are inequivalent and the differences are often important to answer questions about the "necessity" of background independence, see below.

*We don't know. The [manifest, see below] background independence is an aesthetic expectation, one could say a prejudice, that we cannot prove in any scientific way, so the progress in science may show that it has been a good guide or it was a misleading excessive constraint. For several centuries, we have known that science can't systematically make progress by imposing arbitrary philosophical dogmas and stubbornly defending them. Science often finds out that some philosophical expectations, however "beautiful" or "convincing", have been invalid. Expectations about the "background independence" aren't an exception. Again, it is unknown whether the final "best" form of a theory of everything (if there exists "one best form" at all, which is another albeit related "if") will be [manifestly] background-independent.

*No, there's no known way to show that the lack of background independence already implies that a theory isn't a complete theory of all interactions and types of matter. Some necessary conditions for consistency may be understood in the future but at this moment, it's a speculation whether they exist.
Now, the subtleties. You implicitly wrote that string theory is background-dependent. This is a very delicate question. Some formulations (particular sets of equations used to define the theory, at least for a subclass of situations) such as AdS/CFT or Matrix theory are background-dependent. For example, AdS/CFT is formulated as a theory with a preferred background, the empty space $AdS_d\times M$, and all other states are built "on top of that". Similarly, matrix theory defines the theory for the flat space times some simple manifold (torus, K3, etc.). There is no way to see "completely" different backgrounds in this picture and even the equivalence with other nearby shapes of spacetime is far from obvious. In Matrix theory, one has to construct a new matrix model for a new background (this fact is a part of the light-cone gauge package).
However, these are just observations about what the equations "look like". Invariant statements about a theory clearly shouldn't depend on the way how equations "look like", about some possibly misleading coating on the surface: they should only depend on the actual mathematical and physical properties of the theory that may be measured. When we are asking questions about the validity or completeness of a theory, we should really be talking not about "background independence seen in the equations" but rather "background independence of the dynamics".
The dynamics of string theory is demonstrably background-independent.
This point may be shown in most formulations we know. Perturbative string theory (which requires the string coupling to remain weak and uses the weakness to organize all the around "fundamental strings" as the only elementary objects while everything else is a "soliton" or "composite") is a power-law expansion around a predetermined background but we may easily show that if we define perturbative string theory as an expansion around a different background, we get an equivalent theory. One background may be obtained from another background by adding actual physical excitations (a coherent state of gravitons and moduli) allowed by this "another background". There's only one perturbative superstring theory in this sense – whose spacetime fields may be divided to "background" and "excitations" in various ways. But the freedom to divide the fields into "background" and "excitations around it" in many ways isn't a vice in any sense. It is a virtue and, one could say, a necessity because a preferred background (identified with the vacuum ground state) is needed to describe the Hilbert space in an explicit way, approximately as a Fock space.
There is a related question whether the "space of possible backgrounds" is connected. Much of it is connected by dualities and various transitions: T-dualities, S-dualities, U-dualities, conifold and flop transitions, and various related ones that are more fancy and understood by fewer people. It's much more connected than people would be imagining in the 1980s. When we look at simple and symmetric enough vacua, they really seem to be connected: there's just one component of string/M-theory. On the other hand, the total connectedness isn't a dogma. It's a scientific – and mathematical – question whose both answers are conceivable until proved otherwise. The same equations may admit solutions that can't be deformed to one another at all. My ex-adviser Tom Banks is a defender of the viewpoint that sufficiently different backgrounds in string/M-theory should be considered disconnected although his quantum-gravity-based reasoning isn't quite comprehensible to anyone else.
When we talk about background independence, there is one more technical question, namely whether we want the theory to have the same form for all backgrounds including those that change the spacetime at infinity, or just backgrounds that preserve the fields in the asymptotic region. AdS/CFT is background-dependent in one sense because it requires the fields at infinity to converge to the $AdS_d\times M$ geometry with all the fields at their expected values (usually zero). Generally, configurations that change the asymptotic region are "heavily infinite-energy" states that can't really be constructed reliably in the original CFT. However, if you only consider backgrounds that differ in the "bulk", one could still say that even AdS/CFT (and similarly Matrix theory) is background-independent although not manifestly so.
Now, the big elephant is "manifest background independence", a form of equations that don't try to show you any preferred background at all and that are as easy (or difficult) to be applied to one background as any other, arbitrarily faraway background. All the backgrounds should emerge as solutions and they should emerge "with the same ease". This is the "manifest background independence". Some people always mean "manifest background independence" when they talk about "background independence": it should be really easy to see that all the backgrounds follow from the same equations, they think. Again, it's an aesthetic expectation that can't be shown "necessary" for anything in physics, not even the "completeness" of a theory as a final TOE.
There are limited successes. For example, the cubic Witten's open string field theory (of the Chern-Simons type) may be written in the background-independent way so that the cubic term is the only term in the action that is left. It's elegant but in reality, we always solve the equations so that we find a background-like solution and expand around it, to get back to the quadratic plus cubic (Chern-Simons-like) form of the action. While the purely cubic starting point is elegant, we are not learning too much from the first step: we're just reformulating the consistency conditions for the backgrounds as the fact that they solve some (somewhat formal) equations.
String field theory is only good to study perturbative stringy physics (and for some technical reasos, it's actually fully working for processes with internal open strings only although all closed string states may be seen as poles in the scattering amplitudes). Nonperturbatively (at strong coupling), background independence becomes harder because it should make all S-dualities (equivalence between strongly coupled string theory of one type and weakly coupled string theory of another type or the same type) manifest. Despite the overwhelming evidence supporting dualities, there's no known formulation that makes all of them manifest.
There's no way to convincingly argue that there's something wrong about this situation. In fact, one could go further. One could say that physicists have accumulated circumstantial evidence that "the formulation making all symmetries and relationships manifest" is a chimera, whether we like the flavor of these results or not. It's quite a typical situation that formulations making some features of the theory manifest make other features of the theory "hard to see" and vice versa. Because it's so typical, it could even be a "law" – a new kind of "complementarity" which goes directly against "background independence" – although we would have to formulate the law rigorously and no one knows how to do so.
For example, ordinary perturbative string theory in spaces asymptoting the 10-dimensional Minkowski space may be written down using "covariant" equations. That's the word for a description that makes the spacetime Lorentz symmetry manifest. But when we do so, the unitarity – especially the absence of negative-norm "ghost" states in the spectrum – becomes hard to prove. And vice versa. The light-cone gauge formulations make the unitarity manifest but they obscure the symmetry under some generators of the Lorentz symmetry. It's sort of inevitable.
Also, the covariant approaches (RNS) make the spacetime supersymmetry somewhat hard to prove. This "complementarity" may not be inevitable; Nathan Berkovits' pure spinor formalism, if it works and I bet it does, makes both the Lorentz symmetry and the supersymmetry manifest. It's also close to a light-cone gauge Green-Schwarz description so the "unitarity" isn't too hard, either. However, it has an infinite number of world sheet ghosts (and ghosts for ghosts, and so on, indefinitely) and one could argue that the absence of various problems connected with them is non-manifest.
The landscape of string/M-theory, as we know it today, is rather complicated and has lots of structure. We must sharpen our tools if we want to study some transitions in this landscape, a region of it. The tools needed for distinct questions seem to be inequivalent. A manifest background-independent formulation of string theory would make all these transitions equally accessible – all the tools would really be "one tool" used in many ways. In some sense, this desired construction would have to unify "all branches of maths" that become relevant for the research of separated questions in various corners of string theory (and believe me, it does look like different corners of string theory force you to learn functions and algebraic and geometric structures that are really different, studied by very different mathematicians etc.). It would be a formulation that stands "well above" this whole landscape "manifold". Such a "one size fits all" formulation is intriguing but it is in no way guaranteed to exist and failures of attempts to find it over the years provide us with some evidence (although not a proof) that it doesn't exist.
Instead, many people are imagining that string theory's landscape is a sort of a manifold that must inevitably be described by "patches" that are smoothly glued to their neighbors. Each patch requires somewhat different maths. Just like manifolds may be described in terms of an atlas of patches, the same thing could be true for the landscape of string/M-theory. We also have more unified, less fragmented ways to think about the manifolds. It's not clear whether the counterpart of these ways is possible for the stringy landscape and if it is possible, whether the human mind is capable of finding it.
So nothing is guaranteed. The transitions in the landscape and the dualities and duality groups are so mathematically diverse and rich that a formulation that "spits out" all of them as solutions to some universal equations or conditions is an ambitious goal, indeed. It may be impossible to find it.
I also want to mention one simple point about non-stringy theories. The background independence is sometimes used as a "marketing slogan" for some non-stringy proposals but the slogan is extremely misleading because instead of explaining all the duality groups in the whole landscape, including e.g. the $E_{7(7)}(Z)$ U-duality group of M-theory on a seven-torus (these exceptional Lie groups are rather complicated by themselves, and they should appear as one of the solutions to some conditions among many), these alternative theories rather tell you that no spacetime and no transitions and no interesting dualities exist at all. While their proponents try to convince you that you should like this answer, this answer is obviously wrong because the transitions, dualities, and especially the spacetime itself does exist. This version of "background-independent theories" should be called "backgrounds-prohibiting theories" or "spacetime-prohibiting theories" and of course, the fact that one can't derive any realistic spacetimes out of them is a reason to immediately abandon them, not to consider them viable competitors of string/M-theory. This version of "background independence" has absolutely nothing to do with the ambitious goal of finding rules that allow us to derive "all dualities and transitions we know in physics (not only the new, purely stringy ones but also the older ones that have been known in physics before string theory)" as solutions. Instead, this marketing type of "background independence" is a sleight of hand to argue that we should forget all the physics and there's nothing to explain, no dualities, no transitions,  no moduli spaces, no spacetime. And when we believe there's nothing out there, no relevant maths etc., a theory of everything becomes equivalent to a theory of nothing and it's easy to write it down. That's a wrong and intellectually vacuous answer that should be refused, not explained or adopted.
To summarize, background independence is generally an attempt to find as universal, all-encompassing, and elegant formulations of theories, especially string/M-theory, as possible, but it is an emotional expectation, not a solid condition that theories have to obey, and we must actually listen to the evidence if we want to know whether the expectation is right, to what extent it is right, and what new related issues we have to learn even though we had no idea they could matter. It's also possible that the background-independent equations are actually "conditions of consistency of quantum gravity" (which may be written by some quantitative conditions whose precise form is only partially known): when we try to find all the solutions, we find the whole landscape of string/M-theory. Such a formulation of string/M-theory would be extremely non-constructive but after all, that's what "background independence" always wanted. Maybe we don't want too much of background independence.
A: Lubos's answer is correct.  But it's worth stressing that there is no agreed upon definiton of 'background independance' in general. 
The literature is full of definitions that differ from one another, both in intent, philosophy and crucially mathematical detail.  Different theories will use the word in very different ways, and it is often confusing to sort through (especially when you are trying to use the concept as a sieve of theories)
In fact, different types of theories won't even agree what a 'background' is in the first place.  For instance, in GR a backround is a classical solution of Einstein's equation, given by a metric tensor.  Whereas in String theory there is no background that only involves a metric tensor.  Instead a background is a far more general creature with various moduli and extra fields (in fact an infinite tower of vibrational modes).  
Further backround independance is often confused with various buzzwords that mean different things in different contexts.  You might hear the words 'no prior geometry', 'lack of absolute structure' and it is also often confused (erroneously in my opinion) with general covariance and the use of the background field method in field theory.   
In some sense the intent is really to seperate the things that remain fixed in a theory, and those that are left to be dynamic or varied over.  Anderson in his GR book from the 1960s started this type of program, and it was generalized by a number of people to quantum gravity in the 80s.  I think its fair to say that this type of idea meets with a number of problems.  First of which is that it is often easy to take something that is fixed, and make it look dynamic by various tricks.  And then there is the reverse.  You can take a theory that is dynamic, and write it in a formalism where things are allowed to be fixed.
So it's really difficult to actually sort out the essential physical idea, rather than simply take it as an elegant aesthetic criteria.
A: Maxwell's theory in Minkowski spacetime is background-dependent because the Minkowski metric - a fixed geometric structure - is PART of the FORMULATION of the theory. The Minkowski metric appears in the action principle for example.
General relativity is profoundly different because there is no fixed background geometric structure in the Einstein-Hilbert action, there is no fixed geometric structure that is part of the formulation of the theory. GR is background-independent.
The relation to general covariance is Einstein's hole argument:
General covariance says that the laws of physics should take the same form in all coordinates systems. Say you have x-coordinates and y-coordinates, saying the equation of motion have the same form is the same thing as saying you have exactly the same differential equation to solve but in the first case the independent variable is x but in the second differential equation the independent variable is y. (In the Hole argument we will think about just the vacuum field equations to start off with).
Now if you think about this, as Einstein, you will conclude that as soon as you find a metric tensor function that solves the differential equation in the x-coordinates, just simply write down the same function but replace x with y and that WILL solve the differential equation in the y-coordinates. As the to metric tensor functions have the same form but belong to different coordinate systems they will impose DIFFERENT spacetime geometries!
Now here comes the problem that concerned Einstein. Say you have an initial spatial surface given by t=0, and beyond the surface you have a closed region of spacetime devoid of matter (the Hole). Say the two coordinate systems coincide with each other everywhere outside the Hole but differ inside the Hole...you will then have two solutions, they both have the same initial conditions but they impose a different geometry inside the hole. the conclusion is that GR does not determine the distance between spacetime points inside the Hole. Einstein recoiled at this and tried to replace the principle of general covariance only to resolve the Hole argument 1915.
To understand the resolution you first have to understand how these two solutions are related to each other. As they both have the same functional form that means they assume all the same values, they just assume them a different points. So one solution is related to the other by actively dragging the original metric tensor function over the manifold while keeping the coordinate lines attached. This is equivalent to what mathematicians would call a diffeomorphism. When physicist hear diffeomorphism they tend to think you are talking about a mere coordinate transform but really you are talking about something much more radical.
Einstein's resolution was basically to add some material objects and to and define physical points with respect to the matter. He defined a physical point as where two particle tragectories intersected each other. The distance between by points defined this way have physical meaning and are determined by the theory because when you perform a diffeomorphism you simultaneously drag the gravitational field and the matter together.
Or if you like you can introduce a matter field, then the coincidences between the value the gravitational field takes "where" the matter field takes such and such a value ARE preserved under diffeomorphisms. So we can form a relational notion of the matter located with respect to the gravitational field and vise-versa. What Einstein understood was that physical entities can ONLY be located with respect to each other. As Rovelli puts it GR is no longer a theory of fields living over spacetime but is a theory of fields living on top of other fields. Einstein's resolution is the origin of the saying "the stage disappears and becomes one of the actors", and is what Einstein was referring to when he made his remark "beyond my wildest expectations".
Witten understands the importance of diffeomorphism invariance. Because spacetime points defined by coordinate values have no operational meaning, Witten has claimed that in GR there cannot be a local gauge-invariant field, a field that is function of spacetime coordinates, therefore we should replace point particles with strings - see 16:25 onwards of his Newton lecture: https://www.youtube.com/watch?v=XegXKOvhU9Y (people in loop quantum gravity would argue otherwise though!).
Witten would like a background-independent formulation of string theory. In the words of Ed Witten:
“Finding the right framework for an intrinsic, background independent formulation of string theory is one of the main problems in string theory, and so far has remained out of reach.” ... “This problem is fundamental because it is here that one really has to address the question of what kind of geometrical
object the string represents.” [E Witten:  “Quantum background independence in
string theory” hep-th/9306122. “On Background independent open-string field theory” hep-th/9208027]
A: A key point to make is that people think that a solution to Einstein's equations is a particular space-time geometry, a particular background geometry, when really a solution is an equivalence class of distinct geometries related to each other through (what mathematicians call) diffeomorphisms. And if you want to talk about observables and hence physics, you have to be very careful that what you are calculating or doing is true for ALL members of this equivalence class.
The existence of this equivalence class does not then mean there is no notion of space-time geometry, it just means you have to understand geometry in a relational sense. But then relational notions of geometry is nothing new! Rovelli gives the example of Descartes - see his book "Quantum gravity" - draft version can be found at http://www.cpt.univ-mrs.fr/~rovelli/book.pdf 
