For a data structure implementing some abstract data type, in the cell probe model of computation we measure the performance of the data structure solely by the (amortized) number of cells it reads and writes during updates and queries. By allowing the data structure to perform arbitrary calculations and only charging it for the amount of memory it's required to access, a lower bound in the cell probe model is a lower bound on both time and space in any reasonable model of computation.

On the other hand, the strength of the model makes proving lower bounds quite challenging. A breakthrough result by Fredman and Saks (1989) gave an Omega(logn/loglogn) lower bound on the amortized complexity of either updates or queries for the prefix sum abstract data type, introducing a technique called the chronogram technique which has formed the backbone of most breakthrough cell probe since. In particular, the next work on prefix sum lower bounds came over 15 years later when Pătraşcu and Demaine (2006) showed a (tight) lower bound of Omega(logn), which stood as the frontier until the last five years. In this talk we prove the result of Pătraşcu and Demaine.

In this talk, we will go over all classes of algorithms for optimizing convex functions and will look into the various methods used to accelerate these algorithms. We will work with a geometric intuitive picture of all these algorithms and hope to obtain an understanding of what parameters of the algorithm cause acceleration and how these different methods are connected.

We will discuss a Toronto classic from the 80s: that the class SAC1 (aka LogCFL, the class of languages log-space reducible to context-free languages) is closed under complementation. The proof is a beautiful application of the "inductive counting" technique that was initially developed to prove NL = co-NL. No prior background in circuit complexity will be assumed!

In 1972, Charles Stein, dissatisfied with the existing proof of the Central Limit Theorem, devised an alternative. We discuss his method and compare it to the standard Fourier Analysis approach. Central to this method is a characterization of the standard Gaussian random variable \(Z\) as one which satisfies: \(\mathbb{E}[f'(Z)] = \mathbb{E}[Zf(Z)]\) for all well-behaved functions \(f\) (bounded and smooth). Any other random variable \(Y\) which approximately satisfies this identity is then close to \(Z\) in probability metric. We demonstrate some application of the method as well as its variants --- such as the Method of Exchangeable Pairs --- to various problems as time permits.

In this talk I will give an introduction to the number-on-forehead communication model. In particular, I will speak about the exactly-N problem which, despite being one of the most basic problems in the model, is not well-understood. I will present an \(O(\sqrt{\log N})\) upper bound for this problem, first shown by Chandra, Furst, and Lipton and later made explicit by Linial, Pitassi, and Shraibman. If time permits, we will also discuss the (very weak) lower bound.