Skip to content. Skip to navigation
McGill Home SOCS Home
Personal tools
You are here: Home Announcements and Events Seminars Schedule

Seminar Home
Fall 2015 Schedule
Winter 2016 Schedule
Summer 2016 Schedule

SOCS Algorithms Seminar Schedule

Date Category Seminar Info
2013/03/28 Algorithms Place: FDA 232
Time: 10:00 - 11:00
Speaker: Yuval Filmus
Affiliation: PhD Candidate, University of Toronto, Computer Science
Title: The Unexpected Power of Local Search

Yuval Filmus is a Ph.D. candidate in Computer Science in University of Toronto, advised by Prof. Toni Pitassi. His research interests include approximation algorithms, computational complexity, proof complexity, analysis of Boolean functions, and combinatorics. He received his masters degree in Computer Science from the Weizmann institute

Biography of Speaker:

The difficulty of solving combinatorial optimization problems efficiently has led to the design of approximation algorithms. Unfortunately, approximation algorithms are often quite complicated and specialized, which limits their applicability. In this talk, we discuss a fundamental combinatorial optimization problem, monotone submodular maximization over a matroid constraint (MSMM). This problem generalizes classical problems such as Maximum Coverage and Maximum Satisfiability. The simple greedy algorithm achieves the best possible approximation ratio for Maximum Coverage. However, for the more general MSMM problem, achieving the best approximation ratio required the sophisticated continuous greedy algorithm. We present an elementary non-oblivious local search algorithm, which is also theoretically optimal. Our algorithm is much simpler than the existing continuous greedy algorithm, and moreover it may generalize to new situations in which the continuous greedy approach fails.

2013/03/01 Algorithms Place: MC437
Time: 10:00 - 11:00
Speaker: Kevyn Collins-Thompson
Affiliation: Microsoft Research (Redmond) - Context, Learning, and User Experience for Search group
Title: Towards search engines that help people learn: models, algorithms, and large-scale analysis

How can search engines help people learn? The computational challenges involved in this goal include: accurately modeling people's expertise and information-seeking goals from limited evidence; extracting meaning from unstructured text and data; making reliable decisions about information under uncertainty; and modeling how people learn from new information. In addition, real-world solutions to these challenges on the Web must cope with sparse, noisy data and scale effectively to billions of users and pages. In this talk, I will present three advances from my recent research that illustrate progress toward this goal, using as an example the specific personalized search task of finding relevant Web pages at the right level of reading difficulty. First, I will give an overview of novel statistical learning models that can predict the reading difficulty of text with much greater reliability and flexibility than traditional methods. Second, I show how applying reading difficulty prediction to billions of Web pages opens up new and sometimes surprising possibilities for enriching our interactions with the Web, from predicting user and site expertise, to estimating searcher motivation. Third, to enable reliable personalization of search results, I describe a new family of risk-sensitive ranking algorithms that can jointly optimize both relevance and robustness. These developments point toward a future where human information seeking and learning benefit from continued advances in computational learning.

Biography of Speaker:

Kevyn Collins-Thompson is a Researcher in the Context, Learning and User Experience for Search (CLUES) group at Microsoft Research. His core research is in information retrieval and text mining, including a strong interplay with statistical machine learning, mathematical optimization, economics, and natural language processing. His research focuses on models, algorithms, and evaluation methods for improved search and text understanding, especially for human learning. Kevyn received his Ph.D. in Computer Science from the Language Technologies Institute at Carnegie Mellon University and B.Math. in Computer Science from the University of Waterloo. He is a co-recipient of an ACM SIGIR’12 outstanding paper award for his work with Lidan Wang and Paul Bennett on "Robust ranking via risk-sensitive optimization".