January 2008 - talks - lists.cs.princeton.edu

Anirudh Badam general exam
by Melissa M Lawson 16 Jan '08

16 Jan '08

Anirudh Badam will present his research seminar/general exam on Thursday January 24 at 1PM in Room 402. The members of his committee are: Vivek Pai (advisor), Jennifer Rexford, and Larry Peterson. 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. Abstract: Web Caching is the caching of web documents in order to reduce bandwidth usage, server load and perceived download time for the web object download. A web cache stores copies of web objects when they are accessed through cache. The stored objects can be used to server subsequent requests. Web caching has been extensive studied and a plethora of techniques exist today. Solutions are based on developing good cache replacement algorithms which are used to figure out storing what objects can provide more savings, improving file systems which usually involves optimizing file systems for frequent additions, deletions and accesses, etc. However, the existing solutions have scalability problems with respect to memory. Some techniques impose lower bounds on the amount of memory needed for a web cache. Other techniques have huge virtual memory requirements leading to frequent swapping in low memory systems. Cache replacement policies need metadata for better functionality and file systems need huge lists or trees (preferably in memory) for any access to files that it stores. This requires the physical memory to scale as an increasing function of the number of web objects that the cache can store. This restricts not only the number of objects that can be stored in a web cache but also the economical affordability of the system. Hence, we propose a web caching mechanism, the HashCache, a file system optimization approach, which uses hashing to reduce the physical memory requirements. HashCache uses hashing techniques to map files to the disk locations. Hashing makes the cache maintenance and usage to be mostly memory less. Hashing mechanism also allows more flexible mechanisms for metadata maintenance and does not impose lower bounds on the requirements of memory to provide performance guarantees. HashCache exploits the distribution of sizes and contents of web objects to enable an efficient usage of the secondary storage (optimal bucket sizes). Also, with the help of experiments on an implementation of the HashCache architecture we show the usefulness of HashCache. 1. Computer Networks by Peterson and Davie 2. Operating System Concepts by Silberschatz, Galvin and Gagne 3. P. Danzig, R. Hall, and M. Schwartz, A Case for Caching File Objects inside Internetworks, Tech. Report CU-CS-642-93, Dept. of Computer Science, Univ. of Colorado, Boulder, Colo., 1993. 4. S. Acharya and S.B. Zdonik, An Efficient Scheme for Dynamic Data Replication, Tech. Report CS-93-43, Dept. of Computer Science, Brown Univ., Providence, R.I., 1993. 5. M.M. Recker and J.E. Pitkow, Predicting Document Access in Large, Multimedia Repositories, Tech. Report VU-GIT-94-35, Graphics, Visualization, and Usability Center, Georgia Tech, Atlanta, 1994. 6. D.D. Sleator, R.E. Trajan, Amortized efficiency of list update and paging rules, Commun. ACM, Vol. 2, p 202-208, 1985. 7. D. Wessels, K. Claffy, ICP and the Squid Web Cache, IEEE JSAC, Vol. 16, No. 3. 1998. 8. H. Bahn, S.H. Noh, L. Min, K. Koh, Using Full Reference History For Efficient Document Replacement In Web Caches, In Proc. USITS, Colorado, Boulder, 1999. 9. E.P. Markatos, M.G.H. Katevenis, D. Pnevmatikatos, M. Flouris, Secondary Storage Management For Web Proxies, In Proc Usits 99, Boulder, Colorado, 1999. 10. A. Sweeney, Scalability in the XFS File System, In Proc USENIX 96, San Diego, California, 1996. 11. L. Breslau, P. Cao, L. Fan, G. Phillips, Scott Shenker, Web Caching and Zipf-like Distributions: Evidence and Implications , In Proc. IEEE Infocom, 1999. 12 C. Agarwal, J. L. Wolf, P. S. Yu, Caching on the World Wide Web, IEEE Tran. Knowledge and Data Engineering, Vol. 11, No. 1, January, 1999.

1 0

Martin Suchara General Exam
by Melissa M Lawson 15 Jan '08

15 Jan '08

Martin Suchara will present his research seminar/general exam on Monday January 21 at 1PM in Room 402. The members of his committee are: Jennifer Rexford (advisor), Larry Peterson, and David August. 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. Securing Interdomain Routing in Small Groups Although the Internet's routing system has serious security vulnerabilities, none of the existing proposals for a secure variant of BGP has been successfully deployed in practice. This is not surprising since deploying protocols that require the cooperation of tens of thousands of independently-operated networks is problematic. Instead, we argue that small groups should be the basis for securing BGP. We offer a new design in which interdomain routing is secured by as few as 5-10 participating ASes, adding to the effort to secure BGP incrementally. Existence of well accepted cryptographic protocols that secure integrity and confidentiality of data delivery allows us to focus primarily on securing availability of communication. We conduct extensive simulations on a realistic Internet topology, and identify conditions for small groups to be effective. Even though the non-participants outnumber the group members by several orders of magnitude, the participants can achieve remarkable security gains by filtering compromised interdomain routes, cooperating to expose additional path diversity, inducing non-participants to select valid routes, and enlisting a few large ISPs to participate. We also propose two novel mechanisms that the group members can employ to achieve these goals, namely secure overlay routing and the cooperative announcement of each other's address space. Our experiments show that the proposed technique allows small groups to secure interdomain routing efficiently. Reading List Textbook: [1] L. Peterson, and B. Davie, Computer Networks: A Systems Approach, 3rd edition, Morgan Kaufmann Publishers, May 2003. Research papers: [1] D. Clark, "The design philosophy of the DARPA Internet protocols," ACM SIGCOMM Computer Communication Review, Vol. 18, No. 4, pp. 106-114, Aug. 1988. [2] L. Gao, "On inferring autonomous systems relationships in the Internet," IEEE/ACM Transactions on Networking, Vol. 9, No. 6, pp. 733-745, Dec. 2001. [3] O. Nordstrom, and C. Dovrolis, "Beware of BGP attacks," ACM SIGCOMM Computer Communication Review, Vol. 34, No. 2, pp. 1-8, Apr. 2004. [4] R. White, "Securing BGP through secure origin BGP," The Internet Protocol Journal, Vol. 6, No. 3, pp. 15-22, Sep. 2003. [5] S. Kent, C. Lynn, and K. Seo, "Secure Border Gateway Protocol (Secure-BGP)," IEEE Journal on Selected Areas in Communications, Vol. 18, No. 4, pp. 582-592, Apr. 2000. [6] Y. Hu, A. Perrig, and M. Sirbu, "SPV: Secure path vector routing for securing BGP," ACM SIGCOMM Computer Communication Review, Vol. 34, No. 4, pp. 179-192, Aug. 2004. [7] H. Chan, D. Dash, A. Perrig, and H. Zhang, "Modeling adoptability of secure BGP protocols," ACM SIGCOMM Computer Communication Review, Vol. 36, No. 4, pp. 279-290, Aug. 2006. [8] J. Karlin, S. Forrest, and J. Rexford, "Pretty Good BGP: Improving BGP by cautiously adopting routes," in Proc. IEEE International Conference on Network Protocols, pp. 290-299, Nov. 2006. [9] D. Wendlandt, I. Avramopoulos, D. Andersen, and J. Rexford, "Don't secure routing protocols, secure data delivery," in Proc. ACM SIGCOMM HotNets Workshop, Nov. 2006. [10] D. Andersen, H. Balakrishnan, F. Kaashoek, and R. Morris, "Resilient overlay networks," in Proc. 18th ACM Symposium on Operating System Principles, Vol. 35, No. 5, pp. 131-145, Oct. 2001.

1 0

Minlan Yugeneral exam
by Melissa M Lawson 15 Jan '08

15 Jan '08

Minlan Yu will present her research seminar/general exam on Monday January 21 at 10AM in Room 402. The members of her committee are: Jennifer Rexford (advisor), Kai Li, and David August. 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. Rethinking Virtual Network Embedding: Substrate Support for Path Splitting and Migration Abstract: Network virtualization is a powerful way to run multiple architectures or experiments simultaneously on a shared infrastructure. However, making efficient use of the underlying resources requires effective techniques for virtual network embedding --- mapping each virtual network to specific nodes and links in the substrate network. Since the general embedding problem is computationally intractable, past research has focused on two main approaches: (i) significantly restricting the problem space to allow efficient solutions or (ii) proposing heuristic algorithms that do not use the substrate resources efficiently. In this paper, we advocate a different approach: rethinking the design of the substrate network to enable simpler embedding algorithms and more efficient use of resources, without restricting the problem space. In particular, we simplify virtual link embedding by: i) allowing the substrate network to split a virtual link over multiple substrate paths and ii) employing path migration to periodically re-optimize the utilization of the substrate network. We also explore node-mapping algorithms that are customized to common classes of virtual-network topologies. Our simulation experiments show that path splitting, path migration, and customized embedding algorithms enable a substrate network to satisfy a much larger mix of virtual networks. A paper in submission about this work is available online at http://www.cs.princeton.edu/~minlanyu/embed-CCR.pdf <http://www.cs.princeton.edu/%7Eminlanyu/embed-CCR.pdf> Book: L. Peterson, and B. Davie, "Computer Networks: A Systems Approach", Morgan Kaufmann, 3e, 2003 Papers: D. Clark, "The Design Philosophy of the DARPA Internet Protocols," ACM SIGCOMM, August 1988 J.Saltzer, D.Reed and D.Clark, "End-to-End Arguments in System Design", ACM Transactions on Computer Systems, Nov 1984. T. Anderson, L. Peterson, S. Shenker, and J. Turner, "Overcoming the Internet impasse through virtualization," IEEE Computer Magazine, vol. 38, no. 4, pp. 34-41, 2005. A.Bavier, N.Feamster, M.Huang, L.Peterson, and J.Rexford, "In VINI Veritas: Realistic and Controlled Network Experimentation", in Proc. ACM SIGCOMM, Sep 2006. N. Feamster, L. Gao, and J. Rexford, "How to lease the Internet in your spare time," SIGCOMM Comput. Commun. Rev., vol. 37, no. 1, pp. 61-64, 2007. Y. Zhu and M. Ammar, "Algorithms for assigning substrate network resources to virtual network components," in Proc. IEEE INFOCOM, 2006. R. Ricci, C. Alfeld, and J. Lepreau, "A solver for the network testbed mapping problem," ACM Computer Communication Review, vol. 33, no. 2, pp. 65-81, 2003. J. Fan and M. Ammar, "Dynamic topology configuration in service overlay network: A study of reconfiguration policies", in Proc. IEEE INFOCOM, 2006. J. Lu and J. Turner, "Efficient mapping of virtual networks onto a shared substrate", Washington University, Technical Report WUCSE-2006-35, 2006. N. G. Duffield, P. Goyal, A. Greenberg, P. Mishra, K. K. Ramakrishnan, and J. E. van der Merwe, "Resource management with hoses: Point-to- cloud services for virtual private networks," IEEE/ACM Trans. Netw., vol. 10, no. 5, pp. 679-692, 2002.

1 0

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