CSE 592 Advanced Topics in Computer Science -- Propagation Processes and Algorithms on Networks

Fall 2010


Section Information

Date: Mon-Wed
Time: 5:20pm-6:40pm
Room: 1306

Instructor Information

Instructor: Luis Ortiz
Email: le [last name] at cs followed by .sunysb and finally .edu
Office: 2313-c
Phone: (631) 632-1805
Office Hours: 6:50pm-7:50pm M, 2:00pm-4:00pm Tu (or by appointment)

Course Description

The need to study and solve problems in complex systems, and specially complex networks, has given rise to a variety of so called computational ``network-based'' models. Despite the specific differences in the nature of the settings and problems each model addresses, there is striking commonality on some of the kinds of algorithms that have been developed to solve the different problems. One such class of algorithms is inherently based on so called propagation processes, in which ``local information'' (with respect to the network graph) is passed between nodes in the network with the ultimate goal of achieving some ``global'' objective. Of course, the precise type of information propagated depends highly on the specific setting and problem, as are the notions of ``local'' and ``global.''

Propagation-based algorithms have had tremendous practical success in areas such as near-optimal coding in digital communication, planning, scheduling and other resource allocation problems in AI, speech recognition, the analysis of digital circuits in electrical engineering, the determination of protein structure in computational biology, and stereo and image restoration in computer vision, to name a few. The now widely famous PageRank algorithm, which is fundamental to the way in which Google rank pages, also has an interpretation as a propagation algorithm.

This course will cover the fundamental ideas behind propagation-type processes and other similar algorithms that have been used to solve problems in a wide variety of network-based models. There will be an emphasis on highlighting and exploring commonalities between the different propagation processes and algorithms among the different models. The interest is on applying existing or developing novel propagation-based algorithms to new domains. There is also interest in potentially gaining or providing alternative insight into the behavior of propagation algorithms (empirically and theoretically), and perhaps even improving upon them.

Course Purpose and Objectives

Course Organization

The course format involves formal lectures, discussions and presentations, some led by the students themselves. Reading material from a variety of sources, including textbooks, tutorials, classical and recent research papers, and other possible web content, will be handed out, posted or assigned to supplement the lectures.

Course Project

Students complete a research project on a relevant topic. The specific problem requires the instructor's approval. Possible projects include, but are not limited to, an application of a particular model and technique to a specific problem, the development of a system based on network model ideas to solve a particular problem for a particular application domain, or novel experimental evaluations and comparisons of one or various propagation techniques. Ideally, the project would incorporate a combination of theoretical and experimental work. Projects that involve exclusively theoretical work may be permitted only under very close consultation with the instructor and should involve a narrowly and clearly defined problem description and line-of-attack. Students periodically submit progress reports to monitor the project's development. Students give a presentation and submit a written report on the results of the project by the end of the course.

Student Evaluations

Students performance will be evaluated based on their level of participation during the discussions, and the quality of their topic oral presentation and written report, as well as their project's proposal, progress reports, oral presentation and final written report. There may also be sporadic written and/or code/implementation homework assignments (at the discretion of the instructor).

Tentative List of Topics

See syllabus for a tentative list of topics