CAG Schedule of Talks: Fall 2007

COMBINATORIAL ALGORITHMS GROUP
Schedule of Talks: Fall 2007

If you would like to give a talk in our seminar series, please contact Wendy Myrvold (wendym@cs.uvic.ca).

Schedule for Talks:

Date Place Time Speaker Abbreviated Title
Sept. 21 ECS 660 2:30 Daniel German Flattening the Sphere
Sept. 24 ECS 660 1:30 Claire Mathieu Greedy Bidding Strategies for Keyword Auctions
Oct. 12 ECS 660 2:30 John Nordlinger Socially relevant computing
Oct. 19 ECS 660 2:30 NO CAG Pro-D Day
Oct. 23 ECS 660 2:00-4:00 Harry Calkins Mathematica 6 in Education and Research
Oct. 23 ECS 660 4:00-5:00 Harry Calkins Using Mathematica for Graph Theory and Combinatorics
Oct. 29 Elliott 161 10:00 Mark Siggers A Combinatorial Version of the CSP Dichotomy Classification Conjecture
Nov. 1 BEC 217 11:45-1:00 Andrew B. Winston Moderated Online Communities
Nov. 2 ECS 660 2:30 No CAG Special CS dept. meeting
Nov. 9 ECS 660 2:30 No CAG Faculty of Engineering meeting
Nov. 16 ECS 660 2:30 George Tzanetakis A framework for predominant melodic sound source separation using spectral clustering
Nov. 27 ECS 660 1:30 Sue Whitesides Path Planning and Graph Layout, an Algorithmic Perspective
Nov. 30 ECS 660 2:30 Movie N is a Number: A Portrait of Paul Erdos
Dec. 7 _ _ No CAG CMS Winter 2007 Meeting
Dec. 13 Cle A 203 3:30 Bruce Shepherd Disjoint Paths in Graphs
Dec. 14 ECS 660 3:00 Aaron Williams The coolest way to generate balanced parenthesis and k-ary Dyck words

Previous Talks:

Flattening the Sphere
Daniel German
Friday Sept. 21, 2:30pm, ECS 660

Recent advances in digital photomontage have simplified the creation of extreme wide-angle views from a vantage point, including the recreation of the entire sphere (we will refer to these type of images as panoramas). In order to minimize the distortion from the point of view of the viewer, panoramas have been typically presented using curved displays. Unfortunately requiring such systems restricts their use, and little research has been done in the representation of panoramas into a flat surface.

In this talk I discuss the use of map projections for photographic purposes, with emphasis in conformal mappings. In particular I will discuss elliptic curves in the complex space, and argue that there is a lot of potential for this type of functions in photography.

Greedy Bidding Strategies for Keyword Auctions
Claire Mathieu
Computer Science Department at Brown University and Microsoft Research
Visiting Dr. Valerie King
Monday Sept. 24, 1:30pm, ECS 660

How should players bid in keyword auctions such as those used by Google, Yahoo! and MSN? We study the revenue and convergence properties of greedy bidding strategies for a repeated auction on a single keyword, where in each round, each player chooses some optimal bid for the next round, assuming that the other players merely repeat their previous bid.

This is joint work with Matthew Cary, Aparna Das, Ben Edelman, Ioannis Giotis, Kurtis Heimerl, Anna Karlin, and Michael Schwarz.

Socially Relevant Computing and its Impact on Undergraduate Computer Science
John Nordlinger, Microsoft Research,
Friday October 12, 2:30pm, ECS 660

This presentation is an interactive discussion of socially relevant computing, and how it could help to attract students to computer science programs.

Using Mathematica for Graph Theory and Combinatorics
Harry Calkins, Training Developer for Wolfram Research
Tuesday October 23, 4:00-5:00pm, ECS 660

The Mathematica visitor has offered to stay a bit longer and talk about features of mathematica which would be of interest to our CAG group.

Mathematica 6 in Education and Research
Harry Calkins, Training Developer for Wolfram Research
Tuesday October 23, 2:00-4:00pm (including Q&A), ECS 660

This talk illustrates capabilities in Mathematica 6 that are directly applicable for use in teaching and research on campus. Topics of this technical talk include:

Current users will benefit from seeing the many improvements and new features of Mathematica 6 (http://www.wolfram.com/mathematica/newin6), but prior knowledge of Mathematica is not required.

This talk is part of their Pacific NorthWest tour and is open to anyone. Maple and Matlab users may wish to come to compare. UVic talk poster at: http://download.wolfram.com/?key=G38M3D Several UVic departments (Econ, Math, Phys, ECE, CSc, SEOS, ...), already use Mathematica for teaching and/or research. licensing has been individual, but site licensing is being investigated.

A Combinatorial Version of the CSP Dichotomy Classification Conjecture
Mark Siggers, Simon Fraser University
Monday Oct. 29, 10:00am, Elliott 161

Strengthening the conjecture of Feder and Vardi that all CSP are either polynomial time solvable or NP-complete, Bulatov, Jeavons and Krohkin conjectured a classification of exactly which CSPs are NP-complete. Their classification uses algebraic definitions and techniques. We present a couple of equivalent low-machinery graph theoretic classifications. We talk about some of the advantages of each of the various classifications.

This is joint work with J. Nesetril and L. Zadori.

Moderated Online Communities
Andrew B. Winston
Hugh Roy Cullen Centennial Professor
Business Administration, University of Texas, Austin
Thursday, Nov. 1, 11:45-1:00pm, BEC 217.

Online communities provide a social sphere for people to share information and knowledge. While information sharing is becoming a ubiquitous online phenomenon, how to ensure information quality or induce the quality of content, however, remains a challenge due to the anonymity of commentators. This paper introduces moderation into reputation systems. We show that moderation directly impacts strategic commentators' incentive to generate useful information and moderation is generally desirable to improve information quality. Interestingly, we find that when moderated differently upon their reputations, commentators may display a pattern of reputation oscillation, in which they generate useful content to build up high reputation and exploit it once they reach it. As a result, the expected performance from high-reputation commentators can be inferior to that from low-reputation ones (reversed reputation). We finally investigate the optimal moderation resource allocation, and conclude that the seemingly abnormal reversed reputation could arise as an optimal result.

A framework for predominant melodic sound source separation using spectral clustering
George Tzanetakis
Friday Nov. 16, 2:30pm, ECS 660

Clustering using the normalized cut criterion and more generally spectral clustering methods are techniques originally proposed to model perceptual grouping tasks such as image segmentation in Computer Vision. They are based on modeling the problem as a graph and clustering as graph partitioning. In this work it is shown how such techniques can be applied to the problem of dominant melodic source separation in polyphonic music audio signals.

One of the main advantages of this approach is the ability to incorporate multiple perceptually-inspired grouping criteria into a single framework without requiring separate processing stages as many existing Computational Auditory Science Analysis (CASA) approaches do. Experimental results for several tasks including dominant melody pitch detection are presented. The system is based on a sinusoidal modeling analysis front-end. A novel similarity cue based on harmonicity (Harmonically-Wrapped Peak Similariy HWPS) is also introduced. The proposed system is data-driven (i.e requires no prior knowledge about the extracted source), causal, robust, practical and efficient (close to real-time on a fast computer). Although a specific implementation in presented, one of the main advantage of the proposed approach is its ability to utilize different analysis front-ends and grouping criteria in a straightforward manner.

Speaker Bio: George Tzanetakis is currently assistant professor in Computer Science (cross-listed in Music and Electrical and Computer Engineering) at the University of Victoria in Canada. He received his PhD degree in Computer Science from Princeton University in May 2002 and was a PostDoctoral Fellow at Carnegie Mellon University in 2003. He was also main designer of the Moodlogic audio fingerpinting algorithm and is the main designer and developer of the Marsyas audio processing framework (http://marsyas.sness.net). His research deals with all stages of audio content analysis such as feature extraction, segmentation, classification. He is also an active musician and has studied saxophone performance, music theory and composition. More information can be found at: /~gtzan/.

Path Planning and Graph Layout, an Algorithmic Perspective
Sue Whitesides
School of Computer Science, McGill University
Tuesday Nov. 27, 1:30pm, ECS 660

To visualize a graph, or to realize the connectivities it represents, as a circuit of wires or a network of pipes or highways, one must assign its vertices and edges to concrete locations; that is, one must "draw" the graph. Alternatively, abstract graphs can be realized by a variety of geometric relationships, such as visibility, contact, and proximity. When a graph represents a linkage of rods hinged together at their endpoints, its movement properties can exhibit a range of intriguing behaviours and challenging questions, even for a graph as simple as a chain of links.

Biography: Dr. Sue Whitesides is Professor and Director, School of Computer Science, McGill University. Her research interests include: algorithms, discrete mathematics, discrete and computational geometry, algorithmic motion planning, graph layout, graph drawing, applications in brain imaging, and nanofabrication. More information is available at http://www.cs.mcgill.ca/~sue/.

N is a Number: A Portrait of Paul Erdos
Friday Nov. 30, 2:30pm, ECS 660

This movie follows Erdos for four years through four countries, presenting his mathematical quest and its personal and philosophical dimensions. Animated sequences illustrate the kinds of mathematical problems that Erdos pursued.

Disjoint Paths in Graphs
Bruce Shepherd, McGill University
Thursday Dec. 13, 3:30pm, Cle A 203

We consider the well-known edge-disjoint path problem (EDP) where we are given a graph G and pairs of nodes (demands) (s1, t1), (s2t, 2), ... (sk, tk). A subset F of {1,2, ... ,k} is routable if there exists |F| edge-disjoint paths in G that connect the pairs (si, ti) for each i in F. We analyze the problem of finding a maximum (weight) routable subset F. The situation where G is a tree already includes several classical combinatorial optimization problems such as the knapsack and b-matching problems. We discuss what is known for this problem in the three cases where G is a tree, a planar graph, or a general graph. Several open problems will arise en-route.

The coolest way to generate balanced parenthesis and k-ary Dyck words
Aaron Williams
Friday Dec. 14, 3:00pm, ECS 660

Balanced parenthesis are strings with an equal number of ('s and )'s together with the property that no prefix contains more )'s than ('s. The balanced parentheses of length 2n are counted by the nth Catalan number and are in bijective correspondence to objects as varied as binary trees and triangulations of convex polygons. In this talk I will present a novel algorithm for generating exhaustive listings of balanced parenthesis. The algorithm is simple enough to be taught to undergraduate students in a single lecture. It also has optimal efficiency in the sense that each successive string is produced in O(1) time while using only O(n) bits of total storage. The result is based on a subtle variation of the cool-lex method for generating combinations. Further modifications result in a generalized algorithm for k-ary Dyck words and linear extensions of B-posets.

This is joint work with Frank Ruskey.


CAG Schedule of Talks: Fall 2007 / maintained by Wendy Myrvold / wendym@cs.UVic.ca / revised Jan. 11, 2008