SOCS Graduate Seminar Series Seminar Schedule

Optimization problems are problems that naturally arise in many computational tasks. For example, consider a situation in which we want to route a packet between two nodes in a network; then this problem can be phrased as the shortest path problem, which is a well-studied optimization problem. Unfortunately, while we can solve the shortest path problem in polynomial time, many other optimization problems are NP-hard, which means that we could not expect a polynomial-time algorithm that could solve the problems optimally unless P = NP. Hence, we turn to algorithms that find approximate solutions in (quasi) polynomial-time, giving birth to the area of approximation algorithms. In this talk, we will discuss how to design approximation algorithms for NP-hard problems, and we will discuss that some problems have high approximation resistance, i.e., it is NP-hard even to find a good approximate solution.

The General Assembly is a forum that allows any member to bring their concerns, questions, issues, motions or amendments to the highest governing body of the CGGS. Active participation is important and critical to the future of CSGS as you can talk about your concerns and to work on long-term campaigns and plans to improve the quality of graduate studeies within the department. In this GA, the new amendments to the constitution are put to vote. The constitution requires further amendments which will be designed by the new governing body. Members will vote on them in the next general assembly. We will have elections for all the executive positions and If you are interested in running, all the information about the responsibilities of the positions can be found in the attached constitution. The open positions are: President Chair VP finance and operations VP Social VP Academic VP communications Please send me your nominations no later than Tuesday November 27th at 11:30AM. Serving your society is a great opportunity, especially at a time when CSGS is undergoing such major changes. The individuals who are elected into these important positions will work to improve the quality of social life as well as addressing the members' concerns with in the department. Food and drinks will also be provided.

Nowadays Kademlia is one of the most widely used dhts (Distributed Hash Table) in P2P (peer-to-peer) networks. This work studies one essential question about Kademlia overlay networks from a mathematical perspective: how long does it take to locate a node? To answer it, we introduce a random graph K to model a Kademlia overlay and study how long it takes to locate a given vertex in K by using Kademlia’s routing algorithm.

We present a new technique for simulating high resolution surface deformations of soft objects that have a harder skin. We combine a high resolution thin shell with a coarse finite element mesh, and define a special coupling constraint that allows the formation and shape of wrinkles to be determined solely by the shell and interior deformation parameters. This leads to models that approximate the behaviour of fine resolution simulations without the computational expense of using a large number of elements to simulate deformations under the surface. Quadratic shape functions let us use very coarse finite element resolutions to model the overall global deformations efficiently while avoiding visual discretization artifacts that linear functions would produce on the embedded mesh. We validate our model with high resolution simulations and show examples of our method in the generation of wrinkles for facial and character animation, as well as for soft objects such as furniture.

Using procedural narrative generation in video games provides a flexible way to extend gameplay and provide more depth to the game world at low cost to the developers. Current examples of narrative generation in commercial games, however, tend to be simplistic, resulting in repetitive and uninteresting stories. In this talk, we will present the challenges and benefits of narrative generation. Our system, called ReGEN, is developed for narrative generation using a context-aware graph rewriting framework. ReGEN uses a graph representation of the game world to create narratives which reflect and modify the current world state. Using a novel set of metrics to evaluate narrative quality, the approach is validated by comparing the generated narratives to other procedurally generated stories, as well as to authored narratives from commercially successful and critically praised games. The results show that our generated narratives compare favourably to authored narratives. ReGEN's metrics provide a new approach to narrative analysis, and the system provides a unique and practical approach to story generation.

What are the limitations to what computers can learn? Do certain mathematical theorems have have short proofs? Can quantum mechanics be exploited to speed up computation? Is every problem whose solution is efficiently verifiable also efficiently solvable (i.e. is P = NP)? At first these may seem like unrelated questions, but at a high level, they are all concerned with understanding which tasks are complex and which tasks are easy. Although the underlying model and the resource of interest can be different in different contexts, there seems to be a unifying theme captured by the concept of "communication complexity". In many seemingly unrelated settings, efficient solutions to problems can be viewed as efficiently solving certain communication tasks. In other words, many hard tasks have an implicit communication bottleneck, and one can prove the hardness of these tasks by studying them in the context of communication complexity.

In this talk we will: 1) formally define the basic communication complexity model, 2) give some concrete examples to demonstrate how it relates to various branches of theoretical computer science, and 3) argue that these connections are extremely fruitful.

Synthesizing motions for human grasping tasks remains an open problem in computer animation. In this presentation, I begin with a short overview on character animation using a multibody dynamical simulation. I emphasize aspects which make grasping particularly interesting (and difficult). I then present our method for performing one-handed manipulation of objects. Our approach uses offline simulations to learn control policies for a multiphase controller framework. Parameters for individual controllers are found by minimizing phase appropriate objective functions. For this purpose, a derivative-free numerical optimization method is used. The generated motions are physically plausible and the resulting policy is general enough to be used in real time. I will show some videos of our results and discuss some of the techniques used to improve performance.

When a programmer uses general search engines to find code examples, the information accompanying a returned link does not always contain adequate cues for determining whether the link is worth-while to pursue. To mitigate this issue, in this talk, I will introduce the problem of code fragment summarization for extracting succinct cues on Web pages containing code fragments. We developed a machine learning approach using expertise-related, syntactic, and query-related features, guided by an oracle we collected: 73 summaries and 1000 human judgements of whether a code line is in a summary. Our results show that syntactic and query-related features can form summaries that approximate summaries in the oracle, with a precision of 0.55. The novel use of light-weight expertise-related features shows promise, increasing the precision to 0.58. A qualitative analysis shows that even the summaries with lower precision can be useful.

This is joint work with Prof. Martin Robillard.

Reference documentation is an important source of information on API usage. However, information useful to programmers can be buried in irrelevant or boiler-plate text, making it difficult to discover. In this talk, I will explain a technique we used to detect and recommend fragments of API documentation potentially important to a programmer who has already decided to use a certain API element. We categorize text fragments in API documentation based on whether they contain information that is indispensable, valuable, or neither. From the fragments that contain knowledge worthy of recommendation, we extract word patterns, and use these patterns to automatically find new fragments that contain similar knowledge in unseen documentation. In an evaluation study with randomly-sampled method definitions from ten open source systems, we found that with a training set of about 1 000 manually-classified sentences, we could issue recommendations with about, on average, 90% precision and 69% recall.

Does your work involve matrix operations with large dense matrices? Not satisfied with speed you are getting on CPUs? Then you may be aware that modern GPUs provide considerably better performance on many types of matrix computations than most CPUs. However, so far you had to choose vendor-specific APIs (eg: Nvidia CUBLAS only works on Nvidia) making your code non-portable. I present a high-performance portable BLAS library that runs on many GPUs including AMD, Nvidia and Intel GPUs. I will present initial performance results, and discuss future plans.