DIMACS Mixer Series - Mixer I

September 21, 2001
AT&T Labs - Research, 180 Park Avenue, Building 103, Room B104, First Floor, Florham Park, New Jersey

Abstracts:

1.

Gabriela Alexe, Rutgers University 
Consensus algorithms for the generation of all maximal bicliques

Authors: Gabriela Alexe (Rutgers University), Sorin Alexe (Rutgers
University), Yves Crama (University of Liege, Belgium), Stephan Foldes
(Tampere University of Technology, Finland),  Peter L. Hammer (Rutgers
University), Bruno Simeone (''La Sapienza'' University, Italy)

Abstract: We describe a new algorithm for generating all maximal bicliques
(i.e. complete bipartite, not necessarily induced subgraphs) of a graph.
The algorithm is inspired by, and is quite similar to, the consensus
method used in propositional logic. We show that some variants of the
algorithm are totally polynomial, and even incrementally polynomial. The
total complexity of the most efficient variant of the algorithms presented
here is polynomial in the input size, and only linear in the output size.
Computational experiments demonstrate its high efficiency on randomly
generated graphs with up to 2,000 vertices and 20,000 edges. 

Joint work with Sorin Alexe, Yves Crama, Stephan Foldes, Peter L. Hammer 
and Bruno Simeone.



2.

Title: Relationships in High-Dimensional Classifiers

Ofer Melnik

Abstract:

A successfully trained classifier has taken examples of a class and
found a common description of the examples that allows it to
generalize to unseen inputs. In that common description the classifier
expresses the relationships that it has found between the members of
the class. These relationships encompass the basic properties
associated with being in that class.  For decision-region type
classifiers, such as neural networks or decision trees, these
relationships may be hidden within the intrinsic complexity of the
underlying models (the black-box problem). Decision Region
Connectivity Analysis (DRCA) is a general method to extract these
relationships as expressed by the decision region structure of these
models. The method's strongest suits are its independence of model
type or dimensionality, allowing it be applied across different model
types of very high dimensionality. In this talk I'll present the core
DRCA method that allows the analysis of relationships within a class
(intraclass), but also touch upon new research into examining
relationships between different classes (interclass) in
high-dimensional classifiers.



3.

Detlef Ronneburger, Rutgers University
Relationships between Komogorov Complexity
  and Circuit Complexity and some consequences


Abstract:

   In this talk we present work in progress regarding
   the relationship between the time-bounded Kolmogorov
   Complexity of a string x of length N=2^n and
   the circuit complexity of x when viewed as the 
   characteristic string of an n-ary Boolean function.
   We consider some consequences of these observations
   in the contex of derandomization.



4.

Emina Soljanin, Bell Labs
WRITING SEQUENCES ON THE PLANE

The problem of arranging  two dimensional arrays of data into one
dimensional sequences comes up in image  processing, color 
quantization, and optical and magnetic data recording. A good 
arrangement should enable the one dimensional sequences to be
modeled as Markov chains or shifts of finite type. Since this is 
not possible in general, two dimensional data is most commonly 
scanned by rows, columns, or diagonals.

We look into three unusual ways to write a sequence in the plane: 
by Penrose tilings, by space filling curves, and by cylindrical and 
spiral lattices. We show how Penrose tilings can be used to record 
information and how some spiral lattices can be used for quantization 
of color spaces.



5.

Compact Oracles for Reachability and Approximate Distances
in Planar Digraphs

Mikkel Thorup
AT&T Labs - Research, Shannon Laboratory
180 Park Avenue, Florham Park, NJ 07932, USA
mthorup@research.att.com


It is shown that a planar digraph can be preprocessed in near-linear
time, producing a near-linear space distance oracle that can answer
reachability queries in constant time. The oracle can be distributed as
an $O(\log n)$ space label for each vertex and then we can determine
if one vertex can reach another considering their two labels only.

The approach generalizes to approximate distances in weighted planar
digraphs where we can then get a $(1+\eps)$ approximation distance
in $O(\log\log \Delta+1/\eps)$ time where $\Delta$ is the longest
finite distance in the graph and weights are assumed
to be non-negative integers. Our scheme can be extended to 
find and route along the short dipaths.

Our technique is based on a novel {\em dipath decomposition of planar
digraphs\/} that instead of using the standard separator with
$O(\sqrt{n})$ vertices, in effect finds a separator using a constant
number of dipaths.

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage