Werner Backes, Stevens Institute of Technology
URL: http://www.cs.stevens.edu/~wbackes

Title: The xGCC analysis tool

In this talk, I will present the xGCC analysis tool for the verification of safety properties of the XRTL intermediate language. These properties include the absence of buffer overflow, division by zero and the use of uninitialized variables and memory. XRTL is an extension of the Register Transfer Language (RTL) generated by a modified GCC. Abstract interpretation is used for the analysis of XRTL. We introduce approximation by lists of valid intervals for the abstraction of sets of registers and memory blocks. Branching conditions are taken into account for restricting the search space, and widening/narrowing techniques are used to speed up the fixpoint computation for XRTL loops.

Title: Pseudorandom generators for low degree polynomials

Algorithmic derandomization studies whether the output of randomized computations is affected when the random source is replaced with a pseudorandom source that uses much less randomness. For a fixed class of computations, the amount of randomness that must be used by the pseudorandom source can be lower bounded by a counting argument. A pseudorandom source is considered "optimal" if the amount of randomness it uses matches this lower bound. There are only few classes of computations for which efficient constructions of close to optimal pseudorandom sources are known. I will present a construction of such sources for the class of computations described by low-degree polynomials over a sufficiently large field.

Alexei Myasnikov, Stevens Institute of Technology

Title: Cryptography and Generic Complexity

In this talk, I will discuss theoretical foundations of computational security of modern cryptosystems. It has been understood for many years that the standard notions of "hardness" of computations, such as undecidability, the worst and average case complexities, do not apply here. The important property for cryptographic security is generic complexity, i.e., complexity of algorithms on "random" or "most typical" inputs. However, this notion of generic complexity has not been well understood. The focus of the talk will be on the generic complexity of several famous algorithmic problems and their possible applications to cryptography.

Baruch Schieber, IBM

Title: Traffic Engineering of Management Flows by Link Augmentations on Confluent Trees

Service providers rely on the management systems housed in their Network Operations Centers (NOCs) to remotely operate, monitor and provision their data networks. Lately there has been a tremendous increase in management traffic due to the growing complexity and size of the data networks and the services provisioned on them. Traffic engineering for management flows is essential for the smooth functioning of these networks to avoid congestion, which can result in loss of critical data such as billing records, network alarms, etc. As is the case with most intra-domain routing protocols, the management flows in many of these networks are routed on shortest paths connecting the NOC with the service provider's POPs (points of presence). This collection of paths thus forms a ``confluent'' tree rooted at the gateway router connected to the NOC. The links close to the gateway router may form a bottleneck in this tree resulting in congestion. Typically this congestion is alleviated by adding layer two tunnels (virtual links) that offload the traffic from some links of this tree by routing it directly to the gateway router. The traffic engineering problem is then to minimize the number of virtual links needed for alleviating congestion.

In this talk we formulate a traffic engineering problem motivated by the above mentioned applications. We show that the general versions of this problem are hard to solve. However, for some simpler cases in which the underlying network is a tree, we design efficient algorithms. We use these algorithms as the basis for designing efficient heuristics for alleviating congestion in general (non-tree) service provider network topologies.

This is joint work with Randeep Bhatia, Nicole Immorlica, Tracy Kimbrel, Vahab Mirrokni, and Seffi Naor

Ivan Zorych, DIMACS postdoc

Title: A Bayesian Approach to Wireless Location Problems

Several approaches for indoor location estimation in wireless networks are proposed. We explore non-hierarchical and hierarchical Bayesian graphical models that use prior knowledge about physics of signal propagation, as well as different modifications of Bayesian bivariate spline models. The hierarchical Bayesian model that incorporates information about locations of access points achieves accuracy that is similar to other published models and algorithms, but by using prior knowledge, this model drastically reduces the requirement for training data when compared to existing approaches. Proposed Bayesian bivariate spline models for location surpass predictive accuracy of existing methods. It has been shown that different versions of this model, in combination with sampling/importance resampling and particle filter algorithms, are suitable for the real-time estimation and tracking of moving objects. It has been demonstrated that "plug-in" versions of the bivariate Bayesian spline model perform as good as the full Bayesian version. A combination of two Bayesian models to reduce the maximum predictive error is proposed. Models presented in this work utilize MCMC simulations in directed acyclic graphs (DAGs) to solve ill-posed problem of location estimation in wireless networks using only received signal strengths. Similar approaches may be applied to other ill-posed problems.

Joint work with David Madigan, Rutgers University