^January February – 2007 ^March

The talk summarized my Ph.d thesis and presents various distributed storage solutions. From distributed file systems to long-term large scale peer-to-peer storage networks. I will focus on how to achieve asynchronous consensus among processors in presence of crashes (using a failure detector).

Self-stabilizing algorithms can cope with transient faults. Transient faults can alter the system state to an arbitrary state and hence, cause a temporary violation of the algorithm correctness. Our algorithms can be started in an arbitrary state. Thus, can converge to their designed behavior. The talk will focus on a self-stabilizing failure detector, asynchronous consensus and replicated state-machine algorithm suite. We define new requirements for consensus that fit the on-going nature of self-stabilizing algorithms. The wait-free consensus (and the replicated state-machine) algorithm is a classic combination of a failure detector and a (memory bounded) rotating coordinator consensus that satisfy both eventual safety and eventual liveness. Several new techniques and paradigms are introduced. The bounded memory failure detector abstracts away synchronization assumptions using bounded heartbeat counters combined with a balance-unbalance mechanism. The practically infinite paradigm is introduced in the scope of self-stabilization, where an execution of, say, 2^64 sequential steps is regarded as (practically) infinite. Finally, we present the first self-stabilizing wait-free reset mechanism that ensures eventual safety and can be used in other scopes.

The technique of k-anonymization allows the releasing of databases that contain personal information while ensuring some degree of individual privacy. Given a database D that needs to be released, one produces a so-called k-anonymized version of that database where each record is indistinguishable from at least k-1 additional records. The anonymization process is usually performed by suppressing or generalizing database entries. We formally study the concept of generalization, and propose two information-theoretic measures for capturing the amount of information that is lost during the anonymization process. We call these two measures, the entropy measure and the non-uniform entropy measure.

The proposed measures are more eneral and more accurate than the measures that were proposed by Meyerson and Williams ([MW]),and Aggarwal et al. ([AFK]). We then study the problem of achieving k-anonymity with minimal loss of information. We prove that this problem is NP-hard and then study polynomial approximations for the optimal solution. Our first algorithm relies on similar ideas as the approximation algorithm that was proposed in [MW]. It gives an approximation guarantee of $O(ln k)$, for the entropy measure as well as for the previously studied measures. This mproves the best-known $O(k)$-approximation of [AFK]. While the approximation algorithms of [AFK] and [MW] relied on the so-called graph representation framework, which was shown in [AFK] to be limited to Omega(k)-approximations, our algorithm relies on a novel hypergraph representation that enables the improvement in the approximation ratio from $O(k)$ to $O(ln k)$.

As the running time of the algorithm is $O(n^(2k))$,we also show how to adapt the algorithm of [AFK] inorder to obtain a strongly polynomial approximation algorithm for our entropy measure with approximation guarantee of $O(k)$. We leave as an open problem to design an approximation algorithm, strongly polynomial or not, for the non-uniform entropy measure.

Joint work with Aristides Gionis

Graph theory and its applications is an exciting mathematical discipline which motivates the search for new algorithms, exact structures and combinatorial properties. To illustrate this point, consider the following simple question: When can you factor a logic (Boolean) formula, into a (logically equivalent) form in which each variable appears once and only once?

For example, the function $f = ab + acd + ace$ satisfies this property since it can be factored into the "read-once" expression $f = a(b+c(d+e))$. However, the function $h = ab + bc + cd$ does not satisfy the property.

In this talk, we will present the mathematical and computational aspects of this problem. We will show several classical characterizations of read-once functions which involve combinatorics, graph theory and properties of positive (monotone) Boolean functions. We also present the first polynomial time algorithm for recognizing and factoring read-once functions. The algorithm is based on a theorem of Gurvich and on algorithms for cograph recognition and a new efficient method for checking normality.

Finally, we raise a number of questions regarding the factoring certain non-read-once functions. In particular, we are able to show that if the co-occurrence graph of a positive Boolean function f is a tree, then the function is read-twice. However, no characterization is known for general read-twice functions.

Gene expression is directly regulated by protein transcription factors that bind at particular DNA or RNA sites in a sequence specific manner. A comprehensive characterization of these functional non-coding elements,or motifs, remains a formidable challenge, especially for higher eukaryotes.

I will present a rigorous computational methodology for ab-initio motif discovery from expression data, that utilizes the concept of mutual information, and have the following characteristics:

• directly applicable to any type of expression data, thus conceptually unifying existing motif discovery techniques,
• model-independence,i.e.,model-related assumptions commonly made by other methods are not required,
• simultaneously finds DNA motifs in upstream regions and RNA motifs in 3'UTRs and highlights their functional relations,
• scales well to metazoan genomes,
• yields very few false positive predictions if any,
• incorporates systematic analysis of the functional coherence of the predicted motifs, their conservation, positional and orientation biases, cooperativity, and co-localization with other motifs,
• displays predictions via a novel user-friendly graphical interface.

I will present results for a variety of data types, measured for different organisms, including yeast, worm, fly, mouse, human, and the Plasmodium parasite responsible for malaria. I will further discuss in detail surprising observations regarding gene expression regulation that were overlook by previous studies and naturally arise from our analysis. As a shorthand for our methodology we use the acronym FIRE, standing for Finding Informative Regulatory Elements.

Based on joint work with Olivier Elemento and Saeed Tavazoie.