Near-Optimal Smoothing of Structured Conditional Probability Matrices Mesrob I. Ohannessian University of California, San Diego Toyota Technological Institute at Chicago San Diego, CA, USA