- talks - lists.cs.princeton.edu

Colloquium Speaker: John Langford, Friday May 6, 12:30pm
by Nicole E. Wagenblast 05 May '16

05 May '16

Colloquium Speaker John Langford, Microsoft Research Friday, May 6, 12:30pm Computer Science 105 How to make an Infovore An Infovore is an information-based entity that explores the world, learns, and applies these learnings effectively. In essence: a form of weak AI. We have been working on a general-purpose infovore for making decisions using elements of contextual bandits, systems, and experts-style learning that has now been successfully deployed at large scale. I will discuss the architecture of the infovore, the key results upon which it relies, and how everything works together to enable true open-loop learning in the real world.

1 0

Miles Carlsten will present his MSE talk, "The impact of transaction fees on Bitcoin mining strategies" on Friday, May 6 at 1:30pm in CS 301.
by Nicki Gotsis 05 May '16

05 May '16

Miles Carlsten will present his MSE talk, "The impact of transaction fees on Bitcoin mining strategies" on Friday, May 6 at 1:30pm in CS 301. The members of his committee are Arvind Narayanan (adviser) and Mark Braverman. The title and abstract follow below. Everyone is invited to attend. Title: The impact of transaction fees on Bitcoin mining strategies Abstract: There are two incentives for Bitcoin miners to mine Bitcoin blocks. The miners are rewarded both from the minting reward of creating a new block and from the transaction fees on the transactions included in the block mined. Traditionally, the minting reward has always been significantly larger than the transaction fees, but as time goes on the minting fee is designed to diminish, and it is expected that the transaction fees will take its place. We look into the unverified claim that once incentives shift to mostly transaction fees, the security of the system will be the same as it was when it was based on minting rewards. We show that this change can lead to very uneven blocks, which can give rational miners an incentive to intentionally try to fork the blockchain. Additionally, we reexamine a previously known alternate mining strategy, known as Selfish Mining, and show that it will become profitable for any miner (regardless of their hash power) to utilize this strategy.

1 0

Themistoklis Melissaris will present his general exam on Wednesday, May 11, 2016 at 4:30pm in CS 402.
by Nicki Gotsis 04 May '16

04 May '16

Themistoklis Melissaris will present his general exam on Wednesday, May 11, 2016 at 4:30pm in CS 402. The members of his committee are Margaret Martonosi (adviser), Kyle Jamieson, and JP Singh. The title and abstract follow below. Everyone is invited to attend the talk and those faculty wishing to remain for the oral exam are welcome to do so. Title: LOCOMOTIVE: Optimizing mobile web traffic using selective compression Abstract Global mobile traffic is growing at a rapid rate, following an increase in connected mobile devices and adoption of services and mobile apps. A common practice is to reduce web traffic by utilizing compression. However, universal application of compression can introduce latency and energy overheads and raises the need to pinpoint the conditions for compression insertion. My talk will discuss LOCOMOTIVE (Latency Optimizations by COmpressing MObile Transfers In Variable Environments), a framework that determines whether to use compression on the fly based on the traffic and on network conditions. LOCOMOTIVE uses a simple latency model to drive its decisions. The results of this approach indicate savings in both latency and energy, while reducing the data overhead. My work has explored characteristics of mobile traffic across different mobile devices and has studied the energy and latency impact of compression. Reading List 1. Armando Fox, Steven D. Gribble, Eric A. Brewer, and Elan Amir. 1996. Adapting to network and client variability via on-demand dynamic distillation. In Proceedings of the seventh international conference on Architectural support for programming languages and operating systems (ASPLOS VII). ACM, New York, NY, USA, 160-170. DOI=http://dx.doi.org/10.1145/237090.237177 2. Jeffrey C. Mogul, Fred Douglis, Anja Feldmann, and Balachander Krishnamurthy. 1997. Potential benefits of delta encoding and data compression for HTTP. In Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication (SIGCOMM '97), Martha Steenstrup (Ed.). ACM, New York, NY, USA, 181-194. DOI=http://dx.doi.org/10.1145/263105.263162 3. Victor Agababov, Michael Buettner, Victor Chudnovsky, Mark Cogan, Ben Greenstein, Shane McDaniel, Michael Piatek, Colin Scott, Matt Welsh, and Bolian Yin. 2015. Flywheel: Google's data compression proxy for the mobile web. In Proceedings of the 12th USENIX Conference on Networked Systems Design and Implementation (NSDI'15). USENIX Association, Berkeley, CA, USA, 367-380. 4. Feng Qian, Junxian Huang, Jeffrey Erman, Z. Morley Mao, Subhabrata Sen, and Oliver Spatscheck. 2013. How to reduce smartphone traffic volume by 30%?. In Proceedings of the 14th international conference on Passive and Active Measurement (PAM'13), Matthew Roughan and Rocky Chang (Eds.). Springer-Verlag, Berlin, Heidelberg, 42-52. DOI=http://dx.doi.org/10.1007/978-3-642-36516-4_5 5. Christopher M. Sadler and Margaret Martonosi. 2006. Data compression algorithms for energy-constrained devices in delay tolerant networks. In Proceedings of the 4th international conference on Embedded networked sensor systems (SenSys '06). ACM, New York, NY, USA, 265-278. DOI=http://dx.doi.org/10.1145/1182807.1182834 6. Kenneth Barr and Krste Asanović. 2003. Energy aware lossless data compression. In Proceedings of the 1st international conference on Mobile systems, applications and services (MobiSys '03). ACM, New York, NY, USA, 231-244. DOI=http://dx.doi.org/10.1145/1066116.1066123 7. Niranjan Balasubramanian, Aruna Balasubramanian, and Arun Venkataramani. 2009. Energy consumption in mobile phones: a measurement study and implications for network applications. InProceedings of the 9th ACM SIGCOMM conference on Internet measurement conference (IMC '09). ACM, New York, NY, USA, 280-293. DOI=http://dx.doi.org/10.1145/1644893.1644927 8. Feng Qian, Subhabrata Sen, and Oliver Spatscheck. 2014. Characterizing resource usage for mobile web browsing. In Proceedings of the 12th annual international conference on Mobile systems, applications, and services (MobiSys '14). ACM, New York, NY, USA, 218-231. DOI=http://dx.doi.org/10.1145/2594368.2594372 9. Hossein Falaki, Dimitrios Lymberopoulos, Ratul Mahajan, Srikanth Kandula, and Deborah Estrin. 2010. A first look at traffic on smartphones. In Proceedings of the 10th ACM SIGCOMM conference on Internet measurement (IMC '10). ACM, New York, NY, USA, 281-287. DOI=http://dx.doi.org/10.1145/1879141.1879176 10. Larry L. Peterson and Bruce S. Davie. 2011. Computer Networks, Fifth Edition: A Systems Approach (5th ed.), Chapters 1,5,7,9. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.

1 0

Brian Matejek will present his MSE thesis "Learning Global Features for Neuron Reconstruction in EM Images" today, March 4, 2016 at 4:30pm in CS 401
by Nicki Gotsis 04 May '16

04 May '16

Brian Matejek will present his MSE thesis "Learning Global Features for Neuron Reconstruction in EM Images" today, March 4, 2016 at 4:30pm in CS 401. Tom Funkhouser (adviser) and Sebastian Seung are his committee members. All are welcome to join. Please see thesis title and abstract below. Title: Learning Global Features for Neuron Reconstruction in EM Images Abstract: Connectomics, the study of the neural connections, has gained significant attention in the neuroscience community as a method to understand the complex workings of the brain. Recent advancements in neural image acquisition has created a surplus of data too expensive to manually annotate leading to an influx of automatic reconstruction methods. Most current methods employ hierarchical agglomeration techniques that focus on extracted local features. These techniques fail to utilize overall global structure of neurons and other valuable shape descriptors, leading to early errors which compound over time. This paper introduces novel global and local features for predicting merge candidates in oversegmented neural images. Testing on the SNEMI3D challenge dataset, these new features produce great improvement on traditional agglomeration algorithms.

1 0

Robert MacDavid will be presenting his MSE talk, "Enhanced Compression of Interdomain SDN Policies at Internet Exchange Points" on Thursday, May 5th, 2016 in CS 302.
by Nicki Gotsis 04 May '16

04 May '16

Robert MacDavid will be presenting his MSE talk, "Enhanced Compression of Interdomain SDN Policies at Internet Exchange Points" on Thursday, May 5th, 2016 in CS 302. The members of his committee are Jennifer Rexford (adviser) and Nick Feamster. Title and abstract are below. All are invited to attend. Title: Enhanced Compression of Interdomain SDN Policies at Internet Exchange Points Abstract Internet Exchange Points (IXPs) with Software-Defined Networking (SDN) capabilities are a promising way of shaping the future of interdomain traffic delivery on the Internet---allowing IXP participants to express flexible SDN policies on interdomain traffic. Unfortunately, it has proven difficult to compile interdomain traffic policies into forward table sizes reasonable for available commodity switches, and indeed this shows in state-of-the-art SDN-IXP implementations. To compile interdomain traffic SDN policies, available prefix routes must be factored in to ensure correctness, resulting in a forwarding table size explosion. To address the explosion problem, new compression techniques of forwarding table entries are required. In this talk, we discuss the design and analysis of such a compression technique, which allows near-optimal compilation size of SDN policies for IXPs with large numbers of participants

1 1

4:30pm Tue May 10 talk in E-Quad B205 on intersection of biological diversity and robotics
by Jennifer Rexford 03 May '16

03 May '16

> > From: "Heather L. Evans" <heathere(a)Princeton.EDU> > Subject: EE Department Seminar - Amanda Prorok - May 10th > Date: May 3, 2016 at 9:22:00 AM EDT > To: ee-seminar(a)Princeton.EDU > Reply-To: "Heather L. Evans" <heathere(a)Princeton.EDU> > > > Speaker: > Amanda Prorok, University of Pennsylvania > Title: > Diversity and Heterogeneity in Multi-Robot Systems > Day: > Tuesday, May 10, 2016 > > > Time: > 4:30on > Room: > B205, E-Quad > Host: > Prof. Peter Ramadge > > > > > > > > > Abstract: > Nature demonstrates the benefits of biological diversity with ecosystems that are resilient, adaptable, and productive over long time-spans. In robotics research, we are interested in a principled study of diversity with the aim of building on nature's inventions. In this talk, I shed light on the effects and implications of diversity and heterogeneity in multi-robot systems. I begin by displaying empirical results that stem from a collaborative positioning problem. As the need for foundational approaches becomes evident, my focus shifts to the question of how to formalize diversity. I answer this question in the context of heterogeneous robot swarms, with insights that pertain to the particular aspects of performance and security. > > Bio: > Amanda Prorok is currently a Postdoc in the General Robotics, Automation, Sensing and Perception (GRASP) Laboratory at the University of Pennsylvania, where she works with Prof. Vijay Kumar on heterogeneous robot swarms. She completed her PhD at EPFL, Switzerland, where she addressed the topic of localization with ultra-wideband sensing for large-scale, collaborative systems. Her dissertation was awarded the Asea Brown Boveri (ABB) award for the best thesis at EPFL in the fields of Computer Sciences, Automatics and Telecommunications. She was selected as an MIT Rising Star in 2015, and won a Best Paper Award at BICT 2015. > > > > > > Heather Evans > Assistant to the Chair > Department of Electrical Engineering > Princeton University > Engineering Quadrangle, B-210 > Olden Street > Princeton, NJ 08544 > (p): 609-258-7282 > (f): 609-258-0119 > heathere(a)princeton.edu <mailto:heathere@princeton.edu>

1 0

Nayana Prasad Nagendra will present her general exam on Friday, May 13, 2016 at 10am in CS 402
by Nicki Gotsis 03 May '16

03 May '16

Nayana Prasad Nagendra will present her general exam on Friday, May 13, 2016 at 10am in CS 402 The members of her committee are David August (adviser), David Wentzlaff, and Aarti Gupta. 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. For a full calendar view of all of the upcoming general exams, FPO's and Pre-FPO's, please go to the following link . HW-DSWP Abstract: Automatic parallelization by compiler is one way to better utilize multiple cores. Unfortunately, the best performing compiler techniques, such as those in the DSWP (Decoupled Software Pipelining) family of transformations, employ speculation and rely on dynamic information obtained by profiling, a technique unpopular with developers. Runtime techniques, such as Just-In-Time compilers, can address the popularity-of-profiling problem, but they are limited in the amount of dynamic information they can collect without negatively impacting overall program performance. Noting that existing processors already include structures that gather the type of information speculative thread extraction techniques need, I explore the possibility of performing thread extraction transformations in hardware and propose HW-DSWP (Hardware - DSWP) parallelization technique. The framework identifies hot loops based on the trace of backward branches, calculates dependency depth of instructions and segregates the instruction stream into critical and non-critical set which would then be executed on the main thread and additional thread respectively. Books: [1] John L. Hennessy and David A. Patterson, Computer Architecture: A Quantitative Approach (5th Edition), 2011. [2] Andrew W. Appel, Modern Compiler Implementation in ML. Cambridge University Press, 1998 Reading List: [1] G. Ottoni, R. Rangan, A. Stoler, and D. August. “Automatic Thread Extraction with Decoupled Software Pipelining”. In 38th International Symposium on Microarchitecture (MICRO), November 2005 [2] E. Raman, G. Ottoni, A. Raman, M. J. Bridges, and D. August. “Parallel-Stage Decoupled Software Pipelining”. In the International Symposium on Code Generation and Optimization (CGO), April 2008 [3] R. Rangan, N. Vachharajani, M. Vachharajani, and D. I. August. “Decoupled Software Pipelining with the Synchronization Array”. In 13th International Conference on Parallel Architectures and Compilation Techniques (PACT), September 2004 [4] A. Cristal, O. Santana, F. Cazorla, M. Galluzzi, T. Ramirez, M. Pericas, and M.Valero. “Kilo-Instruction Processors: Overcoming the Memory Wall”. IEEE Micro, 25(3), May 2005. [5] S. Srinath, B. Ilbeyi, M. Tan, G. Liu, Z. Zhang, and C. Batten, “Architectural Specialization for Inter-Iteration Loop Dependence Patterns”. In the International Symposium on Microarchitecture (MICRO), December 2014 [6] S. Campanoni, K. Brownell, S. Kanev, T. M. Jones, G.-Y. Wei, and D. Brooks, “HELIX-RC: An Architecture-Compiler Co-Design for Automatic Parallelization of Irregular Programs”. In 41st International Symposium on Computer Architecture (ISCA), June 2014. [7] V. Govindaraju, C. H. Ho, and K. Sankaralingam. “Dynamically Specialized Datapaths for Energy Efficient Computing”. In 17th International Symposium on High-Performance Computer Architecture (HPCA), 2011 [8] S. Campanoni, T. M. Jones, G. Holloway, V. J. Reddi, G. Wei, and D. Brooks. "HELIX: Automatic Parallelization of Irregular Programs for Chip Multiprocessing". In CGO, 2012. [9] J. Yang, K. Skadron, M. Soffa, and K. Whitehouse. “Feasibility of Dynamic Binary Parallelization”. In 4th USENIX conference on Hot Topics in Parallelism, 2011 [10] F. Liu, H. Ahn, S. Beard, T. Oh, and D. August, “DynaSpAM: Dynamic Spatial Architecture Mapping Using out of Order Instruction Schedules”. In 42nd International Symposium on Computer Architecture (ISCA), 2015

1 0

Colloquium Speaker: John Langford, Friday May 6, 12:30pm
by Nicole E. Wagenblast 02 May '16

02 May '16

Colloquium Speaker John Langford, Microsoft Research Friday, May 6, 12:30pm Computer Science 105 How to make an Infovore An Infovore is an information-based entity that explores the world, learns, and applies these learnings effectively. In essence: a form of weak AI. We have been working on a general-purpose infovore for making decisions using elements of contextual bandits, systems, and experts-style learning that has now been successfully deployed at large scale. I will discuss the architecture of the infovore, the key results upon which it relies, and how everything works together to enable true open-loop learning in the real world.

1 0

Olivier Savary Belanger will present his general exam Wednesday, May 11, 2016 at 10am in CS 302.
by Nicki Gotsis 02 May '16

02 May '16

Olivier Savary Belanger will present his general exam Wednesday, May 11, 2016 at 10am in CS 302. The members of his committee are Andrew Appel (adviser), Aarti Gupta, and Davis 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. Abstract: An increasing amount of software is written and proven correct in proof assistants. For example, an optimizing compiler for C, CompCert, has been developed and fully verified in Coq, an interactive theorem prover. For interactive theorem provers to become credible programming environments, their compilation pipelines must generate production quality code. Moreover, these compilation pipelines should be proven correct, lest the guarantees achieved in the interactive theorem provers will not apply to the program being run. We have begun working on a verified compiler for Coq. In addition to being formally verified to preserve semantics from end-to-end, it will include some of the optimizations which are at the heart of fast functional language compilers such as SML/NJ and the OCaml compiler. As preliminary work, I have implemented a shrink-reducer performing reductions analogous to dead-code elimination and function inlining over a CPS intermediate language, and proven it correct for a subset of the language. I will report on the performance of our implementation compared to alternatives which use impure features, and discuss the next few steps towards completing the compilation pipeline. Textbooks: - B. C. Pierce. Types and Programming Languages. ISBN 0262162091. The MIT Press, 2002 Part I (Untyped Systems) Part II (Simple Types) Part IV (Recursive Types) Part V (Polymorphism) Ch. 22-25 - B. C. Pierce. Advanced Topics in Types and Programming Languages. ISBN 0262162288. The MIT Press, 2004. Dependent Types (Ch. 2) - A. W. Appel. Compiling with Continuations. ISBN 0521416957. Cambridge University Press, 1992. Papers: - O. Danvy and A. Filinski. Representing control: a study of the CPS transformation. MSCS 1992. - A. W. Appel and T. Jim. Shrinking Lambda Expressions in Linear Time. JFP 1997. - O. Danvy and L. R. Nielsen. A first-order one-pass CPS transformation. TCS 2003 - P. Letouzey. A New Extraction for Coq. TYPES 2002. - A. Kennedy. Compiling with continuations, continued. ICFP 2007. - R. Kumar et al. CakeML: A Verified Implementation of ML. POPL 2014

1 0

Nora Willett will be presenting her general exam on Tuesday, May 10, 2016 at 10am in CS 402.
by Nicki Gotsis 02 May '16

02 May '16

Nora Willett will be presenting her general exam on Tuesday, May 10, 2016 at 10am in CS 402. The members of her committee are Adam Finkelstein (adviser), Tom Funkhouser, and Szymon Rusinkiewicz. 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: When bringing animated characters to life, artists often augment the primary motion of a character by adding secondary animation such as wrinkling cloth, jiggling bulges, or hair and leaves blown by wind. Such effects can often be achieved for 3D animation through physical simulation. However, 2D animations typically lack sufficient information about the structure of the characters to support such simulations. Animators therefore can only add secondary motion to animated illustrations through arduous manual effort. This paper presents a set of physically-inspired building blocks that attach to layered, illustrated characters in order to propagate motion in a way that produces controllable, composable secondary animation. These components can be easily rigged and controlled via a small number of parameters that produce an expressive range of effects. Our approach supports a wide range of the most common secondary effects, which we demonstrate with an assortment of characters of varying complexity. reading list: 1. A. Jacobson, I. Baran, J. Popovic, and O. Sorkine. Bounded biharmonic weights for real-time deformation. *ACM Trans. Graph*., 30(4):78, 2011. 2. A. Rivers, T. Igarashi, and F. Durand. 2.5 d cartoon models. In *ACM Transactions on Graphics (TOG)*, volume 29, page 59. ACM, 2010. 3. S. C. Hsu and I. H. Lee. Drawing and animation using skeletal strokes. In *Proceedings of the 21st annual conference on Computer graphics and interactive techniques*, pages 109–118. ACM, 1994. 4. S. Chenney, M. Pingel, R. Iverson, and M. Szymanski. Simulating cartoon style animation. In *Proceedings of the 2nd international symposium on Nonphotorealistic animation and rendering*, pages 133– 138. ACM, 2002. 5. R. Barzel, J. R. Hughes, and D. N. Wood. Plausible motion simulation for computer graphics animation. In *Computer Animation and Simulation’96*, pages 183–197. Springer, 1996. 6. R. Barzel. Faking dynamics of ropes and springs. *IEEE Computer Graphics and Applications*, (3):31– 39, 1997. 7. R. Barzel and A. H. Barr. A modeling system based on dynamic constraints. In *ACM SIGGRAPH Computer Graphics*, volume 22, pages 179–188. ACM, 1988. 8. R. C. Davis, B. Colwell, and J. A. Landay. K-sketch: a ’kinetic’ sketch pad for novice animators. In *Proceedings of the SIGCHI Conference on Human Factors in Computing Systems*, pages 413–422. ACM, 2008. 9. R. H. Kazi, F. Chevalier, T. Grossman, and G. Fitzmaurice. Kitty: sketching dynamic and interactive illustrations. In *Proceedings of the 27th annual ACM symposium on User interface software and technology*, pages 395–405. ACM, 2014. 10. P. Shirley, M. Ashikhmin, and S. Marschner. Fundamentals of computer graphics. *CRC Press*, 2009.

1 0