Select a calendar:
Filter February Events by Event Type:
SUNMONTUEWEDTHUFRISAT
Conferences, Lectures, & Seminars
Events for February
-
CS Colloquium
Tue, Feb 01, 2011 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Dr. Rebecca Schulman, Miller Research Fellow, UC Berkeley
Talk Title: What makes a bunch of molecules a cell: The power of chemical reaction networks
Abstract: While we can write programs that emulate our capacity for chess playing or predict our tastes, many tasks that both humans and lower organisms are capable of such as image recognition or directed motion have been surprisingly difficult to reverse engineer. What these processes share is the entwinement of a complex organism with a complex physical environment.
While higher organisms are complex, single cells are much less so.
And even single cells can chase targets, change shape on cue, and self-replicate. How can a cell, a simple group of molecules, orchestrate these behaviors? We can investigate the power of molecular interactions by trying to recreate the computations they perform and the implementation of the computations using synthetic DNA. DNA's chemistry and structure are well-understood, and we can engineer specific interactions between DNA molecules by designing their sequences. We can therefore focus on the power of systems of reactions rather than on the process of individual ones. I'll show how we can use DNA to replicate sequences written in an alphabet of DNA blocks, or tiles, and program molecules to execute a "search and capture" process that forms a tether between two points of unknown location. From these examples we learn that molecular reaction networks are surprisingly powerful: a small set of molecules can both compute and learn arbitrarily complex patterns, and even though molecular interactions are stochastic and unreliable, systems of molecules can robustly perform complex behaviors.
Biography: Rebecca Schulman received undergraduate degrees in mathematics and computer science at MIT. She then spent several years working on search and natural language technology in Silicon Valley before receiving a PhD in the "Computation and Neural Systems" option at the California Institute of Technology, where she worked with Erik Winfree. Dr. Schulman is currently a Miller Research Fellow at UC Berkeley in Jan Liphardt's group.
Host: Profs. Len Adleman, Shang-Hua Teng
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Colloquium
Tue, Feb 08, 2011 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Ankur Moitra, MIT
Talk Title: Vertex Sparsification
Abstract: Suppose we are given a gigantic communication network, but are only interested in a small number of nodes (clients). There are many routing problems we could be asked to solve for our clients. Is there a much smaller network - that we could write down on a sheet of paper and put in our pocket - that approximately preserves all the relevant communication properties of the original network? As we will demonstrate, the answer to this question is YES, and we call this smaller network a vertex sparsifier.
In fact, if we are asked to solve a sequence of optimization problems characterized by cuts or flows, we can compute a good vertex sparsifier ONCE and discard the original network. We can run our algorithms (or approximation
algorithms) on the vertex sparsifier as a proxy - and still recover approximately optimal solutions in the original network. This novel pattern saves both space (because the network we store is much smaller) and time (because our algorithms run on a much smaller graph).
Additionally, we apply these ideas to obtain a master theorem for graph partitioning problems - as long as the integrality gap of a standard linear programming relaxation is bounded on trees, then the integrality gap is at most a logarithmic factor larger for general networks. This result implies optimal bounds for many well studied graph partitioning problems as a special case, and even yields optimal bounds for more challenging problems that had not been studied before. Morally, these results are all based on the idea that even though the structure of optimal solutions can be quite complicated, these solution values can be approximated by crude (even linear) functions.
Biography: Ankur Moitra is a fourth year PhD student in the theory of computation group at MIT, advised by Tom Leighton. His main research interests are in approximation algorithms, learning theory and applied probability. He received a B.S. in electrical and computer engineering from Cornell in 2007, and a M.S.
in computer science from MIT in 2009. Additionally, he has spent a number of summers working in industry, both as a quant at Citigroup and designing blog ranking algorithms at Google.
Host: Prof. David Kempe, USC
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Distinguished Lecture
Thu, Feb 10, 2011 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Dr. James O'Brien, UC Berkeley
Talk Title: Sparse Matrix Factorization, Mesh Modification, and Real-Time FEM Simulation
Abstract: This talk will discuss the use of dynamic remeshing and sparse matrix factorization in the context of real-time dynamics simulations. The first part of the talk will focus on two systems that have been developed for specific applications: destructible environments in "Star Wars: The Force Unleashed" and interactive modeling of prostate brachytherapy. Although dynamic remeshing is often dismissed as impractically slow, in both cases it plays a key part to making the simulations work effectively in a real-time setting. The second part of the talk will focus on an incremental update method for the Cholesky factors of sparse matrices that out-performs standard iterative methods for solving elastodynamic problems. The factors are not recomputed at each time step, but the nonlinearities that normally compel refactoring are not ignored either. Instead, the algorithm makes local incremental updates to the Cholesky factors to maintain error limits on the solution. The results presented will include captured footage from the live game, comparisons of simulated needle insertion to footage with gel tissue phantoms, and demonstrations of the sparse direct solver on large meshes.
Biography: James F. O'Brien is an Associate Professor of Computer Science at the University of California, Berkeley. His primary area of interest is Computer Animation, with an emphasis on generating realistic motion using physically based simulation and motion capture techniques. He has authored numerous papers on these topics. In addition to his research pursuits, Prof. O'Brien has worked with several game companies on integrating advanced simulation physics into game engines, and his methods for destruction modeling were recently used in the film Avatar. He received his doctorate from the Georgia Institute of Technology in 2000, the same year he joined the Faculty at U.C. Berkeley. Professor O'Brien is a Sloan Fellow and ACM Distinguished Scientist, Technology Review selected him as one of their TR-100, and he has been awarded research grants from the Okawa and Hellman Foundations. He is currently serving as ACM SIGGRAPH Director at Large. http://obrien.berkeley.edu/
Host: Prof. Jernej Barbic, USC
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Colloquium
Tue, Feb 15, 2011 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Roxana Geambasu, University of Washington
Talk Title: Regaining Control Over Mobile and Cloud Data
Abstract: Emerging technologies, such as cloud and mobile computing, offer previously unimaginable global access to data; however, they also threaten our ability to control the use of our data, its lifetime, accessibility, privacy, management properties, etc. My research focuses on restoring to users control they've ceded to the cloud and mobile devices. In this talk I will describe two examples of this work. First, I'll present Keypad, an auditing file system for theft- and loss-prone mobile devices that permits users to track and control accesses on their mobile data, even after a device has been stolen.
Second, I'll describe Vanish, a global-scale distributed-trust system that allows users to cause all copies of desired Web data objects, online or offline, to simultaneously self destruct at a specified time. A common thread of these efforts is the integration of systems and crypto techniques to solve new problems in data management brought on by technological change.
Biography: Roxana Geambasu is a doctoral candidate in the Department of Computer Science & Engineering at the University of Washington. Her interests span broad areas of systems research, including cloud and mobile computing, operating systems, file systems, and databases, with a focus on security and privacy. She received her B.S. in Computer Science from the Polytechnic University of Bucharest in 2005 and was the recipient of the first Google Fellowship in Cloud Computing in 2009.
Host: Prof. Ramesh Govindan, USC
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Colloquium
Wed, Feb 16, 2011 @ 03:30 PM - 05:30 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Dieter Gawlick, Oracle
Talk Title: Classification based data base management
Abstract: Patient care - as IT support in other domains - is typically managed by several incompatible programs in terms of their data models and semantics. These programs are focused on specific situation and give doctors a limited view at patient data. The IT technology, however, has evolved to a point that it is now possible to develop a generic patient care application that manages all patient data for all situations requiring none or little domain specific procedural code. This application provides also a framework for capturing medical knowledge. With this knowledge the application is able to extract in real time medically relevant information from data, even if the extraction is outside of the medical expertise of a doctor or if the extraction is outside of the capability of the human brain. By transforming (quantitative) data into (qualitative) information, applications adjust to the way humans absorb and use information. Provisioning - covering data, information, and knowledge - ensures that the fuzziness of qualitative information is always backed by the precision of quantitative data. This approach depends heavily on the classification of data and the management of these classifications; it also requires a new look at event processing, which is used as a major underlying technology.
Biography: Dieter is an architect in Oracle's database division; he has developed key concepts for high-end OLTP, storage management, messaging, workflow, and information dissemination. He is currently focusing on the evolution of data base based event processing, history management, and provenance. He has written numerous papers and served in numerous program committees. Before joining Oracle, he worked at IBM, Ahmdahl (Fujitsu), and Digital (HP).
Talk will be held between 3:30 - 4:30 pm, followed by reception at 4:30 pm
Host: Prof. Shahram Ghandeharizadeh
Location: RRI 101
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Colloquium
Thu, Feb 17, 2011 @ 11:00 AM - 12:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Dr. Craig Boutilier, University of Toronto
Talk Title: Computational Social Choice: A Decision-theoretic Perspective
Abstract: Social choice, an important topic of study for centuries, has recently been the subject of intense investigation and application within computer science. One reason for this is the increasing ease with which preference data from user populations can be derived, assessed, or estimated, and the variety of settings in which preference data can be aggregated for consensus recommendations. However, much work in computational social choice adopts existing social choice schemes rather uncritically. We adopt an explicit decision-theoretic perspective on computational social choice in which an explicit objective function is articulated for the task at hand. With this is place, one can develop new social choice rules suited to that objective; or one can analyze the performance of existing social choice rules relative to that criterion.
We illustrate the approach with two different models. The first is the "unavailable candidate model." In this model, a consensus choice must be selected from a set of candidates, but candidates may become unavailable after agents express their preferences. An aggregate ranking is used as a decision policy in the face of uncertain candidate availability. We define a principled aggregation method that minimizes expected voter dissatisfaction, provide exact and approximation algorithms for optimal rankings, and show experimentally that a simple greedy scheme can be extremely effective. We also describe strong connections to the plurality rule and the Kemeny consensus, showing specifically that Kemeny produces optimal rankings under certain conditions.
The second model is the "budgeted social choice" model. In this framework, a limited number of alternatives can be selected for a population of agents. This limit is determined by some form of budget. Our model is general, spanning the continuum from pure consensus decisions (i.e., standard social choice) to fully personalized recommendation. We show that standard rank aggregation rules are not appropriate for such tasks and that good solutions typically involve picking diverse alternatives tailored to different agent types. In this way, it bears a strong connection to both segmentation problems and multi-winner election schemes. The corresponding optimization problems are shown to be NP-complete, but we develop fast greedy algorithms with theoretical guarantees. Experimental results on real-world datasets demonstrate the effectiveness of our greedy algorithms.
Host: Dr. Milind Tambe, USC
Location: Seeley Wintersmith Mudd Memorial Hall (of Philosophy) (MHP) - 106
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Colloquium
Thu, Feb 17, 2011 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Virginia Vassilevska Williams, UC Berkeley
Talk Title: Path, matrix and triangle problems -- subcubic algorithms and equivalences
Abstract: Many graph and matrix problems studied in optimization have relatively simple algorithms which run in time cubic in the number of vertices or rows. Some examples include matrix multiplication and all-pairs shortest paths. These problems have widespread applications, and developing more efficient algorithms for them would have a big impact. In 1969, Strassen gave a clever truly subcubic algorithm for matrix multiplication, and this insight has since lead to faster algorithms for many of the graph and matrix problems solvable in cubic time.
Nevertheless, several stubborn problems remain for which the best known running time is essentially cubic. The prototypical of these problems is all-pairs shortest paths. Other stubborn problems include the minimum weight cycle (girth) problem, the replacement paths problem, the second shortest simple path problem, and the simplest of them all, the problem of detecting a negative weight triangle in a graph. We have recently been able to show, perhaps surprisingly, that all these problems are equivalent, in the sense that if one has a truly subcubic algorithm, then all of them do. To accomplish this, we define a new, more refined notion of reduction, preserving "subcubicity" (the notion can easily be extended for any time exponent other than 3 as well).
One of our major goals is to develop a theory of equivalences between problems within P, analogous to that of NP-completeness. One reason P vs NP looks so hard to resolve is that many researchers from different areas have all been working on essentially the same (NP-complete) problem with no success. Our situation is entirely analogous: either these problems require essentially cubic time, or we are missing a fundamental insight which would make all of them simultaneously easier. In this talk I will give an overview of my results in the area, both algorithms and equivalences.
Biography: Virginia Vassilevska Williams is currently a postdoctoral fellow working with Prof. Satish Rao, sponsored by a Computing Innovations Fellowship. She obtained her Bachelor's degree in mathematics and engineering and applied science from the California Institute of Technology in 2003. She completed her Ph.D. in computer science at Carnegie Mellon University in 2008 under the guidance of Prof. Guy Blelloch. She also spent a year as a postdoctoral member at the Institute for Advanced Study in Princeton, in Avi Wigderson's group. Her primary research interests are in graph algorithms and computational social choice.
Host: Prof. Ming-Deh Huang, USC
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Colloquium
Tue, Feb 22, 2011 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Dr. Mohit Singh, McGill University
Talk Title: Iterative Methods in Combinatorial Optimization
Abstract: Many fundamental combinatorial optimization problems including minimum spanning tree, matchings, flows are polynomial time solvable but most problems that arise in practice turn out to be NP-hard. Fortunately, many NP-hard problems can be modeled by introducing extra side constraints in some fundamental optimization problem. A natural question to ask is whether we can extend any techniques for solving simple combinatorial optimization problems to NP-hard variants. In this talk we will demonstrate iterative methods as such a general technique to prove near optimal results for many optimization problems.
We will focus on degree bounded network design problems where the task is to minimize the cost of the network and also satisfy given degree bounds on nodes. The most studied problem in this class is the Minimum Bounded Degree Spanning Tree problem. We will present a polynomial time algorithm that returns a spanning tree of optimal cost while exceeding the degree bound of any vertex by at most an additive one. This is the best possible result for this problem and settles a 15-year-old conjecture of Goemans affirmatively.
We will also discuss extensions to degree constrained versions of more general network design problems and give the first additive approximation algorithms using the iterative method. These results add to a rather small list of combinatorial optimization problems which have an additive approximation algorithm.
Biography: Mohit Singh is an Assistant Professor in the School of Computer Science, McGill University since 2010. Mohit Singh received his Bacherlorâs degree in computer science and engineering from Indian Institute of Technology, Delhi in 2003. He obtained his Ph.D. in the Algorithms, Combinatorics and Optimization program from Carnegie Mellon University in 2008 where his advisor was Prof. R. Ravi. He was then a post-doctoral candidate at Microsoft Research, New England. His main research interests are in approximation algorithms, combinatorial optimization and optimization under uncertainty.
Host: Prof. David Kempe
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Colloquium
Thu, Feb 24, 2011 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: William Enck, Penn State University
Talk Title: Analysis Techniques for Mobile Operating System Security
Abstract: Over the last several years, smartphone application markets such as Google's Android Market and Apple's App Store have become a thriving industry with simplified distribution and little barrier to entry for developers. Smartphone users face many security and privacy risks, the most wide-spread of which results from applications operating within the confines of existing operating system protections. In this talk, I will discuss how to assess the current state of smartphone security using a range of analysis techniques. Existing smartphone security is permission oriented. First, I will use a formal model of permission policy to understand the permissions an application asks for, defining a coarse upper bound on its runtime behavior. Second, I will present a performance efficient method of dynamic analysis to determine actual application behavior, and subsequently identify several privacy concerns in real applications. Finally, I will describe a static analysis approach to characterize potential behavior based on implemented functionality. Using these approaches, we identify trends and primary security challenges so that future mobile operating system designs can mitigate existing threats.
Biography: William Enck is a doctoral candidate in the Systems and Internet Infrastructure Security (SIIS) laboratory in the Computer Science and Engineering Department at Penn State University. William's research efforts primarily focus on mobile operating system security, but also include telecommunications security, access control mechanisms in operating systems, hardware security, voting systems security, network security, and large-scale network configuration.
Host: Dr. William Halfond
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
USC Water Institute Seminar
Fri, Feb 25, 2011 @ 11:00 AM - 12:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Stephen Monismith , Chair, Dept of Civil and Env Eng, Stanford University
Talk Title: : (Not quite) Everything you wanted to know about freshwater flows into the San Francisco Bay/Delta - But were afraid to ask
Abstract: I will discuss an overview of one of the central and most contentious issues facing California's management of water resources: the ecological effects of freshwater flows through the Sacramento/San Joaquin Delta into San Francisco Bay and their diversion for human use. In particular, I will focus on selected aspects of the role hydrodynamic processes may play in determining how we manage the system with the aim of achieving the desired "co-equal goals" of ecosystem restoration and water supply reliability. Central to this discussion are the alternative views that argue that the fundamental problem is one of plumbing or that it is the volume of water diverted and the timing of those diversions that matters.
Biography: Stephen Monismith's research in environmental and geophysical fluid dynamics involves the application of fluid mechanics principles to the analysis of flow processes operating in rivers, lakes, estuaries and the oceans. Making use of laboratory experimentation, numerical modelling, and field measurements, his current research includes studies of estuarine hydrodynamics and mixing processes, flows over coral reefs, wind wave-turbulent flow interactions in the upper ocean, turbulence in density stratified fluids, and physical-biological interactions in phytoplankton and benthic systems. Because his interest in estuarine processes is intertwined with an interest in California water policy issues, he has been involved with efforts at developing management strategies for improving the "health" of the Bay through regulation of freshwater flow into the Bay. Professor Monismith is currently director of the Environmental Fluid Mechanics Laboratory. He was a resident fellow in Robinson House (Stanford's environment theme house) 2000-2002. He is a 1989 recipient of the Presidential Young Investigator award. Prior to coming to Stanford, he spent three years in Perth (Australia) as a research fellow at the University of Western Australia.
Host: Prof. Gaurav Sukhatme
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Colloquium
Mon, Feb 28, 2011 @ 03:30 PM - 01:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Sasha Alexander Sherstov, Microsoft Research
Talk Title: Limits of Communication
Abstract: Consider a function f whose arguments are distributed among several parties, making it impossible for any one party to compute f in isolation. Initiated in 1979, communication complexity theory studies how many bits of communication are needed to evaluate f. I will prove that:
1. some natural and practical problems require high communication to achieve any advantage at all over random guessing;
2. solving n instances of any known communication problem on a quantum computer incurs Omega(n) times the cost of a single instance, even to achieve exponentially small correctness probability.
The proofs work by recasting the communication problem geometrically and looking at the dual problem in a novel way. Our results resolve open problems dating back to 1986.
Biography: Alexander Sherstov earned his Ph.D. in computer science in August 2009 at the University of Texas at Austin, under the direction of Prof. Adam Klivans, and is currently a postdoctoral researcher at Microsoft Research. He has broad research interests in theoretical computer science, including complexity theory, computational learning theory, and quantum computing.
Host: Prof. Ming-Deh Huang
Location: SAL 101
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
