- talks - lists.cs.princeton.edu

Colloquium Speaker Yoram Singer, Mon Feb 9, 4:30pm
by Nicole E. Wagenblast 03 Feb '15

03 Feb '15

Colloquium Speaker Yoram Singer, Google Research Monday, February 9, 4:30pm Computer Science 105 Learning compact models from high dimensional large datasets I review the design, analysis, and implementation of stochastic optimization techniques, online algorithms, and modeling approaches for learning in high dimensional spaces using large amounts of data. The focus is on algorithms and models that are efficient, accurate, and yield compact models. Concretely, the forward-backward shrinkage algorithm (Fobos), mirror descent for learning composite objectives (COMID), and the adaptive gradient (AdaGrad) algorithm. We also discuss simple yet effective modeling approaches based on locality for learning from high dimensional data. Yoram Singer is a senior research scientist at Google. From 1999 through 2007 he was an associate professor at the Hebrew University of Jerusalem. From 1995 through 1999 he was a member of the technical staff at AT&T Research. He was the co-chair of the conference on Computational Learning Theory (COLT) in 2004 and of Neural Information Processing Systems (NIPS) in 2007. He serves as an editor of the Journal of Machine Learning, IEEE Signal Processing Magazine, and IEEE Trans. on Pattern Analysis and Machine Intelligence.

1 0

Colloquium Speaker Omer Reingold Wed Feb 4, 12:30pm
by Nicole E. Wagenblast 03 Feb '15

03 Feb '15

Colloquium Speaker Randomness Vs. Memory: A Treasure(s) Hunt Omer Reingold, Weizmann Institute of Science Wednesday, February 4, 12:30pm Computer Science 105 Randomness Vs. Memory: A Treasure(s) Hunt Randomness plays a major role in computation, allowing the execution of tasks that would otherwise be impossible or prohibitively inefficient. Yet the relative power of randomness compared with other resources of computation is mostly unresolved. In this talk we will address the tradeoff between memory and randomness. Namely, can randomness signiﬁcantly reduce the amount of memory needed for algorithmic tasks? This is one of the central problems in Computational Complexity and its study is tied with the study of pseudorandom generators that fool memory-bounded algorithms (i.e. combinatorial objects that look random to small-memory distinguishers). There are many exciting questions on the path towards resolving the randomness vs memory problem. In this talk we will focus on two such areas of research. First, we will discuss small memory algorithms for graph connectivity as well as pseudorandom walks, which we will relate to the general problem of randomness vs. memory. Then we will describe pseudorandom families of hash functions for data structures that are simultaneously small and efficient (with applications to load balancing, the two-choice paradigm, cuckoo hashing, and min-hashing). We will relate such families to progress on more traditional pseudorandom objects such as epsilon-bias sequences and functions with limited independence. Omer Reingold is a Professor of Computer Science at the Weizmann Institute of Science and a Visiting Professor at Stanford University. Past positions include Microsoft Research, the Institute for Advanced Study in Princeton, NJ, and AT&T Labs. His research is in the Foundations of Computer Science and most notably in Computational Complexity and the Foundations of Cryptography with emphasis on randomness, derandomization and explicit combinatorial constructions. He is an ACM Fellow and among his distinctions are the 2005 Grace Murray Hopper Award and the 2009 Gödel Prize.

1 0

Yiming Liu will present his Pre FPO on Monday, Feb. 9, 2015 at 1:30pm in CS 301
by Nicki Gotsis 02 Feb '15

02 Feb '15

Yiming Liu will present his Pre FPO on Monday, Feb. 9, 2015 at 1:30pm in CS 301. The members of his committee are as follows: His advisor is Szymon Rusinkiewicz; his readers are Adam Finkelstein and Aseem Agarwala (Adobe); and his non readers are Thomas Funkhouser and Jianxiong Xiao. His abstract is below. Traditional systems for image design and enhancement are completely reliant on user input, either to generate content directly or to evaluate and tune algorithms. The input must be generated by talented artists, and it is applicable only to the image for which it was originally intended. This poses scalability challenges for such traditional image generation and editing systems. An alternative paradigm, which is being researched in a variety of content-generation domains, is to exploit the large amount of data made available by users over the Internet. This data may take many forms: images, image keywords, and even judgments about image quality. Although the data is noisy and was not originally intended for the task at hand, it nevertheless serves as a useful source of "prior information". These priors make it possible to build image design and enhancement systems that require only a small amount of user input, and do not require the users to be professional artists or designers. This thesis describes three such systems, including low-level image-processing (motion deblurring), high-level editing (keyword-based image stylization), and image design (sketch-driven iconification). First, by learning based on a massive online user study, we develop a metric for automatically predicting the perceptual quality of images produced by motion deblurring algorithms, without access to the original images. Second, by leveraging online image search engines, we investigate an approach to photo filtering that only requires the user to provide one or more keywords. Third, we develop a system that converts a rough user-provided sketch into an attractive customized pictogram by remixing portions of icons retrieved from a large online repository. The projects in this talk are joint work with Aseem Agarwala, Sunghyun Cho, Michael Cohen, Adam Finkelstein, Cynthia Lu, Szymon Rusinkiewicz, Matt Uyttendaele, and Jue Wang.

1 0

Aaron Wong will present his FPO on Monday, Feb. 9, 2015 at 10:30am in CS 301
by Nicki Gotsis 02 Feb '15

02 Feb '15

Aaron Wong will present his FPO on Monday, Feb. 9, 2015 at 10:30am in CS 301 The members of his committee are: Non-readers: Moses Charikar, Kai Li; Readers: Barbara Engelhardt, Mona Singh A copy of his thesis is available in Room 310. Everyone is invited to attend his talk. ABSTRACT Biologists using modern experimental methods are generating a massive number of genomescale datasets. In particular, the rate of large-scale data creation in most organisms is quickly outpacing biologists’ ability to perform detailed follow-up experiments. Thus a substantial gap exists between the massive data being generated and the comparatively small number of experimental validations being performed (i.e. biology knowledge). In this manuscript, we present four solutions that broadly address this growing disparity, focusing on disease- and tissue-specific genomic analysis. These solutions are unified by their approaches to this problem: by combining and integrating available public genome-wide measurements to enable biological discoveries that would otherwise be impossible. First, we demonstrate a method to systematically transfer experimental knowledge between organisms inferred from high-throughput experimental data. By leveraging functional genomic data, we can improve the coverage and accuracy of function predictions across diverse organisms and machine learning methods. Second, we present an interactive web server that addresses the needs of biologists to visualize their experimental results in the context of multi-species functional predictions and relationships. Third, we describe a method that, for the first time, leverages large data compendia to build genome-scale tissue-specific functional maps in human by integrating thousands of genomescale datasets. Our method can extract both functional and tissue/cell-type signals even when genomic data are not resolved for the tissue and very little are known about the expression of genes in the tissue. Finally, we detail a method for biologists to analyze their genome-scale datasets in the context of the massive public data compendium. Biologists are generating and trying to make sense of massive high-throughput datasets, and their biological questions can be more precisely addressed within the biological context of their experiment. By incorporating their experimental results in the search and integration of gene expression compendia, we demonstrate improved predictive performance in identifying additional functionally related genes.

1 0

Colloquium Speaker Omer Reingold Wed Feb 4, 12:30pm
by Nicole E. Wagenblast 29 Jan '15

29 Jan '15

Colloquium Speaker Randomness Vs. Memory: A Treasure(s) Hunt Omer Reingold, Weizmann Institute of Science Wednesday, February 4, 12:30pm Computer Science 105 Randomness Vs. Memory: A Treasure(s) Hunt Randomness plays a major role in computation, allowing the execution of tasks that would otherwise be impossible or prohibitively inefficient. Yet the relative power of randomness compared with other resources of computation is mostly unresolved. In this talk we will address the tradeoff between memory and randomness. Namely, can randomness signiﬁcantly reduce the amount of memory needed for algorithmic tasks? This is one of the central problems in Computational Complexity and its study is tied with the study of pseudorandom generators that fool memory-bounded algorithms (i.e. combinatorial objects that look random to small-memory distinguishers). There are many exciting questions on the path towards resolving the randomness vs memory problem. In this talk we will focus on two such areas of research. First, we will discuss small memory algorithms for graph connectivity as well as pseudorandom walks, which we will relate to the general problem of randomness vs. memory. Then we will describe pseudorandom families of hash functions for data structures that are simultaneously small and efficient (with applications to load balancing, the two-choice paradigm, cuckoo hashing, and min-hashing). We will relate such families to progress on more traditional pseudorandom objects such as epsilon-bias sequences and functions with limited independence. Omer Reingold is a Professor of Computer Science at the Weizmann Institute of Science and a Visiting Professor at Stanford University. Past positions include Microsoft Research, the Institute for Advanced Study in Princeton, NJ, and AT&T Labs. His research is in the Foundations of Computer Science and most notably in Computational Complexity and the Foundations of Cryptography with emphasis on randomness, derandomization and explicit combinatorial constructions. He is an ACM Fellow and among his distinctions are the 2005 Grace Murray Hopper Award and the 2009 Gödel Prize.

1 0

Joshua Kroll's PreFPO will take place Feb 3, 2015 at 2pm in CITP conference room (Sherrerd 306)
by Nicki Gotsis 28 Jan '15

28 Jan '15

Joshua Kroll will present his PreFPO on Feb 3, 2015 at 2pm in CITP conference room (Sherrerd 306). The members of his committee are: Ed Felten (advisor); Matt Green (Johns Hopkins University) and Arvind Narayanan (readers); Andrew Appel and Nick Feamster (nonreaders). Everyone is invited to attend his talk. The talk title and abstract follow below: Title: Accountable Algorithms Abstract: Important decisions about people are increasingly made by algorithms: Votes are counted; voter rolls are purged; financial aid decisions are made; taxpayers are chosen for audits; air travelers are selected for search; credit eligibility decisions are made. Citizens, and society as a whole, have an interest in making these processes more transparent. Yet the full basis for these decisions is rarely available to affected people: the algorithm or some inputs may be secret; or the implementation may be secret; or the process may not be precisely described. A person who suspects the process went wrong has little recourse. And an oversight authority who wants to ensure that decisions are made according to an acceptable policy has little assurance that proffered decision rules match decisions for actual users. Traditionally, Computer Science addresses these problems by demanding a specification of the desired behavior, which can then be enforced or verified. But this model is poorly suited to real-world oversight tasks, where the specification might be complicated or might not be known in advance. For example, laws are often ambiguous precisely because it would be politically (and practically) infeasible to give a precise specification of their meaning. Instead, people do their best to approximate what they believe the law will allow and disputes about what is actually acceptable happen after-the-fact via expensive investigation and adjudication (e.g. in a court or legislature). As a result, actual oversight, in which real decisions are reviewed for their correctness, fairness, or faithfulness to a rule happens only rarely, if at all. Further, Computer Science often sees rules as self-enforcing: the mere fact that an automated check fails is sufficient to demonstrate that some choice was invalid. However, like all rules, automated rules (even those implemented by cryptography) are just the intentions of a system designer and only bear relevance to the extent that people will actually follow them, either due to internalized incentives or the external threat of punishment. In this thesis, we present a novel approach to relating the tools of technology to the problem of overseeing decision making processes. Our methods use the tools of computer science to cryptographically ensure the technical properties that can be proven, while providing information necessary for a political, legal, or social oversight process to operate effectively. First, we present a system for the accountable execution of legal warrants, in which the decision by a judge to allow an investigator access to private or sensitive records is realized cryptographically, so that the investigator's access to sensitive information is limited to only that information which the judge has explicitly allowed (and this can be confirmed by a disinterested third party). This system is an example of the current style of technical systems for accountability: a well-defined policy, specified in advance, is operationalized with technical tools. However, our construction does not just enforce the policy, but can convince others that the policy is being enforced correctly. Second, we present accountable algorithms, unifying the tools of zero-knowledge computational integrity with cryptographic commitments to design processes that admit meaningful after-the-fact oversight, consistent with the norm in law and policy. Accountable algorithms can attest to the valid operation of a decision policy even when all or part of that policy is kept secret.

1 0

Annie Edmundson will present her General Exam on January 21st, 2015 at 2pm in 302
by Nicki Gotsis 15 Jan '15

15 Jan '15

Annie Edmundson will present her General Exam on January 21st, 2015 at 2pm in 302. The members of her committee are Ed Felten, Arvind Narayanan and Cynthia Sturton (UNC-Chapel Hill). 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 are attached. Abstract: Malicious hardware provides an attacker a greater advantage than software-based attacks because it gives an attacker control over the entire software stack while providing a smaller chance of detection and prevention. The supply chain process for devices is extremely hard to secure in order to provide trusted microelectronic components; current methods for malicious circuit detection at design time usually look for circuitry that is never or rarely used. These methods include dynamic analysis during verification testing and boolean function analysis on a gate-level netlist. This work shows how to defeat the state-of-the-art algorithms in design time hardware trojan detection. We have implemented a backdoor in the LEON3 processor, which implements the SPARC V8 ISA; the malicious backdoor will allow a user-level program to enter supervisor mode with a specific sequence of instructions. We will also discuss fundamental problems of trojan detection, as well as possible areas for improvement. Reading List: Textbooks: 1. Anderson, Ross. Security engineering. John Wiley & Sons, 2008. 2. Harris, David Money, and Sarah L. Harris. Digital design and computer architecture. Elsevier, 2013. Chapters 1-5, 6.5, 6.6, 7.5, 7.6 Papers: 1. Agrawal, Dakshi, Selcuk Baktir, Deniz Karakoyunlu, Pankaj Rohatgi, and Berk Sunar. "Trojan detection using IC fingerprinting." In Security and Privacy, 2007. SP'07. IEEE Symposium on, pp. 296-310. IEEE, 2007. 2. Bilzor, Michael, Ted Huffmire, Cynthia Irvine, and Tim Levin. "Security checkers: Detecting processor malicious inclusions at runtime." In Hardware-Oriented Security and Trust (HOST), 2011 IEEE International Symposium on, pp. 34-39. IEEE, 2011. 3. Hicks, Matthew, Murph Finnicum, Samuel T. King, Milo Martin, and Jonathan M. Smith. "Overcoming an untrusted computing base: Detecting and removing malicious hardware automatically." In Security and Privacy (SP), 2010 IEEE Symposium on, pp. 159-172. IEEE, 2010. 4. King, Samuel T., Joseph Tucek, Anthony Cozzie, Chris Grier, Weihang Jiang, and Yuanyuan Zhou. "Designing and Implementing Malicious Hardware." LEET 8 (2008): 1-8. 5. Sturton, Cynthia, Matthew Hicks, David Wagner, and Samuel T. King. "Defeating UCI: Building stealthy and malicious hardware." In Security and Privacy (SP), 2011 IEEE Symposium on, pp. 64-77. IEEE, 2011. 6. Waksman, Adam, and Simha Sethumadhavan. "Silencing hardware backdoors." In Security and Privacy (SP), 2011 IEEE Symposium on, pp. 49-63. IEEE, 2011. 7. Waksman, Adam, and Simha Sethumadhavan. "Tamper evident microprocessors." In Security and Privacy (SP), 2010 IEEE Symposium on, pp. 173-188. IEEE, 2010. 8. Waksman, Adam, Matthew Suozzo, and Simha Sethumadhavan. "FANCI: identification of stealthy malicious logic using boolean functional analysis." In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, pp. 697-708. ACM, 2013. 9. Zhang, Jie, Feng Yuan, Lingxiao Wei, Zelong Sun, and Qiang Xu. "VeriTrust: verification for hardware trust." In Proceedings of the 50th Annual Design Automation Conference, p. 61. ACM, 2013. 10. Zhang, Jie, Feng Yuan, and Qiang Xu. "DeTrust: Defeating hardware trust verification with stealthy implicitly-triggered hardware Trojans." In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, pp. 153-166. ACM, 2014.

1 0

Colloquium Speaker Adam Wierman, Today, 11am
by Nicole E. Wagenblast 15 Jan '15

15 Jan '15

Colloquium Speaker Adam Wierman, CalTech Data Centers, Energy, and Online Optimization Thursday, January 15, 11:00am Computer Science 105 This talk will tell two stories, one about designing sustainable data centers and one about the underlying algorithmic challenges, which fall into the context of online convex optimization. Story 1: The typical message surrounding data centers and energy is an extremely negative one: Data centers are energy hogs. This message is pervasive in both the popular press and academia, and it certainly rings true. However, the view of data centers as energy hogs is too simplistic. One goal of this talk is to highlight that, yes, data centers use a lot of energy, but data centers can also be a huge benefit in terms of integrating renewable energy into the grid and thus play a crucial role in improving the sustainability of our energy landscape. In particular, I will highlight a powerful alternative view: data centers as demand response opportunities. Story 2: Typically in online convex optimization it is enough to exhibit an algorithm with low (sub-linear) regret, which implies that the algorithm can match the performance of the best static solution in retrospect. However, what if one additionally wants to maintain performance that is nearly as good as the dynamic optimal, i.e., a good competitive ratio? In this talk, I'll highlight that it is impossible for an online algorithm to simultaneously achieve these goals. Luckily though, in practical settings (like data centers), noisy predictions about the future are often available, and I will show that, under a general model of prediction noise, even very limited predictions about the future are enough to overcome the impossibility result. Adam Wierman is a Professor in the Department of Computing and Mathematical Sciences at the California Institute of Technology, where he is a founding member of the Rigorous Systems Research Group (RSRG) and maintains a popular blog called Rigor + Relevance. His research interests center around resource allocation and scheduling decisions in computer systems and services. He received the 2011 ACM SIGMETRICS Rising Star award, the 2014 IEEE Communications Society William R. Bennett Prize, and has been coauthor on papers that received of best paper awards at ACM SIGMETRICS, IEEE INFOCOM, IFIP Performance (twice), IEEE Green Computing Conference, IEEE Power & Energy Society General Meeting, and ACM GREENMETRICS.

1 0

Santiago Cuellar will present his General Exam on Wednesday, January 21st, 2015 in Room 402 at 2pm.
by Nicki Gotsis 14 Jan '15

14 Jan '15

Santiago Cuellar will present his General Exam on Wednesday, January 21st, 2015 in Room 402 at 2pm. The members of his committee are Andrew W. Appel, David Walker, and Aarti Gupta. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His/her abstract and reading list follow below. ================================================ Abstract: The first verified separate compiler for C, Compositional CompCert, was recently introduced with an operational model supporting language-independent linking and machine-checked proofs of vertical and horizontal composition, strengthening Leroy’s original CompCert proofs. The key techniques for its verification are structured simulations: logical relations between runtime states that enforce safety invariants in the presence of compiler-managed memory regions (private) and addressable portions of the stack frames that might be leaked to foreign modules through external function calls (public). However, the invariants are too strict to allow merging of stack frame as needed, for example, in function inlining optimizations. Moreover, changing the simulations is challenging since they strike a delicate balance that satisfies relies and guarantees among the compiled modules. In this work we present a refinement of the structured simulations that admits a larger number of compiler transformations (e.g. Function inlining) while maintaining compatibility with the operational model and the semantics preservation proof of the full compiler. The relaxation of the simulation works together with a strengthening of the proof for the composition of compiler phases (transitivity). The development has been written and verified in the proof assistant Coq. ======================================================== Reading List: Text books: * A. W. Appel. Modern Compiler Implementation in ML. Cambridge University Press, 1998 * Part I Fundamentals of Compilation * 13. Garbage Collection * 15. Functional Programming Languages (?) * 17. Dataflow Analysis * 19. Static Single-Assignment Form B. Pierce. Types and Programming Languages. 2002. * Part I Untyped Systems * Part II Simple Types * Part IV Recursive Types * Part V Polymorphism * 22. Type Reconstruction * 23. Universal Types * 24. Existencial Types * 25. An ML Implementation of system F Papers * [A. W. Appel] VeriSmall: Veriﬁed Smallfoot Shape Analysis. In First International Conf. on Certiﬁed Programs and Proofs Dec. 2011 * *[L. Beringer, G. Stewart, and A. W. Appel] Verified compilation for shared-memory C. In Esop’ 14: The 23rd European Symposium on Programming, 2014. * *[Leroy 2009] X. Leroy. Formal verification of a realistic compiler. Communications of the ACM, 52(7):107–115, 2009. * *[James T. Perconti and Amal Ahmed] Verifying an Open Compiler Using Multi-Language Semantics. Programming Languages and Systems 2014 * [Reynolds 2002] J.C. Reynolds. Separation Logic: a Logic for Shared Mutable Data Structures. In LICS’02: Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science, pages 55 - 74, 2002. * [Lerner 2003] S. Lerner, T. Millstein, and C. Chambers. Automatically Proving the Correctness of Compiler Optimizations. In PLDI’03: Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, 2003. * [Leroy and Blazy 2008] X. Leroy and S. Blazy. Formal verification of a C-like memory model and its uses for verifying program transformations. J. Automated Reasoning, 41(1):1–31, 2008. * [G. Morrisett and D. Walker] From System F to Typed Assembly Language

1 0

Colloquium Speaker Adam Wierman, Thursday, Jan 15, 11am
by Nicole E. Wagenblast 14 Jan '15

14 Jan '15

Colloquium Speaker Adam Wierman, CalTech Data Centers, Energy, and Online Optimization Thursday, January 15, 11:00am Computer Science 105 This talk will tell two stories, one about designing sustainable data centers and one about the underlying algorithmic challenges, which fall into the context of online convex optimization. Story 1: The typical message surrounding data centers and energy is an extremely negative one: Data centers are energy hogs. This message is pervasive in both the popular press and academia, and it certainly rings true. However, the view of data centers as energy hogs is too simplistic. One goal of this talk is to highlight that, yes, data centers use a lot of energy, but data centers can also be a huge benefit in terms of integrating renewable energy into the grid and thus play a crucial role in improving the sustainability of our energy landscape. In particular, I will highlight a powerful alternative view: data centers as demand response opportunities. Story 2: Typically in online convex optimization it is enough to exhibit an algorithm with low (sub-linear) regret, which implies that the algorithm can match the performance of the best static solution in retrospect. However, what if one additionally wants to maintain performance that is nearly as good as the dynamic optimal, i.e., a good competitive ratio? In this talk, I'll highlight that it is impossible for an online algorithm to simultaneously achieve these goals. Luckily though, in practical settings (like data centers), noisy predictions about the future are often available, and I will show that, under a general model of prediction noise, even very limited predictions about the future are enough to overcome the impossibility result. Adam Wierman is a Professor in the Department of Computing and Mathematical Sciences at the California Institute of Technology, where he is a founding member of the Rigorous Systems Research Group (RSRG) and maintains a popular blog called Rigor + Relevance. His research interests center around resource allocation and scheduling decisions in computer systems and services. He received the 2011 ACM SIGMETRICS Rising Star award, the 2014 IEEE Communications Society William R. Bennett Prize, and has been coauthor on papers that received of best paper awards at ACM SIGMETRICS, IEEE INFOCOM, IFIP Performance (twice), IEEE Green Computing Conference, IEEE Power & Energy Society General Meeting, and ACM GREENMETRICS.

1 0