DIMACS Mixer Series - October 12, 2000

AT&T Labs, Florham Park, NJ



Eldar Fischer
NEC Research Institute-DIMACS Postdoc

Testing graphs for colorability properties

A property $P$ of graphs is called testable if for every $\epsilon$ there exists a randomized algorithm which, by making $C(\epsilon)$ queries about vertex pairs of an input graph $G$ with $n$ vertices, distinguishes with high probability between the case of $G$ satisfying $P$ and the case that it has to be modified by adding and removing more than $\epsilon n^2$ edges to make it satisfy $P$.

Goldreich, Goldwasser and Ron showed that certain graph properties, like $k$-colorability are testable. A version of the Regularity Lemma of Szemeredi which is suitable for obtaining results about the existence of certain induced subgraphs, allows one to show that all properties describable by any of several generalized notions of colorability are testable.

This talk presents the above lemma and some of its applications, starting with a coloring notion used in a joint work with Alon Krivelevich and Szegedy to show that certain first order graph properties are testable, and proceeding to its generalizations.


Felix Lazebnik
University of Delaware

On Properties of Graphs Defined by Systems of Equations In this talk we present a simple method for constructing infinite families of graphs defined by a class of systems of equations over finite fields (or just arbitrary commutative rings). We show that the graphs in all such families possess some general properties including regularity and bi-regularity, existence of special vertex colorings, and existence of covering maps --- hence, embedded spectra --- between every two members of the same family. Another general property, recently discovered, is that nearly every graph constructed in this manner edge-decomposes either the complete, or complete bipartite, graph which it spans. In many instances, specializations of these constructions have proved useful in various graph theory problems, but especially in many extremal problems concerning dense graphs with forbidden cycles or of high girth, and Ramsey type problems. A part of the talk is a survey of the results (old and new) obtained by using these constructions and of the origins of the method.


Bruce Moision
NEC Research Institute-DIMACS Postdoc

Symbolic dynamics and constrained codes Constrained codes are a part of almost every magnetic or optical storage device. Questions related to the construction of encoders and decoders and the achievable rates of constrained codes may be answered by the theory of symbolic dynamics. We discuss some problems which were motivated by practical questions in the design of constrained codes.


Nicolas Schabanel

Wireless data delivery

New technologies imply new problems. Here is some algorithmic solutions proposed to broadcast information over wireless mediums taking advantages of the particular features of this medium.


Venkatesh Srinivasan
DIMACS-Institute for Advanced Study Postdoc

The static membership problem in the bitprobe model

We consider the following data structure problem in the bitprobe model: Given a set of keys drawn from a big universe, store it so that membership queries can be answered efficiently. We shall describe schemes to solve this problem in the bitprobe model. We show that deterministic schemes for this problem show a time-space tradeoff behaviour while randomized schemes do simultaneously well in space and time.


Xiaodong Sun
Graduate Student, Rutgers

Explicit Interpolation Sets Using Perfect Hash Families

Let S be a set of functions with common domain D. We call X, a subset of D, an interpolation set for S if the values on X uniquely determine a function f in S. Small interpolation sets have useful applications in learning theory and combinatorial group testing. Recently, Piotr Indyk showed by probabilistic method the existence of interpolation sets of size $O(k^2 \log k \log n)$ for the class $S^n_k$ consisting of Boolean functions on $n$ variables that are symmetric functions on a subset of at most $k$ variables. Indyk also gave an explicit construction of interpolation sets of size $O(k^4 \log ^4 n)$ for $S^n_k$. We have a variant of Indyk's method to get an explicit construction of interpolation sets of size $O(k^{10}\log n\log\log n/\log\log\log n)$ for this class of functions.


Eric van den Berg
DIMACS Member, Telcordia Technologies

Modeling Heavy Tailed Time Series An important topic in time series analysis is how to deal with data which exhibit features like long range dependence, nonlinearity and heavy tails. Many datasets from fields such as telecommunications, finance and economics appear to be compatible with the assumption of heavy tailed mariginal distributions. Examples include file lengths, CPU times to complete a job, interarrival times between packets in a network and lengths of on/off cycles. Traditionally autoregressive moving average (ARMA) models have been succesfully applied to model datasets with light tailed noise variables, even when the underlying stochastic process is not quite linear. However, for heavy tailed datasets the ARMA class of models does not appear to be rich enough to model the dependency structure in the data. Moreover, a misguided attempt to fit such a model to heavy tailed datasets anyway can be quite misleading.

Document last modified on October 4, 2000.