SCS
Student
Seminar
Series

go to the list of abstracts
abstracts

go to the list of previous talks
previous talks

go to the list of other SCS seminars
scs seminars

go to the SCS home page
SCS

go to the CMU home page
CMU

     

The Next Talk Sp'16 Talks General Info Speaking Req't

A General Framework for Frontier-Based Approximate Shortest Paths

Monday, May 2nd, 2016 from 12-1 pm in GHC 2109.

Aram Ebtekar, CSD

The A* algorithm aims to balance depth-first (greedy) and breadth-first (Dijkstra) search to quickly find an approximate shortest path in a graph. While its runtime will depend on choosing a good heuristic suitable to the domain's structure, we can under mild conditions guarantee that each state is expanded at most once, and that a solution will be found to within a configurable optimality factor. In this talk, we explore these conditions in great generality, leading to a framework that encapsulates a family of known search algorithms. Some of these algorithms provide additional benefits, such as anytime solution bound improvement, dynamic path repair, multi-core processing, and the use of multiple inadmissible heuristics. Using this framework, we can better understand existing algorithms, mix and match their features in a modular fashion, and design new variants with the same theoretical guarantees. In particular, we present ePA*SE, an efficient parallel version of A*.

Joint work with Maxim Likhachev.

In partial fulfillment of the Speaking Requirement.


Spring 2016 Schedule
Mon, Jan 18 GHC 6501 Expired
Fri, Jan 22 GHC 6501 Expired
Mon, Jan 25 GHC 6501 Expired
Fri, Jan 29 GHC 6501 UNAVAILABLE
Mon, Feb 1 GHC 6501 Shen Chen Xu Parallel and Distributed Graph Decomposition with application to Spanners
Fri, Feb 5 GHC 6501 Expired
Mon, Feb 8 GHC 6501 Expired
Fri, Feb 12 GHC 6501 Expired
Mon, Feb 15 GHC 6501 Expired
Fri, Feb 19 GHC 6501 Expired
Mon, Feb 22 GHC 6501 Expired
Fri, Feb 26 GHC 6501 Expired
Mon, Feb 29 GHC 6501 Expired
Fri, Mar 4 GHC 6501 Expired
Mon, Mar 7 GHC 6501 Expired
Fri, Mar 11 GHC 6501 Expired
Fri, Mar 18 GHC 6501 Expired
Mon, Mar 21 GHC 6501 Expired
Fri, Mar 25 GHC 6501 John Wright How to learn a quantum state
Mon, Mar 28 GHC 6501 Expired
Fri, Apr 1 GHC 6501 Expired
Mon, Apr 4 GHC 6501 Expired
Fri, Apr 8 GHC 6501 Expired
Mon, Apr 11 GHC 6501 Expired
Fri, Apr 15 GHC 4303 Spring Carnival By request only
Mon, Apr 18 GHC 6501 Junchen Jiang CFA: A Practical Prediction System for Video QoE Optimization
Fri, Apr 22 GHC 6501 Hannah Gommerstadt Monitoring and Blame Assignment for Higher-Order Session Types
Mon, Apr 25 GHC 6501 Ameya Velingker Bridging the Capacity Gap Between Interactive and One-Way Communication
Fri, Apr 29 GHC 6501 Expired
Mon, May 2 GHC 2109 Aram Ebtekar A General Framework for Frontier-Based Approximate Shortest Paths
Fri, May 6 NSH 3002 Logan Brooks Forecasting Seasonal Epidemics of Influenza with an Ensemble of Customized Statistical Methods
Mon, May 9 GHC 6501 Yixin Luo Data Retention in Flash-Based SSDs


General Info

The Student Seminar Series is an informal research seminar by and for SCS graduate students from noon to 1 pm on Mondays and Fridays. Lunch is provided by the Computer Science Department (personal thanks to Sharon Burks and Debbie Cavlovich!). At each meeting, a different student speaker will give an informal, 40-minute talk about his/her research, followed by questions/suggestions/brainstorming. We try to attract people with a diverse set of interests, and encourage speakers to present at a very general, accessible level.

So why are we doing this and why take part? In the best case scenario, this will lead to some interesting cross-disciplinary work among people in different fields and people may get some new ideas about their research. In the worst case scenario, a few people will practice their public speaking and the rest get together for a free lunch.


Guideline & Speaking Requirement Need-to-Know

Note: Step #1 below are applicable to all SSS speakers. You can schedule AT MOST THREE talks per semester.

SSS is an ideal forum for SCS students to give presentations that count toward fulfilling their speaking requirements. The specifics, though, vary with each department. For instance, students in CSD will need to be familiar with the notes in Section 8 of the Ph.D. document and follow the instructions outlined on the Speakers Club homepage. Roughly speaking, these are the steps:

  1. Schedule a talk with SSS by sending your talk title, abstract, additional info (like "Joint work with..." or "In Partial Fulfillment of the Speaking Requirement"), and a picture of yourself (preferably jpeg) to sss@cs at least TWO WEEKS before your scheduled talk.
  2. After you are confirmed with your SSS slot, go to the Speakers Club Calendar and schedule your talk at least THREE WEEKS in advance of the talk date.
  3. On the day of your talk, make sure you print Speakers Club evaluation forms for your evaluators to use.
Students outside of CSD will need to check with their respective departments regarding the procedure. As another example, ISRI students fulfill their speaking requirements by attending a semesterly Software Research Seminar and giving X number of presentations per school year. If you have experience with your department that might help others in your department, please feel free to contribute your knowledge by emailing us. Thank you!


SSS Coordinators

Armaghan Naik, Computational Biology
Lin Xiao, CSD

 


Web contact: sss+www@cs