What is the black hole information paradox really? Preliminaries
What is the black hole information paradox really? Is it a sophisticated way to ponder and debate the existence of an operator  on the boundary that can tease out the interior of a black hole? If this is the case, can one formulate the problem completely without invoking gauge/gravity duality in at least some crude fashion?  I have heard popular accounts claiming to be some matter of "dilution of encoded distinctions" of in-falling objects. This makes me think plausibly "wrongly of it as some statistical mechanics problem". In fact when I first heard about it I thought it was either just something that could be completely articulated as a GR problem or a QFT problem.
The Question
What is the canonical statement of the problem? Why was I wrong in my youth to think that one needed some form of Yang Mills to describe the problem? 
 A: The information paradox is 40-45 years old. AdS/CFT is not even 20 years old, modern string theory (after D-branes) is probably 25 years old. This is to say that the information paradox doesn't need any of these, even though of course you can try to solve it in the context of string theory.
In a nutshell, the information paradox is a sharp theoretical inconsistency between quantum field theory and general relativity. It shows that one must go beyond these to theory, in particular toward a quantum-gravity theory.
-The general relativity side of the process is: an object fall into a black hole, the black hole is black (that is no object can escape) and is bald (it has no hair, that is the information carried by the hole is rescricted to a few parameters like charge, mass and angular momentum).
-The quantum field theory side is that the black hole evaporates thermally, nothing is left behind. Unitarity is violated, since the process can be seen as sending a pure state, entangling the radiation coming from the hole with the hole itself and then ending up with a radiation maximally entangled with nothing. That is, a pure state evolved in a mixed state, with no information of the initial infos. Information is lost.
A: This has been open for a while so I will bite.
The information paradox has two versions or iterations. The previous one is that information is demolished by black holes by the entropy of its event horizon and that Hawking radiation that is emitted is in a pure blackbody distribution. A blackbody distribution of radiation is maximally random. If you make a plot of frequencies  vs intensity, a completely coherent form of radiation is a spike at one frequency. So for $n$ possible frequencies, thinking in a discrete sense, at a certain frequency you have the probability for that $p(\nu)~=~1$. The Shannon information-entropy equation for the $n^{th}$ frequency only occupied is then
$$
\sum_i p(\nu_i)log(p(\nu_i))~=~p(\nu_n)log(p(\nu_n))~=~log(1)~=~0.
$$
There is no entropy. For a Boltzmann or Bose-Einstein distribution the result is more general. In the case of Hawking radiation the entropy result is maximal.
Entropy is something we still debate over. The Boltzmann constant $k_B~=~1.38\times 10^{-23}j/K$ is a conversion factor between energy and temperature. For a system with $N$ particles in thermal distribution the entropy is $S~=~\frac{3}{2}Nk_B$ and the thermal energy of this system is $E~=~\frac{3}{2}Nk_BT$. The question over the information paradox is over whether entropy is a measure of one's inability to access information or whether information is completely erased.
The problem with the idea that entropy is this objective measure of information and that the second law of thermodynamics $dS/dt~\ge~0$ means information is destroyed is that it is hard to conclude this does not mean energy is destroyed or created. With $dE~=~dQ~-~TdS$, we have a picture that the increase in entropy is a conversion process. In this perspective entropy is more of a subjective quantity. 
The holographic principle works on this perspective. For a Schwarzschild black hole the tortoise coordinate found by integrating on the metric is
$$
r^*~=~ r~-~2m~log(r~-~ 2m)
$$
and the time it takes a signal emitted near the horizon to reach a distant observer $t~=~r^*/c$ is very large. An observer who witnesses material and information falling onto a black hole never witnesses it being destroyed. In fact with Hawking radiation one has to conclude that information very near the horizon is also appearing as Hawking radiation. In this perspective it then appears that information is never really destroyed by a black hole.
This does not end the story however.  Almheiri, Marolf, Polchinski, and Sully (AMPS) found that something goes wrong. Hawking radiation involves a vacuum polarization falling in and out of the black hole. This means that Hawking radiation is quantum entangled with the black hole. The entanglement must grow monotonically and violate certain entropy bounds. Further, with considerations of the interior it also means this entanglement between two states becomes one with three states. A bipartite entanglement evolves into a tripartite entanglement. This is not possible by unitary evolution of quantum mechanics, and is called the quantum monogamy principle. This means according to AMPS one must either abandon unitarity or the equivalence principle of general relativity. With the latter it is then argued that the horizon over time evolves into a sort of singularity or firewall.
Verlinde published a paper that argued that black hole quantum mechanics is ultimately an open system. Susskind wrote a paper that argued this openness is due to the fact that the interior states are actually the same as the exterior states because the black hole is a nontraversable wormhole. This then prevents the problem of violating quantum monogamy. It appears that conservation of information is still holding the front. This is still of course research in progress.
