- talks - lists.cs.princeton.edu

Sivakanth Gopi will present his Generals Monday, April 27, 2015 at 1pm in rm 401
by Nicki Gotsis 20 Apr '15

20 Apr '15

Sivakanth Gopi will present his Generals Monday, April 27, 2015 at 1pm in rm 401. His committee is as follows: Zeev Dvir (advisor), Sanjeev Arora, and Bob Tarjan. 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. ============================================ 2-Server PIR with sub-polynomial communication ------ A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the i'th bit of an n-bit database replicated among two servers (which do not communicate) while not revealing any information about i to either server. The privacy of the user is information theoretic and does not rely on any cryptographic assumptions. In this work we construct a new 2-server PIR scheme with total communication cost sub polynomial in n. This improves over the currently known 2-server protocols which require n^{1/3} communication and matches the communication cost of known 3-server PIR schemes. Our improvement comes from reducing the number of servers in existing protocols, based on Matching Vector Codes, from 3 or 4 servers to 2. This is achieved by viewing these protocols in an algebraic way (using polynomial interpolation) and extending them using partial derivatives. Reading list: References [1] Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009. [2] Boaz Barak, Zeev Dvir, Amir Yehudayoff, and Avi Wigderson. Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 519–528. ACM, 2011. [3] Richard Beigel and Jun Tarui. On ACC [circuit complexity]. In Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on, pages 783–792. IEEE, 1991. [4] Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan. Private information retrieval. In FOCS, pages 41–50, 1995. [5] Zeev Dvir. Incidence theorems and their applications. Foundations and Trends R in Theoretical Computer Science, 6(4):257–393, 2010. [6] Zeev Dvir, Parikshit Gopalan, and Sergey Yekhanin. Matching vector codes. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 705–714. IEEE, 2010. [7] Klim Efremenko. 3-query locally decodable codes of subexponential length. In STOC, pages 39–44, 2009. [8] Jonathan Katz and Luca Trevisan. On the efficiency of local decoding procedures for error-correcting codes. In 32nd ACM Symposium on Theory of Computing (STOC), pages 80–86, 2000. [9] David A Mix Barrington, Richard Beigel, and Steven Rudich. Representing boolean functions as polynomials modulo composite numbers. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pages 455–461. ACM, 1992. [10] Alexander A Razborov and Sergey Yekhanin. An Ω(n 1/3 ) lower bound for bilinear group based private information retrieval. In Foundations of Computer Science, 2006. FOCS’06. 47th Annual IEEE Symposium on, pages 739–748. IEEE, 2006. 1 [11] Gabor Tardos and DA Mix Barrington. A lower bound on the MOD 6 degree of the OR function. Computational Complexity, 7(2):99–108, 1998. [12] Sergey Yekhanin. Towards 3-query locally decodable codes of subexponential length. J. ACM, 55(1), 2008.

1 0

Jordan Ash will present his masters thesis talk Wednesday, April 22, 2015 at 3:30 in rm 401
by Nicki Gotsis 20 Apr '15

20 Apr '15

Jordan Ash will present his masters thesis talk Wednesday, April 22, 2015 at 3:30 in rm 401 His readers are Rob Schapire (adviser) and Barbara Engelhardt. Everyone is invited to attend his talk. His abstract follows below. Title: A Novel Domain Adaptation Solution to the Transductive Transfer Learning Problem Abstract: Most classification algorithms rely on the assumption that training and testing data come from the same distribution. When this assumption is violated, classification performance can be seriously affected. Transfer learning, a new and increasingly popular branch of machine learning, seeks to solve this problem. In this thesis, we introduce a novel transductive transfer learning technique that functions by aligning the training and testing datasets before classification. Our method is motivated by a particular problem involving Magnetoencephalography ( MEG) data classification, but can be used for other transfer learning problems as well.

1 0

Quan Zhu will present his Pre-FPO Friday, April 24, 2015 in rm 401 at 10am
by Nicki Gotsis 17 Apr '15

17 Apr '15

Quan Zhu will present his Pre-FPO Friday, April 24, 2015 in rm 401 at 10am. The members of his committee are: Olga Troyanskaya (adviser), Mona Singh, Kai Li, Moses Charikar, and Vessela Kristensen (University of Oslo, Norway) Title: Exploring gene similarities in large-scale compendia Public gene expression datasets have been rapidly accumulating, yet there is currently a lack of effective tools in reusing existing datasets and exploring them for targeted analyses. One of the most central analyses is discovering similar genes in a data-driven way through clustering, biclustering, and query-search approaches. This thesis explores these issues and is divided into three parts. In the first part, we describe a fast, content-based, query-based search solution for discovering gene similarities in large data collections. The second part of this thesis then explores different applications of the search tool, including the role of coexpression in leading to regulatory factor discovery and biological network inference when it is being integrated with secondary data. Lastly, we extend work from a recently developed biclustering approach that discovers low-rank submatrix from a large matrix, and we explore its usage and describe a modification that can enumerate all coregulated genes and conditions. We first present the developed system SEEK, a web-based tool and a novel algorithm for exploring and visualizing gene expression patterns from thousands of datasets. Through flexible multi-gene queries, the system uses gene “hubbiness” correction procedure for balancing well-coexpressed genes in the results. It uses an automatic, data-driven dataset weighting algorithm for filtering irrelevant datasets, up-rank datasets which may be relevant to the user’s query, on the basis of coexpression of query genes. This algorithm thus eliminates the need to manually find relevant datasets (which is impossible), and at the same time achieves query-sensitivity. Notably, through robust search of thousands of human datasets, the retrieval of functionally co-annotated genes always improves with the inclusion of more datasets, showing the promise of the large compendia. We extend the function of SEEK to 5 other model organisms, in a new system called modSEEK, with the goal of enabling accurate searches in a wider experimental variety. In terms of the applications, we show that SEEK and modSEEK, when integrated with secondary Chip-seq compendia, are accurate in uncovering upstream transcription factor (TF) and their relationships. These are summarized in a TF regulatory network which carries value in hypothesis generations and directing follow-up studies. Regulatory associations between TF’s are accurate according to in vitro motif evidence. Biclustering is a problem that involves computationally intensive calculations. Prior work operates on binary version of the matrix, which may incur a small loss of resolution. Finding multiple biclusters usually involves masking the data with random values which prevents finding overlapping biclusters. At the same time, this solution is computationally inefficient since masking the data and repeating the procedure does not reduce problem size. I thus develop a recursive, divide-and-conquer approach that extends the recently developed algorithm on finding low-rank submatrix (see Aaditya V. Rangan et al). The proposed algorithm applies his algorithm on large-scale and finds multiple low-rank biclusters. The approach finds high-resolution small biclusters and combines them through post-processing. This algorithm is fast and capable of enumerating all biclusters in the dataset.

1 1

Marcela Melara will present her General Exam Tuesday, April 21, 2015 at 10am in Rm 301
by Nicki Gotsis 14 Apr '15

14 Apr '15

Marcela Melara will present her General Exam Tuesday, April 21, 2015 at 10am in Rm 301 The members of her committee are: Ed Felten (advisor), Mike Freedman, Arvind Narayanan. 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: We present CONIKS, an end-user key verification service capable of integration in end-to-end encrypted communication systems. CONIKS builds on related designs for transparency of web server certificates but solves several new challenges specific to key verification for end users. In comparison to prior designs, CONIKS enables more efficient monitoring and auditing of keys, allowing small organizations to effectively audit even very large key servers. CONIKS users can efficiently monitor their own key bindings for consistency, downloading less than 20 kB per day to do so even for a provider with billions of users. CONIKS users and providers can collectively audit providers for non-equivocation, and this requires downloading a constant 2.5 kB per day regardless of server size. Unlike any previous proposal, CONIKS also preserves the level of privacy offered by today’s major communication services, hiding the list of usernames present and even allowing providers to conceal the total number of users in the system. Reading List: J. Li, M. Krohn, D. Mazieres and D. Shasha, “Secure Untrusted Data Repository (SUNDR).” OSDI, 2004. R. C. Merkle, “A digital signature based on a conventional encryption function.” CRYPTO, 1987. S.Micali, M. Rabin and S. Vadhan, “Verifiable Random Functions.” FOCS, 1999. D. Wendlandt, D. G. Andersen, A. Perrig, “Perspectives: Improving SSH-style Host Authentication with Multi-Path Probing.” USENIX Security Symposium, 2008. B. Laurie, “Certificate Transparency.” ACM Queue, 2014. M. D. Ryan, “Enhanced Certificate Transparency and End-to-End Encrypted Mail.” NDSS, 2014. A. Ulrich, R. Holz, P .Hauck and G. Carle, “Investigating the OpenPGP web of trust.” ESORICS, 2011. C. Ellison, “Establishing identity without certification authorities.” Usenix Security, 1996. D. Mazieres, M. Kaminsky, M. F. Kaashoek and E. Witchel, “Separating key management from file system security.” SOSP, 1999. N. Borisov, I. Goldberg and E. Brewer, “Off-the-Record Communication, or, why not to use PGP.” WPES, 2004. A. Whitten and J. D. Tygar, “Why Johnny Can’t Encrypt: A Usability Evaluation of PGP 5.0.” Usenix Security, 1999. T. Perrin, “Axolotl Ratchet.” https://github.com/trevp/axolotl/wiki R. Andersen, “Security Engineering,” 2nd Ed., 2008. Chapters 3, 5, 6, 21. J. Katz and Y. Lindell, “Introduction to Modern Cryptography”, 1st Ed., 2007.

1 0

Fwd: EE Department Seminar-Prof. Muriel Medard - April 20, 2015 4:30pm
by Jennifer Rexford 13 Apr '15

13 Apr '15

> From: "Cynthia L. Menkes" <cmenkes(a)Princeton.EDU> > Date: April 13, 2015 at 4:26:51 PM EDT > To: ee-seminar(a)Princeton.EDU > Subject: EE Department Seminar-Prof. Muriel Medard - April 20, 2015 4:30pm > Reply-To: "Cynthia L. Menkes" <cmenkes(a)Princeton.EDU> > > > > >

1 0

Colloquium Speaker Kyle Jamieson today, 12:30pm
by Nicole E. Wagenblast 13 Apr '15

13 Apr '15

Colloquium Speaker Kyle Jamieson, University College, London Monday, April 13, 12:30pm Computer Science 105 Leveraging Array Signal Processing in the Wireless Internet of Things Phased array signal processing has long been employed outdoors in radar, underwater in sonar, and underground in seismic monitoring. Today, it has the potential to revolutionize the Internet of Things (IoT) by giving us the ability to track every one of the billions of IoT devices indoors, and meet their exploding bandwidth requirements. But to make the shift to indoor wireless networks, it must cope with strong multipath radio reflections, packetized data transmissions, and commodity hardware platforms. In this talk I will describe two relevant systems through the lens of system-building and experimentation. First, I will describe an indoor location system that uses solely the existing Wi-Fi infrastructure to achieve a median location accuracy of 23 centimeters, and sub-second response time, allowing Wi-Fi-enabled devices to be tracked in real-time. Next, I will present a MIMO-based Sphere Decoder system that leverages novel search algorithms and geometric reasoning to increase wireless throughput, the first of its kind that scales to 256-QAM constellation densities with computational demands that are practically realizable in current ASIC hardware. Finally, I will conclude with a vision of how these techniques will support exciting IoT applications such as video analytics over billions of indoor wireless cameras. Kyle Jamieson is a Senior Lecturer (U.S. equivalent: Assistant Professor) in the Department of Computer Science at University College London (UCL). His research interests are in building wirelessly networked systems for the real world that cut across the boundaries of digital communications and networking. Prior to joining UCL, he received the B.S., M.Eng., and Ph.D. (2008) degrees in Computer Science from the Massachusetts Institute of Technology. He then received a Starting Investigator fellowship from the European Research Council in 2011, Best Paper awards at USENIX 2013 and CoNEXT 2014, and a Google Faculty Research Award in 2015. He regularly serves on the program committees of the ACM MobiCom, USENIX NSDI, and ACM SIGCOMM conferences.

1 0

James Gordon Stewart will present his FPO Thursday, 4/16/2015 at 9AM in 401
by Nicki Gotsis 09 Apr '15

09 Apr '15

James Gordon Stewart will present his FPO Thursday, 4/16/2015 at 9AM, 401 Computer Science Building. The members of his committee are: Andrew Appel (advisor), readers: David Walker, and Zhong Shao (Yale) and nonreaders: David August and Sharad Malik (ELE). A copy of his thesis "Verified Separate Compilation for C" is available in rm 310. Everyone is invited to attend his talk.

1 0

Yossi Gilad talk, Tuesday April 7, 11am
by Nicole E. Wagenblast 07 Apr '15

07 Apr '15

Yossi Gilad, IBM Tuesday, April 6, 11am Friend Center, 108 CDN-on-Demand: Fighting DoS with Untrusted Clouds We present the design and implementation of CDN-on-Demand, a system that provides low-cost protection for websites against DDoS attacks, without impacting on website operation and expenses under normal operating conditions. CDN-on-Demand is a software package rather than a service, it migrates websites to a scalable infrastructure in case of high-load and serves clients from proxies that it automatically deploys on multiple low cost cloud services. In contrast to current CDN services, CDN-on-Demand protects against rogue service providers and compromised proxies by introducing an object security mechanism; this eliminates the need to trust the host with private keys or certificates. Furthermore, CDN-on-Demand protects the website against economic and degradation of service attacks that exploit the automatic scaling mechanism; we show that popular services are vulnerable to such attacks. We provide an open-source implementation of CDN-on-Demand, which we use to evaluate each component as well as the integrated CDN-on-Demand system. Joint work with Amir Herzberg and Michael Sudkovich

1 1

Keller Center Leadership Keynotes: Mobile Data and Pricing- Paul Jacobs and Dennis Strigl 4/9/15 (RSVP required by 4/7 to attend)
by Scott Karlin 07 Apr '15

07 Apr '15

Please note: RSVP to bjarvie(a)princeton.edu by Tuesday 4/ 7 is required to attend this event. Keller Center Leadership Keynots: Mobile Data and Pricing Thursday, April 9, 2015, 9:15am-11:45am Friend Center Convocation Room Mobile Innovation: Delivering Increased Capacity and Efficiency Paul Jacobs Executive Chairman and former CEO of Qualcomm Data Pricing Evolution: A Carrier's Perspective Dennis Strigl Former CEO of Verizon Wireless and COO of Verizon RSVP Required to Attend send email by April 7 to bjarvie(a)princeton.edu

1 0

April 13 - Software-Defined Networking at the National Security Agency (Bryan Larish, NSA)
by Nick Feamster 06 Apr '15

06 Apr '15

Software-Defined Networking at the National Security Agency Byan Larish, National Security Agency. CS/CITP SPECIAL EVENT Date: Monday, April 13, 2015 Location: 105 Computer Science Time: 4:30 pm This event is co-sponsored by CITP and the Department of Computer Science. The IT department at the NSA is similar to many other large organizations; budgets and manpower are declining, while at the same time demands for higher reliability and additional services are increasing. Because of these factors, these IT departments must change how they do business when building their IT infrastructure. Open networking and software defined networking (SDN) are two promising technology trends that the NSA is applying to resolve these challenges in different areas of its network architecture. This talk will detail that element’s open networking and SDN initiatives in three areas: an OpenStack data center; a data center that hosts a storage cloud; and the campus area networks at branch offices. The talk will describe the motivation for each initiative, the architectures and solutions considered, and early-on lessons learned from development and deployment. Bio: Bryan Larish is the Technical Director for Enterprise Connectivity & Specialized IT Services at the National Security Agency (NSA), and he is responsible for setting the technical direction of the development and operation of NSA’s global network infrastructure. Prior to joining NSA, Bryan worked in the Chief Engineer’s office at the U.S. Navy’s Space and Naval Warfare Systems Command (SPAWAR). In that role, he was responsible for implementing engineering techniques used to manage, architect, and plan the U.S. Navy’s communications/IT systems portfolio. Bryan’s other experience includes Technical Director for Navy engineering policy and various engineering roles at SPAWAR. Bryan holds a Ph.D. and M.S. in electrical and computer engineering from the Georgia Institute of Technology and a B.S.E. in electrical engineering from Arizona State University.

1 0