This course introduces the students to constructing rigorous mathematical models for learning, reasoning, and analyzing their efficiency with techniques from the theory of computational complexity. The course also demonstrates some modern approaches to coupling the theories of learning and knowledge representation to create machines which use learned symbolic knowledge to reason and make decisions based on that knowledge.