1.

**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**

DIMACS/ATT Postdoc

*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.