CSE642 Algorithms Seminar

Locations and Hours:

Friday 11:00-12:30 @ 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.
  • 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. Please email me (Jie Gao) if you want to be added to the list.

Schedules for Fall06: (past offering: Spring 2006)

9/8: Prof. Steve Skiena has a top secret open problem.

9/15: Guest talk by Dr. Joshua Buresh Oppenheim.

Title:  Towards Models for Backtracking and Dynamic Programming


Since most algorithms that people use can intuitively be classified into large paradigms of algorithms such as greedy, dynamic programming, linear and semidefinite programming, local search, etc., it is natural to ask what problems can be computed by these paradigms. This question can be seen as an alternative to asking what problems can be computed by all, say, poly-time algorithms in that the restriction on the algorithms is more conceptual rather than complexity-theoretic.  Of course, to ask a question about an algorithmic paradigm, you first have to formally define the paradigm. We offer one very natural model, pBT, which captures many algorithms generally considered to be dynamic programming or backtracking.  This model is an extension of the Priority Algorithm model of Borodin, Nielsen and Rackoff, which captures greedy algorithms.  We demonstrate many upper and lower bounds in this model for problems such as interval scheduling, knapsack and SAT.  We then define a stronger model, pBP, and show that it seems to capture some aspects of dynamic programming that pBT does not, but still does not solve even tractable problems that do not intuitively have dynamic programming algorithms.

This is joint work with Mikhail Alekhnovich, Allan Borodin, Sashka Davis, Russell Impagliazzo, Avner Magen and Toni Pitassi.

9/22: Prof. Rob Johnson led an open problem session about graph compression.

9/29: Prof. Joe Mitchell led an open problem session.

10/6: We continue on Rob Johnsonís problem on graph compression.

10/13: Update on min weight triangulation problem and continued discussion.

10/20: Guest talk by Jia Fang from Yale University on localization in sensor networks.

Title: Localization in Sparse Networks using Sweeps

Abstract: A bilateration ordering of a graph is an ordering of its vertices so that the first two vertices of the ordering are adjacent, and each subseequent vertex is adjacent to at least two vertices preceding it. We consider networks whose underlying graphs have a bilateration ordering and are also generically globally rigid. We give a provably correct localization algorithm for such networks under the assumption that the given inter-node distances are exact.

The worst case computational complexity of the algorithm is exponential. However, we show by experimental evaluation that the algorithm can feasibly localize a large class of networks with average degree as low as three. We devise some techniques for the case where the given inter-node distances may be noisy, which experimental evaluations indicate is promising.

10/27: Guest talk by Prof. Vincenzo Liberatore.

11/3: Guest talk by Alexandar Kroller.

Title: The Energy-Constrained Unit-Transit Dynamic Network Flow Problem.

Joint work with Sandor Fekete and Ekkehard Koehler

11/10: Fall workshop on computational geometry, Smith College.

11/17: Talk by Prof. Radu Sion.

Title: Conditional E-Cash

We introduce a novel conditional e-cash protocol allowing future anonymous cashing of bank-issued e-money only upon the satisfaction of an agreed-upon public condition. Payers are able to remunerate payees for services that depend on future, yet to be determined outcomes of events. Once payment complete, any double-spending attempt by the payer will reveal its identity; no double-spending by the payee is possible. Payers can not be linked to payees or to ongoing or past transactions. The flow of cash within the system is thus both correct and anonymous. We discuss several applications of conditional e-cash including online trading of financial securities, prediction markets, and betting systems.

If you are interested in getting your hands on the paper before the seminar, please email sion AT cs DOT sunysb DOT edu and Radu will print and deliver a copy for you. He in fact encourages you to do so. The reasons for the paper version are complicated, illogic, yet mandatory (having to do with corporate rules on IP).

11/24: Thanksgiving.

12/1: Open problem session, led by Jie Gao, on embedding of a graph s.t. greedy forwarding is always successful.

12/8: NYU theory day.

12/15: Last meeting! Followed by CS department party.

Last updated: 12/7/06