CSE642 Algorithms Seminar

Locations and Hours:

Wednesday 11:00-12:15 @ Computer Science Lounge (CS Building 1211).

Course Description:

This reading group provides a meeting place for Stony Brook faculty, postdocs, and students interested in the analysis of algorithms. We meet once a week, with one of three different missions:

• Paper presentations -- This is fairly informal, with one person (i.e. student) responsible each time for leading the discussions. Nobody will have to lead for more than one paper per semester. We highly encourage students to volunteer for paper presentations, as it is a good opportunity to learn how to give a technical presentation and our reading group is a friendly group of audience to start with. The list of papers you can choose to present, if you do not have a paper already, can be found below.
• Open Problem Bull Sessions -- where we pose and attack accessible research problems. A good time is had by all.
• Road Trips -- to the special computational geometry or theory days at NYU, Columbia, and the like.

You can get one credit for participating by simply registering for CSE 642. You are also welcome to come without registering. 

We have a mailing list. Further announcement will be distributed through the list. Please email me (jgao at cs) to be added to the mailing list.

Schedule:

September 3: introduction and open problem session (Joe proposed the Shrokuro problem).

September 10: Special session featuring Ashish Lohia and Shang Yang’s RPE. 10am-12am. Location: AMS Seminar Room, Math 1-122A.

September 17: Invited speaker: Prof. Matya Katz from Ben Gurion University

Title: Polynomial-Time Approximation Schemes for Piercing and Covering with Applications in Wireless Networks

Abstract: Let D be a set of disks of arbitrary radii in the plane, and let P be a set of points. In this talk we focus on the following problem (and mention several related problems), with applications in wireless networks. Assuming P contains the set of center points of disks in D, find a minimum-cardinality subset P^* of P (if exists), such that each disk in D is pierced by at least h points of P^*, where h is a given constant. We call this problem "minimum h-piercing". We present a constant-factor approximation algorithm for this problem, followed by a polynomial-time approximation scheme. The PTAS is based on an adapted and extended version of Chan's separator theorem. The talk is based on join work with Paz Carmi and Nissan Lev-Tov.

September 24: Open problem session led by Luis Ortiz on a coloring problem: given a graph and a threshold for each node between [1, degree-1], such that a node will be colored black if the number of black neighbors is strictly smaller than the threshold, and colored white otherwise. Question: is such a coloring always possible? If so, give an algorithm. If not, is testing for colorability NP-complete?

October 1: holiday, no class.

October 8:

October 15:

October 22:

October 29:

Events:

1. Fall workshop on Computational Geometry 2008: October 31-November 1^st, at RPI. 2-page abstract submission Deadline is September 15^th, 2008.

2. NY theory day, TBD.

3. New York Computer Science and Economics Day (NYCE Day), October 3^rd.

Past offerings:

Spring 2008, Fall 2007, Spring 2007, Fall 2006, Spring 2006.