Why do steel Newton's balls work? To my understanding when an elastic ball (which can perfectly deform) collides with a hard surface,  they exert an equal and opposite force on each other. At some point, the ball's velocity must be 0. However, at this point (when velocity is 0) how can the floor be applying an upward accelerating force (beyond the normal force that only counters the weight force)?
However, if the balls got deformed, I understand that the elastic force will push it off the floor. That all makes sense until I thought about Newton's cradle when you have 2 steel balls smacking into each other. It sure doesn't look like the steel is deforming a whole lot. 
So, does the steel actually "deform" and are elastic collisions in general possible without temporary deformation?
 A: Even a very small steel deformation can hold a lot of elastic energy. Steel has a Young's modulus of about $E=200$ GPa, so the force it exerts if it is compressed by a distance $\Delta L$ is $$F=\frac{EA}{L_0}\Delta L$$ where $A$ is the area and $L_0$ is the original thickness. So an indentation $\Delta L/L_0=0.00005$ (1 $\mu$m of a 2 cm ball) gives a force of 10 megaNewton over the contact surface - the actual compression from a Newton ball is likely far smaller. This paper found a contact force a bit larger than a kN when a dropped steel ball bounced. 
The total time the balls stay pressed together is roughly the time it takes for a sound wave to progress from the impact across the ball, $r/c_s$. For a 2cm steel ball this is $0.35\cdot 10^{-5}$ s. But since the impact speed is about 1 m/s that means the indentation is also at most a few $\mu$m.
So you will not see the elastic compression - it is too small and fast.
A: Steel does deform. The deformation during a collision of steel balls can be calculated using the Hertz impact theory (see the expression for compression distance in http://www.physics.emory.edu/faculty/brody/Advanced%20Lab/Advanced-Lab-Elasticity3.pdf ).
A: Most solid materials are elastic, just like the elastic ball.  So, in simple terms, the floor acts like a spring when you bounce a ball off of it.  The material is stiff, though, so it only deforms a very tiny amount to generate the reaction force.
You could measure the deformation of the floor with proper equipment.  You could accurately simulate the deformation of the floor with a computer.  You just can't see the deformation because it is small, and it all happens really fast.
A floor, a steel ball, even big rock all deform a very small amount, like a spring, when a force is applied.
