DIMACS Fall Mixer, Monday, November 25, 2013


Hao Huang, IAS/DIMACS Postdoc

Title: The Inducibility of Directed Graphs

In modern extremal combinatorics, a substantial number of problems study the asymptotic relations between densities of subgraphs. One particularly interesting topic called inducibility is to find the maximum possible induced density of a given subgraph. We study this problem in the digraph setting, and solve the inducibilities for all the complete bipartite digraphs. Our result confirms a conjecture by Falgas-Ravry and Vaughan, and provides the first known explicit instance of density problem for which one can prove extremality of an iterated blow-up construction.

David S. Johnson, Organizer, DIMACS implementation Challenge Series

Title: The TSP for random points in the unit square: an experimental and statistical study

Instances of the Traveling Salesman Problem (TSP) that are generated by placing cities uniformly at random within the unit square provide reasonable surrogates for the instances arising in many real-world TSP applications. They are also an interesting object of study on their own.

The optimal tour length is known to grow as c\sqrt{n} for some constant c, but the exact value of c and the details of the convergence rate have not been determined. In this talk I report on an ongoing study of this and related questions with David Applegate and Bill Cook, based on experiments with millions of instances using the Concorde software package. Interesting statistical questions arise.

Janne Lindqvist, ECE

Title: Nudging People with Computer Systems

Computer systems today affect directly or indirectly billions of people. For example, using mobile phones directly integrates computer systems into people daily lives. In this talk, I will present my research program on redesigning computer systems for detecting and nudging behavior change. We will discuss how to redesign mobile phone platforms to make privacy-sensitive sensor access (e.g. localization) transparent to users, and how this affects their behavior. We will also discuss how similar approaches can be used for other important societal purposes including password security, mitigating distracted driving and bringing people together in local communities.

Dr. Janne Lindqvist is an assistant professor of Electrical and Computer Engineering and a member of DIMACS and WINLAB at Rutgers University. Janne directs the Rutgers Human-Computer Interaction group. From 2011-2013, Janne was an assistant research professor of ECE at Rutgers. Prior to Rutgers, Janne was a post-doc with the Human-Computer Interaction Institute at Carnegie Mellon University School of Computer Science. Janne received his M.Sc. degree in 2005, and D.Sc. degree in 2009, both in Computer Science and Engineering from Helsinki University of Technology, Finland. He works at the intersection of human-computer interaction, mobile computing and security engineering. Before joining academia, Janne co-founded a wireless networks company, Radionet, which was represented in 24 countries before being sold to Florida-based Airspan Networks in 2005. His work has been featured several times in MIT Technology Review and recently also in New York Times, phys.org Tech Republic, and other online venues. During his first year at Rutgers, Janne was awarded three NSF grants totaling nearly $1.3 million and a MobiCom best paper award.

Pratyusa K.Manadhata, HP

Title: Big data analytics for security

This is the age of big data. Enterprises collect large amounts of data about their operations and analyze the data to improve all aspects of their businesses. Big data analytics for security, i.e., the analysis of very large enterprise data sets to identify actionable security information and hence to improve enterprise security, however, is a relatively unexplored area. In this talk, we highlight the challenges and opportunities in big data analytics for security and present a few examples in industrial settings.

Tom Ostrand, Dimacs visitor

Title: Models for Software Fault Prediction

Using data from empirical studies of 170 releases of nine large industrial software systems, we developed and evaluated a negative binomial regression model (the Standard Model) that ranks files in decreasing order of their expected fault counts in the next release of a system. For the nine systems studied, the top 20% of files in the predicted rankings included 75-94% of the actual faults in the next release.

The Standard Model uses a surprisingly simple set of input variables that include characteristics of the next release's code, and counts of changes and faults detected in past releases. Augmented models that use additional input variables yielded either very slight or no improvement over the Standard Model's results.

Shubhangi Saraf, Rutgers University

Title: Incidence Geometry and Connections to Theoretical Computer Science

The classical Sylvester-Gallai theorem states the following: Given a finite set of points in the Euclidean plane, if the line through every pair of points passes through a third point, then all points must be collinear. Thus basically the result shows that many `local' linear dependencies implies a `global' bound on the dimension of the entire set of points. Variations of these questions have been well studied in additive combinatorics and incidence geometry. In the last few years, similar questions have also found applications in several structural results in theoretical computer science. In this talk I will describe some of the applications and connections in theoretical computer science to areas such as polynomial identity testing and local algorithms for error correcting codes.

Based on joint works with Albert Ai, Zeev Dvir, Neeraj Kayal, Avi Wigderson.