- talks - lists.cs.princeton.edu

Omri Weinstein will present his pre-FPO Sept 16, 2014 at 11am in CS Room 401 (Title: Interactive Information Complexity and Applications)
by Nicki Gotsis 11 Sep '14

11 Sep '14

Omri Weinstein will present his pre-FPO on September 16, 2014 at 11am in CS Room 401. The members of his committee are: Mark Braverman, advisor; Anup Rao(University of Washington), reader; Zeev Dvir, reader; Sanjeev Arora, non-reader; Michael Saks(Rutgers), non-reader. Everyone is invited to attend his talk. The talk title and abstract follow below: Title: Interactive Information Complexity and Applications Abstract: ======= Few models in the history of theoretical computer science have affected the field in so many ways as profoundly as communication complexity. With applications in nearly every area of computer science, this model constitutes one of the few known techniques for proving unconditional lower bounds - the holy grail of complexity theory. Developing tools in communication complexity is therefore a promising approach for making progress in other computational models such as streaming, property testing, distributed computing, circuit complexity and data structures. One striking example of such tool is information theory, introduced by Shannon in the late 1940's in the context of the one way data transmission problem. Shannon's work revealed the intimate connection between information and communication, namely, that the amortized transmission cost of a random message is equal to the amount of information it contains. Classical information theory, however, does not readily convert to interactive setups, where two (or more) parties must engage in a multi-round conversation in order to accomplish a desirable task. The goal of our ongoing research is to extend this theory, develop the right tools, and understand how information behaves in interactive setups, such as the communication complexity model. Our main measure if interest is the Information Complexity of a function, which informally captures the least amount of information the parties need to disclose each other about their inputs in order to solve the underlying task. We demonstrate the broad power of this theory via applications to communication complexity, data streaming, circuit lower bounds, privacy and economics. In particular, I will discuss how information complexity helped us make progress on some of the most fundamental questions in communication complexity, including the limits of parallel computation, interactive compression, and the KRW conjecture.

1 0

Fwd: EE SEMINAR : Thursday September 18th, 4:30pm, E-Quad B205- Aryeh Kontorovich-Good Margins Make Good Neighbors
by Jennifer Rexford 10 Sep '14

10 Sep '14

An EE seminar that may be of interest to folks in CS, too... Begin forwarded message: > From: "Lisa R. Lewis" <ll2(a)Princeton.EDU> > Subject: EE SEMINAR : Thursday September 18th, 4:30pm, E-Quad B205- Aryeh Kontorovich-Good Margins Make Good Neighbors > Date: September 10, 2014 at 10:29:06 AM EDT > To: ee-seminar(a)Princeton.EDU > Reply-To: "Lisa R. Lewis" <ll2(a)Princeton.EDU> > > > > > DEPARTMENT OF > ELECTRICAL ENGINEERING > SEMINAR SERIES > > > > > Speaker: Dr. Aryeh Kontorovich > Ben-Gurion University of the Negev > Title: Good Margins Make Good Neighbors > Date: Thursday, September 18, 2014 > Time: 4:30 p.m. > Room: E-Quad, B205 > Host: Prof. Sergio Verdu > > > Abstract: Although well-known by practitioners to be an effective classification tool, nearest-neighbor methods have been somewhat neglected by learning theory of late. The goal of this talk is to revive interest in this time-tested technique by recasting it in a modern perspective. We will present a paradigm of margin-regularized 1-nearest neighbor classification which: (i) is Bayes-consistent (ii) yields simple, usable finite-sample error bounds (iii) provides for very efficient algorithms with a principled speed-accuracy tradeoff (iv) allows for near-optimal sample compression. Further extensions include multiclass, regression, and metric dimensionality reduction. I will argue that the regularized 1-nearest neighbor is superior to k-nearest neighbors in several crucial statistical and computational aspects. > > Based on a series of works with: Lee-Ad Gottlieb, Robert Krauthgamer, Roi Weiss > > > > Bio: Aryeh Kontorovich received his undergraduate degree in mathematics with a certificate in applied mathematics from Princeton University in 2001. His M.Sc. and Ph.D. are from Carnegie Mellon University, where he graduated in 2007. After a postdoctoral fellowship at the Weizmann Institute of Science, he joined the Computer Science department at Ben-Gurion University of the Negev in 2009 as an assistant professor; this is his current position. His research interests are mainly in machine learning, with a focus on probability, statistics, automata theory and metric spaces. > >

1 0

2-3pm Fri Aug 29 talk on scaling social search
by Jennifer Rexford 29 Aug '14

29 Aug '14

Speaker: Siddhartha Bannerjee Title: Scaling Social Search - PageRank Estimation for Large Networks When and Where: 29th August (Friday) at 2:00 PM in Room 402 in the CS bldg. Abstract: Although effective search is one of the great successes of the internet, social search lags far behind. A major hurdle is the complexity of existing algorithms for estimating Personalized PageRank -- a generalization of PageRank which measures centrality with respect to a fixed node in a network. In particular, to estimate PageRank values up to the required accuracies, existing algorithms need time which scales linearly in the network size -- this renders them infeasible for real-time social search. In this talk, I will present FAST-PPR, the first algorithm for Personalized PageRank estimation with an average running-time guarantee which is sublinear in the network size. This speedup is achieved via a combination of linear algebraic techniques and random walks; this new approach may prove useful in other estimation problems on networks. Moreover, I'll present detailed empirical studies on numerous large networks, wherein FAST-PPR dramatically outperforms existing algorithms -- for example, with target nodes sampled according to popularity, on the 2010 Twitter graph with 1.5 billion edges, FAST-PPR has a 160 factor speedup compared to the state-of-the-art. Joint work with Peter Lofgren, Ashish Goel and C. Seshadri. Paper available at http://arxiv.org/abs/1404.3181.

1 1

talk on Tilera processor architecture, Sept 11 4:30 pm, E-Quad B205 - Matthew Mattina
by Jennifer Rexford 18 Aug '14

18 Aug '14

> > > Speaker: Matthew Mattina > Tilera > Title: Architecture and Performance of the TILE-Gx72 ManyCore Processor > Date: Thursday, September 11, 2014 > Time: 4:30 p.m. > Room: E-Quad, Room B205 > Host: Prof. David Wentzlaff > > Abstract: This talk describes the Tilera TILE-Gx processor architecture, discusses the design choices that result in high throughput performance and power-efficiency, and presents performance results on representative applications for the 72-core TILE-Gx72, the flagship processor in Tilera's TILE-Gx family. This processor family is comprised of a series of high-performance, low-power 64-bit manycore processor SoCs, tightly coupled with high performance packet processing. These highly integrated processors deliver industry-leading performance and performance-per-watt in the embedded networking, cyber security, and high throughput computing markets. Of particular interest is the iMesh network-on-chip, which scales to 100s of cores and provides high-speed interconnection of all on-die elements and cache coherence across the chip. > > Biography: Mr. Mattina is the Chief Technology Officer at Tilera and is responsible for overall processor strategy and technology. As processor architect at Tilera, he co-led the design of the 64-core TILE-Pro, and the 9- to 72-core TILE-Gx processor families. Prior to Tilera, Mr. Mattina was with Intel Corporation where he was co-lead architect for the Tukwila Multicore Processor, supervising a team of architects and designers. At Intel, Mr. Mattina invented and designed the Intel Ring Uncore Architecture, used across Intel's x86 multicore processor designs. This technology won the Intel Achievement Award in 2010. Prior to Intel, he was an architect and circuit design engineer at Digital Equipment Corporation, working on the Alpha EV7 and EV8 processors. Mr. Mattina also served as Technical Leader at Cisco Systems in the TelePresence Infrastructure Business Unit, where he contributed to the hardware and software design of next-generation high-definition video conferencing products. He has been granted over 20 patents and has published journal and conference papers relating to CPU design, multicore processors, and cache coherence protocols. Mr. Mattina holds a BS in Computer and Systems Engineering from Rensselaer Polytechnic Institute and a MS in Electrical Engineering from Princeton University.

1 0

FPO: August 12, 2014, at 10am in CS 402 (Yuri Pritykin)
by Nicki Gotsis 05 Aug '14

05 Aug '14

Yuri Pritykin will present his FPO on Tuesday, August 12, 2014 at 10am in CS 402. The members of his committee are Mona Singh, advisor; Bernard Chazelle and Olga Troyanskaya, readers; Andrea LaPaugh and Vivek Pai, non-readers. A copy of his/her thesis, is available in Room 310. Everyone is invited to attend his/her talk. Nicki Gotsis Graduate Coordinator Room 310, Computer Science (609) 258-5387 ngotsis(a)cs.princeton.edu

1 0

Huy Nguyen will present his FPO on Monday, 7/14/2014 at 11AM, 402 Computer Science Building.
by Nicki Gotsis 08 Jul '14

08 Jul '14

Huy Nguyen will present his FPO on Monday, 7/14/2014 at 11AM, 402 Computer Science Building. The members of his committee are Moses Charikar (advisor), Bernard Chazelle and Piotr Indyk, MIT (readers), and Sanjeev Arora and Mark Braverman (non-readers). A copy of his thesis, is available in Room 310. Everyone is invited to attend his/her talk.

1 0

Today 4:30-5:30: Deep Learning in Detection and Recognition
by Jianxiong Xiao 02 Jul '14

02 Jul '14

Speaker: Xiaogang Wang Room: CS 402 Time: July 2nd Wednesday 4:30-5:30 Title: Deep Learning in Detection and Recognition Abstract: In this seminar, I will introduce our recent works on developing deep models to solve several computer vision problems, especially focusing on pedestrian detection and face recognition. Deep models significantly advance the state-of-the-art on these challenges because of their capability of automatically learning hierarchical feature representations from data, disentangling hidden factors, jointly optimizing key components in a computer vision system, and their learning capacity. Through examples, I will share our experience on how to formulate a vision problem with deep learning, and how to effectively train a deep neural network. Instead of treating a deep model as a black box, we investigate the connection between deep models and existing vision systems, such that a lot of insights and experience accumulated from vision research can be used to develop new deep models and effective training strategies. Taking pedestrian detection as an example, pedestrian detection, new layers are designed to function as part detectors, modeling deformations and inferring the visibility of body parts. I will also report our results on face recognition which can be addressed by deep learning in several different ways. Bio: Xiaogang Wang received his Bachelor degree in Electrical Engineering and Information Science from the Special Class of Gifted Young at the University of Science and Technology of China in 2001, M. Phil. degree in Information Engineering from the Chinese University of Hong Kong in 2004, and PhD degree in Computer Science from Massachusetts Institute of Technology in 2009. He is an assistant professor in the Department of Electronic Engineering at the Chinese University of Hong Kong since August 2009. He received the Outstanding Young Researcher in Automatic Human Behaviour Analysis Award in 2011, Hong Kong RGC Early Career Award in 2012, and Young Researcher Award of the Chinese University of Hong Kong. He is the associate editor of the Image and Visual Computing Journal. He was the area chair of ICCV 2011, ECCV 2014 and ACCV 2014. His research interests include computer vision, deep learning, crowd video surveillance, object detection, and face recognition.

1 0

Logan Stafman's Generals: Thursday, May 22, 2014 (2pm) in Rm. 402
by Nicki Gotsis 15 May '14

15 May '14

Logan Stafman will present the General Exam on Thursday, May 22, 2014 (2pm) in Rm. 402. The members of Logan's committee are Margaret Martonosi, Jennifer Rexford, and Vivek Pai. Everyone is invited to attend Logan's talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Logan's abstract and reading list follow below. Abstract Recently, we have been asking for our mobile phones to do more computation than ever before, while maintaining energy efficiency. Many mobile apps, in particular sensing apps, approach the problem of energy usage optimization by offloading heavy computation to the cloud. While this approach helps to save computation energy, it can often increase latency, bandwidth usage, and communication energy. As compute capability and heterogeneity of mobile devices both increase, the tradeoffs regarding when to offload computation to the cloud, whether from a latency, bandwidth, or energy standpoint, have become complex. While researchers have developed some systems to automate this offloading process in applications by offloading entire virtual machines and automatically partitioning applications, more remains to be done. This work studies automated techniques for optimizing application partitioning and offload. We consider energy and bandwidth oriented partitioning approaches. In addition, we discuss how the addition of new application modules (such as compression) can improve the payoff from offloading. Our work uses two example applications: SignalGuru and Sphinx. For SignalGuru, our partitioning approach improves bandwidth usage by up to 10x and offers energy savings as well. We discuss how these applications need to be adapted to obtain these goals, and how this process can be automated. We will also discuss how differences in the hardware of mobile devices can strongly affect the optimal partitioning choices for these applications. Reading List SignalGuru - Emmanouil Koukoumidis, Li-Shiuan Peh, and Margaret Martonosi. 2011. SignalGuru: leveraging mobile phones for collaborative traffic signal schedule advisory. In Proceedings of the 9th international conference on Mobile systems, applications, and services (MobiSys '11). MAUI - Eduardo Cuervo, Aruna Balasubramanian, Dae-ki Cho, Alec Wolman, Stefan Saroiu, Ranveer Chandra, and Paramvir Bahl. 2010. MAUI: making smartphones last longer with code offload. In Proceedings of the 8th international conference on Mobile systems, applications, and services (MobiSys '10). CloneCloud - Byung-Gon Chun, Sunghwan Ihm, Petros Maniatis, Mayur Naik, and Ashwin Patti. 2011. CloneCloud: elastic execution between mobile device and cloud. In Proceedings of the sixth conference on Computer systems (EuroSys '11). Junxian Huang, Feng Qian, Alexandre Gerber, Z. Morley Mao, Subhabrata Sen, and Oliver Spatscheck. 2012. A close examination of performance and power characteristics of 4G LTE networks. In Proceedings of the 10th international conference on Mobile systems, applications, and services (MobiSys '12). ACM, New York, NY, USA, 225-238. DOI=10.1145/2307636.2307658 Brian D. Noble, M. Satyanarayanan, Dushyanth Narayanan, James Eric Tilton, Jason Flinn, and Kevin R. Walker. 1997. Agile application-aware adaptation for mobility. In Proceedings of the sixteenth ACM symposium on Operating systems principles (SOSP '97), William M. Waite (Ed.). ACM, New York, NY, USA, 276-287. DOI=10.1145/268998.266708 Flinn, Jason; SoYoung Park; Satyanarayanan, M., "Balancing performance, energy, and quality in pervasive computing," Distributed Computing Systems, 2002. Proceedings. 22nd International Conference on , vol., no., pp.217,226, 2002 doi: 10.1109/ICDCS.2002.1022259 Jason Flinn and M. Satyanarayanan. 1999. Energy-aware adaptation for mobile applications. In Proceedings of the seventeenth ACM symposium on Operating systems principles (SOSP '99). ACM, New York, NY, USA, 48-63. DOI=10.1145/319151.319155 Balan, Rajesh Krishna, et al. "Tactics-based remote execution for mobile computing." Proceedings of the 1st international conference on Mobile systems, applications and services . ACM, 2003. Robert LiKamWa, Bodhi Priyantha, Matthai Philipose, Lin Zhong, and Paramvir Bahl. 2013. Energy characterization and optimization of image sensing toward continuous mobile vision. In Proceeding of the 11th annual international conference on Mobile systems, applications, and services (MobiSys '13). ACM, New York, NY, USA, 69-82. DOI=10.1145/2462456.2464448 Book: Operating Systems: Internals and Design Principles, 7th Edition - William Stallings

1 0

Special seminar - Jonathan Viventi, NYU poly
by Scott Karlin 15 May '14

15 May '14

“High-Resolution Brain Machine Interfaces using Flexible Silicon Electronics" Jonathan Viventi, Department of Electrical and Computer Engineering & Center for Neural Science, New York University Date: Thursday, May 29th Time: 4:30pm Location: A32 Princeton Neuroscience Institute Abstract Current implantable brain devices for clinical and research applications require that each electrode is individually wired to a separate electronic system. Establishing a high-resolution interface over broad regions of the brain is infeasible under this constraint, as an electrode array with thousands of passive contacts would require thousands of wires to be individually connected. To overcome this limitation, we have developed new implantable electrode array technology that incorporates active, flexible electronics. This technology has enabled extremely flexible arrays of 1,024 electrodes and soon, thousands of multiplexed and amplified sensors spaced as closely as 250 µm apart, which are connected using just a few wires. These devices yield an unprecedented level of spatial and temporal micro-electrocorticographic (µECoG) resolution for recording and stimulating distributed neural networks. I will present the development of this technology and data from in vivo recordings. I will also present examples of finely detailed spatial and temporal patterns from feline neocortex that give rise to seizures and suggest new stimulation paradigms to treat epilepsy. Finally, I will discuss new electrode designs and supporting hardware to enable chronic implantation of µECoG arrays with multiplexed recording and stimulation to enable a bi-directional interface with the brain. Bio Jonathan Viventi is an Assistant Professor of Electrical and Computer Engineering at the New York University Polytechnic School of Engineering and an Assistant Professor of Neural Science at New York University. Dr. Viventi earned his Ph.D. in Bioengineering from the University of Pennsylvania and his M.Eng. and B.S.E. degrees in Electrical Engineering from Princeton University. Dr. Viventi's research applies innovations in flexible electronics, low power analog circuits, and machine learning to create new technology for interfacing with the brain at a much finer scale and with broader coverage than previously possible. He creates new tools for neuroscience research and technology to diagnose and treat neurological disorders, such as epilepsy. Using these tools, he collaborates with neuroscientists and clinicians to explore the fundamental properties of brain networks in both health and disease. His research program works closely with industry, including filing five patents and several licensing agreements. His work has been featured as cover articles in Science Translational Medicine and Nature Materials, and has also appeared in Nature Neuroscience, the Journal of Neurophysiology, and Brain. Dr. Viventi has received several awards for his work, including a Taking Flight Award from Citizens United for Research in Epilepsy (CURE), a “Grand Challenge” award from New York University, the Mahoney Institute of Neurological Sciences / Neuroscience Graduate Group Flexner Award for Best Neuroscience Thesis at the University of Pennsylvania, the Solomon R. Pollack Award for Best Thesis in the Department of Bioengineering at the University of Pennsylvania, and the Nano/Bio-Interface Center Graduate Research Award for Best Graduate Research on Nanotechnology Applied to Biology at the University of Pennsylvania. Host: Uri Hasson

1 0

Aleksey Boyko: PreFPO on Wednesday, May 21st 12pm, Rm. 402
by Nicki Gotsis 14 May '14

14 May '14

Aleksey Boyko will present his Pre FPO which is scheduled for Wednesday, May 21st at noon in Rm. 402. Members of his committee are: Thomas Funkhouser (advisor), Brian Kernighan (reader), Szymon Rusinkiewicz (reader), Adam Finkelstein (non-reader), and Jianxiong Xiao(non-reader). Everyone is invited to attend his talk. The title and abstract are below. Title: "On tools and interfaces for efficient and accurate interactive annotation of static 3D point clouds" Abstract: Collecting massive 3D scans of real world environments has become a common practice for many private companies and government agencies. This data is accurate and rich enough to provide impressive visualizations of these environments. However, to truly tap into the potential that such a precise digital depiction of the world offers, these scans need to be annotated. Existing automatic methods report high accuracies for object localization and segmentation, thus greatly improving the complexity of the task. However, the central task of annotation, proper label assignment to the discovered objects, is still a challenging task for existing systems. The goal of this work is to design an interface that facilitates the process of labeling objects in large natural 3D scenes. Prior efforts in this field span a variety of approaches, from purely manual to automatic, to achieve different levels of success. Manual annotation systems produce near perfect results at a cost of enormous human effort. Automatic methods aim at requiring less human input but achieve much lower accuracy, which in turn requires more human interaction. Machine-aided tools attempt to balance these two extremes, however the necessary level of annotator's effort is rarely considered, while the task of training a model that hopefully achieves higher accuracy still takes the center stage. Noticing that the machines have yet a long way to go to match humans' ability to understand real world, and how prone to fatigue and frustration humans are, a preferable approach is to make user effort a priority in any annotation interface. This dissertation assumes the necessity of the human annotator to confirm labels for all objects in order to ensure correctness and explicitly focuses on the tools and interfaces that streamline and facilitate this process. Taking advantage of the scene continuity of the 3D scan data this work advances in two principal directions. First, annotation of objects in groups is proposed to increase the throughput of the information flow from the user to the machine. Second, the non-essential yet time consuming tasks (e.g., scene navigation, selection decisions) are relayed onto a machine by employing an active learning approach to streamline the annotation process and diminish user fatigue and distraction. After evaluating these two directions, a third hybrid approach is proposed---a group active interface. This method takes advantage of the human ability to understand entire scenes and queries objects in groups that are easy to understand and label together thus further increasing the throughput of the annotation process. Empirical evaluation of this approach on a pre-segmented object data indicates an improvement by a factor of 1.7 in annotation time compared to other methods discussed without loss in accuracy.

1 0