ALT Alex Dimakis is a UT Austin Professor and the co-director of the National AI Institute on the Foundations of Machine Learning. He received his Ph.D. from UC Berkeley and the Diploma degree from NTU in Athens, Greece. He has received several awards including the James Massey Award, NSF Career, a Google research award, the UC Berkeley Eli Jury dissertation award, and several best paper awards. He served as an Associate Editor for several journals including IEEE Transactions on Information Theory and as an Area Chair for Machine Learning conferences (NeurIPS, ICML, AAAI). His research interests include information theory and machine learning. He is an IEEE Fellow for contributions to distributed coding and learning.

ALT Alexander "Sasha" Rush is an Associate Professor at Cornell Tech and a researcher at Hugging Face. His research interest is in the study of language models with applications in controllable text generation, efficient inference, and applications in summarization and information extraction. In addition to research, he has written several popular open-source software projects supporting NLP research, programming for deep learning, and virtual academic conferences. His projects have received paper and demo awards at major NLP, visualization, and hardware conferences, an NSF Career Award and Sloan Fellowship. He tweets at @srush_nlp.

ALT Vladimir Braverman's picture

ALT Vladimir Braverman is a Professor of Computer Science at Rice University and a Visiting Researcher with Google Research. Previously, he was an Associate Professor in the Department of Computer Science at Johns Hopkins University. Braverman received a PhD in Computer Science at UCLA. Braverman’s research interests include efficient sublinear algorithms and their applications to machine learning and digital health.

ALT Photo of Amit Charakraborty

ALT Abstract: An n-vertex graph with maximum degree D is (D+1)-colorable: an almost trivial combinatorial result, with an equally simple greedy algorithm to produce a (D+1)-coloring. However, given a stream of edges of such a graph, can we maintain a valid (D+1)-coloring as the edges arrive, while using not much more than O(n) space? What if the edges are chosen by an adversary who can look at our current coloring and add additional edges to try to confound us? This is the newly-popular setting of adversarially robust streaming algorithms and this talk is about the coloring problem in this setting. We obtain upper and lower bound results for this problem. In O(n polylog n) space, we can maintain an O(D^(5/2))-coloring of such an adversarial graph. On the other hand, every adversarially robust coloring algorithm under the same space limitation must spend Omega(D^2) colors. We in fact prove more general. results that trade off the space usage against the color budget. [...]

ALT A streaming algorithm is given a sequence of items and seeks to compute or approximate some function of this sequence using a small amount of memory. A body of work has been developed over the last two decades, resulting in optimal streaming algorithms for a number of problems. I will start by surveying some of these problems. I will then investigate the adversarial robustness of streaming algorithms. An algorithm is considered robust if its performance guarantees hold even if the stream is chosen adaptively by an adversary that observes the outputs of the algorithm along the stream and can react in an online manner. While deterministic streaming algorithms are inherently robust, many central problems do not admit sublinear-space deterministic algorithms; on the other hand, space-efficient randomized algorithms for these problems are generally not adversarially robust. This raises the question of whether there exist efficient adversarially robust (randomized) streaming algorithms [...]

ALT Photo of Sébastien Bubeck

ALT Abstract: Since the late 19th century, mathematicians have realized the importance and generality of selection problems: given a collection of sets, select an element in each set, possibly in a "nice" way. Of particular importance in computer science is the scenario where the ground set is a metric space, in which case it is natural to ask for Lipschitz selection. In this talk I will describe a far-reaching extension of this classical Lipschitz selection problem to an online setting, where sets are streaming to the selector. I will show how Riemannian gradient descent (aka mirror descent) can be used to approach this type of problems. I will illustrate the power of the framework by solving a long-standing problem in online shortest path known as layered graph traversal (introduced by Papadimitriou and Yannakakis in 1989).