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

Ankit Garg will present his Pre-FPO on Thursday, February 4, 2016 at 1:30 pm in CS 402.
by Nicki Gotsis 28 Jan '16

28 Jan '16

Ankit Garg will present his Pre-FPO on Thursday, February 4 at 1:30 pm in CS 402. The members of his committee are Mark Braverman (adviser), Sanjeev Arora, Zeev Dvir, Ran Raz (IAS) and Avi Wigderson (IAS). Everyone is invited to attend his talk. The talk title and abstract follow below: Title: Information theoretic relaxations in complexity theory Abstract: Since Shannon’s “A Mathematical Theory of Communication”, information theory has found applicability in a wide range of scientific disciplines. Over the past two decades, information theory has reemerged in theoretical computer science as a mathematical tool with applications to streaming algorithms, data structures, communication complexity etc. In the first part of talk, I will talk about a new information theoretic framework for proving parallel repetition of 2-prover 1-round games. Using this framework, we can resolve the open question about parallel repetition of small value games. This is based on joint work with Mark Braverman. In the second part of the talk, I will talk about near optimal round-communication tradeoffs for quantum communication complexity of disjointness. The techniques involved in the proof include quantum information complexity and the self reducibility of disjointness. This is based on joint work with Mark Braverman, Young Kun Ko, Jieming Mao and Dave Touchette.

1 0

CSML Seminar: David Dunson, Tomorrow, January 19, 2016 at 12:30pm | Computer Science, Room 105
by Nicole E. Wagenblast 18 Jan '16

18 Jan '16

David Dunson-Duke University Tuesday, January 19, 2016 12:30pm-1:30pm Computer Science, Room 105 * Lunch will be provided * Title: “Probabilistic inference from complex and high-dimensional data” Abstract: There is a well-known increasing trend in complexity and size of data being collected across fields. Although many approaches have been developed for analyzing such data, there is a clear lack of methods that are robust, computationally scalable, and provide realistic uncertainty quantification. We develop broad new tools for probabilistic inference from big and complex data along several threads, including a new framework for robust Bayesian inferences using coarsening, and new algorithms for scalable computation relying on (i) breaking data into subsets, estimating posterior probability measures for each subset and combining via Wasserstein barycenters; and (ii) approximate Markov chain Monte Carlo algorithms, which replace expensive transition kernels with approximations. We discuss theoretical results on robustness, computational complexity, and statistical accuracy and illustrate the methods with several applications. If you would like to be added to the CSML listerv, please email capizzi(a)princeton.edu .

1 0

Colloquium Speaker Tom Griffiths, today, 12:30pm
by Nicole E. Wagenblast 15 Jan '16

15 Jan '16

Colloquium Speaker Tom Griffiths, University of California, Berkeley Friday, January 15, 12:30pm Computer Science 105 Human and machine learning Human cognition still sets the standard we aspire to in many areas of machine learning, including problems such as identifying causal relationships, acquiring and using language, and learning concepts from a small number of examples. In these cases, human and machine learning can establish a mutually beneficial relationship: we can use the formal tools developed in machine learning to provide insights into human learning, and translate those insights into new machine learning systems. I will use the case of causal induction to illustrate the value of this approach, but also highlight some applications in language and concept learning. I will also argue that the same kind of mutually beneficial relationship could potentially exist between developing data-intensive approaches to cognitive science and making sense of large volumes of behavioral data in computer science.

1 0

Colloquium Speaker Tom Griffiths, Fri Jan 15, 12:30pm
by Nicole E. Wagenblast 14 Jan '16

14 Jan '16

Colloquium Speaker Tom Griffiths, University of California, Berkeley Friday, January 15, 12:30pm Computer Science 105 Human and machine learning Human cognition still sets the standard we aspire to in many areas of machine learning, including problems such as identifying causal relationships, acquiring and using language, and learning concepts from a small number of examples. In these cases, human and machine learning can establish a mutually beneficial relationship: we can use the formal tools developed in machine learning to provide insights into human learning, and translate those insights into new machine learning systems. I will use the case of causal induction to illustrate the value of this approach, but also highlight some applications in language and concept learning. I will also argue that the same kind of mutually beneficial relationship could potentially exist between developing data-intensive approaches to cognitive science and making sense of large volumes of behavioral data in computer science.

1 0

Colloquium Speaker Tom Griffiths, Fri Jan 15, 12:30pm
by Nicole E. Wagenblast 12 Jan '16

12 Jan '16

Colloquium Speaker Tom Griffiths, University of California, Berkeley Friday, January 15, 12:30pm Computer Science 105 Human and machine learning Human cognition still sets the standard we aspire to in many areas of machine learning, including problems such as identifying causal relationships, acquiring and using language, and learning concepts from a small number of examples. In these cases, human and machine learning can establish a mutually beneficial relationship: we can use the formal tools developed in machine learning to provide insights into human learning, and translate those insights into new machine learning systems. I will use the case of causal induction to illustrate the value of this approach, but also highlight some applications in language and concept learning. I will also argue that the same kind of mutually beneficial relationship could potentially exist between developing data-intensive approaches to cognitive science and making sense of large volumes of behavioral data in computer science.

1 0

Soumyadeep Ghosh will present his Pre-FPO, "Hardware Assurance with Pluggable Trust Architectures" on Friday, January 15, 2016 at 3:30pm in CS 301
by Nicki Gotsis 11 Jan '16

11 Jan '16

Soumyadeep Ghosh will present his Pre-FPO on Friday, January 15, 2016 at 3:30pm in CS 301. The members of his committee are David August (advisor), Andrew Appel and Aarti Gupta (readers), David Wentzlaff and Simha Sethumadhavan, Columbia University (non-readers). Everyone is invited to attend his talk. The talk title and abstract follow below: Title: Hardware Assurance with Pluggable Trust Architectures Abstract: Today, a user must take it on faith that their hardware and software providers have built a system which will not betray them to malicious actors. While significant research has been done on securing the software stack, these techniques all assume the presence of secure hardware. However, a number of factors such as incompleteness of techniques for verifying complex hardware designs, outsourcing and off-shoring of design and fabrication, and the incorporation of third-party components diminish confidence in the security of computer hardware. To address this problem, we propose a new architecture that allows users to select their own basis of trust in the system, independent of the device manufacturer. Trust is established via a pluggable and user-swappable hardware element called the Sentry. This pluggable-trust architecture isolates the effects of compromised hardware by allowing only the correctly executed results of signed software to be communicated externally. The basis of trust for the entire system is the Sentry, which acts as a gatekeeper and bridges the physical gap between the untrusted processor and any I/O device. The Sentry’s minimal effect on performance, the simplicity of its design, and its pluggability enable its production at an independent trusted fabrication plant. Its simplicity also makes the Sentry's verification tractable, giving the user choice in trust providers.

1 0

Sarthak Grover will present his General Exam on Friday, January 8, 2016 in CS 302 at 2pm.
by Nicki Gotsis 06 Jan '16

06 Jan '16

Sarthak Grover will present his General Exam on Friday, January 8, 2016 in CS 302 at 2pm. The members of his committee are Nick Feamster (Adviser), Kyle Jamieson, and Jennifer Rexford. 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* With a large increase in broadband services and capacity, it has become important to understand home network infrastructure and usage. Over the past two years, we have studied home network usage from two perspectives: the gateway and the ISP. In the first empirical study of home network availability, infrastructure, and usage, we deployed routers running custom firmware in multiple homes to collect measurements of home and Internet connectivity, as well as how users use their home network. Our results showed that half the home networks studied utilize less than half their available capacity. We followed up to this work by studying the relationship between traffic demand and service tier upgrades from the perspective of ISPs. In a unique controlled experiment, we compare two groups of Comcast subscribers from the same city: a control group (105 Mbps) and a randomly selected treatment group that was upgraded to 250 Mbps without their knowledge. We study how users who are already on service plans with high downstream throughput respond to a higher service tier (upgraded unknowingly), as compared to a similar control group. To our surprise, subscribers with moderate traffic demands increase their usage in response to a service-tier upgrade relatively more than high-volume subscribers do. We speculate that even though these users may not take advantage of the full available capacity, the service tier increase generally improves performance, which causes them to use the Internet more than they otherwise would have. *Reading List* 1. Bischof, Zachary S., Fabián E. Bustamante, and Rade Stanojevic. "Need, want, can afford: Broadband markets and the behavior of users." In Proceedings of the 2014 Conference on Internet Measurement Conference, pp. 73-86. ACM, 2014. 2. Kreibich, Christian, Nicholas Weaver, Boris Nechaev, and Vern Paxson. "Netalyzr: illuminating the edge network." In Proceedings of the 10th ACM SIGCOMM conference on Internet measurement, pp. 246-259. ACM, 2010. 3. Quan, Lin, John Heidemann, and Yuri Pradkin. "When the internet sleeps: correlating diurnal networks with external factors." In Proceedings of the 2014 Conference on Internet Measurement Conference, pp. 87-100. ACM, 2014. 4.Maier, Gregor, Anja Feldmann, Vern Paxson, and Mark Allman. "On dominant characteristics of residential broadband internet traffic." InProceedings of the 9th ACM SIGCOMM conference on Internet measurement conference, pp. 90-102. ACM, 2009. 5. Dicioccio, Lucas, Renata Teixeira, and Catherine Rosenberg. "Measuring home networks with homenet profiler." In Passive and Active Measurement, pp. 176-186. Springer Berlin Heidelberg, 2013. 6.Zheleva, Mariya, Paul Schmitt, Morgan Vigil, and Elizabeth Belding. "The increased bandwidth fallacy: performance and usage in rural zambia." InProceedings of the 4th Annual Symposium on Computing for Development, p. 2. ACM, 2013. 7.Cho, Kenjiro, Kensuke Fukuda, Hiroshi Esaki, and Akira Kato. "The impact and implications of the growth in residential user-to-user traffic." In ACM SIGCOMM Computer Communication Review, vol. 36, no. 4, pp. 207-218. ACM, 2006. 8.Paxson, Vern. "End-to-end routing behavior in the Internet." Networking, IEEE/ACM Transactions on 5, no. 5 (1997): 601-615. 9.Paxson, Vern. "Strategies for sound internet measurement." In Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, pp. 263-271. ACM, 2004. 10.Calvert, Kenneth L., W. Keith Edwards, and Rebecca E. Grinter. "Moving Toward the Middle: The Case Against the End-to-End Argument in Home Networking." In HotNets. 2007. 11.Sundaresan, Srikanth, Walter De Donato, Nick Feamster, Renata Teixeira, Sam Crawford, and Antonio Pescapè. "Broadband internet performance: a view from the gateway." In ACM SIGCOMM computer communication review, vol. 41, no. 4, pp. 134-145. ACM, 2011. 12.Peterson, Larry L., and Bruce S. Davie. Computer networks: a systems approach. Elsevier, 2007. 13.Grover, Sarthak, Mi Seon Park, Srikanth Sundaresan, Sam Burnett, Hyojoon Kim, Bharath Ravi, and Nick Feamster. "Peeking behind the NAT: an empirical study of home networks." In Proceedings of the 2013 conference on Internet measurement conference, pp. 377-390. ACM, 2013. 14.Grover, Sarthak, Roya Ensafi, and Nick Feamster. “A case study of traffic demand response to broadband service-plan upgrades.” In Proceedings of the 2016 Passive and Active Measurement Conference. 2016.

1 0

Soner Sevinc will present his FPO, "A Framework for Access Control and Resource Allocation in Federations" on Thursday, 1/14/2016 at 9am in CS 402
by Nicki Gotsis 05 Jan '16

05 Jan '16

Soner Sevinc will present his FPO, "A Framework for Access Control and Resource Allocation in Federations" on Thursday, 1/14/2016 at 9am in CS 402. The members of his committee are: Larry Peterson (adviser); Andy Bavier and Jennifer Rexford (readers); Michael Freedman and David Walker (nonreaders). A copy of his thesis is available in Room 310. Everyone is invited to attend his talk. The talk abstract follow below: ABSTRACT: In this thesis we address the access control and resource allocation problems in computational federations, such as testbeds and cloud computing federations. The computational federations of today are growing in their number of participant organizations, where one challenge is to allow organizations participate autonomously by expressing how much of their resources should be used and by whom, through complex policies. In addition, such organizations should be able to exchange resources with any other organizations without necessarily knowing all of them beforehand. We introduce our federation framework which allows to build federations in varying complexities easily, by synthesizing trust management, policy languages and resource discovery into a single system. Although these three have been studied separately in the past, we show that they are in fact related, and can be viewed as separate layers of a more general system. We argue that complex agreements that involve indirect trust relationships is one key way to enable resource exchange in a federation with numerous organizations, and this can be realized by our synthesis architecture that provides usability as well as expressiveness. As part of our framework, federation policy language (FPL) is used to express both the security and allocation policies, by providing simple primitives such as contracts that hide the underlying complexity. FPL primitives allow system administrators to express policies such as indirect trust and resource restrictions within the same construct. Underneath, FPL uses our distributed trust management system (CERTDIST) to implement and impose policy primitives. CERTDIST uses digital certificates to allow or deny resource requests and a DHT for complex distributive proofs in an e!cient way. The Resource discovery part of our framework (CODAL) is layered on top of FPL, and uses contracts to discover peers, FPL security and allocation policies to authorize for resources that are located possibly in many di↵erent organizations. We evaluate the federation framework with a realistic emulation of a large scale federation using real PlanetLab traces, that shows that complex policies can be expressed with a minimal amount of code, and we can e!ciently perform the access control and resource discovery operations in a federation.

1 0

Ben Jones will present his Generals Exam on Tuesday, January 12, 2016 at 11am in CS 302.
by Nicki Gotsis 05 Jan '16

05 Jan '16

Ben Jones will present his Generals Exam on Tuesday, January 12, 2016 at 11am in CS 302. The members of his committee are: Nick Feamster (adviser), Andrew Appel, and Prateek Mittal. 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 Censorship measurement is an important problem and social scientists, CS researchers, and advocacy groups all aim to discover what governments censor, how they restrict access, and how decisions about censorship vary across regions, countries, and time. Unfortunately, existing approaches cannot perform censorship measurements at a scale sufficient to answer these questions; worse, users must perform these measurements on-site, which is potentially risky due to the threat of retaliation against citizens who perform measurements. In my talk, I will present SPICE (Stealthy Panopticon for Internet Censorship Exploration) [7], a tool designed to measure censorship and evade the surveillance that puts users at risk. SPICE’s contributions are modeling censorship and surveillance, developing two strategies for reducing measurement risk, and implementing the measurements for one of these strategies. We model censorship based on existing work on the Great Firewall of China (GFC) and we model surveillance based on leaked Snowden documents and our campus IDS. We observe that surveillance and censorship systems have different goals, and thus certain types of measurement techniques may be able to characterize a censorship system without triggering a surveillance system. Although it is almost certainly impossible to eliminate risk (or even determine if we have succeeded in doing so), we posit that we may be able to reduce risk with measurement techniques that are difficult to observe or distinguish from innocuous network activity. Reading List Textbook: L. L. Peterson and B. S. Davie. Computer Networks, Fifth Edition: A Systems Approach. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 5th edition, 2011. Papers: [1] Anonymous. Towards a Comprehensive Picture of the Great Firewall’s DNS Censorship. In 4th USENIX Workshop on Free and Open Communications on the Internet (FOCI 14), San Diego, CA, Aug. 2014. USENIX Association. [2] A. Filasto` and J. Appelbaum. OONI: Open Observatory of Network Interference. In Presented as part of the 2nd USENIX Workshop on Free and Open Communications on the Internet, Berkeley, CA, 2012. USENIX. [3] J. Geddes, M. Schuchard, and N. Hopper. Cover Your ACKs: Pitfalls of Covert Channel Censorship Circumvention. In Proceedings of the 2013 ACM SIGSAC Conference on Computer &; Communications Security, CCS ’13, pages 361–372, New York, NY, USA, 2013. ACM. [4] A. Houmansadr, C. Brubaker, and V. Shmatikov. The Parrot is Dead: Observing unobservable network communications. In Proceedings of the 2013 IEEE Symposium on Security and Privacy, 2013. [5] B. Jones, R. Ensafi, N. Feamster, V. Paxson, and N. Weaver. Ethical concerns for censorship measurement. In Proceedings of the 2015 ACM SIGCOMM Workshop on Ethics in Networked Systems Research, pages 17–19. ACM, 2015. [6] B. Jones and N. Feamster. Can Censorship Measurements Be Safe(R)? In Proceedings of the 14th ACM Workshop on Hot Topics in Networks, HotNets-XIV, pages 1:1–1:7, New York, NY, USA, 2015. ACM. [7] M. Ku ̈hrer, T. Hupperich, J. Bushart, C. Rossow, and T. Holz. Going Wild: Large-Scale Classification of Open DNS Resolvers. In Proceedings of the 2015 ACM Conference on Internet Measurement Conference, IMC ’15, pages 355–368. ACM, 2015. [8] K. Schomp, T. Callahan, M. Rabinovich, and M. Allman. On Measuring the Client-side DNS Infrastructure. In Proceedings of the 2013 Conference on Internet Measurement Conference, IMC ’13, pages 77–90, New York, NY, USA, 2013. ACM. [9] W. Scott, S. Berg, and A. Krishnamurth. Satellite: Observations of the Internets Stars. Technical report, University of Washington, 2015. [10] A. Sfakianakis, E. Athanasopoulos, and S. Ioannidis. CensMon: A Web censorship monitor. In USENIX Workshop on Free and Open Communication on the Internet (FOCI), 2011.

1 0

Xin Jin will present his Pre FPO on Monday, January 11, 2016 at 4pm in CS 302
by Nicki Gotsis 04 Jan '16

04 Jan '16

Xin Jin will present his Pre FPO on Monday, January 11, 2016 at 4pm in CS 302. The members of his committee are: Jennifer Rexford (adviser), David Walker (reader), Ratul Mahajan (Microsoft Research, reader), Nick Feamster (non-reader), Aarti Gupta (non-reader). Everyone is invited to attend his talk. The talk title and abstract follow below: Title: Dynamic management of software-defined networks Abstract: Network management is a difficult problem, since network administrators have to continuously update network configurations to alleviate congestion by routing more efficiently, to detect and block cyber-attacks, to perform planned maintenance, etc. Network updates are painful because operators unfortunately have to balance the tradeoff between the disruption caused by the problem (e.g., congestion and cyber-attacks), and the disruption introduced in fixing the problem. In this talk, I will present my research on building new network management systems that can (1) efficiently compose configuration updates from multiple network services, (2) quickly apply them to switches, and (3) effectively handle topology changes. I will first present CoVisor, a new kind of network hypervisor that enables, in a single network, the deployment of multiple network services written in different programming languages and operating on different controller platforms. CoVisor provides a simple API that allows network administrators to define the composition of multiple controllers, to choose the virtual topology exposed to each controller, and to constrain the packet handling capability of each controller. We developed a new set of efficient algorithms for composing controller applications and for compiling configurations of virtual networks into those of the physical network. We built a CoVisor prototype and showed that it is several orders of magnitude faster than a vanilla implementation without our optimizations. In the second part of the talk, I will present Dionysus, a new network update system that can quickly and consistently update network configurations. Dionysus uses a novel tool called a dependency graph to capture the dependencies between individual update operations. Based on the dependency graph, Dionysus dynamically schedules operations according to runtime conditions, and guarantees the consistency of the updates. We built a prototype of Dionysus and extensively evaluated it with testbed experiments and large-scale simulations. Results showed that Dionysus improves the median update speed by 53–88% as compared to prior methods. Finally, I will present Owan, a novel traffic management system that optimizes wide-area big data transfers with centralized joint control of the optical and network layers. Owan can dynamically change the network-layer topology by reconfiguring the optical devices. We developed efficient algorithms that dynamically reconfigure the optical circuits in the optical layer so that most transfers can use one or few hops in the network layer to reach their destinations. Testbed experiments and large-scale simulations showed that Owan completes big data transfers up to 4× faster on average, and up to 1.35× more transfers meet their deadlines, as compared to prior methods that only control the network layer.

1 0