COMBINATORIAL ALGORITHMS GROUP

If you would like to give a talk in our seminar series, please contact Wendy Myrvold (wendym@cs.uvic.ca).
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  ProD Day 
Oct. 23  ECS 660  2:004:00  Harry Calkins  Mathematica 6 in Education and Research 
Oct. 23  ECS 660  4:005: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:451: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 kary Dyck words 
Recent advances in digital photomontage have simplified the creation of extreme wideangle 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.
This is joint work with Matthew Cary, Aparna Das, Ben Edelman, Ioannis Giotis, Kurtis Heimerl, Anna Karlin, and Michael Schwarz.
This presentation is an interactive discussion of socially relevant computing, and how it could help to attract students to computer science programs.
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.
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.
Strengthening the conjecture of Feder and Vardi that all CSP are either polynomial time solvable or NPcomplete, Bulatov, Jeavons and Krohkin conjectured a classification of exactly which CSPs are NPcomplete. Their classification uses algebraic definitions and techniques. We present a couple of equivalent lowmachinery 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.
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 highreputation commentators can be inferior to that from lowreputation 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.
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 perceptuallyinspired 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 frontend. A novel similarity cue based on harmonicity (HarmonicallyWrapped Peak Similariy HWPS) is also introduced. The proposed system is datadriven (i.e requires no prior knowledge about the extracted source), causal, robust, practical and efficient (close to realtime 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 frontends and grouping criteria in a straightforward manner.
Speaker Bio: George Tzanetakis is currently assistant professor in Computer Science (crosslisted 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/.
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/.
We consider the wellknown edgedisjoint path problem (EDP) where we are given a graph G and pairs of nodes (demands) (s_{1}, t_{1}), (s_{2}t, _{2}), ... (s_{k}, t_{k}). A subset F of {1,2, ... ,k} is routable if there exists F edgedisjoint paths in G that connect the pairs (s_{i}, t_{i}) 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 bmatching 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 enroute.
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 coollex method for generating combinations. Further modifications result in a generalized algorithm for kary Dyck words and linear extensions of Bposets.
This is joint work with Frank Ruskey.