In machine learning, as throughout computer science, there is a tradeoff between expressiveness and tractability. On the one hand, we need powerful model classes to capture the richness and complexity of the real world. On the other, we need inference in those models to remain tractable, otherwise their potential for widespread practical use is limited. Deep learning can induce powerful representations, with multiple layers of latent variables, but these models are generally intractable. We are developing new classes of similarly expressive but still tractable models, including sum-product networks and tractable Markov logic. These models capture both class-subclass and part-subpart structure in the domain, and are in some aspects more expressive than traditional graphical models like Bayesian networks and Markov random fields. Research includes designing representations, studying their properties, developing efficient algorithms for learning them, and applications to challenging problems in natural language understanding, vision, and other areas.