April 2015 - talks - lists.cs.princeton.edu

rescheduled: Qian Zhu will present his Pre-FPO May 8, 2015 in rm 401 at 9:30am
by Nicki Gotsis 30 Apr '15

30 Apr '15

Qian Zhu will present his Pre-FPO May 8, 2015 in rm 401 at 10am. The members of his committee are: Olga Troyanskaya (adviser), Mona Singh, Kai Li, Andrea LaPaugh, 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 2

Jonathan Balkind will present his General Exam on May 7, 2015 at 10am in CS 301.
by Nicki Gotsis 30 Apr '15

30 Apr '15

Jonathan Balkind will present his General Exam on May 7, 2015 at 10am in CS 301. The members of his/her committee are David Wentzlaff (advisor), David Walker, and David 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. Title: "META: The Multicore Effect-Tracking Architecture" Abstract: Modern processors from smartphones to servers are seeing higher core counts in order to take advantage of increasing silicon area while reducing the processors' overall energy consumption. Unfortunately, parallelising code across general purpose cores generally imposes a software overhead which makes only larger blocks of code worthwhile to parallelise. With META, we make the observation that many functions only read and write (or have effects) to a pre-defined subset of an application's memory space. Based on this, we believe that architectural awareness of functions' effects can provide a low-overhead mechanism for parallelising existing code. META can enable the offload of fine-grain functions such as memory copies and I/O operations which would otherwise sit on the critical execution path of the main, energy intensive core. With suitable programming language and operating system support, META can bring higher level abstractions such as futures, callbacks, and work queues to the hardware level, thus reducing OS and/or runtime overheads. We evaluate the potential energy and performance improvements of META using a software simulator and implement some of the hardware structures in verilog RTL to determine the area requirements and complexity of the proposed design. Reading list: Dynamic memory disambiguation using the memory conflict buffer. David M. Gallagher, William Y. Chen, Scott A. Mahlke, John C. Gyllenhaal, and Wen-mei W. Hwu. 1994. In Proceedings of the sixth international conference on Architectural support for programming languages and operating systems (ASPLOS VI). ACM, New York, NY, USA, 183-193. DOI=10.1145/195473.195534 http://doi.acm.org/10.1145/195473.195534 Mondrian memory protection. Emmett Witchel, Josh Cates, and Krste Asanović. 2002. In Proceedings of the 10th international conference on Architectural support for programming languages and operating systems (ASPLOS X). ACM, New York, NY, USA, 304-316. DOI=10.1145/605397.605429 http://doi.acm.org/10.1145/605397.605429 Cilk: an efficient multithreaded runtime system. Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, and Yuli Zhou. 1995. In Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming (PPOPP '95), Richard L. Wexelblat (Ed.). ACM, New York, NY, USA, 207-216. DOI=10.1145/209936.209958 http://doi.acm.org/10.1145/209936.209958 Transactional memory: architectural support for lock-free data structures. Maurice Herlihy and J. Eliot B. Moss. 1993. In Proceedings of the 20th annual international symposium on computer architecture (ISCA '93). ACM, New York, NY, USA, 289-300. DOI=10.1145/165123.165164 http://doi.acm.org/10.1145/165123.165164 The CHERI capability model: revisiting RISC in an age of risk. Jonathan Woodruff, Robert N.M. Watson, David Chisnall, Simon W. Moore, Jonathan Anderson, Brooks Davis, Ben Laurie, Peter G. Neumann, Robert Norton, and Michael Roe. 2014. In Proceeding of the 41st annual international symposium on Computer architecuture (ISCA '14). IEEE Press, Piscataway, NJ, USA, 457-468. Cyclone: A Safe Dialect of C, Trevor Jim, Greg Morrisett, Dan Grossman, Michael Hicks, James Cheney, and Yanling Wang. USENIX Annual Technical Conference, pages 275–288, Monterey, CA, June 2002. Tagged Memory and Minion Cores in the lowRISC SoC. Alex Bradbury, Gavin Ferris, and Robert Mullins. Memo. Computer Laboratory, University of Cambridge, December 2014. Idempotent processor architecture. Marc de Kruijf and Karthikeyan Sankaralingam. 2011. In Proceedings of the 44th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-44). ACM, New York, NY, USA, 140-151. DOI=10.1145/2155620.2155637 http://doi.acm.org/10.1145/2155620.2155637 A case for unlimited watchpoints. Joseph L. Greathouse, Hongyi Xin, Yixin Luo, and Todd Austin. 2012. In Proceedings of the seventeenth international conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS XVII). ACM, New York, NY, USA, 159-172. DOI=10.1145/2150976.2150994 http://doi.acm.org/10.1145/2150976.2150994 Dataflow execution of sequential imperative programs on multicore architectures. Gagan Gupta and Gurindar S. Sohi. 2011. In Proceedings of the 44th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-44). ACM, New York, NY, USA, 59-70. DOI=10.1145/2155620.2155628 http://doi.acm.org/10.1145/2155620.2155628 Task Superscalar: An Out-of-Order Task Pipeline. Yoav Etsion, Felipe Cabarcas, Alejandro Rico, Alex Ramirez, Rosa M. Badia, Eduard Ayguade, Jesus Labarta, and Mateo Valero. 2010. In Proceedings of the 2010 43rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO '43). IEEE Computer Society, Washington, DC, USA, 89-100. DOI=10.1109/MICRO.2010.13 http://dx.doi.org/10.1109/MICRO.2010.13 A dependency-aware task-based programming environment for multi-core architectures. Perez, J.M.; Badia, R.M.; Labarta, J., Cluster Computing, 2008 IEEE International Conference on , vol., no., pp.142,151, Sept. 29 2008-Oct. 1 2008. DOI=10.1109/CLUSTR.2008.4663765 http://dx.doi.org/10.1109/CLUSTR.2008.4663765

1 0

Haoyu Zhang will present his General Exam on May 7, 2015 at 10am in CS 401
by Nicki Gotsis 30 Apr '15

30 Apr '15

Haoyu Zhang will present his General Exam on May 7, 2015 at 10am in CS 401. The members of his committee are Mike Freedman (Advisor), Jen Rexford, and Nick Feamster. 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 > Software-defined networking (SDN) offer greater flexibility than > traditional distributed network architectures, at the risk of the > controller being a single point-of-failure. Unfortunately, existing > fault-tolerance techniques, such as replicated state machine, are > insufficient to ensure correct network behavior under controller > failures. The challenge is that, in addition to the application state of > the controllers, the switches maintain hard state that must be handled > consistently. Thus, it is necessary to incorporate switch state into the > system model to correctly offer a "logically centralized" controller. > > We introduce Ravana, a fault-tolerant SDN controller platform that > processes the control messages transactionally and exactly once (at both > the controllers and the switches). Ravana maintains these guarantees in > the face of both controller and switch crashes. The key insight in > Ravana is that replicated state machines can be extended with > lightweight switch-side mechanisms to guarantee correctness, without > involving the switches in an elaborate consensus protocol. Our prototype > implementation of Ravana provides transparent fault tolerance: > controller applications can run on Ravana without modifying a single > line of code. Experiments show that Ravana achieves high throughput with > reasonable overhead, compared to a single controller, with a failover > time under 100ms. We also use verification tools to prove Ravana's > correctness under controller failures. Reading List > [1] J. H. Saltzer and M. F. Kaashoek, Principles of Computer System > Design: An Introduction. Morgan Kaufmann Publishers Inc., 2009. > > [2] L. Lamport, “Time, Clocks, and the Ordering of Events in a > Distributed System,” Commun. ACM, July 1978. > > [3] M. Rosenblum and J. K. Ousterhout, “The Design and Implementation > of a Log-structured File System,” ACM Trans. Comput. Syst., Feb. 1992. > > [4] B. Liskov and J. Cowling, “Viewstamped Replication Revisited,” > tech. rep., MIT, July 2012. > > [5] D. B. Terry, M. M. Theimer, K. Petersen, A. J. Demers, M. J. > Spreitzer, and C. H. Hauser, “Managing Update Conflicts in Bayou, a > Weakly Connected Replicated Storage System,” in SOSP, Dec. 1995. > > [6] W. Lloyd, M. J. Freedman, M. Kaminsky, and D. G. Andersen, “Don’T > Settle for Eventual: Scalable Causal Consistency for Wide-area Storage > with COPS,” in SOSP, Oct. 2011. > > [7] D. Ongaro and J. Ousterhout, “In Search of an Understandable > Consensus Algorithm,” in USENIX ATC, June 2014. > > [8] J. C. Corbett, J. Dean, M. Epstein, A. Fikes, C. Frost, J. J. > Furman, S. Ghemawat, A. Gubarev, C. Heiser, P. Hochschild, W. Hsieh, > S. Kanthak, E. Kogan, H. Li, A. Lloyd, S. Melnik, D. Mwaura, D. Nagle, > S. Quinlan, R. Rao, L. Rolig, Y. Saito, M. Szymaniak, C. Taylor, R. > Wang, and D. Woodford, “Spanner: Google’s Globally-distributed > Database,” in OSDI, Oct. 2012. > > [9] M. Casado, M. J. Freedman, J. Pettit, J. Luo, N. Gude, N. McKeown, > and S. Shenker, “Rethinking Enterprise Network Control,” IEEE/ACM > Trans. Netw., Aug. 2009. > > [10] T. Koponen, M. Casado, N. Gude, J. Stribling, L. Poutievski, M. > Zhu, R. Ramanathan, Y. Iwata, H. Inoue, T. Hama, and S. Shenker, > “Onix: A Distributed Control Platform for Large-scale Production > Networks,” in OSDI, 2010. > > [11] E. B. Nightingale, K. Veeraraghavan, P. M. Chen, and J. Flinn, > “Rethink the Sync,” in OSDI, Nov. 2006.

1 0

Jonathan Schneider will present his Generals on May 6, 2015 at 2pm in CS 302
by Nicki Gotsis 30 Apr '15

30 Apr '15

Jonathan Schneider will present his Generals on May 6, 2015 at 2pm in CS 302. The members of his committee are Mark Braverman (advisor), Sanjeev Arora, and Zeev Dvir. Everyone is invited to attend his/her 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 information complexity of a function f is the minimum amount of information Alice and Bob need to exchange to compute the function f. In this talk, I will describe joint work with Mark Braverman where we provide an algorithm for approximating the information complexity of an arbitrary function f to within any additive error α>0, thus resolving an open question as to whether information complexity is computable. In the process, we give the first explicit upper bound on the rate of convergence of the information complexity of f when restricted to b-bit protocols to the (unrestricted) information complexity of f. Reading List : 1. Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach. 2. Thomas Cover, Joy Thomas. Elements of Information Theory. 3. Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to compress interactive communication. 4. Mark Braverman, Ankit Garg, Denis Pankratov, and Omri Weinstein. From information to exact communication. 5. Mark Braverman and Anup Rao. Information equals amortized communication 6. M. Karchmer and A. Wigderson. Monotone circuits for connectivity require superlogarithmic depth. 7. Anat Ganor, Gillat Kol, Ran Raz. Exponential separation of Information and Communication. 8. Rahul Jain. New strong direct product results in communication complexity 9. Ran Raz. A parallel repetition theorem. 10. Mark Braverman and Anup Rao. Towards coding for maximum errors in interactive communication. 11. Zvika Brakerski and Yael Tauman Kalai. Efficient interactive coding against adversarial noise. 12. Gillat Kol, Ran Raz. Interactive Channel Capacity.

1 0

Young Kun Ko will present his Generals April 29, 2015 at 2pm in CS 302
by Nicki Gotsis 29 Apr '15

29 Apr '15

Young Kun Ko will present his Generals on April 29, 2015 at 2pm in CS 302. The members of his committee are: Mark Braverman (adviser), Zeev Dvir, and Elad Hazan 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 The celebrated PPAD hardness result for finding an exact Nash equilibrium in a two-player game initiated a quest for finding approximate Nash equilibria efficiently, and is one of the major open questions in algorithmic game theory. We study the computational complexity of finding an ε-approximate Nash equilibrium with good social welfare. Hazan and Krauthgamer and subsequent improvements showed that finding an ε-approximate Nash equilibrium with good social welfare in a two player game and many variants of this problem is at least as hard as finding a planted clique of size O(log n) in the random graph G(n, 1/2). We show that any polynomial time algorithm that finds an ε-approximate Nash equilibrium with good social welfare refutes (the worst-case) Exponential Time Hypothesis by Impagliazzo and Paturi, confirming the recent conjecture by Aaronson, Impagliazzo and Moshkovitz. Specifically, it would imply a 2O˜(n1/2) algorithm for SAT. Our lower bound matches the quasi-polynomial time algorithm by Lipton, Markakis and Mehta for solving the problem. Reading List Textbooks • Computational Complexity (Arora & Barak) Papers • How hard is it to approximate the best Nash Equilibrium? by Elad Hazan and Robert Krauthgamer • Inapproximability of NP-complete variants of Nash equilibrium by Per Austrin, Mark Braverman, Eden Chlamtac • Playing large games using simple strategies by Richard J. Lipton, Evangelos Markakis, and Aranyak Mehta • AM with multiple Merlins by Scott Aaronson, Russell Impagliazzo, and Dana Moshkovitz • Quantum de finetti theorems under local measurements with applications by Fernando G. S. L. Brandao and Aram Harrow • Interactive proofs and the hardness of approximating cliques by Uriel Feige, Shafi Goldwasser, Laszlo Lovasz, Shmuel Safra, and Mario Szegedy • Inapproximability of densest k-subgraph from average case hardness by Noga Alon, Sanjeev Arora, Rajsekar Manokaran, Dana Moshkovitz, and Omri Weinstein • Graph expansion and the unique games conjecture by Prasad Raghavendra and David Steurer • Finding endogenously formed communities by Maria-Florina Balcan, Christian Borgs, Mark Braverman, Jennifer Chayes, and Shang-Hua Teng • The PCP theorem by gap amplification by Irit Dinur _______________________________________________ talks mailing list talks(a)lists.cs.princeton.edu To edit subscription settings or remove yourself, use this link: https://lists.cs.princeton.edu/mailman/listinfo/talks

1 0

Colloquium Speaker Scott Aaronson Wed April 29, 12:30pm
by Nicole E. Wagenblast 29 Apr '15

29 Apr '15

Colloquium Speaker Scott Aaronson, MIT Wednesday, April 29, 12:30pm Computer Science 105 Exploring the Limits of the Efficiently Computable I'll give a broad overview of my research over the last decade aimed at understanding the relationship between computational complexity and physics -- and in particular, the capabilities and limitations of quantum computers. Possible topics, depending on time, will include the BosonSampling model of quantum computing, creating unforgeable 'quantum money' using hidden subspaces, quantum computing versus the polynomial-time hierarchy, maximal separations between classical and quantum query complexity, the need for structure in quantum speedups, and the computational complexity of decoding Hawking radiation. Scott Aaronson is an Associate Professor of Electrical Engineering and Computer Science at MIT. He studied at Cornell and UC Berkeley, and did postdocs at the Institute for Advanced Study as well as the University of Waterloo. His research focuses on the capabilities and limitsof quantum computers, and more generally on computational complexity and its relationship to physics. His first book, Quantum Computing Since Democritus, was published in 2013 by Cambridge University Press. Aaronson has written about quantum computing for Scientific American and the New York Times, and writes a popular blog. He’s received the National Science Foundation’s Alan T. Waterman Award, the United States PECASE Award, and MIT's Junior Bose Award for Excellence in Teaching.

1 1

Quan Zhu will present his Pre-FPO May 8, 2015 in rm 401 at 9:30am (rescheduled)
by Nicki Gotsis 28 Apr '15

28 Apr '15

Quan Zhu will present his Pre-FPO May 8, 2015 in rm 401 at 10am. The members of his committee are: Olga Troyanskaya (adviser), Mona Singh, Kai Li, Andrea LaPaugh, 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 0

Kelvin Zou will present his General Exam April 29th at 12pm in CS 401
by Nicki Gotsis 27 Apr '15

27 Apr '15

Kelvin Zou will present his General Exam April 29th at 12:00pm in CS 401. His committee is as follows: Jen Rexford (Adviser), Mike Freedman, and Nick Feamster. 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: Middleboxes, or network functions are at once an abomination (a violation of the end-to-end argument) and a necessity (for deploying higher-level network services between endpoints). We may apply different types of network functions to certain traffic in a certain order (service chaining), and change the service chain dynamically (dynamic service chaining), to both enhance performance and improve security. Current techniques for (dynamic) service chaining rely on manipulating how the network switches route traffic. However, tweaking the routing configuration is clumsy and inefficient, mainly because the network switches have limited forwarding table size for fine-grained policies and high routing-update latencies, ad it requires the administrators to control the whole network. Instead, we propose a NF-aware architecture that makes network functions an explicit part of the end-to-end path, and thus facilitates configuring and reconfiguring service chains. The key insight of the architecture is that an end-to-end session, which we call supersession, is split into subsessions between NFs, and between an endpoint and an NF. The supersession-subsession abstraction allows us to design a simple protocol for handling (dynamic) service chaining that offer richer order-preservation semantics than routing solutions. For instance, when reconfiguring service chains for a certain supersession, the protocols can guarantee that any TCP byte sequence is processed either in the new or in the old chain, but not in both. We implemented and evaluated the protocols in a Linux system that can host a wide range of network functions, and show that the reconfiguration is 10x faster than in routing-based solutions. We also show that the overhead incurred by the architecture is negligible and that flows can be processed at line speed by NF hosts in a 40 Gbps network. Reading list: testbook Computer Networks, A system approach, Larry Peterson and Bruce Davie. Papers: Improving TCP/IP Performance over Wireless Networks (TCP proxy) An End-to-End Approach to Host Mobility (TCP Migrate) END-TO-END ARGUMENTS IN SYSTEM DESIGN (end-to-end argument) Serval: An End-Host Stack for Service-Centric Networking (Mobility protocol) Middleboxes No Longer Considered Harmful (Middlebox protocol/architecture) Design and Implementation of a Consolidated Middlebox Architecture OpenNF: Enabling Innovation in Network Function Control Split/Merge: System Support for Elastic Execution in Virtual Middleboxes SIMPLE-fying Middlebox Policy Enforcement Using SDN FlowTags: Enforcing Network-Wide Policies in the Presence of Dynamic Middlebox Actions

1 2

Maciej Halber will present his Generals on 5/1/15 at 3pm in 301.
by Nicki Gotsis 27 Apr '15

27 Apr '15

Maciej Halber will present his Generals on 5/1/15 at 3pm in 301. The members of his committee are: Thomas A. Funkhouser (Adviser), Adam Finkelstein, and Jianxiong Xiao. 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: Urban reconstruction is a long-standing and challenging task in computer graphics and vision. In this project we explore ways of producing texture images needed for producing virtual representation of cities. Given a large dataset of street-side images and accompanying LiDaR data, the goal is to be able to generate high quality facade textures - images depicting building facades that are both globally correct (underlying structure of a facade is preserved) and free of local artifacts (such as seams). The challenge comes from a many undesirable properties of such datasets - buildings are in most cases not observed from fronto-parallel views, are often partially-occluded and, especially for tall buildings, they might not be completely captured in any of the input images. In this work we present a system designed to deal with such issues. Presented system first detects simple planar geometry from LiDaR data, followed by a two stage synthesis process. Street-side images are first merged using per pixel quality metric, computed from geometrical relationship between camera and the detected plane. Initial merges are then combined and refined in the second stage to generate a plausible completion of unknown, unobserved parts of the facade. This is achieved using a state-of-the-art texture synthesis approach, where the optimized distance function considers not only the local color properties, but also leverages information about input image quality and underlying structure of a facade. Reading list: 1. Fundametals of Computer Graphics; Peter Shirley; Steve Marschner Publisher: A K Peters/CRC Press; 3rd edition (July 21, 2009) ISBN-10: 1568814690 ISBN-13: 978-1568814698 2. State of the Art in Example-based Texture Synthesis; Wei, Li-Yi and Lefebvre, Sylvain and Kwatra, Vivek and Turk, Greg; Eurographics 2009 3. A Survey of Urban Reconstruction; Przemyslaw Musialski, Peter Wonka, Daniel G. Aliaga, Michael Wimmer, Luc van Gool, Werner Purgathofer; Computer Graphics Forum 2013 4. Region Filling and Object Removal by Exemplar-based Image Inpainting; Criminisi, A. and Perez, P. and Toyama, K.; Trans. Img. Proc. 2004 5. Texture Optimization for Example-based Synthesis; Vivek Kwatra and Irfan Essa and Aaron Bobick and Nipun Kwatra; ACM Transactions on Graphics, SIGGRAPH 2005 6. PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing; Connelly Barnes and Eli Shechtman and Adam Finkelstein and Dan B Goldman; ACM Transactions on Graphics (Proc. SIGGRAPH); 2009; 7. Space-Time Completion of Video; Wexler, Yonatan and Shechtman, Eli and Irani, Michal; IEEE Trans. Pattern Anal. Mach. Intell. 2007; 8. Image Melding: Combining Inconsistent Images using Patch-based Synthesis; Soheil Darabi and Eli Shechtman and Connelly Barnes and Dan B Goldman and Pradeep Sen; ACM Transactions on Graphics (TOG) (Proceedings of SIGGRAPH 2012); 9. Image Completion using Planar Structure Guidance; Jia-Bin Huang, Sing Bing Kang, Narendra Ahuja, and Johannes Kopf; ACM Transactions on Graphics (Proceedings of SIGGRAPH 2014); 10. Symmetry - Guided texture Synthesis and Manipulation; Vladimir G. Kim and Yaron Lipman and Thomas Funkhouser; ACM Transactions on Graphics 2012; 11 .Transformation Guided Image Completion; Huang, J-. B. and Kopf, J. and Ahuja, N. and Kang, S. B.; International Conference on Computational Photography 2013; 12. Image-based Street-side City Modeling; Xiao, Jianxiong and Fang, Tian and Zhao, Peng and Lhuillier, Maxime and Quan, Long; ACM Transactions on Graphics 2009; 13. Interactive Multi-View Facade Image Editing; Przemyslaw Musialski and Christian Luksch and Michael Schwarzler and Matthias Buchetics and Stefan Maierhofer and Werner Purgathofer; Vision, Modeling and Visualization Workshop 2010; 14. Semantic Decomposition and Reconstruction of Residential Scenes from LiDAR Data; Lin, Hui and Gao, Jizhou and Zhou, Yu and Lu, Guiliang and Ye, Mao and Zhang, Chenxi and Liu, Ligang and Yang, Ruigang; ACM Transactions on Graphics, (Proc. of SIGGRAPH 2013)

1 0

Elena Sizikova will present her Generals on 5/30/15 at 9am in CS 402
by Nicki Gotsis 24 Apr '15

24 Apr '15

Elena Sizikova will present her Generals on 5/30/15 at 9am in CS 402. The members of her committee are: Tom Funkhouser (adviser), Adam Finkelstein, and Mona Singh. 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: Many problems in computer graphics require processing sets of partially wrong pairwise measurements to find a globally optimal arrangement. One such example arises from research on reconstruction of ancient Theran frescos, in which scans of partially eroded fragments were obtained in an effort to automate the reconstruction process. Previously, algorithms were developed to propose potential pairwise matches between adjacent fragments, but the majority of the resulting matches are false predictions. In this work, I explore a genetic algorithm based approach that includes a robust global relaxation step to both recover clusters of correctly and consistently aligned fragments and to detect and discard predicted matches that are false. Reading List: 1 Computer Graphics with OpenGL, 4th Ed., Hearn, Baker, and Carithers. Prentice Hall, 2010. 2 Antonio Garcia Castaneda,Benedict Brown, Szymon Rusinkiewicz, Thomas Funkhouser, and Tim Weyrich. Global Consistency in the Automatic Assembly of Fragmented Artefacts. Intl. Symposium on Virtual Reality, Archaeology and Cultural Heritage (VAST) (Oct. 2011). 3 JF. Kleber and R. Sablatnig. 2009. A Survey of Techniques for Document and Archaeology Artefact Reconstruction. In Document Analysis and Recognition, 2009. ICDAR ’09. 4 A.R. Willis and D.B. Cooper. 2008. Computational reconstruction of ancient artifacts. Signal Processing Magazine, IEEE 25, 4(July 2008), 65–83. 5 P.J. Besl, H.-D. McKay: A method for registration of 3-D shapes, Pattern Analysis and Machine Intelligence, 1992. 6 S. Rusinkiewicz, M. Levoy. Efficient Variants of the ICP Algorithm. 3D Imaging and Modeling, 2001. 7 A. Singer. 2011. Angular synchronization by eigenvectors and semidefinite programming. Applied and Computational Harmonic Analysis 30, 1 (2011), 20 – 36. 8 K. N. Chaudhury, Y. Khoo, A. Singer. Global Registration of Multiple Point Clouds Using Semidefinite Programming. SIAM Journal on Optimization. 9 O. Özyeşil, A. Singer, R. Basri, "Stable Camera Motion Estimation using Convex Programming”, SIAM Journal on Imaging Sciences. 10 Peter Henry, Michael Krainin, Evan Herbst, Xiaofeng Ren, Dieter Fox, "RGB-D mapping: Using depth cameras for dense 3D modeling of indoor environments, ISER, 2010.

1 1