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



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
Contacting the Center

Document last modified on September 20, 2001.