Raissa d'Souza
Bell Labs-DIMACS Postdoc
Modeling physics with discrete reversible lattice dynamics
Simple microscopic dynamics can capture essential aspects of physics, such as locality, microscopic reversibility, and conservation laws. From such simple microscopic dynamics we can observe the emergence of complex macroscopic physical phenomena. I will first discuss a well known microscopic model of particle collisions which, in the macroscopic limit, obeys the equations of hydrodynamics. Then I will illustrate the use of such models as a laboratory for studying nonequilibrium thermodynamics via a model of pattern formation in a closed system. In this model we observe the initial growth of bushy fractal clusters (resembling frost on a window pane), then the slow approach to thermodynamic equilibrium during which the cluster structures anneal and undergo a transition to structures resembling branched polymers.
Steve Fortune
Bell Labs
Polynomial Root Finding Using Iterated Eigenvalue Computation
Computing numerical approximations to the roots of a univariate polynomial is a classic problem from numerical analysis and symbolic algebra. I present a novel iterative algorithm that combines floating-point linear algebra with extended-precision arithmetic. Given a current estimate of the roots, the algorithm constructs a generalization of a companion matrix of the polynomial-- actually an eigenvalue formulation of Lagrange interpolation. The eigenvalues of the matrix, computed in floating-point with standard numerical methods, form the new estimate of the roots. Perhaps surprisingly, the iteration converges to approximations of the roots accurate to floating-point precision. The algorithm has been successfully applied to very hard and ill-conditioned polynomials, e.g. the Wilkinson polynomial of degree 600. In practice, the algorithm appears to be an order of magnitude faster than the best alternatives.
Ashwin Nayak
DIMACS-AT&T Postdoc
The constant round quantum communication complexity of Set Disjointness
Since Buhrman, Cleve, and Wigderson (FOCS 98) showed that the Set-Disjointness problem could be solved by exchanging O(sqrt(n)) quantum bits (as opposed to Theta(n) classical bits), several attempts have been made to pin down the quantum communication complexity of the problem. I will talk about a polynomial lower bound for the problem obtained by studying quantum communication in a constant number of rounds.
David Shallcross
DIMACS Member, Telcordia Technologies
Inferring network topology from packet delay data, and related problems
I will describe a project that involves inferring IP network topology and performance from packet delay and loss data between selected monitor points. I discuss specific mathematical problems that arise, some variations on these problems, and some approaches to solving these problems.
Cliff Smyth
Rutgers University, Department of Mathematics
Some Correlation Inequalities and Applications
We prove a dual version of Reimer's inequality (a.k.a the van den Berg Kesten conjecture), outline some applications (a solution of Rudich's Conjecture among others), present an inequality of which Reimer's inequality and our dual inequality is a special case.
Martin Strauss
AT&T Labs
Secure Multiparty Computation of Approximations
Approximation algorithms can sometimes be used to obtain efficient solutions where no efficient exact computation is known. Furthermore, for some applications, several parties will want to cooperate to compute a function of their inputs without revealing more information than necessary. For the first time, we present definitions and protocols of secure multiparty approximate computation that show how to realize most of the cost savings available by using an approximation instead of an exact computation of a function, f, without revealing more than necessary to compute f exactly.
We make three contributions. First, we give formal definitions of secure multiparty approximate computations. Second, we introduce some general techniques for constructing secure multiparty approximations. Finally, we present an efficient, sublinear-communication, private approximate computation for the Hamming and L^1 distances.
This is joint work with Joan Feigenbaum, Jessica Fong, and Rebecca Wright.
Mahesh Viswanathan
DIMACS-Telcordia Postdoc
Checking Properties for Massive Data Sets
Massive data sets are increasingly important in a wide range of applications including observational sciences, product marketing, and monitoring and operations of large systems. Furthermore, massive data sets are often distributed: Several different, physically separated data sets may together comprise one logical data set. The enormous scale, and distributed nature of the data sets of interest must be addressed with new algorithmic techniques.
In this talk, we consider an important class of problems that is closely tied with the analysis and validation of software systems, namely, checking if data sets have certain properties. We discuss two computational models for designing algorithms. The sampling model is one where an algorithm examines very few bits of the data and checks for certain properties. In the streaming model the data is examined once sequentially, but the algorithm uses very limited space to do its computation. We present sampling and streaming algorithms for some illustrative, pragmatic examples.