^November December – 2012 ^January

One of the main problems in Statistical Learning Theory is to estimate an unknown function by a function from a given family, using random data. Although seemingly unrelated, it turns out that this question has very strong connections to problems in Asymptotic Geometric Analysis. In this talk I will present some of these connections, and show why some natural problems in Asymptotic Geometric Analysis (e.g., embedding theorems, estimates on the singular values of random matrices, etc), are essential in the study of the basic problems in Learning Theory.

High throughput DNA sequencing has transformed the landscape of genomic data by providing an affordable means to sequence the genomes of numerous species and multiple individuals per species. There has been a particularly dramatic increase in the last five years in the availability of individual human genomes and the genomes of closely related primate species. These data provide a rich source of information about human evolution and the forces that helped shape the human genome. This talk will focus on two specific problems I explored during my postdoctoral research using these new data sets.

The first problem I will be presenting is recovery of ancient human demography and the evolutionary relationships between different human population groups. I developed a new method, called G-PhoCS (Generalized Phylogenetic Coalescent Sampler) to infer demographic parameters along a population tree, and applied this method to the complete genomes of six human individuals from major human population groups. This approach allowed us to recover very ancient trends in human demography dating back as far back as 130 thousand years ago. The second problem is that of inferring signatures of recent natural selection acting on regulatory elements in the human genome. Much of the DNA in the human genome is devoted to the regulation of gene expression, but regulatory DNA elements are typically short, dispersed and often not conserved across long evolutionary timescales. This has made it very difficult for researchers to study the selective constraints that act on regulatory DNA in the human genome. I developed a method, called INSIGHT (Inference of Natural Selection from Interspersed Genomically coHerent elemenTs), that addresses these challenges by making use of individual human genomes and the genomes of closely related primates. This method was used to perform the first comprehensive study of natural selection acting on transcription factor binding sites, which are the most well characterized regulatory elements in the human genome. Our study sheds light on the selective forces that shaped these elements, and has possible implications to the study of human disease.

This talk will highlight the methodological and algorithmic challenges in these problems, and will not require any prior biological knowledge.

Graph products are a basic combinatorial object, introduced by Alfred Whitehead and Bertrand Russell in their 1912 Principia Mathematica. They are widely studied and used in applications in different fields, for example information theory, and hardness of approximation. In the first part of the talk, motivated by a problem in communication, we present a new type of graph product, which we call the Bi-partite Graph Product, or BGP for short. We characterize the spectrum of the BGP, and derive two results: an edge discrepancy result, and a new explicit construction of a co-spectral graph family. In the second part of the talk we show how to use the well-known Tensor graph product to obtain a family of uniquely k-colorable graphs. Our main tool of analysis is Connelly's condition in Rigidity Theory combined with an explicit construction and algebraic calculations of the rigidity stress matrix. Based on joint works with Michael Langberg and Igor Park.

Pebble automata (PA) over infinite alphabets are an extension of the classical PA. They were introduced by Neven, Schwentick, and V. Vianu about ten years ago and recently found applications in XML. The notion of PA over infinite alphabets is very robust. In addition to equivalence of various models of PA, the set of languages they accept is closed under all Boolean operations. However, the emptiness problem for these languages is undecidable for three or more pebbles. Reducing Hilbert's tenth problem to the emptiness problem for 2-PA languages, we prove that the latter is also undecidable. In addition, we present an example of a 3-PA language that is not accepted by 2-PA, i,e., 2-PA automata are weaker than 3-PA. Finally, we show that 2-PA can accept a non-semi-linear language. The talk does not presume any prior knowledge of models of computation over infinite alphabets. Joint work with Tony Tan.