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

Seminar Home
Fall 2013 Schedule
Winter 2014 Schedule
Summer 2014 Schedule

SOCS Faculty Candidate Talk Seminar Schedule

Date Category Seminar Info
2013/04/11 Faculty Candidate Talk Place: McConnell 437
Time: 10:00 - 11:00
Speaker: Yang Cai
Affiliation: PhD student, Massachusetts Institute of Technology (MIT)
Area: Mathematical Economics
Title: Mechanism Design: a new algorithmic framework

In his seminal paper, Myerson [1981] provides a revenue-optimal auction for a seller who is looking to sell a single item to multiple bidders. Extending this auction to simultaneously selling multiple heterogeneous items has been one of the central problems in Mathematical Economics. We provide such an extension that is also computationally efficient. Our solution proposes a novel framework for mechanism design by reducing mechanism design problems (where one optimizes an objective function on "rational inputs") to algorithm design problems (where one optimizes an objective function on "honest inputs"). Our reduction is generic and provides a framework for many other mechanism design problems. In the end of my talk, I will also briefly overview some of my other work, including algorithmic pricing, generalization of the Min-max theorem for multiplayer games and online matching.

Biography of Speaker:

Yang Cai is currently finishing his Ph.D. at MIT under the supervision of Constantinos Daskalakis. He received his Bachelor degree in Computer Science from Peking University. His research interests include Algorithmic Game Theory, Online Algorithms and Logic

2013/04/09 Faculty Candidate Talk Place: McConnell 437
Time: 10:00 - 11:00
Speaker: Christopher Pal
Affiliation: École Polytechnique de Montréal
Area: Data Mining
Title: Big Data, Mining Multimedia and Semi-supervised Learning

In this talk I’ll begin by presenting some recent work with my students on mining the text and images of Wikipedia biographies. I’ll present a technique to disambiguate faces and identities using richly structured probabilistic models. I’ll discuss the role of generative, discriminative and semi-supervised learning in both text and general data mining and some considerations regarding the importance and interaction of model complexity and the amount of data available. I’ll then present some of our work on large-scale recognition in the wild in which we scale up with more data through mining image search results and YouTube. I’ll discuss a semi-supervised learning technique based on a probabilistic sparse kernel method and the use of null categories to account for noisy labels. The technique allows us to boost performance on the standard labeled faces in the wild evaluation using faces mined from YouTube as well as boost accuracy on the task of tagging faces of celebrities within YouTube videos. I’ll discuss the issues involved with scaling to truly big data and our experiences working in collaboration with Google using a corpus of over 1.2 million YouTube videos and their text annotations.

Biography of Speaker:

Christopher Pal is an assistant professor in the department of « génie informatique et génie logiciel » at the École Polytechnique Montréal. Prior to arriving in Montréal, he was an assistant professor in the department of Computer Science at the University of Rochester. He has been a research scientist with the University of Massachusetts Amherst at the Center for Intelligent Information Retrieval and Information Extraction and Synthesis Lab. He has also been affiliated with Microsoft Research's Interactive Visual Media Group and their Machine Learning and Adaptive Systems group. He has four patents, there are over 1100 citations to his work on Google Scholar and he has been the recipient of a Google research award. He earned his M. Math and Ph.D. from the University of Waterloo

2013/02/12 Faculty Candidate Talk Place: McConnell 437
Time: 10:00 - 11:00
Speaker: Thomas Vidick
Affiliation: MIT: Department of Computer Science and Artificial Intelligence Laboratory
Title: The complexity of entangled games: hardness results and approximation algorithms

Multiplayer games, from their use in cryptography to their role in the proof of the PCP theorem, play a central role in modern theoretical computer science. Recently the introduction of a new element, quantum entanglement, has brought a second life to the study of these games. Entanglement plays the role of a distributed resource that the players can tap in order to increase their odds of winning: how does its use affect the properties of the game? In turn, multiplayer games have proved a valuable tool in the study of fundamental properties of entanglement. In this talk I will present some recent result on the complexity of entangled games. I will show that the class MIP*(3) of languages having three-prover entangled proof systems contains the class NEXP. This resolves a long-standing open question in quantum complexity by showing that entangled-prover proof systems are no less powerful than their classical counterparts. The proof is based on adapting the multilinearity test from Babai et al's seminal result MIP = NEXP [BFL'91] to the entangled-player setting, and demonstrates the strength of one of the most interesting aspects of entanglement, its monogamy. Time permitting I will briefly discuss applications of entangled games to two very different areas: device-independent proofs of security in cryptography and approximation algorithms based on the use of semidefinite programming.

Biography of Speaker:

Thomas Vidick is currently a postdoctoral associate in the Computer Science and Artificial Intelligence Laboratory (CSAIL) at MIT. His research interests are in quantum computing and complexity theory, and he has made contributions to the theory of quantum multi-prover interactive proofs, quantum cryptography, pseudo-randomness, and approximation algorithms. He completed his Ph.D. in Computer Science from UC Berkeley in Fall 2011, working with Umesh Vazirani. His thesis was awarded the Bernard Friedman Memorial Prize in applied mathematics. He is a co-recipient of the FOCS'12 best paper award for his paper with Tsuyoshi Ito on "A multi-prover interactive proof for NEXP sound against entangled provers".