- talks - lists.cs.princeton.edu

A Vijayaraghavan preFPO
by Melissa M. Lawson 01 Mar '12

01 Mar '12

Aravindan Vijayaraghavan will present his preFPO on Wednesday March 7 at 11AM in Room 302 (note room). The members of his committee are: Moses Charikar, advisor; Sanjeev Arora and Mark Braverman, readers; David Blei and Konstantin Makarychev, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ---------------------- Understanding Approximability through Average-case Analysis We study the approximability of fundamental graph optimization problems through approximation algorithms for both realistic average-case and worst-case instances of problems. We study average-case instances to shed new light on approximability in two ways : 1. designing better algorithms for realistic average-case instances. 2. designing new algorithms with better guarantees even in worst-case, and identifying new barriers for further progress. In the first part of the thesis, we study Graph partitioning problems which are ubiquitous in computer science and form a central topic of study. However, constant factor approximations have been elusive. Since real-world instances are unlikely to behave like worst-case instances, a compelling question is : can we design better algorithms for realistic average case instances? We study a semi-random model for graph partitioning problems, that is more general than previously studied random models, and that seems to capture many real-world instances well. We design new O(1) approximation algorithms for classical graph partitioning problems like Balanced Separator, Sparsest cut, Multicut and Small set expansion for these semi-random instances. Our algorithms are based on new SDP-based techniques and work in a wider range of parameters than algorithms for previously studied random and semi-random models. In the second part, we show how insights from algorithms for a natural average-case version are used to obtain new worst-case approximation algorithms for the Densest k-Subgraph problem -- an important yet poorly understood problem in combinatorial optimization. The counting-based algorithms for the average-case version of the problem are translated to algorithms for the worst-case using linear programming hierarchies: this gives an improved n^{1/4} factor approximation. Studying the average-case version also points to a concrete barrier for further progress on approximations for Densest k-subgraph. These results are based on joint works with Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Venkatesan Guruswami, Konstantin Makarychev, Yury Makarychev and Yuan Zhou.

1 0

3:00pm Mon Mar 5: Uday Khedker on Heap Reference Analysis
by Moses S. Charikar 01 Mar '12

01 Mar '12

Speaker: Uday Khedker, IIT Bombay Title: Heap Reference Analysis Using Access Graphs Day: Monday, March 5, 2012 Time: 3:00 pm Room: Room 402, CS building Abstract: Despite significant progress in the theory and practice of program analysis, analyzing properties of heap data has not reached the same level of maturity as the analysis of static and stack data. The spatial and temporal structure of stack and static data is well understood while that of heap data seems arbitrary and is unbounded. We devise bounded representations which summarize properties of the heap data. This summarization is based on the structure of the program which manipulates the heap. The resulting summary representations are certain kinds of graphs called access graphs. The boundedness of these representations and the monotonicity of the operations to manipulate them make it possible to compute them through data flow analysis. An important application which benefits from heap reference analysis is garbage collection, where currently liveness is conservatively approximated by reachability from program variables. As a consequence, current garbage collectors leave a lot of garbage uncollected, a fact which has been confirmed by several empirical studies. We propose the first ever end-to-end static analysis to distinguish live objects from reachable objects. We use this information to make dead objects unreachable by modifying the program. This application is interesting because it requires discovering data flow information representing complex semantics. In particular, we formulate the following new analyses for heap data: liveness, availability, and anticipability and propose solution methods for them. Together, they cover various combinations of directions of analysis (i.e. forward and backward) and confluence of information (i.e. union an! d interse ction). Our analysis can also be used for plugging memory leaks in C/C++ languages. Reference: Uday P. Khedker, Amitabha Sanyal, and Amey Karkare. Heap Reference Analysis Using Access Graphs. ACM Transactions on Programming Languages & Systems. 30, 1 (Nov. 2007), 1. DOI=http://doi.acm.org/10.1145/1290520.1290521.

1 0

8pm tonight: What Does It Mean To Be Literate in the Age of Google?
by Adam Finkelstein 28 Feb '12

28 Feb '12

This public lecture may be of interest: http://lectures.princeton.edu/2012/daniel-m-russell/ What Does It Mean To Be Literate in the Age of Google? Daniel M. Russell Über Tech Lead for Search Quality and User Happiness, Google February 28, 2012 Louis Clark Vanuxem Lecture What does it mean to be literate at a time when you can search over billions of texts in less than 300 milliseconds? Although you might think that “literacy” is one of the great constants that transcends the ages, the skills of a literate person have changed substantially over time as texts and technology allow for new kinds of reading and understanding. Knowing how to read is just the beginning of it—knowing how to frame a question, pose a query, how to interpret the texts that you find, how to organize and use the information you discover, how to understand your metacognition—these are all critical parts of being literate as well. In this talk Russell review what literacy is today, in the age of Google, and show how some very surprising and unexpected skills will turn out to be critical in the years ahead. Daniel M. Russell is the Über Tech Lead for Search Quality and User Happiness for Google where he studies how people search for and organize information. He earned his PhD in computer science at the University of Rochester (NY), specializing in artificial intelligence until he realized that magnifying and understanding human intelligence was his real passion. Twenty years ago he foreswore AI in favor of HI, and enjoys teaching, learning, running and music, preferably all in one day. He has worked at Xerox PARC before it was PARC.com, was in the Advanced Technology Group at Apple where he wrote the first 100 web pages for www.Apple.com using SimpleText. He has also worked at IBM as a senior research scientist, and briefly at a startup that developed tablet computers a few years before the iPad.

1 0

Colloquium speaker Alekh Agarwal Tuesday Feb 28 4:30pm
by Nicole E. Wagenblast 27 Feb '12

27 Feb '12

Computation meet Statistics: Trade-offs and fundamental limits Alekh Agarwal , University of California, Berkeley Tuesday, February 28, 2012 , 4:30 PM Computer Science Small Auditorium (Room 105) The past decade has seen the emergence of datasets of an unprecedented scale, with both large sample sizes and dimensionality. Massive data sets arise in various domains, among them computer vision, natural language processing, computational biology, social networks analysis and recommendation systems, to name a few. In many such problems, the bottleneck is not just the number of data samples, but also the computational resources available to process the data. Thus, a fundamental goal in these problems is to characterize how estimation error behaves as a function of the sample size, number of parameters, and the computational budget available. In this talk, I present two research threads that provide complementary lines of attack on this broader research agenda: lower bounds for statistical estimation with computational constraints, and (ii) distributed algorithms for statistical inference. The first characterizes fundamental limits in a uniform sense over all methods, whereas the latter provides explicit algorithms that exploits the interaction of computational and statistical considerations in a distributed computing environment. [Joint work with John Duchi, Pradeep Ravikumar, Peter Bartlett and Martin Wainwright] Alekh Agarwal is a fifth year PhD student at UC Berkeley, jointly advised by Peter Bartlett and Martin Wainwright. Alekh has received PhD fellowships from Microsoft Research and Google. His main research interests are in the areas of machine learning, convex optimization, high-dimensional statistics, distributed machine learning and understanding the computational trade-offs in machine learning problems.

1 1

4:30pm Thu Mar 1 talk by Prateek Mittal in E-Quad B205
by Jennifer Rexford 24 Feb '12

24 Feb '12

> > > Speaker: > Prateek Mittal, UIUC > Title: > Trustworthy Communications Using Social Networks > Day: > Thursday, March 1, 2012 > Time: > 4:30 pm > Room: > B205, E-Quad > > Abstract: > Internet systems and applications are shifting towards a participatory paradigm, where users contribute content and resources. Popular examples include reputation systems such as Yelp, peer-to-peer networks, Web 2.0 applications like Wikipedia, and online forums such as Slashdot. These applications, however, struggle with the concepts of identity and trust, as it is easy to create a large number of pseudonyms (called Sybils) that join the system and disrupt its functionality. In this talk, I will outline two mechanisms for defending against the Sybil attack. A common theme in these mechanisms is the use of social network trust relationships to validate user identities. Such an approach forces the adversary to inﬁltrate users’ trusted social circles, presenting a signiﬁcant barrier for attack. > > First, I will present SybilInfer, an algorithm for labeling nodes in a social network as honest users or Sybils controlled by an adversary. SybilInfer uses a combination of Bayesian inference and Monte-Carlo techniques to perform a global analysis of the entire social graph to isolate attackers. Second, I will present X-Vine, a mechanism that enables users in a social network to efficiently communicate with each other, while resisting Sybil attacks. X-Vine is scalable, preserves the privacy of users’ social network contacts, and provides a basis for pseudonymous communication. Finally, I will conclude by highlighting the potential for leveraging social networks in the design of trustworthy communication systems that improve user security and privacy. > > Bio: > Prateek Mittal is a Ph.D. Candidate in Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign. His research in security and privacy focuses on computer networks and distributed systems, with an emphasis on social networks and Internet protocols. He is also interested in applications of network modeling and analysis techniques to interdisciplinary settings, especially cancer genomics. He received the M.E. Van Valkenburg graduate research award for outstanding doctoral research, the Rambus Computer Engineering fellowship, and the ACM CCS 2008 outstanding paper award. He earned his M.S. in Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign and a B.Tech. in Computer Science and Engineering at the Indian Institute of Technology, Guwahati. > > Host: Ruby Lee > > > > > > > > >

1 0

S Gerrish preFPO
by Melissa M. Lawson 23 Feb '12

23 Feb '12

Sean Gerrish will present his preFPO on Wednesday February 29 at 2:30PM in Room 402. The members of his committee are: David Blei, advisor; Rob Schapire and Hanna Wallach (UMass), readers; Kosuke Imai (POL) and Matthew Salganik (SOC), nonreaders. Everyone is invited to attend his talk. His abstract follows below. --------------------------- Title: Patterns of influence and decision-making in politics and foreign relations The past several decades have seen an explosion of digitized information in fields such as political science. In this period, a variety of statistical tools have been developed to better understand patterns in these records by incorporating information such as records of behavior and the text of documents. In this talk, I will present several recent statistical models for discovering patterns in digital records in the fields of politics, bibliometrics, and international relations. These models, which emphasize topic modeling, will link legislative text to voting patterns, written judges' opinions to citations of these opinions, and the text of newspaper articles to countries' international relations. I will also describe details of approximate posterior inference for these models, and will briefly touch upon advances in such methods. This talk includes ongoing work.

1 0

Colloquium Speaker Alekh Agarwal TuesFeb 28, 4:30pm
by Nicole E. Wagenblast 22 Feb '12

22 Feb '12

Computation meet Statistics: Trade-offs and fundamental limits Alekh Agarwal , University of California, Berkeley Tuesday, February 28, 2012 , 4:30 PM Computer Science Small Auditorium (Room 105) The past decade has seen the emergence of datasets of an unprecedented scale, with both large sample sizes and dimensionality. Massive data sets arise in various domains, among them computer vision, natural language processing, computational biology, social networks analysis and recommendation systems, to name a few. In many such problems, the bottleneck is not just the number of data samples, but also the computational resources available to process the data. Thus, a fundamental goal in these problems is to characterize how estimation error behaves as a function of the sample size, number of parameters, and the computational budget available. In this talk, I present two research threads that provide complementary lines of attack on this broader research agenda: lower bounds for statistical estimation with computational constraints, and (ii) distributed algorithms for statistical inference. The first characterizes fundamental limits in a uniform sense over all methods, whereas the latter provides explicit algorithms that exploits the interaction of computational and statistical considerations in a distributed computing environment. [Joint work with John Duchi, Pradeep Ravikumar, Peter Bartlett and Martin Wainwright] Alekh Agarwal is a fifth year PhD student at UC Berkeley, jointly advised by Peter Bartlett and Martin Wainwright. Alekh has received PhD fellowships from Microsoft Research and Google. His main research interests are in the areas of machine learning, convex optimization, high-dimensional statistics, distributed machine learning and understanding the computational trade-offs in machine learning problems.

1 0

Colloquium Speaker Michael Bernstein Wed Feb 22 4:30pm
by Nicole E. Wagenblast 21 Feb '12

21 Feb '12

Crowd-Powered Systems Michael Bernstein , MIT Wednesday, February 22, 2012 , 4:30 PM - 5:30 PM Computer Science Small Auditorium (Room 105) Crowd-powered systems combine computation with human intelligence, drawn from large groups of people connecting and coordinating online. These hybrid systems enable applications and experiences that neither crowds nor computation could support alone. Unfortunately, crowd work is error-prone and slow, making it difficult to incorporate crowds as first-order building blocks in software systems. I introduce computational techniques that decompose complex tasks into simpler, verifiable steps to improve quality, and optimize work to return results in seconds. These techniques advance crowdsourcing into a platform that is reliable and responsive to the point where crowds can be used in interactive systems. In this talk, I will present two crowd-powered systems to illustrate these ideas. The first, Soylent, is a word processor that uses paid micro-contributions to aid writing tasks such as text shortening and proofreading. Using Soylent is like having access to an entire editorial staff as you write. The second system, Adrenaline, is a camera that uses crowds to help amateur photographers capture the exact right moment for a photo. It finds the best smile and catches subjects in mid-air jumps, all in realtime. These systems point to a future where social and crowd intelligence are central elements of interaction, software, and computation. Michael Bernstein is a PhD candidate in Computer Science at the Massachusetts Institute of Technology. His research in human-computer interaction focuses on crowdsourcing and social computing systems. He has been awarded Best Student Paper at UIST 2010, Best Paper at ICWSM 2011, the NSF graduate research fellowship and the Microsoft Research PhD fellowship. His work has appeared in venues like the New York Times, Slate, CNN and The Atlantic. He earned his masters in Computer Science at MIT, and a bachelors degree in Symbolic Systems at Stanford University.

1 1

Colloquium Speaker Ohad Shamir Tues Feb 21 4:30pm
by Nicole E. Wagenblast 17 Feb '12

17 Feb '12

Machine Learning: Higher, Faster, Stronger Ohad Shamir , Microsoft Research New England Computer Science Small Auditorium (Room 105) Tuesday, February 21, 2012 , 4:30 PM - 5:30 PM Over the past decade, machine learning has emerged as a major and highly influential discipline of computer science and engineering. As the scope and variety of its applications increase, it faces novel and increasingly challenging settings, which go beyond classical learning frameworks. In this talk, I will present two recent works which fall under this category. The first work introduces a new model of sequential decision making with partial information. The model interpolates between two well-known online learning settings ("experts" and multi-armed bandits), and trades-off between the information obtained per round and the total number of rounds required to reach the same performance. The second work discusses the problem of parallelizing gradient-based learning algorithms, which is increasingly important for web-scale applications, but is highly non-trivial as these algorithms are inherently sequential. We show how this can be done using a generic and simple protocol, prove its theoretical optimality, and substantiate its performance experimentally on large-scale data. Ohad Shamir is a postdoctoral researcher at Microsoft Research New England. He joined Microsoft in 2010 after receiving a Ph.D. in computer science from the Hebrew university, advised by Prof. Naftali Tishby. His research focuses on machine learning, with emphasis on novel algorithms which combine practical applicability and theoretical insight. His work was recognized by several awards, such as the Hebrew University's Schlomiuk Ph.D. thesis prize, the COLT 2010 best paper award, and the Wolf foundation scholarship.

1 0

B Kapicioglu preFPO
by Melissa M. Lawson 16 Feb '12

16 Feb '12

Berk Kapicioglu will present his preFPO on Wednesday February 22 at 11AM in Room 402. The members of his committee are: Rob Schapire, advisor; David Blei and Tony Jebara (Columbia), readers; Jennifer Rexford and Andrea LaPaugh, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ----- Original Message ----- Title: Applications of Machine Learning to Location Data. Abstract: First, we introduce a new graphical model for tracking radio-tagged animals and learning their movement patterns. The model provides a principled way to combine radio telemetry data with an arbitrary set of user-deﬁned, spatial features. We describe an efﬁcient stochastic gradient algorithm for ﬁtting model parameters to data and demonstrate its eﬀectiveness via asymptotic analysis and synthetic experiments. We also apply our model to real datasets, and show that it outperforms the most popular radio telemetry software package used in ecology. We conclude that integration of different data sources under a single statistical framework, coupled with appropriate parameter and state estimation procedures, produces both accurate location estimates and an interpretable statistical model of animal movement. Second, we present the “Place Discovery” problem, where the goal is to provide a context-dependent and personalized ranking of nearby places. To the best of our knowledge, we are the first to pose this as a machine learning problem. We provide a new matrix approximation algorithm that leverages implicit bipartite ranking and spatial constraints. We demonstrate on real location datasets that our methods significantly improve on the amount of personalization achieved by state-of-the-art matrix approximation methods, such as Maximum-Margin Matrix Factorization. Lastly, we talk about “Location Prediction”. Here, the goal is to predict the coordinates (i.e. latitude and longitude) of a user at an arbitrary time in the future. We design an unsupervised hierarchical Bayesian graphical model for location prediction that learns natural topics such as home and work from unlabeled location data. We apply our model both to data gathered from mobile applications, where there are many users but each user has sparse location points, and to data gathered from cellular carriers. Our model outperforms existing methods in both cases.

1 0