WebNotice Postings for Department of Computer Science

08-Feb-2010 through 08-Feb-2011


Monday, 08 February 2010, 11:00AM -- D.L. Pratt, 290 C
Machine Learning Seminar
Speaker: Charlie Tang, School of Computer Science, University of Waterloo
Title: "Sparsely Connected Deep Networks for More Robust Visual Recognition"
Abstract: Deep architectures such as the Deep Belief Networks (DBNs) are excellent at modeling high dimensional visual data. However, classification using DBNs are not very robust to variations such as occlusion and random noise if examples are not included in the training set. Due to the impractical nature of adding all possible noises that may exist in the real-world environment to the training set, it is desirable for the DBNs to be more robust to out-of-sample test images.

We will first show that by restricting the first hidden layer to be sparsely connected to the visible layer (specifically in the form of localized receptive fields), recognition is automatically improved over a standard DBN on the MNIST dataset. We will also present a denoising algorithm which tries to identify a subset of the first hidden layer nodes as been affected by noise and "ignores" them. The algorithm combines top-down and bottom-up inputs and further improves recognition results when the test images contain occlusions and noises. The denoising algorithm takes advantage of a generative model and is applicable to any deep feed-forward network with localized first layer connections.

Tuesday, 9 February 2010, 11:00AM -- Bahen Centre, Rm. 1180
Distinguished Lecture Series Lecture
Speaker: Dr. Joe Marks, Vice President, Disney Research
Title: "Interactive Media Research at The Walt Disney Company"
Remarks: Speaker bio: Joe Marks grew up in Dublin, Ireland. Being more perseverant than imaginative, he earned three degrees from Harvard University. His areas of interest include computer graphics, human-computer interaction, and artificial intelligence. He has worked previously at Bolt Beranek and Newman and at Digital's Cambridge Research Laboratory. Prior to joining The Walt Disney Company he was the Research Director at Mitsubishi Electric Research Labs in Cambridge, MA, from 2000-2006.
Abstract: The research challenges in interactive media faced by the different business units of The Walt Disney Company fall in four broad categories: motion pictures, park attractions, games & sports, and media networks. Enumerating these challenges provides a key industry perspective on promising directions for future research in digital arts, experiential media systems, creative environments, and emerging media technologies.

Tuesday, 9 February 2010, 3:15PM -- Pratt 266
Theoretical Computer Science Seminar
Speaker: Joshua Brody, Dartmouth College
Title: "Communication Complexity and You: A Winning Combination"
Abstract: Communication Complexity has been used to prove lower bounds and hardness results in a wide variety of domains, from the theoretical (circuit complexity, proof complexity) to the practical (streaming algorithms, data structures, etc.)

In this talk I'll present some recent results on two communication problems: Gap Hamming Distance and Multiparty Pointer Jumping. The Gap Hamming Distance problem captures the hardness of computing certain functions on data streams, even when randomness and approximation are used. Proving sufficiently strong lower bounds for Multiparty Pointer Jumping would resolve a major open question in circuit complexity.

Despite the different nature of the applications, the lower-bounds proofs in each problem use similar techniques, which should be useful in other problems as well.

The results on Gap Hamming Distance are joint work with Amit Chakrabarti, Oded Regev, Thomas Vidick, and Ronald de Wolf. This talk assumes no prior knowledge of communication complexity.

Friday, 12 February 2010, 11:00AM -- D.L.Pratt Building, Rm. 266
Computational Vision Seminar
Speaker: Simon Prince, University College London
Title: "Superpixel Lattices"
Abstract: Unsupervised over-segmentation of an image into superpixels is a common preprocessing step for image parsing algorithms. Ideally, every pixel within each superpixel region will belong to the same real-world object. Existing algorithms generate superpixels that forfeit many useful properties of the regular topology of the original pixels: for example, the nth superpixel has no consistent position or relationship with its neighbors. We propose two novel algorithms that produce superpixels that are forced to conform to a grid (a regular superpixel lattice). Despite this added topological constraint, these algorithms are comparable in terms of speed and accuracy to alternative segmentation approaches. Finally, we propose a way to learn about the regularities of images to form a prior on the shape and size of the superpixels in the lattice.

Friday, 12 February 2010, 11:10AM -- GB 244 - Galbraith Bldg
Theoretical Computer Science Seminar
Speaker: Eden Chlamtac, Weizmann Institute of Science
Title: "New Approximation Algorithms for Densest k-Subgraph"
Abstract: We consider the Densest k-Subgraph (DkS) problem: Given a graph G and a parameter k, find a subgraph of G on k vertices with the maximum number of edges. This is a well known optimization problem, which is a natural optimization version of the decision problem k-CLIQUE.

The previous best known approximation ratio by Feige, Kortsarz and Peleg in 2001 was O(n^{1/3-epsilon}) for epsilon estimated at around 1/60. We improve on this result, giving an O(n^{1/4+delta}) approximation for any delta>0.

In essence, our algorithm relies on the following principle: In a random graph with average degree n^alpha, a planted k-subgraph can be detected if it has average degree (strictly) greater than k^alpha. We show that this principle largely carries over to provide results in the same spirit for worst-case (non-random) instances.

Joint work with Aditya Bhaskara, Moses Charikar, Uriel Feige and Aravindan Vijayaraghavan.

Thursday, 25 February 2010, 2:00PM -- Pratt 266
Theoretical Computer Science Seminar
Speaker: Yi Wu, Carnegie Mellon University
Title: "Approximability of NP hard problems in Learning and CSPs"
Abstract: An alpha-approximation algorithm is an algorithm guaranteed to output a solution that is within an alpha ratio of the optimal solution. We are interested in the following question: Given an NP-hard optimization problem, what is the best approximation guarantee that any polynomial time algorithm could achieve?

We mostly focus on studying the approximability of two classes of NP-hard problems: Constraint Satisfaction Problems (CSPs) and Computational Learning Problems. Our research in the field of CSPs is to show that certain Semidefinite Programming (SDP) algorithms are the optimal polynomial time approximation algorithm; our work in the learning area is to prove that tasks are inherently hard; i.e., there is no better-than-trivial algorithm for the problems.

We will describe results on the approximability of several problems from these two classes such as Max-Cut, Satisfiable 3-CSPs and agnostic learning of monomials and low degree PTFs.

Tuesday, 30 March 2010, 11:00AM -- Bahen Centre, Rm. 1180
Distinguished Lecture Series Lecture
Speaker: Professor Maja Mataric, Computer Science and Neuroscience, University of Southern California
Title: "To be announced"


...... WebNotice