Combinatorial Methods for Learning and Information Theory

Combinatorial structures are ubiquitous in Computer Science - graphs, trees, strings, and automata are all used in various subfields as modeling tools and objects of study in their own right. Networks can represent connections between wireless routers, or relations between data in a server. Trees are a natural way of encoding data at a high level, and strings are the low-level equivalent stored in physical memory. Automata are a natural definition of limited computational devices. This thesis is concerned with these structures in a learning-theoretic setting. We will study four notions of learning. In Chapter 2, we analyze a message passing protocol over graphs, where nodes in the graph are attempting to track the data leaving a source. In this setting, the data at the source is the learned quantity. In chapter 3, we study the sample complexity of recovering arbitrary strings and trees passed through a lossy channel. Here, the the original string/tree is the object to be learned. In chapter 4 we study a search game on a graph, where one player moves a token between vertices, and the other must learn the location of this token using limited feedback. Finally, in Chapter 5 we consider a learning protocol over deterministic finite automata, where the learner is given access only to bits generated from a random walk on the automata, and must learn the structure from these bits.