- talks - lists.cs.princeton.edu

G Reis preFPO
by Melissa M Lawson 15 Jan '08

15 Jan '08

George Reis will present his preFPO on Friday, January 18th at 10:00am in Room 402. The members of his committee are David August: advisor: Niraj Jha (ELE) and Shubu Mukherjee (Intel), readers; David Walker and Li-Shiuan Peh (ELE), nonreaders. Everyone is invited to attend his talk. His abstract follows below. ----------------------------------------------------------- Software Modulated Fault Tolerance In recent decades, microprocessor performance has been increasing exponentially, due in large part to smaller and faster transistors enabled by improved fabrication technology. While such transistors yield performance enhancements, their smaller size and sheer number make chips more susceptible to transient faults. Designers frequently introduce redundant hardware or software to detect or recover from these faults because process and material advances are often insufficient to mitigate their effect. Regardless of the methods used for adding reliability, these techniques incur unnecessary and significant performance penalties by uniformly protecting the entire application. They do not take into account the varying resilience to transient faults of different program regions. This overprotection leads to wasted resources that reduce performance. To maximize fault coverage while minimizing the performance impact, this thesis takes advantage of the key insight that not all faults in an unprotected application will cause an incorrect answer and not all parts of the program respond the same way to reliability techniques. First, this thesis demonstrates the varying vulnerability and performance responses of an application and identifies those regions which are most susceptible to faults as well as those which are inexpensive to protect. Second, this thesis advocates the use of software and hybrid approaches to fault tolerance to enable the synergy of high-level information with specific redundancy techniques. Third, this thesis demonstrates how to exploit this non-uniformity via Software-Modulated Fault Tolerance (SMFT). SMFT leverages reliability and performance information at a high level and directs the reliability choices at fine granularities to provide the most efficient use of processor resources for an application. This thesis shows the effectiveness of SMFT via two specific implementations: one that utilizes both performance and reliability profiles to achieve effective trade-offs, and a second that only uses code information to direct the reliability choices.

1 0

D Steurer general exam
by Melissa M Lawson 11 Jan '08

11 Jan '08

David Steurer will present his research seminar/general exam on Friday January 18 at 2PM in Room 402. The members of his committee are: Sanjeev Arora (advisor), Moses Charikar, and Bernard Chazelle. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Unique Games with Expanding Constraints Graphs are Easy We consider the following constraint satisfaction problem: Given an over-determined system of linear equations modulo a prime number k, where each equations depends only on two variables, we want to find a solution that satisfies as many of the equations as possible. Khot's Unique Games Conjecture asserts that this problem is hard to approximate even if almost all equations can be satisfied. Proven true, the conjecture would imply that current algorithmic techniques are optimal for many combinatorial optimization problems, in particular, Maximum Cut and Vertex Cover. By some researchers, it has also been conjectured that the problem remains hard to approximate even if the constraint graph of the instance has significant expansion. This conjecture would have implied strong inapproximability results for the notorious Sparset Cut problem. In this talk, I will present an approximation algorithm that refutes the latter conjecture. Our algorithm is based on a novel analysis of a well-known semidefinite programming relaxation. Our analysis also leads to a strong parallel repetition theorem for unique games when the constraint graph is an expander. The presented results are based on joint work with Sanjeev Arora, Subhash Khot, Alex Kolla, Madhur Tulsiani, and Nisheeth Vishnoi. books / survey articles: - Kleinberg, Tardos. Algorithm Design. - Boyd, Vandenberghe. Convex Optimization. - Lovasz. Semidefinite programs and combinatorial optimization. - Hoory, Linial, Wigderson. Expander graphs and their applications. (Chapters 2,4,7) - Arora, Barak. Complexity Theory: A Modern Approach. (PCP Chapters, 18 & 19) research articles: - Lovasz. On the Shannon capacity of a graph. - Feige, Lovasz. Two-prover one-round proof systems, their power and their problems. - Goemans, Williamson. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. - Karger, Motwani, Sudan. Approximate Graph Coloring by Semidefinite Programming. - Alon, Naor. Approximating the Cut-Norm via Grothendieck's Inequality. - Trevisan. Approximation algorithms for unique games. - Charikar, Makarychev, Makarychev. Near-optimal algorithms for unique games. - Chlamtac, Makarychev, Makarychev. How to Play Unique Games Using Embeddings. - Khot. On the power of unique 2-prover 1-round games. - Khot, Kindler, Mossel, O'Donnell. Optimal inapproximability results for max-cut and other 2-variable CSPs? - Khot, Vishnoi. The unique games conjecture, integrality gap for cut problems, and embeddability of negative type metrics into l1.

1 0

R Fiebrink general exam
by Melissa M Lawson 04 Jan '08

04 Jan '08

Rebecca Fiebrink will present her research seminar/general exam on Thursday January 10 at 2PM in Room 402. The members of her committee are: Perry Cook (advisor), David Blei, and Ken Steiglitz. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. Abstract In this talk, I will present recent work on incorporating analysis into the ChucK music programming language. A consequence of this project is that composers and musicians can perform live audio analysis, even coding on the fly, using a powerful and flexible programming language framework, and then use the output of analysis tasks to drive synthesis parameters or to provide features for training and running classifiers in real-time. This work also provides music information retrieval researchers with a tool for fast prototyping of music analysis and modeling algorithms, which can be incorporated into live performance settings as well as off-line music analysis. As such, this project draws heavily on prior work in music information retrieval (MIR), applied machine learning, human computer interaction, and computer music systems and performance practices. In the past decade, MIR has blossomed as a research area, drawing on disciplines including machine learning, library science, signal processing, HCI, systems design, and information retrieval. Popular research problems include learning semantically meaningful categorizations of acoustic or symbolic data (e.g., genre labels), extracting musically or cognitively-salient features from audio (e.g., pitch and harmony transcription, audio source separation), and providing new interfaces and systems for people to search for music and organize large music collections (e.g., query-by-humming, content-based playlist generation). Many of these problems have been addressed in recent years using standard or novel machine learning and modeling techniques. A variety of programming frameworks and languages have been developed to create music since the 1950s. These languages are used in live musical performance, as well as interactive sound and art installations. Recently, languages such as ChucK have enabled performers to write and modify code during performances, a practice known as live-coding. Most music programming languages offer tight control over sound synthesis and modification and draw on established metaphors for exposing this control. These languages tend not to offer much support for analysis tasks (e.g., feature extraction); when musicians do integrate analysis into real-time performance (e.g., pitch tracking), they tend to use customized, task-specific systems. Computer music and MIR have proceeded as mainly independent fields, despite potential benefits of cross-pollination. Many MIR systems would be appropriate and useful in a performance context, and MIR research would be enriched by a consideration of the goals and constraints unique to live music, but no existing MIR or computer music framework is appropriate for both performance and analysis. Therefore, we have worked to add analysis capabilities into ChucK, lowering the barriers to MIR researchers wishing to prototype or port algorithms to a real-time performance context, and to computer musicians wishing to incorporate such algorithms into their performance. The first step of this work was to design new classes and data flow models for analysis that were in harmony with ChucK's existing conventions for syntax, synchronization, objects, and controlling events in time. We were then able to implement common analysis-driven synthesis tasks and extractors for standard MIR features. Following this, we incorporated the ability to perform "on-the-fly" machine learning using the extracted features. At present, several standard computer music and MIR tasks have been implemented using ChucK's growing collection of feature extractors and classifiers. It is hoped that this work will provide new avenues for both artistic expression and technical exploration. We have released the new version of ChucK with analysis to the public, and we plan to take advantage of these new capabilities in future compositions for the Princeton Laptop Orchestra. We are also excited to explore practical issues presented by "on-the-fly" learning, including dealing with the computational constraints of real-time performance. Next steps in this work involve efficiency-driven refinements to the language and building infrastructure to accommodate more sophisticated musical modeling tasks. Reading list Bergstra, James, Norman Casagrande, Dumitru Erhan, Douglas Eck, and Balazs Kegl. 2006. Aggregate features and AdaBoost for music classification. Machine Learning 65: 473-484. Collins, Nick, Alex McLean, Julian Rohrhuber, and Adrian Ward. 2003. Live coding in laptop performance. Organised Sound 8(3): 321-330. Downie, J. Stephen. 2003. Music information retrieval. In Annual Review of Information Science and Technology 37, ed. Blaise Cronin, 295-340. Medford, NJ: Information Today. Ellis, Daniel P. W., and Graham E. Poliner. 2006. Classification-based melody transcription. Machine Learning 65: 439-456. Jordan, Michael I. 2004. Graphical models. Statistical Science 19(1): 140-155. Lew, Michael S., Nicu Sebe, Chabane Djeraba, and Ramesh Jain. 2006. Content-based multimedia information retrieval: State of the art and challenges. ACM Transactions on Multimedia Computing, Communications and Applications 2(1): 1-19. Raphael, Chris. 2001. A probabilistic expert system for automatic musical accompaniment. Journal of Computational and Graphical Statistics 10(3): 487-512. Rowe, Robert. 2001. Machine musicianship. Cambridge, MA: The MIT press. Schapire, Robert E. 2001. The boosting approach to machine learning: An overview. MSRI Workshop on Nonlinear Estimation and Classification, Berkeley, CA, March. Tzanetakis, Georg, and Perry R. Cook. 2002. Musical genre classification of audio signals. IEEE Transactions on Speech and Audio, July. Wang, Ge. Forthcoming. A history of programming and music. In Cambridge Companion to Electronic Music, ed. Nick Collins and Julio D'Escrivan. Cambridge University Press.

1 0

S Brahma general exam
by Melissa M Lawson 03 Jan '08

03 Jan '08

Siddhartha Brahma will present his research seminar/general exam on Monday January 7 at 2PM in room 402. The members of his committee are: Robert Tarjan (advisor), Moses Charikar, and Sanjeev Arora. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Distribution Sensitive Data Structures A distribution sensitive data structure is one whose running time on a sequence of operations supported by the data structure depends on some distributional properties of the sequence. Although some work had been done before, distribution sensitive data structures became important after the seminal paper on Splay trees by Sleator and Tarjan[0]. In the paper several types of distributive properties were defined and it was proved that splay trees have several of these properties (eg. static optimality, working set property, dynamic finger property, etc) by using amortized analysis, and miraculously without storing any extra information about the sequence. Then the question naturally arises whether we can define similar properties for data structures other than binary search trees. There has been interesting work recently in terms of both defining new properties (unified property) and proving these properties for new or existing data structures (eg. planar point location data structures, priority queues, etc). We will start off with a broad survey of the whole area. Then we will prove several results for the working set data structure extending it to work for predecessor queries and improving the insertion and deletion times. We will also look at an extension of splay trees called Multi-Splay trees that has been recently proposed. We will prove new results on the amortized time to perform joins and splits on Multi-Splay trees. Reading List: [0] D. D. Sleator and R. E. Tarjan. Self-adjusting binary search trees. J.ACM, 1985. [1] John Iacono. Distribution Sensitive Data Structures. Ph.D. Thesis. Rutgers, SUNY,2001. [2] Chengwen Chris Wang. Multi-Splay Trees. PhD thesis, CMU, Pittsburg, PA, 2006. [3] Introduction to Algorithms. Cormen, Leiserson, Rivest and Stein, MIT Press, 2001.(Chapters 10-14, 17, 18-21) [5] J.Iacono and S.Langerman. Proximate planar point location. in SODA 2003 [6] R. E. Tarjan. Amortized computational complexity. SIAM J. Appl. Discrete Meth., 1983. [7] Data Structures and Network Algorithms. Robert E. Tarjan, 1983 [8] John Iacono: Optimal planar point location. SODA 2001 [9] Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu: Dynamic Optimality--Almost. FOCS 2004 [10] C.C.Wang, J.Derryberry, D.D.Sleator: O(\log\log n)-competitive dynamic binary search trees. SODA 2006 [11] Heather D. Booth. An overview of Red-Black and Finger Trees. Technical Report. Princeton University, 1990.

1 0

talk at 11am on routing-protocol convergence by Pierre Francois
by Jennifer Rexford 14 Dec '07

14 Dec '07

TALK ANNOUNCEMENT: Title: BGP convergence in much less than a second Speaker: Pierre Francois, Universite Catholique de Louvain Date: 11:00am on Friday December 14 Location: CS room 402 Abstract -------- This talk will about recent improvements to the Border Gateway Protocol, the routing protocol used by Internet Service Providers to exchange routing information to provide Internet-wide connectivity. It will show how a fast recovery of connectivity can now be achieved in the case of a link or node failure within an ISP network. We will emphasize that most business cases allow a local BGP recovery (convergence) in case of failure, i.e. a convergence where inter-domain path exploration is actually not required to recover the connectivity after a failure. We will show that although convergence could be local, iBGP deployements do not favor the propagation of alternate paths within an ISP network, which artificially lead to transient lack of connectivity, disclosed to neighboring peers. We will then turn to router implementation issues that could not allow a fast convergence of BGP due to the scaling factors of BGP Reaching sub-second convergence of BGP will however be shown possible by first allowing a better propagation of alternate paths within ISP networks, and second enable the recent improvements to BGP router implementations and to Forwarding Information Bases designs.

1 0

F Perry preFPO
by Melissa M Lawson 13 Dec '07

13 Dec '07

Frances Perry will present her preFPO on Wednesday December 19 at 10:30 AM in Room 402. The members of her committee are: David Walker, advisor; Andrew Appel and David Tarditi (Microsoft), readers; David August and Margaret Martonosi, nonreaders. A copy of her abstract follows below. Everyone is invited to attend her talk. Formal Reasoning about Transient Faults My thesis research focuses on guaranteeing that software is reliable in the presence of transient faults. A transient fault occurs when an energetic particle strikes a chip and causes a change in state in the processor. These faults do not cause permanent damage, but they may affect the computation that is currently executing. Transient faults have been shown to be the cause of crashes at major companies, and current technology trends, such as decreasing transistor size, will make future processors much more susceptible. Researchers in architecture and compilers have already developed a number of different solutions using software, hardware or a combination of the two. The general approach of all these solutions is to duplicate computations and check for consistency between the copies. Unfortunately, generating correct fault-tolerant code is difficult, and there has been very little research on verifying these techniques. Testing is rarely sufficient because full coverage would require testing all combinations of features in conjunction with all combinations of faults. Along with colleagues, I designed a new type system that guarantees that faulty executions of a well-typed program are identical to non-faulty executions up to the point where a fault is detected. We use a hybrid hardware-software solution in which an added hardware queue buffers the stores from the original computation and only writes them to memory if the duplicate computation agrees. Faults can occur at any point and randomly modify a register or queue value. The assembly-level type system tracks information about the two computations which we use to rigorously prove that well-typed programs satisfy reliability properties. We use these reliability properties to show that all executions containing a single fault will always detect the fault before the difference from non-faulty versions becomes observable. More recently, I designed a typed system for reasoning about software solutions for control-flow faults. Control-flow faults arise when a fault causes a jump or branch instruction to transfer control to an unexpected code address. Current software solutions can detect most, but not all, control-flow faults. I formally analyzed a subset of these solutions that can detect any fault that causes incorrect control transfers between basic blocks. Similarly to the previous work, this is accomplished by using a type system to track reliability properties. However, the type system contains new techniques that allow it to reason soundly even when code transfers to an unexpected location and continues executing. Here, I proved that executions with a single fault will visit at most one incorrect block before the fault is detected.

1 0

M Hibbs FPO
by Melissa M Lawson 13 Dec '07

13 Dec '07

Matt Hibbs will present his FPO on Thursday December 20 at 2PM in Icahn Labs Room 280. The members of his committee are; Olga Troyanskaya, advisor; Tom Funkhouser and Kai Li, readers; David Botstein (Genomics) and Leonid Kruglyak (Mol Bio), nonreaders. A copy of his thesis, "Analysis and Visualization of Large-Scale Gene Expression Microarray Compendia" is on display in Room 310. Everyone is invited to attend his talk.

1 0

Talk Today
by Ginny Hogan 12 Dec '07

12 Dec '07

Shaz Qadeer, Microsoft Research, will present his talk, "Taming Concurrency: A Program Verification Perspective", 4:15pm Computer Science room 105 -

1 0

11am Fri Dec 14 talk on routing-protocol convergence by Pierre Francois
by Jennifer Rexford 10 Dec '07

10 Dec '07

TALK ANNOUNCEMENT: Title: BGP convergence in much less than a second Speaker: Pierre Francois, Universite Catholique de Louvain Date: 11:00am on Friday December 14 Location: CS room 402 Abstract -------- This talk will about recent improvements to the Border Gateway Protocol, the routing protocol used by Internet Service Providers to exchange routing information to provide Internet-wide connectivity. It will show how a fast recovery of connectivity can now be achieved in the case of a link or node failure within an ISP network. We will emphasize that most business cases allow a local BGP recovery (convergence) in case of failure, i.e. a convergence where inter-domain path exploration is actually not required to recover the connectivity after a failure. We will show that although convergence could be local, iBGP deployements do not favor the propagation of alternate paths within an ISP network, which artificially lead to transient lack of connectivity, disclosed to neighboring peers. We will then turn to router implementation issues that could not allow a fast convergence of BGP due to the scaling factors of BGP Reaching sub-second convergence of BGP will however be shown possible by first allowing a better propagation of alternate paths within ISP networks, and second enable the recent improvements to BGP router implementations and to Forwarding Information Bases designs.

1 0

Speaker Wednesday -
by Ginny Hogan 10 Dec '07

10 Dec '07

Shaz Qadeer, Microsoft Research, will present his talk "Taming Concurrency: A Program Verification Perspective" Wednesday Dec 12th at 4:15 pm Computer Science Room 105 -

1 0