COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Fall 2007

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.

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:

• 2D and 3D visualization
• Dynamic interactivity
• On-demand scientific data
• Example-driven course materials
• Symbolic interface construction
• Practical and theoretical applications

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.

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.

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.

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.

We consider the well-known edge-disjoint path problem (EDP) where we are given a graph G and pairs of nodes (demands) (s₁, t₁), (s₂t, ₂), ... (s_k, t_k). A subset F of {1,2, ... ,k} is routable if there exists |F| edge-disjoint 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 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.

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.