David Johnson, AT&T Labs - Research

Title: The Combinatorics of Anonymity

Suppose we are given n buckets with varying integral sizes, and wish to fill some fraction alpha of them will balls, with a bucket of size k being filled as soon as it receives k balls. Our goal is to minimize the number of balls used.

If we know the sizes of the buckets, this is a trivial problem: Just identify the (alpha)n smallest buckets, and fill them. But what if we do not know the sizes of the buckets in advance, and after each ball placement only find out whether the bucket is now full or not?

This problem models a cryptographic question. Suppose an adversary wishes to prevent a multiparty protocol from succeeding. Typically with such protocols, the adversary need only corrupt half (or a third) of the parties to attain its goal. But suppose each party is protected by a sequence of some number of cryptographic walls, each of which requires a certain amount of computation to break through. If parties have differing numbers of walls, and the adversary does not know how many walls a given party has until it breaks through the last one, we get our balls-and-buckets problem.

This cryptographic connection is formalized in a paper I've written with Juan Garay, Aggelos Kiayis, and Moti Yung. Here I will concentrate on the combinatorial side, giving algorithms for the adversary (bucket filler) in the presence various levels of partial information about the sizes, and near-matching lower bounds on what is possible, both for deterministic and randomized algorithms.

Paul Kantor, Rutgers University

Title: Homeland Security Research at Rutgers and Fred Roberts

Following the 9/11 attacks, Fred Roberts was one of a small group of highly respected research leaders who were invited to Washington to initiate a new method of funding research related to national security issues, using the NSF grant review mechanism to quickly screen and initiate projects. The DIMACS proposals were immediately successful. The talk will discuss one thread of that research, which involves the application of machine learning, operations research and information retrieval techniques to problems as diverse as monitoring message streams, identifying authors, detecting nuclear threats at ports and borders, and spotting small-scale threats in an urban environment. The work has been very productive, and has led to two major centers, DyDAn and then CCICADA, as well as other DIMACS projects supported by the Department of Homeland Security and the Intelligence Advanced Research Projects Activity (IARPA). This talk will explore the connections, and astonishing breadth of several of those projects. Some currently unsolved problems will be highlighted.

Henry Pollak, Columbia University

Title: Mathematical Modeling and its Teaching - A Systems Point of View

We will have a look at the following topics, and how they impact on one another:

The history of the teaching of mathematical modeling The relation to applied mathematics and to word problems The inherent contradiction in the teaching of modeling The education of mathematics teachers to teach modeling Past and present efforts and barriers to success Honoring both Research and Development What if all else fails - alternate visions of the future

Robert Sedgewick, Princeton University

Title: From Analysis of Algorithms to Analytic Combinatorics

Analytic Combinatorics aims to enable precise quantitative predictions of the properties of large combinatorial structures. Primarily due to the efforts of Philippe Flajolet and his many research collaborators, the theory has emerged over recent decades as essential both for the scientific analysis of algorithms in computer science and for the study of scientific models in many other disciplines, including probability theory, statistical physics, computational biology and information theory. This talk surveys thirty years of joint work with Flajolet that was inspired by learning the analysis of algorithms from Knuth and that culminated in the publication of two books: "An Introduction to the Analysis of Algorithms" and "Analytic Combinatorics".

Eduardo Sontag, Rutgers University

Title: From balanced signed graphs to monotone systems in systems biology

In several papers, as well as in his 1977 book "Graph Theory and its Applications to Problems of Society", Fred studied the problem of balancing of signed graphs and its application in sociology and other fields. In these applications, a negative edge typically indicates a "dislike" between two individuals, while a positive edge corresponds to a "like" relationship. A graph is balanced if every undirected path has a net positive sign. We show in this talk how these same notions, when translated to genes, proteins, and other molecular species, for which positive and negative edges indicate "activation" and "inhibition" respectively, can be used to provide powerful tools for the analysis of the dynamics of bio-molecular systems.

Robert E. Tarjan, Princeton University

Title: Incremental Topological Ordering

A classical result of graph theory states that a directed graph is acyclic if and only if it has a topological order, an order of the vertices such that each arc leads from a smaller to a larger vertex. Given a graph, one can find such an order (and test for the existence of a cycle) in linear time, using either depth-first search or successive removal of vertices with no incoming arcs. But suppose the graph is built an arc at a time? Can one efficiently maintain a topological order and test for cycles incrementally, as the graph is built? This talk will describe recent work on this problem by M. Bender, J. Finemanm S. Gilbert, and the speaker.

Rebecca Wright, DIMACS

Title: Cryptography, Privacy, and Security at DIMACS

In this talk, I will talk about some past, present, and future activities at DIMACS relating to cryptography, privacy, and security. I will also spend some time discussing what you can do for DIMACS and what DIMACS can do for you.