Abstract: There are two big strands of algorithm analysis, in one of which complexity theory and big-O upper bounds are dominant. This talk is about the other one, which grew from Knuth's original analysis of linear probing hashing in 1962, and is interested in precise average-case analysis of commonly used algorithms. The mathematical machinery, which has many other applications, involves large combinatorial structures, generating functions, complex analysis and asymptotic analysis. It was well refined by Flajolet, Sedgewick and others in the case of a single variable. After discussing the above I will move on to describe the much greater difficulties in the multivariate case and how a joint project with Robin Pemantle (UPenn) has made major progress. The talk is aimed at introducing this strand of my research, and me and my work more generally.
The CICS Theory Seminar is free and open to the public. If you are interested in giving a talk, please email Cameron Musco or Rik Sengupta. Note that in addition to being a public lecture series, this is also a one-credit graduate seminar (CompSci 891M) that can be taken repeatedly for credit.