- talks - lists.cs.princeton.edu

M Hardt general exam
by Melissa Lawson 05 May '09

05 May '09

Moritz Hardt will present his research seminar/general exam on Monday May 11 at 2PM in Room 302 (note room). The members of his committee are: Boaz Barak, advisor, Sanjeev Arora, 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. -------------------------------------------------- I. Title + abstract What are plausible hard instances for Unique Games? Unique Games are a family of constraint satisfaction problems conjectured to be NP-hard. This conjecture due to Khot implies that simple semidefinite programs (SDP) achieve optimal approximation ratios for several important problems including Max-Cut and Vertex Cover. Unfortunately, little evidence in support of the conjecture exists. Indeed, random instances of Unique Games are known to be easy. In this work we thus address the question: What are plausible hard instances for Unique Games? Our approach is to consider the refutation problem induced by subsampling a given SDP gap instance to constant degree. While subsampling preserves global parameters such as the integrality gap, the lack of local structure may lead to computational hardness. In support of our methodology, we observe that a constant degree subsample of essentially any unsatisfiable k-CSP instance gives rise to strong lower bounds in the Lasserre SDP hierarchy so long as k is greater than 3. Based on the work of Charikar, Makarychev and Makarychev, we also show that for 2-CSPs and Unique Games a constant degree subsample of any unsatisfiable instance gives strong lower bounds in the Sherali-Adams linear programming hierarchy. Unfortunately, our approach can only go so far. Appealing to Grothendieck's inequality, we show that for any 2-CSP the induced refutation problem is solvable in polynomial time. We then consider the question whether known SDP gaps withstand additional constraints when subsampled to constant degree. Somewhat surprisingly, we can show that already the triangle inequalities annihilate the integrality gap of the well known Feige-Schechtman gap instance for Max-Cut. This remains true even in a constant degree subsample. As for a future research direction, similar ideas could apply to all known Unique Games gap instances. My talk is based on ongoing research with Boaz Barak, Thomas Holenstein and David Steurer. II. Reading list Books: * Arora, Barak. Computational Complexity. Chapters 11,13,14,18--23 Papers: [Ale03] Alekhnovich. More on average case vs approximation complexity [ABW09] Applebaum, Barak, Wigderson. Public Key Cryptography from Different Assumptions [AKK+08] Arora, Khot, Kolla, Steurer, Tulsiani and Vishnoi. Unique Games on Expanding Constraint Graphs are Easy [CMM09] Charikar, Makarychev, Makarychev. Integrality Gaps for Sherali- Adams Relaxations [Fei02] Feige. Relations between Average Case Complexity and Approximation Complexity [FS02] Feige and Schechtman. On the optimality of the random hyperplane rounding technique for MAX CUT [Hol07] Holenstein. Parallel Repetition: Simplifications and the no-signaling case [KKMO04] Khot, Kindler, Mossel, O'Donnell. Optimal inapproximability results for max-cut and other 2-variable CSPs? [KV05] Khot, Vishnoi. The unique games conjecture, integrality gap for cut problems, and embeddability of negative type metrics into l1. [Rag08] Raghavendra. Optimal Algorithms and Inapproximability Results for Every CSP? [Sch08] Schoenebeck. Linear Level Lasserre Lower Bounds for Certain k-CSPs [TTV09] Trevisan, Tulsiani, Vadhan. Regularity, Boosting, and Efficiently

1 0

T Yue general exam
by Melissa Lawson 05 May '09

05 May '09

Tao Yue will present his research seminar/general exam on Monday May 11 at 10AM in room 402. The members of his committee are: Mona Singh, advisor, Olga Troyanskaya, and Tom Funkhouser. 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 --------- Sequence similarity has long been used to find orthologs between proteins in different species, or to find paralogs within a species. Predictions of these evolutionary relationships can be exploited to infer and transfer functional annotations between proteins. In the past decade, high-throughput screening techniques have enabled the construction of protein interaction networks for many model organisms. In addition to direct protein interactions, other associations can also be made between pairs of proteins: coexpression, phylogenetic, neighborhood, gene fusion, etc. Such networks provide the opportunity to characterize a protein not just by its sequence, but by its interaction and association partners. This talk explains how to exploit these networks to detect functionally similar proteins between different species. Such networks, particularly the protein interaction networks, provide more direct evidence of function than does sequence similarity. We evaluate the power of various metrics for uncovering functionally similar proteins without using sequence similarity. In addition, we apply Rankprop, a diffusion-based process that has previously been used on sequence similarity, to these networks. We show that the use of networks from multiple organisms yields improvements in precision and recall. Furthermore, this procedure can be used to disambiguate predictions made by sequence-based methods, as well as correct errors. These techniques show promising applications as more interaction data becomes available. They also have potential future applications to the detection of analogous proteins, i.e., those that evolved the same function independently and thus lack sequence similarity. TEXTBOOK --------- Mount, Bioinformatics: Sequence and Genome Analysis. Cold Spring Harbor Laboratory Press, 2004. Chapters 1-7, 11. PAPERS: General area: Protein networks --------------------------------------- Barabasi and Oltvai, Network Biology: Understanding the Cell's Functional Organization. Nature Reviews Genetics, February 2004, 101-113. Nabieva and Singh, Protein function prediction via analysis of interactomes. Prediction of Protein Structures, Functions, and Interactions (ed J. Bujnicki), 2009. Zhu et al, Getting connected: analysis and principles of biological networks. Genes & Developmnent 21 (2007): 1010-1024. PAPERS: Subareas ----------------------------------------------------------------------- Bandyopadhyay et al. Systematic identification of functional orthologs based on protein network comparison. Genome Research 16 (2006), pp. 428-435. Li et al. OrthoMCL: Identification of Ortholog Groups for Eukaryotic Genomes. Genome Research 13 (2003), pp. 2178-2189. Remm et al. Automatic Clustering of Orthologs and In-paralogs from Pairwise Species Comparisons. J. Molecular Biology (2001) 314, pp. 1041-1052. Sharan et al. Conserved patterns of protein interaction in multiple species. PNAS, February 8, 2005, 1974-1979. Sharan and Ideker. Modeling cellular machinery through biological network comparison. Nature Biotechnology 24 (2006), 427-433. Singh et al. Global alignment of multiple protein interaction networks with application to functional orthology detection. PNAS, September 2, 2008, pp. 12763-12768. Yosef et al. Improved Network-based Identification of Protein Orthologs. Bioinformatics Vol. 24 ECCB 2008, pp. i200-i206.

1 0

A Halderman FPO
by Melissa Lawson 04 May '09

04 May '09

Alex Halderman will present his FPO on Friday May 8 at 8AM in Room 402. The members of his committee are: Ed Felten, advisor; Andrew Appel and Avi Rubin (Johns Hopkins), readers; Brian Kernighan and Adam Finkelstein, nonreaders. A copy of his thesis, "Investigating Security Failures and their Causes: An Analytic Approach to Computer Security", is on display in Room 310. Everyone is invited to attend his talk.

1 0

J Terrace general exam
by Melissa Lawson 01 May '09

01 May '09

Jeff Terrace will present his research seminar/general exam on Friday May 8 at 2PM in Room 302 (note room). The members of his committee are: Mike Freedman, advisor, Jennifer Rexford, and Vivek Pai. 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: Massive storage systems typically replicate and partition data over many potentially-faulty components to provide both reliability and scalability. Yet many commercially- deployed systems, especially those designed for inter- active use by customers, sacrifice stronger consistency properties in the desire for greater availability and higher throughput. I will present the design, implementation, and evaluation of CRAQ, a distributed object-storage system that challenges this inflexible tradeoff. The basic approach, an improvement on Chain Replication, maintains strong consistency while greatly improving read throughput. By distributing load across all object replicas, CRAQ scales linearly with chain size without increasing consistency coordination. At the same time, it exposes non- committed operations for weaker consistency guarantees when this suffices for some applications, which is especially useful under periods of high system churn. I will explore additional design and implementation considerations for geo-replicated CRAQ storage across multiple datacenters to provide locality-optimized operations. I will also discuss multi-object atomic updates and multicast optimizations for large-object updates. Reading List: [1] G. DeCandia, D. Hastorun, M. Jampani, G. Kakula-pati, A. Lak-shman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: Amazon’s highly available key-value store. [2] R. Guerraoui, D. Kostic, R. R. Levy, and V. Quma. A high throughput atomic storage algorithm. [3] R. van Renesse and F. B. Schneider. Chain replication for supporting high throughput and availability. [4] I. Stoica, R. Morris, D. Liben-Nowell, D. Karger, M. F. Kaashoek, F. Dabek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup protocol for Internet applications. [5] M. Burrows. The Chubby lock service for loosely-coupled distributed systems. [6] S. Ghemawat, H. Gobioff, and S.-T. Leung. The google ?le system. [7] M. Castro and B. Liskov. Practical byzantine fault tolerance. [8] B. F. Cooper, R. Ramakrishnan, U. Srivastava, A. Silberstein, P. Bohannon, H.-A. Jacobsen, N. Puz, D. Weaver, and R. Yerneni. PNUTS:Yahoo!'s Hosted Data Serving Platform. [9] M. K. Aguilera, A. Merchant, M. Shah, A. Veitch, and C. Karamanolis. Sinfonia: a new paradigm for building scalable distributed systems. In Proc. SOSP, Oct. 2007. [10] K. P. Berman. Reliable Distributed Systems, Chapters 13-19.

1 0

W Lloyd general exam
by Melissa Lawson 01 May '09

01 May '09

Wyatt Lloyd will present his research seminar/general exam on Friday May 8 at 10AM in Room 302 (note room). The members of his committee are: Mike Freedman, 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: Byzantine fault-tolerant (BFT) replication, while offering robustness in the face of arbitrary failures, arguably has not been widely adopted due to its performance overhead. System designers often opt for protocols that sacrifice consistency or avoid replicating work, at the cost of correctness in the face of failures. By using historical information, however, I will argue that stronger consistency and high performance are not mutually exclusive. This talk will present Prophecy, a system that interposes itself between clients and any replicated service to minimize request replication when results are historically consistent. At the core of Prophecy is a trusted sketcher component, designed to replace the semi-trusted load balancer that mediates access to a service. The sketcher maintains a compact history table of request/response pairs that allows it to perform fast, load-balanced reads when state transitions do not occur, and slow, replicated reads otherwise. Despite its simplicity, the sketcher provides a new form of consistency called delay-once consistency: informally, faulty nodes can return only stale (not arbitrary) data and only for an exponentially-small number of times. A prototype implementation demonstrates Prophecy's high throughput compared to BFT systems, and its competitiveness with traditional load-balancing. I will also describe and evaluate Prophecy's ability to scale-out to support large replica groups. As Prophecy is most effective when state transitions are rare, I will finally present a measurement study of popular websites that demonstrates a high extent of static data. Reading List: __Papers__ [1] L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem. ACM Trans. Program. Lang. Sys., 4(3), 1982. [2] Castro, M. and Liskov, B. Practical byzantine fault tolerance. In OSDI, 1999. [3] R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E. Wong. Zyzzyva: Speculative Byzantine fault tolerance. In SOSP, 2007. [4] A. Clement, E. Wong, L. Alvisi, and M. Dahlin. Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults. In NSDI, 2009. [5] M. P. Herlihy, and J. M. Wing. Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Sys. 12(3), 1990. [6] B. F. Cooper, R. Ramakrishnan, U. Srivastava, A. Silberstein, P. Bohannon, H.-A. Jacobsen, N. Puz, D. Weaver, and R. Yerneni. PNUTS: Yahoo!'s hosted data serving platform. In VLDB, 2008. [7] G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: Amazon's highly available key-value store. In SOSP, 2007. [8] Fitzpatrick, B. 2004. Distributed caching with memcached. Linux Journal, 124, 2004. [9] J. Karlin, S. Forrest, and J. Rexford. Pretty Good BGP: Improving BGP by cautiously adopting routes. In ICNP, Nov. 2006. [10] L. Poole, and V.S. Pai. ConfiDNS: leveraging scale and history to detect compromise. In USENIX Annual, June 2008. __Textbook__ K. P. Birman, Reliable Distributed Systems, Springer, 2008. Part III and Chapter 24.6.

1 0

Y Wang FPO
by Melissa Lawson 29 Apr '09

29 Apr '09

Yi Wang will present his FPO on Wednesday May 6 at 3PM in Room 402. The members of his committee are: Jen Rexford, advisor; Mike Freedman and Jacobus Van der Merwe (AT&T), readers; Larry Peterson and Ed Felten, nonreaders. A copy of his thesis, "A Principled Approach to Managing Routing in Large ISP Networks", is on display in Room 310. Everyone is invited to attend his talk.

1 0

E Raman FPO
by Melissa Lawson 29 Apr '09

29 Apr '09

Easwaran Raman will present his FPO on Wednesday May 6 at 9:30AM in Room 402. The members of his committee are: David August, advisor; Doug Clark and Teresa Johnson (HP Labs), readers; David Walker and Vivek Pai, nonreaders. A copy of his thesis "Parallelization Techniques with Improved Dependence Handling", is on display in Room 310. Everyone is invited to attend his talk.

1 0

3pm talk today on Sustainable Networks and Systems for the Developing World in room 402
by Jennifer Rexford 28 Apr '09

28 Apr '09

Speaker: Lakshmi Subramanian, NYU Title: Sustainable Networks and Systems for the Developing World Date/time: 3-4pm Tuesday April 28 Location: room 402 in the Computer Science building Abstract: The Internet and the World Wide Web have largely remained urban phenomena and a significant fraction of the developing world, especially in rural and underdeveloped regions, remains disconnected from the rest of the world. In this talk, I will briefly elaborate on our current efforts in addressing three broad challenges that can help in bridging the digital divide: (a) developing low-cost high-bandwidth connectivity solutions; (b) extending the Web to developing regions; (c) building new mobile applications for enhancing healthcare and financial services. This talk will specifically focus on the challenge of low-cost connectivity solutions for developing regions. I will describe our experiences in developing and deploying WiFi-based Long Distance (WiLD) Networks, a low-cost connectivity solution which provides the ability to achieve nearly 6-10 Mbps over 100s of kilometers for roughly $1000/link. WiLD networks have been deployed in 10 developing countries and have been used to provide telemedicine services in Aravind Eye hospitals in India to 50,000 patients/year in rural areas which is currently being expanded to cover 500,000 patients/year. We are currently extending WiLD networks to develop WiFi based Rural Extensions (WiRE), a low-cost alternative to cellular networks for rural settings. Bio Prof. Lakshminarayanan Subramanian is an Assistant Professor in the Courant Institute of Mathematical Sciences at NYU. His research interests are in the space of networks, distributed systems, security and technologies for developing regions. He received his MS and PhD from UC Berkeley and B.Tech from IIT-Madras.

1 0

F Cole FPO
by Melissa Lawson 24 Apr '09

24 Apr '09

Forrester Cole will present his FPO on Friday May 1, 2009 in Room 401 (note room). The members of his committee are: Adam Finkelstein, advisor; Tom Funkhouser and Doug DeCarlo (Rutgers), readers; Szymon Rusinkiewicz and David Blei, nonreaders. A copy of his thesis, "Line Drawings of 3D Models", is on display in Room 310. Everyone is invited to attend his talk.

1 0

T Capra FPO
by Melissa Lawson 24 Apr '09

24 Apr '09

Tony Capra will present his FPO on Friday May 1, 2009 at 10AM in Room 302 (note room). The members of his committee are: Mona Singh, advisor; Olga Troyanskaya and Tom Funkhouser, readers; Frederick Hughson (MOL) and Christodoulos Floudas (ChemEng), nonreaders. A copy of his thesis, "Algorithms for the Identification of Functional Sites in Proteins", is on display in Room 310. Everyone is invited to attend his talk.

1 0