- talks - lists.cs.princeton.edu

A Halderman preFPO
by Melissa M Lawson 11 May '07

11 May '07

Alex Halderman will present his preFPO on Thursday, May 17 at 10 A.M. in CS 302. The members of his committee are: Ed Felten, advisor; Andrew Appel and Avi Rubin (Johns Hopkins), readers; Adam Finkelstein and Brian Kernighan, non-readers. Everyone is invited to attend his talk. The abstract follows below. ------------- Learning from Security Failures in Non-Traditional Computing Environments Decades of bitter experience with security failures in desktop computers and network environments have led to intuitions and engineering practices that help us build more robust systems. However, as computers are becoming smaller and cheaper, they are taking on new forms that challenge our intuitions. >From RFID tags embedded in sneakers and passports, to "smart" cell phones and car navigation systems, many new applications occupy environments that look little like those with which researchers are familiar, and the old rules increasingly do not apply. When security fails in such environments, it often fails spectacularly, with layers of vulnerabilities that, compounded, are costly or impossible to repair. By studying such security disasters, and asking why they are especially severe, we hope to develop new security techniques suitable for a world of ubiquitous computing. One traditional security intuition that is now being challenged is the distinction between data and software. When received from a trusted source, data files are considered a lower risk than software, since only software can contain security bugs that weaken the computer's defenses. Recent events cause us to question the value of this distinction. In a widely-publicized incident, the record label Sony-BMG sold several million music CDs (normally considered a data-only medium) that contained undisclosed software intended to thwart copying. We studied this software using a variety of analytical techniques and discovered that it contained serious defects that threatened consumers' security and privacy. Merely playing the CDs caused the installation of dangerous software that provided several routes for attackers to subvert the computer's security mechanisms. These problems were exacerbated by the non-traditional environment of a hybrid music and software CD, which allowed the discs to avoid scrutiny by the ecosystem of security software vendors that monitor for deviant behavior. Other security intuitions are being challenged in the realm of embedded computers. Once, such systems were though of as "dumb" appliances, protected from most security risks by their simple designs and lack of network connectivity, but as they have grown increasingly sophisticated, they have come to resemble full-blown computers, together with the attendant security problems. We found evidence of this trend in the United States' most widely used electronic voting machine, the Diebold AccuVote-TS. Using reverse-engineering and novel software analysis methods, we discovered that the machine suffers from many of the same security problems as desktop PCs, including the potential for attackers to install malicious software and spread viruses from machine to machine. Because of its embedded nature, the machine has none of the protections that are now standard on desktop computers. As a result, an attacker could exploit these problems to steal votes undetectably on a wide scale. In many ways, our approach to these and other examples can be compared to the systematic disaster investigations conducted after major transportation accidents or structural failures. We seek to learn what went wrong not only in each particular case but also in the broader context that allowed the problems to occur. Our findings highlight the need to extend existing protections to non-traditional environments, as well as to develop new security techniques that are suitable to these applications. We propose specific remedies in each case, such as cryptographic privacy protection protocols for camera phones, and efficient machine-assisted auditing techniques for voting. We also apply our theories to predict problems that may be discovered in the future: for instance, Internet worms that spread by exploiting weaknesses in the new generation of networked videogame consoles. Finally, we consider legislative and regulatory remedies, including policy measures that have already gained momentum in the wake of our findings concerning the Sony-BMG and Diebold systems.

1 0

Y Zhu general exam
by Melissa M Lawson 10 May '07

10 May '07

Yaping Zhu will present her research seminar/general exam on Wednesday May 16 at 10AM in Room 402. The members of her committee are Jennifer Rexford (advisor), Larry Peterson, and Vivek Pai. Everyone is invited to attend her talk, and those faculty members wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. ---------------------------------- Abstract Conventional wisdom has held that routing protocols can not achieve both scalability and high availability. Despite scaling rather well, today's Internet routing system does not react quickly to changing network conditions. Overlay networks, on the other hand, can respond quickly to changing network conditions, but their reliance on aggressive probing does not scale to large topologies. This project presents a resilient layered routing architecture called UFO (Underlay Friendly to Overlays), which achieves the best of both worlds by providing router support for overlay routing mechanisms. UFO comprises two changes to existing routers: (i) data-plane support for deflection packets at the behest of the overlay and (ii) explicit notification about significant changes in network conditions. We present these two mechanisms, and demonstrate how they facilitate the scalable deployment of overlay routing mechanisms at the network layer. Prototype is implemented based on PL-VINI platform, with preliminary evaluation results. Reading List 1. L.Peterson and B.Davie, "Computer Networks: A Systems Approach", 3rd Edition. 2. D.Clark, "Design Philosophy of the DARPA Internet Protocols", in Proc. ACM SIGCOMM, Aug 1988. 3. J.Saltzer, D.Reed and D.Clark, "End-to-End Arguments in System Design", ACM Transactions on Computer Systems, Nov 1984. 4. 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. 5. D.Andersen, H.Balakrishnan, M.Kaashoek, and R.Morris, "Resilient Overlay Networks", in Proc. ACM SOSP, Oct 2001. 6. N.Feamster, D.Andersen, H.Balakrishnan, and F.Kaashoek, "Measuring the Effects of Internet Path Faults on Reactive Routing", in Proc. ACM SIGMETRECS, Jun 2003. 7. A.Nakao, L.Peterson, and A.Bavier, "A Routing Underlay for Overlay Networks", in Proc. ACM SIGCOMM, Aug 2003. 8. J.Jannotti, "Network Layer Support for Overlay Networks", in Proc. IEEE OPENARCH, 2002 9. T.Griffin, F.Shepherd, and G.Wilfong, "The Stable Paths Problem and Interdomain Routing", IEEE Transactions on Networking. Volume10, Issue2 p232-243. 10. R.Morris, E.Kohler, J.Jannotti, and M.Kaashoek, "The Click Modular Router", in Proc. ACM SOSP, Dec 1999.

1 0

Yi Wang general exam
by Melissa M Lawson 10 May '07

10 May '07

Yi Wang will present his research seminar/general exam on Wednesday May 16 at 2PM in Room 402. The members of his committee are Jennifer Rexford (advisor), Larry Peterson, and Kai Li. 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. ---------------------------------- Morpheus: Making Routing Programmable Abstract: The Border Gateway Protocol (BGP) is used by Internet Service Providers (ISPs) to exchange reachability information with neighboring domains. Internet Service Providers (ISPs) express complex policies, affecting everything from business relationships with their neighbors to traffic engineering, scalability, and security, by configuring the BGP. However, the routing architecture within an ISP, coupled with the multi-step BGP route-selection algorithm running on the routers, imposes significant restrictions on the policies that can be realized in practice. These restrictions stand in the way of ISPs achieving policy objectives that are important in practice, such as enabling new services to customers. We argue that the limitations of BGP can be overcome by providing greater visibility into the candidate routes, a more flexible decision process, and support for for multipath routing and forwarding. We present Morpheus, a modular, open routing platform that enables network operators to realize many useful policies that are infeasible today through: (1) flexible composition of multiple (possibly third-party developed) policy modules, and (2) programming the route-selection algorithms. Morpheus also supports multipath routing, which is essential in enabling many new customizable routing services. Morpheus can be readily deployed without requiring changes in other domains. We've implemented an Morpheus prototype as an extension to XORP, the extensible open routing platform. Our evaluation of the prototype demonstrates that the system can scale to the large number of address blocks and BGP sessions present in large backbone networks. We are currently working on demonstrating the flexibility of the prototype in supporting new routing policies. Reading list: Textbook: L. Peterson and B. Davie, Computer Networks: A Systems Approach, Morgan Haulmann, 3e, 2003 Papers: [1] D. Clark, " <http://www.cs.utah.edu/classes/cs7941-001/papers/e2e88.pdf> The Design Philosophy of the DARPA Internet Protocols," ACM SIGCOMM, August 1988 [2] N. Feamster, H. Balakrishnan, J. Rexford, A. Shaikh, and J. van der Merwe, " <http://www.cs.princeton.edu/%7Ejrex/papers/rcp.pdf> The Case for Separating Routing from Routers," ACM SIGCOMM workshop on Future Directions in Network Architecture, August 2004 [3] A. Greenberg, G. Hjalmtysson, D. Maltz, A. Meyers, J. Rexford, G. Xie, H. Yan, J. Zhan, and H. Zhang, " <http://www.cs.princeton.edu/%7Ejrex/papers/ccr05-4d.pdf> A Clean Slate 4D Approach to NetworkControl and Management," ACM SIGCOMM Computer Communications Review, October 2005 [4] M. Handley, E. Kohler, A. Ghosh, O. Hodson, P. Radoslavov, " <http://www.xorp.org/papers/xorp-nsdi.pdf> Designing Extensible IP Router Software," USENIX Symposium on Networked Systems Design and Implementation, May 2005 [5] Matthew Caesar, Donald Caldwell, Nick Feamster, Jennifer Rexford, Aman Shaikh, and Jacobus van der Merwe, " <http://www.cs.princeton.edu/%7Ejrex/papers/rcp-nsdi.pdf> Design and implementation of a Routing Control Platform," USENIX Symposium on Networked Systems Design and Implementation, May 2005 [6] B. Raghavan and A. Snoeren, " <http://www.cs.ucsd.edu/%7Ebraghava/papers/platypus-sigcomm04.pdf> A System for Authenticated Policy-Compliant Routing," ACM SIGCOMM, September 2004 [7] T. V. Lakshman, T. Nandagopal, R. Ramjee, K. Sabnani, and T. Woo, " <http://www.sigcomm.org/HotNets-III/HotNets-III%20Proceedings/lakshman.pdf> The SoftRouter Architecture," ACM Workshop on Hot Topics in Networks, November 2004 [8] G. Goodell, W. Aiello, T. Griffin, J. Ioannidis, P. McDaniel, and A. Rubin, " <http://www.isoc.org/isoc/conferences/ndss/03/proceedings/papers/5.pdf> Working Around BGP: An Incremental Approach to Improving Security and Accuracy for Interdomain Routing," Symposium on Network and Distributed System Security, February, 2003 [9] T. Griffin, B. Shepherd, and G. Wilfong, " <http://www.stanford.edu/%7Erjohari/336/Griffin_SPP.pdf> The Stable Paths Problem and Interdomain Routing," IEEE Transactions on Networking, 10(2), April 2002 [10] M. Caesar and J. Rexford, " <http://www.cs.princeton.edu/%7Ejrex/papers/policies.pdf> BGP Routing Policies in ISP Networks," IEEE Network Magazine, Special Issue on Interdomain Routing, November/December 2005 [11] Hong Yan, T. S. Eugene Ng, David Maltz, Hui Zhang, Hemant Gogineni and Zheng Cai, " <http://www.cs.rice.edu/%7Eeugeneng/papers/NSDI07-4D.pdf> Tesseract: A 4D Network Control Plane", USENIX Symposium on Networked Systems Design & Implementation, April 2007 [12] Wen Xu and Jennifer Rexford, " <http://www.cs.princeton.edu/%7Ejrex/papers/multipath06.pdf> MIRO: Multi-path Interdomain ROuting," ACM SIGCOMM, September 2006

1 0

JiMin Song general exam
by Melissa M Lawson 10 May '07

10 May '07

JiMin's exam is at 10AM this morning. It was not mentioned in the talk announcement. Sorry!

1 0

C Kim general exam
by Melissa M Lawson 10 May '07

10 May '07

Chang Kim will present his research seminar/general exam on Tuesday May 15 at 10AM in Room 402. The members of his committee are Jennifer Rexford (advisor), Margaret Martonosi, 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. ---------------------------------- SEIZE: Scalable and Efficient Zero-configuration Enterprise Architecture Abstract Most conventional enterprise or campus networks consist of Ethernet-based IP subnets interconnected by routers. Although each subnet runs with minimal (or zero) configuration by virtue of Ethernet's flat-addressing and self-learning capability, interconnecting subnets at the IP-level introduces a significant amount of configuration and management overhead on both end-hosts and routers. The configuration problem becomes more serious as an enterprise network grows by merging multiple remote sites or by supporting a large number of mobile end-hosts. Deploying enterprise-wide Ethernet, however, cannot solve this problem because Ethernet bridging does not scale. As an alternative, we propose a scalable and efficient zero-configuration architecture (SEIZE) for enterprise networks. SEIZE provides "plug-and-play" capability via flat addressing and yet allows for scalability and efficiency through a combination of shortest-path routing and hash-based location resolution. Networking nodes perform location resolution on an on-demand basis and can cache the results to optimize routing paths and to avoid redundant resolution as well. We implemented a SEIZE prototype system using a collection of Click modular router elements and the XORP routing protocol daemon. For evaluation, we run the system on Emulab with real enterprise traffic traces. Our experiments show that SEIZE exhibits near-optimal path efficiency, while limiting the number of host information entries replicated over a network and reducing the control overhead as much as two orders of magnitude compared with the conventional Ethernet bridging. Papers 1. L. Kleinrock, and F. Kamoun, "Hierarchical Routing for Large Networks; Performance Evaluation and Optimization," Computer Networks vol. 1, 1977. 2. R. Perlman, " An Algorithm for Distributed Computation of a Spanning Tree in <http://www1.cs.columbia.edu/%7Eji/F02/ir02/p44-perlman.pdf> an Extended LAN," Proc. ninth Data Communications Symposium, 1985. 3. D. Peleg, and E. Upfal, " A Trade-Off between Space and Efficiency for Routing <http://portal.acm.org/ft_gateway.cfm?id=62217&type=pdf&coll=GUIDE&dl=GUIDE&… CFTOKEN=37897046> Tables," Journal of the ACM, 1989. 4. T. Rodeheffer, C. Thekkath, and D. Anderson, "SmartBridge: A scalable bridge architecture <http://www.sigcomm.org/sigcomm2000/conf/paper/sigcomm2000-6-2.pdf> ," Proc. ACM SIGCOMM, 2000. 5. Andy Myers, T. S. Eugene Ng, and H. Zhang, "Rethinking the Service Model: Scaling Ethernet to a Million <http://www.cs.cmu.edu/%7Eacm/papers/myers-hotnetsIII.pdf> Nodes," Proc. of HotNets-III, 2004. 6. R. Perlman, " <http://www.ieee-infocom.org/2004/Papers/26_1.PDF> Rbridges: Transparent routing," Proc. of IEEE Infocom, 2004. 7. S. Sharma, K. Gopalan, S. Nanda, and T. Chiueh, "Viking: <http://www.ieee-infocom.org/2004/Papers/47_3.PDF> A multi-spanning-tree Ethernet architecture for metropolitan area and cluster networks," Proc. of IEEE Infocom, 2004. 8. D. Karger, E. Lehman, T. Leighton, M. Levine, D. Lewin, and R. Panigrahy, " Consistent hashing and random trees: distributed caching <http://www.akamai.com/dl/technical_publications/ConsistenHashingandRandomTr… CachingprotocolsforrelievingHotSpotsontheworldwideweb.pdf> protocol for relieving hot spots on the World Wide Web," Proc. ACM STOC, 1997. 9. J. Eriksson, M. Faloutsos, and S. Krishnamurthy, "PeerNet: Pushing Peer-to-Peer Down the Stack <http://iptps03.cs.berkeley.edu/final-papers/peernet.pdf> ," Proc. of International Workshop on Peer-to-Peer Systems, 2003. 10. D. Clark, R. Braden, A. Falk, and V. Pingali, "FARA: Reorganizing the addressing architecture <http://www.isi.edu/newarch/DOCUMENTS/FARA.FDNA03.pdf> ," Proc. of ACM SIGCOMM Workshop on Future Directions in Network Architecture, 2003. 11. M. Caesar, T. Condie, J. Kannan, K. Lakshminarayanan, I. Stoica, and S. Shenker, "ROFL: Routing on Flat Labels <http://project-iris.net/irisbib/papers/flatlabels:sigcomm2006/paper.pdf> ," Proc. of ACM SIGCOMM, 2006. 12. M. Caesar, M. Castro, E. Nightingale, Gerg O, and A. Rowstron, "Virtual Ring Routing: Network Routing Inspired by <http://www.sigcomm.org/sigcomm2006/discussion/getpaper.php?paper_id=33> DHTs," Proc. of ACM SIGCOMM, 2006. Textbooks 1. L. Peterson, and B. Davie, Computer Networks: A Systems Approach, Morgan Kaufmann, 3e, 2003 2. R. Perlman, Interconnections: Bridges, Routers, Switches, and Internetworking Protocols, Addison-Wesley, 2e, 1999

1 0

J Song general exam
by Melissa M Lawson 10 May '07

10 May '07

JiMin Song will present her research seminar/general exam on Thursday May 10 in Room 302 (note room!). The members of her committee are: Mona Singh (advisor), Olga Troyanskaya, and Tom Funkhouser. 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 Protein interactions play a key role in almost all biological processes. Recently, high-throughput experiments have uncovered large networks of protein-protein interactions for several species, including human, fruit fly and yeast. It has been postulated that analysis of these protein interaction maps should provide hints to the cell's higher-level organization, and help uncover protein functions, complexes and pathways. A protein-protein interaction network is considered as an undirected graph such that nodes are proteins and edges are interactions between two proteins. Graph clustering methods provide one way for analyzing these networks in order to uncover functional modules and protein complexes. I introduce an evaluation framework for analyzing graph clustering methods. I consider six different evaluation measures, taking into account biological process, cellular component, and protein complex annotations, to compare four diverse graph clustering algorithms. I selected four graph clustering methods, a spectral clustering method, a Markov clustering method, a density-periphery based clustering method, and a clique-finding clustering method. I find that the clique-finding clustering method consistently out performs the others, suggesting that future research along these lines should focus on methods with similar properties. Reading list Textbook: Bioinformatics by Mount - Chapters: 3, 4, 5, 7, 10. Papers: - E Alm and AP Arkin, Biological networks, Curr. Opin. Struct. Biol 2003 - LH Hartwell et al, From molecular to modular cell biology, Nature 1999 - Spirin and Mirny, Protein complexes and functional modules in molecular networks, PNAS 2003 - Sharan et al, Network-based prediction of protein function, EMBO 2007 - Newman, Modularity and community structure in networks, PNAS 2006 - Enright et al, An efficient algorithm for large-scale detection of protein families, NAR 2002 - Altaf-Ul-Amin, Development and implementation of an algorithm for detection of protein complexes in large interaction networks, BMC Bioinformatics 2006 - Palla et al, Uncovering the overlapping community structure of complex networks in nature and society, Nature 2005 - Brohee and van Helden, Evaluation of clustering algorithms for protein-protein interaction networks, BMC Bioinformatics 2006

2 1

A Feldman general exam
by Melissa M Lawson 09 May '07

09 May '07

Ari Feldman will present his research seminar/general exam on Tuesday May 15 at 2PM in Room 402. The members of his committee are Ed Felten (advisor), Andrew Appel, and David Walker. 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. ----------------------------------- Security Analysis of the Diebold AccuVote-TS Voting Machine The Diebold AccuVote-TS is the most widely deployed electronic voting platform in the United States. It belongs to a class of voting systems known as Direct Recording Electronic (DRE) voting machines, which are essentially general-purpose computers running specialized software that displays the ballots, records each voter's choices, and tabulates the votes. Since, on DREs, the most important parts of the voting process depend entirely on software, the possibility that malicious software could be installed on them poses a grave threat to the accuracy and trustworthiness of elections. Although computer scientists have long recognized the threat of malicious code to DREs, election officials and policy-makers have, until recently, been slow to accept it. Moreover, often attention in this area has focused on the threat posed by a malicious developer employed by a voting machine manufacturer. In this talk, I describe how malicious software running on a single AccuVote-TS can steal votes with little if any risk of detection. The malicious software can modify all of the records, audit logs, and counters kept by the voting machine, so that even careful forensic examination of these records will find nothing amiss. I also show how anyone who has physical access to a voting machine, or to a memory card that will later be inserted into a machine, can install malicious code in as little as one minute. Furthermore, I explain how the AccuVote-TS is susceptible to viruses that can spread a vote-stealing payload automatically from machine to machine during normal pre- and post-election activity. Finally, I discuss the following strategies for mitigating the threat of malicious software on voting machines: hardware modifications, limiting access to voting machines and memory cards, parallel testing, whole system certification, and software independent design. I argue that, of these, only software independent design can provide an acceptable level of security. Reading List: Books Niels Ferguson, Bruce Schneier. Practical Cryptography. Indianapolis: Wiley, 2003. Matt Bishop. Computer Security. Addison-Wesley, 2003. Chapters 1-3, 10, 12-14, 20, 22-24, 29. Papers William A. Arbaugh, David J. Farber, Jonathan M. Smith. A Secure and Reliable Bootstrap Architecture. Available at: http://www.cs.umd.edu/~waa/pubs/oakland97.pdf. Arel Cordero, David Wagner, David Dill. The Role of Dice in Election Audits -- Extended Abstract. Available at: http://www.cs.berkeley.edu/~daw/papers/dice-wote06.pdf. June 2006. Douglas W. Jones. Counting Mark-Sense Ballots. 2003. Available at: http://www.cs.uiowa.edu/~jones/voting/optical/. Douglas W. Jones. Voting on Paper Ballots. Available at: http://www.cs.uiowa.edu/~jones/voting/paper.html. Chris Karlof, Naveen Sastry, David Wagner. Cryptographic Voting Protocols: A Systems Perspective. Available at: http://www.cs.berkeley.edu/~daw/papers/neffchaum-usenix05.pdf. Tadayoshi Kohno, Adam Stubblefield, Aviel D. Rubin, Dan S. Wallach. Analysis of an Electronic Voting System. February 2004. Available at: http://avirubin.com/vote.pdf. C. Andrew Neff. Practical High Certainty Intent Verification for Encrypted Votes. Available at: http://www.votehere.com/vhti/documentation/vsv-2.0.3638.pdf. October 2004. C. Andrew Neff. Verifiable Mixing (Shuffling) of ElGamal Pairs. Available at: http://www.votehere.com/vhti/documentation/egshuf-2.0.3638.pdf. April 2004. Lawrence Norden et al. The Machinery of Democracy: Voting System Security Accessibility, Usability, and Cost. Brennan Center for Justice. pp. 38-121 (Accessibility, Usability). Available at: http://www.brennancenter.org/dynamic/subpages/download_file_38150.pdf. Stefan Popoveniuc, Ben Hosp. An Introduction to Punchscan. Available at: http://www.punchscan.org/papers/ popoveniuc_hosp_punchscan_introduction.pdf. October 2006. Ronald L. Rivest. On Estimating The Size of a Statistical Audit. Available at: http://theory.lcs.mit.edu/~rivest/Rivest- OnEstimatingTheSizeOfAStatisticalAudit.pdf. November 2006. Ronald L. Rivest, John P. Wack. On the notion of "software independence" in voting systems. Available at: http://vote.nist.gov/SI-in-voting.pdf. July 2006. Naveen Sastry, Tadayoshi Kohno, David Wagner. Designing Voting Machines for Verification. Available at: http://www.cs.berkeley.edu/~daw/papers/varch-use06.pdf.

1 0

A Agarwal preFPO
by Melissa M Lawson 08 May '07

08 May '07

Amit Agarwal will present his preFPO on Monday May 14 at 3:30PM in Room 302 (note room!). The members of his committee are: Moses Charikar, advisor; Rob Schapire and Sanjeev Khanna (U Penn), readers; Ken Steiglitz and Bob Tarjan, nonreaders. Everyone is invited to attend his talk. His abstract follows below. --------------------------------- Optimization has emerged as a field of central importance for its practical applications in operations research, physics, chemistry, applied mathematics, and computer science. As our understanding of optimization has deepened, it has emerged that several important optimization problems are difficult to solve exactly in reasonable amount of time, assuming widely believed complexity assumptions. The natural approach in such cases is to obtain approximate solutions. There is a huge body of work towards designing algorithms with provable guarantees about their sub-optimality. In general, two kinds of error estimation techniques have been evolved for such problems: multiplicative and additive. In the study of approximation algorithms one typically looks for multiplicative approximation to problems which are NP-hard. On the other hand, results in the field of online optimization typically have additive errors. The latter work also has connections to machine learning and statistics. I will present three results in the broad area of approximate optimization: (i) The first result is on improved approximation for directed cut problems from joint work with Noga Alon and Moses Charikar. (ii) The second result bridges the field of approximation algorithms and network coding theory. We show that certain integrality gaps studied by the approximation algorithms community are the same as certain parameters in network coding. This is joint work with Moses Charikar. (iii) Finally we present faster algorithms for online optimization with applications to portfolio management. This is based on papers with Elad Hazan, Robert Schapire, Satyen Kale, and Adam Kalai.

1 0

Q Xi general exam
by Melissa M Lawson 08 May '07

08 May '07

Qian Xi will present her research seminar/general exam on Monday May 14 at 10:30AM in Room 402. The members of her committee are JP Singh (advisor), David August, and Vivek Pai. 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: Writing multi-threaded programs on chip multi-processors is a challenge. Because of the runtime unpredictability, access to shared data should be arranged carefully to guarantee correctness and efficiency. Lock-based mechanisms are conventional ways to provide mutual exclusion, but locks aren't easy to manage and they can cause serious problems such as deadlock. Maurice Herlihy et al. proposed a lock-free data structure called Transactional Memory (TM) to eliminate the problems induced by locks. TM systems have received a lot of interest recently due to advent of multi-core processors, and due to a widespread belief that TM provides a higher-level and less error-prone parallel programming model than locks, while still achieving comparable performance. Most TM implementations have used toy or kernel benchmarks to measure performance, and almost exclusively small data structures. This benchmarks gave little insight into how real applications will behave with TM. In this project, we present a CMP benchmark suite implemented in software TM (STM), containing both kernel and real application level programs, from scientific computing and multimedia domains. We aim not only to understand performance profiles under STM relative to the more conventional threads+locks programming model, but more importantly, to understand whether STM is a preferable interface for programming on CMP. In the current experimental study, we find that STM achieves good performance, nearly the same as lock-based mechanisms, for small sizes of shared data. On the other hand, programs with large shared data size incur a loss of performance for several reasons in STM. Then, from a programmer's aspect of view, we summarize the benefits and drawbacks of current STM systems while writing parallel programs. We also compare interfaces of different STM implementations and comment on appropriate STM primitives for parallel programming. Readling list: Book: David E. Culler, Jaswinder Pal Singh, Anoop Gupta. Parallel Computer Architecture: A Hardware/Software Approach (2nd edition) Papers: - Maurice Herlihy, J. Eliot B. Moss. Transactional Memory: Architectural Support for Lock-Free Data Structures. Proceedings of the 20th International Symposium in Computer Architecture, 1993, pp. 289300. - Nir Shavit, Dan Touitou. Software Transactional Memory. Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing , 1995, pp. 204-213. - Kunle Olukotun, Basem A. Nayfeh, Lance Hammond, Ken Wilson, and Kunyung Chang. The Case for a Single-Chip Multiprocessor. ACM SIGOPS Operating Systems Review, 1996, pp. 2-10. - Austen McDonald et al. Characterization of TCC on Chip-Multiprocessors. Proceedings of the 14th International Conference on Parallel Architecture and Compilation Techniques, 2005. - Kevin E. Moore et al. LogTM: Log-based Transactional Memory. Proceedings of the 12th Annual International Symposium on High Performance Computer Architecture, 2006. - Tim Harris, Simon Marlow, Simon Peyton Jones, Maurice Herlihy. Composable Memory Transactions. ACM Conference on Principles and Practice of Parallel Programming 2005. - Maurice Herlihy, Victor Luchangco, Mark Moir, William Scherer. Software Transactional Memory for Dynamic-Sized Data Structures. Proceedings of the 22nd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 2003. - Austen McDonald et al. Architectural Semantics for Practical Transactional Memory. Proceedings of the 33rd annual international symposium on Computer Architecture, 2006.

1 0

X Ma general exam
by Melissa M Lawson 03 May '07

03 May '07

Xiaojuan Ma will present her research seminar/general exam on Wednesday May 9 at 10 AM in Room 301 (note room!). The members of her committee are Fei-Fei Li, Szymon Rusinkiewicz, Tom Funkhouser. Her advisor is Perry Cook. Everyone is invited to attend her talk, and those faculty members wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. -------------------------------------------- Abstract: Assistive devices and tools for persons with aphasia, a debilitating condition that robs an individual of the ability to communicate, have traditionally depended on icons to convey the meaning of words that the individuals have lost. Despite the predominant use of icons, which are created by artists, speech language pathologists suggest that personal digital photographs may be easier for people to map to the real phenomena. Also, compared to other visual art resources such as icons, images are cheaper, ubiquitous, numerous, and varied. A concept of picture-as-language, which uses digital photographs as a language has shown some significant and long-lasting effects on the learning for people with mental retardation, developmental disabilities, or learning disabilities. Designing for a population that relies heavily on picture representations, it is important to understand to what extent the choice of icons and images affects the adoption and usability of assistive technology. A study with unimpaired members of an older demographic likely to be affected by aphasia shows that, for sentences with words replaced by either images or icons, the word-level and sentence-level meaning are retained equally well for both images and icons. It is also supported by a further study with our target group, people with aphasia, on the effectiveness of icons and images on conveying noun concepts. However, compared to concrete nouns, both studies showed that neither icons or images performed as well on abstract nouns. What's more, the study with senior citizens revealed that both icons and images did a poor job of embodying verbs and attributes. A third study evaluating the efficacy of four different visual representations of verbs for subjects from the general population addressed the question of the best representation of both motion and abstract verbs. Related video and image database for verb illustrations is under construction. Books: Preece, J., Rogers, Y., and Sharp, H. Interaction Design: Beyond Human-Computer Interaction. New York: John Wiley & Sons, Inc., 2002. Shneiderman, B. Designing the User Interface: Strategies for Effective Human-Computer Interaction. Boston: Addison Wesley, 1997. Chapters: 1-4, 10, 11 Papers: Newell A.F., Carmichael, A., Gregor, P., and Alm, N. Information Technology for Cognitive Support. The Human-Computer Interaction Handbook, Jacko, J. and Sears, A. (Editors). Mahwah, NJ: Lawrence Erlbaum Associates, Inc, 2002. 464-481. R. D. Steele, M. Weinrich, R. T. Wertz, M. K. Kleczewska, and G. S. Carlson. Computer-Based Visual Communication in Aphasia. Neuropsychologia, 27(4):409-426, 1989. van de Sandt-Koenderman, M. W. M. E. High-tech AAC and aphasia: widening horizons? Aphasiology (2004), 18 (3), 245-263. Baecker, R., Small, I., and Mander, R. Bringing Icons to Life. Proceedings of CHI '91 Human Factors in Computing Systems. New York: ACM, 1991, pp. 1-6. J. L. Boyd-Graber, S. S. Nikolova, K. A. Moffatt, K. C. Kin, J. Y. Lee, L.W. Mackey, M. M. Tremaine, and M. M. Klawe. Participatory design with proxies: Developing a desktop-PDA system to support people with aphasia. In Proc. CHI2006, pages 151-160. ACM Press, 2006. K. Tee, K. Moffatt, L. Findlater, E. MacGregor, J. Mc-Grenere, B. Purves, and S. S. Fels. A visual recipe book for persons with language impairments. In Proc. CHI 2005, pages 501-510. ACM Press, 2005. Danielsson, H. and Svensk. A. Digital Pictures as Cognitive Assistance. In Proceedings of the 6th European Conference for the Advancement of Assitive Technology, 2001. (5 pages) R. Mihalcea and B. Leong. Toward communicating simple sentences using pictoral representations. In Proc. of the Conf. of the Assoc. for Machine Translation in the Americas 2006, Boston, MA, 2006. T. Takasaki. Pictnet: Semantic infrastructure for pictogram communication. In P. Sojka, K.-S. Choi, C. Fellbaum, and P. Vossen, editors, Proc. Global WordNet Conference 2006, pages 276-289. GlobalWordNet Association, January 2006. Pettersson, Rune. Interpretation of Image Content. Educational Communication and Technology Journal, v36 n1 p45-55 Spr 1988.

1 0