• Welcome to CSRS 2013

This year's Dartmouth Computer Science Research Symposium (CSRS) is on September 21, 2013. Talks and poster sessions will be in and around the Filene Auditorium in Moore Hall, and food will be in Occom Commons, located within Goldstein Hall.

The Dartmouth Computer Science Research Symposium is an annual exhibition of the research being conducted in the field of Computer Science here at Dartmouth. It not only provides a means of communicating research interests and goals to fellow department members, but to the greater Dartmouth community as well. Students and faculty are given an opportunity to present their research in either talk or poster form. CSRS serves to strengthen the solidarity of our department, provide critical presentation experience, and widen perspectives of Computer Science among both students and faculty.

Every year, the symposium features a keynote talk given by a distinguished member of the field from outside Dartmouth College. This year, out keynote speaker is Professor Javed Aslam from Northeastern University.

## Note

We will be presenting the Patrick Tsang Best Student Talk award and the Patrick Tsang Best Student Poster award. These awards will be determined by faculty committee and announced at the end of the day.

• 2013-09-21: fixed typos
• 2013-09-20: added presenter, small changes to schedule times, updated abstacts
• 2013-09-16: updated schedule
• 2013-09-06: schedule
• 2013-08-19: schedule
• 2013-08-12: cleaned site code
• 2013-08-10: created CSRS2013 website
• Program

Directions: This map shows Occom Commons, Filene Auditorium (Moore Hall), and the suggested route between them. (©2013 Google, Google Maps)

Time Speaker/Event Title/Venue
08:30 - 08:50 Breakfast Outside Filene Auditorium, Moore Hall
08:50 - 09:00 Tom Cormen Opening Remarks, Best TA Award
09:00 - 10:00 Javed Aslam Big Data Meets the Big City: Using a Vehicular Sensor Network for Traffic Analysis
10:00 - 10:15 Coffee break Outside Filene Auditorium, Moore Hall
10:15 - 10:40 Pete Winkler Thresholds of Computability
10:40 - 11:05 Jianfu Zhou A GPU-based Parallel Method of Protein Structure Alignment and Search
11:05 - 11:30 Tom Cormen Edge coloring for Regular Bipartite Multigraphs
11:30 - 11:55 Xia Zhou Practical Conflict Graphs in the Wild
12:00 - 13:00 Lunch Occom Commons in Goldstein Hall
13:15 - 13:40 Keith Carlson (video) L0 Sampling and Its Applications
13:40 - 14:05 Weifu Wang A fast streaming spanner for PRM*
14:05 - 15:05 Group Presentations Devin Balkcom, DALi Lab, Daniel Rockmore, Kotz Lab, ...
15:05 - 16:05 Poster session &
Coffee break
Outside Filene Auditorium, Moore Hall
16:10 - 16:35 Sagar Kale (video) Submodular Maximization Meets Streaming: Matchings, Matroids, and More
16:35 - 17:00 Andrew Campbell Biorythm Study: A term in the life of a Dartmouth class
17:00 - 17:25 Rebecca Shapiro "Weird Machines" in ELF: A Spotlight on the Underappreciated Metadata
17:25 - 18:10 Group Presentations Michael Casey, Vision Learning Group, ...
18:10 - 18:15 Prasad Jayanti Closing Remarks
19:00 - 20:30 Award Ceremony, Dinner Occom Commons in Goldstein Hall

*All talks are in Filene Auditorium in the basement of Moore Hall.

## Talk Abstracts

Javed Aslam (Big Data Meets the Big City: Using a Vehicular Sensor Network for Traffic Analysis)

We present a large-scale, country-wide analysis of traffic and mobility patterns in the country of Singapore through the use of data collected from 16 thousand taxis and over 12 thousand loop detectors corresponding to 1,300 road segments spread throughout the country. We demonstrate that taxis behave like a rapidly mixing Markov chain and that through the use of simple machine learning techniques one can view an instrumented fleet of taxis as a roving sensor network from which one can obtain historical and real-time information on overall traffic and perform urban planning for vehicular traffic.

Pete Winkler (Thresholds of Computability)

What makes some problems tractable, others intractable? One approach to trying to figure this out is to look for problems that depend on a parameter, and that are easy when the parameter is on one side of a threshold, and hard on the other side. We'll give some examples, and sketch some new results that may help us understand what happens at these thresholds.

Tom Cormen (Edge Coloring For Regular Bipartite Multigraphs)

Although an optimal deterministic algorithm for edge coloring a regular bipartite multigraph is known, it is difficult to discern the exact algorithm from its description in the literature. Moreover, there is no known implementation of this algorithm. My students and I have been exploring simple, deterministic approaches to solving this problem. I will describe two of our approaches. One is based on finding a perfect matching, and I will describe a simple heuristic that works very well in practice. The other is based on constrained cycle finding. We are still investigating how well this approach works and what improvements we can continue to make.

Xia Zhou (Practical Conflict Graphs in the Wild)

Today, most radio spectrum allocation algorithms use conflict graphs to capture interference conditions. The use of conflict graphs, however, is often questioned by the wireless community for two reasons. First, building accurate conflict graphs requires significant overhead, and hence does not scale to outdoor networks. Second, conflict graphs cannot properly capture accumulative interference.

In this talk, I'll describe our recent measurement study to understand how severe these problems are, and whether they can be overcome. We build “practical” conflict graphs using measurement-calibrated propagation models, which remove the need for exhaustive signal measurements by interpolating signal strengths using calibrated models. Calibrated models are imperfect, and we study the impact of their errors on multiple steps in the process, from calibrating propagation models, predicting signal strengths, to building conflict graphs. I'll summarize key findings from our study, and introduce a graph augmentation technique to address remaining accumulative interference.

Keith Carlson (L0 Sampling and Its Applications)

We look at the problem of sampling from a data stream where both insertions and deletions are allowed. A sampling technique is presented which uses $O(\log^2 n)$ space to perform L0 sampling. With this sampling we show that given a stream of insertions and deletions of edges in a graph, we can determine connectivity in $O(n * \log^3 n)$ space.

Weifu Wang (A fast streaming spanner for PRM*)

Sampling-based probabilistic roadmap algorithms such as PRM and PRM* have been shown to be effective at solving certain motion planning problems, but the large graphs generated to express the connectivity and a metric on the configuration space may require much storage space and be expensive to search. Recent work by Marble and Bekris applied spanner algorithms to PRM*; these algorithms prune some edges in a dense graph, while guaranteeably maintaining an approximation to the metric. In this paper, we apply (and improve) a state-of-the-art streaming spanner algorithm to prune PRM* roadmaps. The algorithm we present has the main advantage of computational speed; when applied to PRM*, the processing time per vertex is independent of the number of sampled vertices, $n$, as compared to $O(n \log^2 n\log \log n)$ by Marble in 2012. In practice, the algorithm we present prunes a graph with about 20 million edges in less than 20 seconds on a modern desktop computer; compared to the time required for generating such a roadmap, this additional processing time is essentially trivial. In fact, because the combination of this algorithm with PRM* avoids the need for many collision detections, the combination runs several times faster than PRM* alone.

Sagar Kale (Submodular Maximization Meets Streaming: Matchings, Matroids, and More)

We study the problem of finding a maximum matching in a graph given by an input stream listing its edges in some arbitrary order, where the quantity to be maximized is given by a monotone submodular function on subsets of edges. We call this problem maximum submodular-function matching (MSM) problem. We give a one-pass 7.75-approximation algorithm and a $O(\epsilon^{-3})$-pass $(3+\epsilon)$-approximation algorithm for MSM. We extend the techniques and results to multiple matroids constraint and to matchings in bounded-degree hypergraphs.

Andrew Campbell (Biorythm Study: A term in the life of a Dartmouth class)

Dartmouth's 10-week teaching term is typically an intense experience for students and faculty -- having its own unique "biorhythm". The first few weeks are low key. Students are relaxed,smile a lot, and then as the complexity and demands of the term increase students get visibly more stressed, have less sleep and time to exercise -- well that is the hypothesis. Multiply that by 3 for each class students take and you have the Dartmouth term - it is demanding because we tend to push students to learn complex topics typically taught over a 15-week semester in a 10-week term. The Biorhythm project uses a combination of automatic sensing and experience sampling on smartphones to shine a light on the impact of the Dartmouth term and its workload on stress, sleep, mood, activity, sociability, eating habits, health and burnout of a single class of 54 students. In this talk, we discuss the study, methods and initial results.

Rebecca Shapiro ("Weird Machines" in ELF: A Spotlight on the Underappreciated Metadata)

Although software exploitation historically started as an exercise in coaxing the target's execution into attacker-supplied binary shellcode, it soon became a practical study in pushing the limits of unexpected computation that could be caused by crafted data not containing any native code. We show how the ABI metadata that drives the creation of a process' runtime can also drive arbitrary computation. We introduce our design and implementation of Cobbler, a proof-of-concept toolkit capable of compiling a simple assembly language into well-formed ELF executable metadata that get "executed" by the runtime loader (RTLD). Our proof-of-concept toolkit highlights how important it is that defenders expand their focus beyond the code sections of untrusted binaries.

• Posters

Registered Posters

Du Tran (EXMOVES: Exemplar-based Features for Scalable Action Recognition)

This paper introduces EXMOVES, a mid-level exemplar-based representation for efficient recognition of actions in videos. The entries in our descriptor are produced by evaluating a set of movement classifiers over space-temporal volumes of the input sequence. Each movement classifier is a simple exemplar-SVM trained on low-level features, i.e., an SVM learned using a single annotated positive space-time volume and a large number of unannotated videos.

Our representation offers two main advantages. First, since our mid-level features are learned from individual video exemplars, they require minimal amount of supervision. Second, we show that simple linear classification models trained on our global video descriptor yield action recognition accuracy approaching the state-of-the-art but at orders of magnitude lower cost, since at test-time no sliding window is necessary and linear models are efficient to learn and test. This enables scalable action recognition, i.e., efficient classification of a large number of different actions even in large video databases. We show the generality of our approach by building our mid-level descriptor from two different low-level representations. The accuracy and efficiency of the approach is demonstrated on several large-scale action recognition benchmarks.

Timothy Pierson (Smart Bracelet for Smoking Cessation)

Smoking-related diseases remain the world's most preventable causes of death. In the United States alone there are 20 million smokers, and if they continue to smoke, 10 million of them will die from diseases directly attributable to smoking. Quitting smoking, however, is enormously difficult. Each year 40% of smokers will try to quit but only 3-5% will succeed. Although researchers have developed a number of cessation therapies, evaluating the efficacy of those therapies has been challenging due to a lack of reliable data on patient smoking behavior.

We propose a novel two-stage approach to provide the missing smoking behavior data. The first stage uses an innovative nicotine sensor recently developed by the Department of Chemistry at Dartmouth College. Lab tests confirm the sensor is able to detect airborne nicotine emitted by a burning cigarette. This sensor can discover smoking activity, but cannot determine if the patient is smoking or if someone else nearby is smoking. To determine if the patient is smoking, the second stage of our method uses a bracelet-mounted 9-axis accelerometer to detect the wrist movements associated with smoking. By using both stages, ultimately we hope to provide researchers with reliable data on when the patient chooses to smoke and when they are exposed to others smoking. Our work so far has focused on the nicotine sensor and unfortunately our initial experiments suggest it is not quite ready for field deployment.

Ira Ray Jenkins (Fingerprinting IEEE 802.15.4 Devices)

Wireless networks are ubiquitous in modern society. From opening pet doors to monitoring patients with implanted medical devices, the uses for embedded sensor networks seem limitless. The IEEE 802.15.4 wireless standard was developed to address the demands for inexpensive, low-power, low-rate, and low-throughput radio communication networks. These types of wireless networks are designed to be quick and easy to deploy, but may represent new attack vectors on mission-critical systems. We investigate new methods of fingerprinting these devices by exploring techniques to differentiate between multiple 802.15.4 compliant radio-hardware manufactures and firmware distributions.

Athina Panotopoulou (Sentiment Analysis of Constitutions)

Have you ever labeled different nations according to their politics? Have you ever thought about their constitutions? Or, do you think that countries which respect more the fundamental rights have "happier" constitutions? Lastly, what have in common US and Philippines? We give an answer to all of the above questions by measuring the polarity of constitutions among different countries.

Mohammad Haris Baig (Reconstructing 3D from a Single Image)

We study the problem of estimating Depth for a scene from a single RGB Image. Depth is a highly robust cue that is extremely invariant to changes in the appearance of objects and has significantly improved conventional machine vision approaches of pose estimation and gesture recognition. Image based Machine Vision techniques struggle trying to account for the immense variability in RGB Images to allow better understanding of Objects. By estimating depth from RGB Images, we aim to assist existing methods for object classification, scene categorization, segmentation etc that currently rely on RGB information only by helping to reduce this variability. We learn parametric models on a per-image basis from relevant examples in large scale RGB-D datasets (datasets comprising of Images and their corresponding depths) and propose modifications to existing methods of estimating parameters of these models. Whereas parametric models have been employed previously in estimating depth before, they do not scale well to larger datasets and show good performance for only certain scene types. We account for these limitations of parametric models and demonstrate state of the art results in a wide variety of settings.

Fanglin Chen (Dartmouth Biorhythm: Student well-being inference by passive monitoring)

A 10-week quarter with overwhelming assignments for each student is stressful. Can we find hints from the students’ life pattern to discover the status of their personality, well-being and even learning success? This work focuses on using mobile sensing techniques and Experience Sampling Methods to unveil correlations between longitudinal sensing/survey data and psychological/educational ground truth of student community.

Chen Fang (Unbiased Metric Learning)

Many standard computer vision datasets exhibit certain types of bias, which may be the consequence of illumination condition, different imaging system and preference of dataset collectors. Therefore, it is challenging to build a classification system that can generalize well to unseen and novel datasets using these biased datasets. In this work we propose Unbiased Metric Learning (UML), a metric learn-ing approach ,to achieve this goal. UML operates in the following two steps: (1) By varying hyperparameters, it learns a set of less biased candidate distance metrics on training examples from multiple biased datasets. The key idea is to learn a neighborhood for each example, which consists of not only examples of the same category from the same dataset, but those from other datasets. The learning framework is based on structural SVM and an additional constraint is introduced to ensure the desired neighborhood property. (2) Do model validation on a set of weakly-labeled web images retrieved by issuing class labels as keywords to search engine. The metric with best validation performance is selected. Although the web images sometimes have noisy labels, they often tend to be less biased, which makes them suitable for the validation set in our task. Cross-dataset image classification experiments are carried out. Results show significant performance improvement on four well-known computer vision datasets.

Submission Guidelines

To register your poster, send an with your name, poster title, and abstract.

Preparation

Consult this website from our friends in the WISP program for tips on how to make a good poster. We will have new easels this year, which should accommodate poster sizes up to A0.

Printing

Posters can be printed in the Evans Map Room, which is located in Baker/Berry Library. Acceptable formats include Powerpoint and PDF. See the Map Room FAQ for details. Posters take a nontrivial amount of time to print. Get your posters in a few days early to ensure they can all be printed in time for the conference. The CS Department will pay for CSRS poster printing. Details and account information will be sent by email to registered poster presenters.

Best poster award

To facilitate judging, presenters will be expected to stand by their posters during the poster sessions.

• Past CSRS

• FAQ

What is the CSRS?

The Dartmouth Computer Science Research Symposium is an annual exhibition conducted by the Department of Computer Science at Dartmouth College. The main objectives are to provide a means of communicating research interests and goals to not only fellow department members, but to the greater Dartmouth community as well. Hence, we welcome participation by students and faculty members who are not part of the department but are interested in applications and research in computer science. Students and faculty are given an opportunity to present their research in a professional environment, either in the form of talks, or in a comprehensive poster session, or as demonstrations of working models.

Can I attend if I am not in the Computer Science department?

Yes! We encourage participation from people working in areas related to computer science, including mathematics, engineering, security, even areas as diverse as music and arts. If you think your work would benefit from exposure to computer scientists, or if you want to know more about active research in computer science at Dartmouth, we encourage you to attend.

Do I need to register for the symposium?

No. We don't require you to register for the event. If you do plan to attend, we'd appreciate an email, so we know how many people to expect.

What were previous editions of the CSRS like?

To browse previous CSRS websites go here

How can I contact the organisers?

• Behind the logo!

Jon designed CSRS 2013 logo. Take a closer look by clicking the image to get a high resolution image.

This logo was generated using the research topics and areas of interests for the Dartmouth Computer Science faculty. The design mimicks a green, monochrome CRT screen displaying in 80x25 text-mode. Each line of text is fully justified, using fixed-width font.

• Contact Information

Organizers