^October November – 2012 ^December

Given three permutations on the integers 1 through n, consider the set system consisting of each interval in each of the three permutations. In 1982, Beck conjectured that the discrepancy of this set system is O(1). In other words, the conjecture says that each integer from 1 through n can be colored either red or blue so that the number of red and blue integers in each interval of each permutation differs only by a constant. (The discrepancy of a set system based on two permutations is at most two.) Our main result is a counterexample to this conjecture: for any positive integer n = 3^k, we construct three permutations whose corresponding set system has discrepancy at least k/3.

Time permitting I will also discuss an implication of this result to the integrality gap of the Gilmore-Gomory LP relaxation for Bin Packing.

Joint with Alantha Newman and Aleksandar Nikolov

Faster algorithms can be obtained by minimizing communication. That is, reducing the amount of data sent across the memory hierarchy and between processors. The communication costs of algorithms, in terms of time or energy, are typically much higher than the arithmetic costs. We have computed lower bounds on these communication costs by analyzing geometric and expansion properties of the underlying computation DAG of algorithms. These techniques (honored by SIAG-LA prize for 2009-2011 and SPAA'11 best paper award) inspired many new algorithms, where existing ones proved not to be communication-optimal. Parallel matrix multiplication is one of the most studied fundamental problems in parallel computing. We obtain a new parallel algorithm based on Strassen's fast matrix multiplication that is communication-optimal. It exhibits perfect strong scaling, within the maximum possible range. The algorithm asymptotically outperforms all known parallel matrix multiplication algorithms, classical and Strassen-based. It also demonstrates significant speedups in practice, as benchmarked on several super-computers (Cray XT4, Cray XE6, and IBM BG/P). Our parallelization approach is simple to implement, and extends to other algorithms. Both the lower bounds and the new algorithms have an immediate impact on saving power and energy at the algorithmic level. Based on joint work with Grey Ballard, James Demmel, Olga Holtz, Ben Lipshitz

This talk will briefly introduce the streaming computational model in the context of data mining. We will focus on working with matrices that are revealed over time and are too large to store. Working with such massive matrices requires creating a concise yet accurate approximation for them. These are called matrix sketches. This talk will shortly survey new results for matrix sketching in two streaming models. In the first, the matrix is presented to the algorithm one entry at a time. Examples include recommender systems whose input is of the form "user i rated item j 3 stars". In the second, the matrix is revealed row by row, for example, "document i contains terms j_1,…,j_k". This is the case in web crawling where the crawler cannot store all the documents it visits.