I will discuss the gauge/string duality and non-critical strings, with a particular emphasis on the discretized, or matrix model, approach. This approach has been recently generalized to four dimensional non-critical strings, and yields fully non-perturbative results. An important insight on the gauge theory side is that instantons yield a non-trivial 1/N expansion at strong coupling, and generate open string contributions, in addition to the familiar closed strings from Feynman
diagrams.