August 13, 2014 (Wednesday) CSE Room No. 302 3:30 PM
Distributed Computation in Dynamic Network via Random Walks
Dr. Anisur Rahaman Molla
Singapore University of Technology and Design (SUTD)
In this talk, we will discuss distributed computation in dynamic networks in which the network topology changes (arbitrarily) from round to round. We use random walk as a key tool to solve distributed problems in dynamic networks. Random walk is a fundamental technique which has found numerous applications in algorithms and complexity theory. The local and lightweight nature of random walks is especially useful for providing uniform and efficient solutions to distributed control of dynamic networks. Given their applicability in dynamic networks, we first focus on developing distributed algorithms for performing random walks in such networks. Next we talk on designing fast distributed algorithm for the fundamental problem of information dissemination (also called as gossip) in a dynamic network. In gossip, or more generally, k-gossip, there are k pieces of information (or tokens) that are initially present in some nodes in the network and the problem is to disseminate the k tokens to all nodes.
This talk will try to be self-contained; no background will be assumed beyond basic algorithms. This talk is based on joint works with Atish Das Sarma at eBay Research Lab, USA and Gopal Pandurangan at Nanyang Technological University, Singapore.
Anisur Rahaman Molla is a Postdoc Researcher at Singapore University of Technology and Design (SUTD). He has recently completed his PhD from Nanyang Technological University, Singapore. Anisur received an MTech degree in Computer Science from Indian Statistical Institute, Kolkata in 2010 and BSc and MSc in Mathematics from Calcutta University in 2005 and 2007 respectively. He worked at ISI, Kolkata as a visiting scientist for six months after finishing his MTech course. His current research interest includes design and analysis of distributed graph algorithms, randomized algorithms and probabilistic analysis and algorithms for dynamic networks.
June 13, 2014 (Friday) CSE Seminar Room (No. 107) 11 AM
Visual Content Analysis: A Few Challenges and Solutions
Senior Research Scientist
Humans have an intriguing ability to process visual information amazingly fast and with nearly perfect recognition rates. With the proliferation of the Internet, availability of cheap digital cameras, and the ubiquity of cell-phone cameras, the amount of accessible visual content has increased astronomically. Websites such as Flickr alone boast of over 5 billion images, not counting the hundreds of other such websites and countless other images that are not published online. This explosion poses unique challenges with regard to the discoverability of these images. The billions of images will be of little use if there is no efficient process to access them at will. With such enormous collections of available visual content, manual processing becomes prohibitive and it is therefore of great practical importance to build ³visual recognition systems². Visual recognition is a fundamental problem in computer vision. It subsumes the problems of classification, annotation, retrieval, object localization, object detection etc. In this talk, I will describe a few real-world visual content analysis projects I have worked on.
Gaurav Aggarwal is a senior research scientist with Yahoo! Labs Bangalore. He received the B.Tech. degree in computer science and engineering from the Indian Institute of Technology, Madras, in 2002 and the M.S. and Ph.D. degrees in computer science from the University of Maryland, College Park, in 2004 and 2008, respectively. He has held Research Scientist position with Object Video Inc. and a Research Assistant Professor position with Department of Computer Science and Engineering, University of Notre Dame before joining Yahoo. His research interests are in image and video processing, computer vision, pattern recognition and machine learning.
May 13, 2014 (Tuesday) CSE Seminar Room (No. 107) 4 PM
Boxicity and Cubicity of Graphs
Sunil Chandran L
Department of Computer Science and Automation
Indian Institute of Science
A graph is said to have a d-dimensional box representation (respectively cube representation- we consider d-dimensional cubes of unit volume) if the vertices of G can be assigned axis parallel d-dimensional boxes (resp. cubes) in such a way that two vertices are adjacent if and only if the corresponding boxes (resp. cubes) intersect. The smallest non-negative integer d for which this is possible, is the boxicity (resp. cubicity) of the graph G. In this talk we will present an overview of the results we obtained on boxicity and cubicity of graphs over the last few years. For example, we will discuss the relation of boxicity and cubicity with the width parameters such as treewidth and bandwidth, the connection between boxicity and the partial order dimension and upper bounds for cubicity in terms of boxicity, and some interesting results regarding the boxicity and cubicity of certain special classes of graphs.
April 29, 2014 (Tuesday) CSE Seminar Room (No. 107) 4 PM
Some graph theoretic and rank based approaches to understand the biology of microRNAs
Genome Institute of Singapore
microRNAs are tiny non coding RNA molecules with the capability of controlling protein levels by silencing functional mRNA molecules. After its discovery, in the past two decades significant amount of research has confirmed its role in pathogenesis of various major diseases. Predicting the genes to which a particular microRNA can bind has huge public health significance. It is equally important to understand how this newly discovered non coding RNA molecules wire with the Gene Regulatory Network. In this talk some graph theoretic and ranking based meta analytic approaches would be discussed in relation to the biology of microRNAs and their implication in diseases.
Debarka Sengupta did his B. Tech and Ph. D. in Computer Science and Engineering from West Bengal University of Technology and Jadavpur University respectively. He worked in software as well as analytics industry for nearly 4 years as a software consultant and senior data scientist respectively. The organizations he worked for include Infosys, IBM, CoreCompete LLC. etc. He spent four years in the Machine Intelligence Unit of Indian Statistical Institute working as a Junior and (then) Senior Research Fellow in a DST sponsored Swarnajayanti project. For more than two years he served as a department editor of XRDS- the ACM magazine for students, published by ACM (NY, USA). He was awarded Infosys spot award in July, 2007 for his performance. His PhD work was selected for presentation at TechVista 2011, organized by Microsoft Research. His research interests include machine learning, bioinformatics, social networks, game theory etc. He has published research articles in many prominent scientific journals and conferences. He has one US patent on rank aggregation. Currently he is serving as a postdoctoral researcher at the Genome Institute of Singapore.
March 7, 2014 (Friday) CSE Seminar Room (No. 107) 4:30 PM
Exploration and Multi-armed Bandits
Imagine that we wish to increase the click through rate (CTR) on the links in a web page, and designers have provided us three possible configurations for rendering the page: D1 (black text on white background), D2 (white text on black background), and D3 (D1 with a smaller font size). Likely, the propensity of users to click on links will differ for D1, D2, and D3. Given that the CTRs of these configurations are unknown to begin, how must we adaptively split traffic among them in order to maximize the total number of clicks? In addition to this illustrative example, the ``explore or exploit?'' dilemma arises in numerous applications in practice, including clinical trials, packet routing, and game playing.
This tutorial will introduce the theory of stochastic multi-armed bandits, which answers how to trade off the exploration of competing options with the exploitation of the best. Arguments based on intuition, mathematics, and experiments will lead the audience through a discussion that all are welcome to attend.
Shivaram Kalyanakrishnan is a scientist at Yahoo Labs Bangalore. His primary research interests lie in the fields of artificial intelligence and machine learning, spanning areas such as reinforcement learning, agents and multiagent systems, humanoid robotics, multi-armed bandits, and on-line advertising. He obtained his Ph.D. in Computer Science from the University of Texas at Austin (2011), and his B.Tech. in Computer Science and Engineering from the Indian Institute of Technology Madras (2004). He has extensively used robot soccer as a test domain for his research, and has actively contributed to initiatives such as RoboCup and the Reinforcement Learning competitions.
March 6, 2014 (Thursday) CSE Seminar Room (No. 107) 3:30 PM
Cellular automaton models for collective cell behaviour
Prof. Andreas Deutsch
Cellular automata are introduced as models for collective behaviour in interacting cell populations. We focus on mechanisms of collective cell migration, clustering and invasion and demonstrate how analysis of the models allows for prediction of emerging properties at the individual cell and the cell population level. Finally, we discuss applications of the invasion models to glioma tumours.
Ref.: A. Deutsch, S. Dormann: Cellular Automaton Modeling of Biological Pattern Formation: Characterization, Applications, and Analysis Birkhäuser, Boston, 2005 (2nd ed. 2014)
Prof. Andreas Deutsch is the head of the department for Innovative Methods of Computing, TU Dresden . He has a diploma in mathematics, a PhD in biology, and a habilitation in theoretical biology. He is considered an authority in theoretical biology in general and cancer modelling in particular. He develops mathematical models and simulation tools for detecting organizational principles of selected biological systems. He focuses on collective phenomena of "interacting cell systems". Disorders in cell interaction can imply diseases and malignant pattern formation (e.g. tumor growth) and important insights into function and regulation of biological systems is gained from the linking of mathematical modeling and computational tools with biological/biomedical (in vitro, in vivo) data.
February 26, 2014 (Wednesday) CSE Seminar Room (No. 107) 3:30 PM
Health Data Analytics
Dr. Shaibal Roy
Applied Research Works
The cost of healthcare is rising rapidly in developing economies, and has already reached a breaking point in the developed nations. The United States alone spends almost $3T on healthcare, which is more than the GDP of France, Italy or India. And yet, the revolution in Big Data is yet to make a dent in that cost. Today, iTunes and Amazon do a better job of tracking music and books you like than the healthcare system does in tracking your health care.
In this talk, Dr. Roy will outline how the Affordable Care Act (aka “Obamacare”) is rapidly transforming the $3T health care industry in the United States, and the role that data analytics play in that transformation.
Dr. Shaibal Roy is Founder and CEO at Applied Research Works, a healthcare transformation company with offices in Palo Alto, Honolulu, and Kolkata. ARW’s mission is to improve quality and outcomes in healthcare by transforming health data into actionable information. ARW's flagship product Cozeva is currently used by some of the largest health plans in the United States, and by over 700 practices.
Before founding ARW, Dr. Roy was Chief Architect at BlackBerry from 2002 to 2006. During those 4 years, he spearheaded BlackBerry's meteoric growth from less than 400,000 devices to over 20 million devices. Before BlackBerry, Dr. Roy was co-founder of a venture-funded startup that was acquired by BlackBerry, and, before that, another venture-funded startup that was acquired by Netscape. Dr. Roy is co-inventor in over 30 patents, and has co-authored many papers and a book.
Dr. Roy hold a B.Tech. from IIT Kharagpur and a Ph.D. from Stanford University, both in Computer Science.
January 22, 2014 (Friday) CSE Seminar Room (No. 107) 4 PM
Challenges in Graph Data Management
University of Maryland
In modern world graph-structured data is everywhere; social networks, communication networks, traffic information networks, financial transaction networks are to name a few. Utility and growth of many of these networks are reaching newer heights every day due to rapid proliferation of internet enabled devices. There is tremendous value in managing these large dynamic networks efficiently and process, query, and detect events in real-time. In my talk I will discuss two of the systems that we have built addressing some of the key challenges in graph data management.
In the first part of my talk, I will focus on building an in-memory, distributed graph data management system for managing such large networks, and supporting low-latency query processing over it. The key challenge in a distributed graph database is partitioning a graph across a set of machines in a balanced way that minimizes the number of distributed traversals across partitions. We noted that the ideal solution to this problem is hard, and propose aggressive replication of the nodes to minimize communication bandwidth and support low-latency querying. We developed a hybrid replication policy that monitors read-write frequencies of the nodes to dynamically decide what data to replicate, and whether to do eager or lazy replication. We evaluate our system on Amazon EC2 and show that our system significantly reduces the number network calls.
In the second part, I will look into the problem of ego-centric aggregate queries on these graphs; such queries has not been studied throughly before. Many tasks like personalized, tailored trends in social networks, anomaly or event detection in communication or financial transaction networks, local search and alerts in spatio-temporal networks falls under this category. Keeping in mind the challenges of executing large number of simultaneous ego-centric queries in such dynamic networks, we proposed EAGr, an flexible, general purpose, and user extensible in-memory framework that is built around the notion of an aggregation overlay graph, a pre-compiled data structure that encodes the computations to be performed when an update or a query is received. The overlay graph enables sharing of partial aggregates across different ego-centric queries, and also allows partial pre-computation of the aggregates to minimize the query latencies. Our experiments show that EAGr can easily handle graphs of size up to 320 million nodes and edges, and achieve update and query throughputs of over 500,000/s using a single, powerful machine.
Time permitting, I will touch upon my ongoing work on devising declarative methods to specify anomaly/interesting events on these networks, and developing efficient evaluation techniques using search space pruning and approximate data structures.
Jayanta Mondal did his BTech in Computer Science and Engineering at IIT Kharagpur and is currently pursuing his PhD at University of Maryland at College Park.
January 21, 2014 (Friday) CSE Seminar Room (No. 107) 2:30 PM
Perspectives on Mobile Cloud Computing and its Applications
Dr. Pradipta De
University of Georgia
With growing use of smartphones, and other mobile devices, the users are expecting desktop like experience on the mobile devices. Inherently resource limited mobile devices are not suitable to meet the requirements. Cloud computing offers the promise of unbounded resource on demand. The possibilty of augmenting resource limited mobile computing with on demand resources from cloud forms the core principle of mobile cloud computing (MCC). Although earlier prototypes of systems based on MCC principles focused on computation offloading, lately other application types are also drawing attention. Even the reverse offloading, where idle smartphone resources are harnessed to augment computation, has also been investigated. In this talk, we will take a look at the MCC from these different perspectives, focusing mainly on computation offloading and introducing other aspects that should be considered for offloading. Finally, we will cover concrete examples of application of MCC to augment mobile applications.
Pradipta De is an Assistant Professor of Computer Science Department at The State University of New York (SUNY), Korea based in Songdo Global University Campus. He also holds an affiliate appointment as Research Assistant Professor at StonyBrook University. Prior to joining SUNY, Korea, Pradipta worked as a Research Staff Member with IBM Research - India from 2005 to 2012. Pradipta received his Ph.D. from StonyBrook University (SUNY) in 2007. He did his undergraduate in Computer Science and Engineering from Jadavpur University, Kolkata. His current research interests are in distributed systems, focusing on design of efficient cloud based systems and mobile applications. Currently he is investigating the use of cloud computing for enhancing mobile applications, with a focus on use of offloading techniques for locationing and mobile affective computing. At SUNY Korea, Pradipta leads the Mobile Systems and Solutions (MoSyS) lab.
January 3, 2014 (Friday) CSE Seminar Room (No. 107) 2:30 PM
Detection and Characterization of Intrinsic Symmetry over 3D Shapes
University of Georgia
This talk will present a comprehensive framework for detection and characterization of partial intrinsic symmetry over 3D shapes. To identify prominent symmetric regions which overlap in space and vary in form, the proposed framework is decoupled into a correspondence space voting procedure followed by a transformation space mapping procedure. In the correspondence space voting procedure, significant symmetries are first detected by identifying surface point pairs on the input shape which are locally similar in their intrinsic geometry and maintain an intrinsic distance structure globally. Since different point pairs can share a common point, shape regions can potentially overlap. To this end, a global intrinsic distance-based voting technique is employed to ensure the inclusion of only point pairs that exhibit significant symmetry. In the transformation space mapping procedure, the Functional Map framework is employed to generate the final map of symmetries between point pairs. The transformation space mapping procedure ensures the retrieval of the underlying dense correspondence map throughout the 3D shape that follows a particular symmetry. Additionally, the formulation of a novel cost matrix enables the inner product to successfully indicate the complexity of the symmetry transformation. The proposed transformation space mapping procedure is shown to result in the formulation of a metric symmetry space where each point in the space represents a specific symmetric transformation and the distance between points represents the complexity between the corresponding transformations. Experimental results show that the proposed framework can successfully process complex 3D shapes possessing rich symmetries.
Anirban Mukhopadhyay is a PhD Candidate of Computer Science Department and a part of Visual and Parallel Computing Laboratory at University of Georgia. His research mainly focuses on Geometric Analysis of Deformable Shapes and its application in Medical Image Analysis. He is a recipient of James L. Carmon Scholarship Award (2012) and MICCAI Society Travel Award (2012). He spent 2 summers as an intern in Siemens Corporate Research (Princeton, NJ) and Mitsubishi Electric Research Labs (Cambridge, MA). Mr. Mukhopadhyay serves as a reviewer in IEEE/ACM Transactions of Computational Biology and Bioinformatics.
2013 | 2012 | 2011 | 2010 | 2009 | 2008