Kinetic and Dynamic Data Structures for Convex Hulls and Upper Envelopes
Giora Alexandron School of Computer Science Tel Aviv University gioraa@post.tau.ac.il
Haim Kaplan School of Computer Science Tel Aviv University haimk@post.tau.ac.il
Micha Sharir School of Computer Science Tel Aviv University and Courant Institute of Mathematical Sciences New York University michas@post.tau.ac.il
Let S be a set of n moving points in the plane. We present a kinetic and dynamic (randomized) data structure for maintaining the convex hull of S. The structure uses O(n) space, and processes an expected number of O(n^{2}_{s}_{+2}(n) log n) critical events, each in O(log^{2}n) expected time, including O(n) insertions, deletions, and changes in the flight plans of the points. Here s is the maximum number of times where any specific triple of points can become collinear, _{s}(q) = _{s}(q)/q, and _{s}(q) is the maximum length of DavenportSchinzel sequences of order s on n symbols. Compared with the previous solution of Basch et al. [?], our structure uses simpler certificates, uses roughly the same resources, and is also dynamic. Dotted Interval Graphs
Yonathan Aumann BarIlan University aumann@cs.biu.ac.il
We introduce a generalization of interval graphs, which we call dotted interval graphs (DIG). A dotted interval graph is an intersection graph of arithmetic progressions (= dotted intervals). Coloring of dotted intervals graphs naturally arises in the context of high throughput genotyping. We study the properties of dotted interval graphs, with a focus on coloring. We show that any graph is a DIG, but that DIG_{d} graphs, i.e. DIGs in which the arithmetic progressions have a jump of at most d, form a strict hierarchy. We show that coloring DIG_{d} graphs is NPcomplete even for d=2. For any fixed d, we provide a 5/6d approximation for the coloring of dig_{D} graphs.
Joint work with: Moshe Lewenstein, Oren Malamud, Ron Pinter, and Zohar Yakhini
Rounding two and three dimensional solutions of the SDP relaxation of MAX CUT
Adi Avidor Tel Aviv University adi@post.tau.ac.il
Uri Zwick
Goemans and Williamson obtained an approximation algorithm for the MAX CUT problem with a performance ratio of _{GW} 0.87856. Their algorithm starts by solving a standard SDP relaxation of MAX CUT and then rounds the optimal solution obtained using a random hyperplane. In some cases, the optimal solution of the SDP relaxation happens to lie in a low dimensional space. Can an improved performance ratio be obtained for such instances? We show that the answer is yes in dimensions two and three and conjecture that this is also the case in any higher fixed dimension. In two dimensions an optimal approximation algorithm was already obtained by Goemans. (Note that 0.88456.) We obtain an alternative derivation of this result using Gegenbauer polynomials. Our main result is an improved rounding procedure for SDP solutions that lie in R^{3} with a performance ratio of about 0.8818. The rounding procedure uses an interesting yinyan coloring of the three dimensional sphere. The improved performance ratio obtained resolves, in the negative, an open problem posed by Feige and Schechtman [STOC’01]. They asked whether there are MAX CUT instances with integrality ratios arbitrarily close to _{GW} that have optimal embeddings, i.e., optimal solutions of their SDP relaxations, that lie in R^{3}.
A Citation Analysis of Michael Rabin’s Work
Judit BarIlan Department of Information Science BarIlan University and School of Library, Archive and Information Studies The Hebrew University of Jerusalem judit@cc.huji.ac.il
Michael Rabin’s first publication is from 1953 in Hebrew in the Riveon LeMatematika. ISI’s Science Citation Index (“Web of Science”) indexes 32 of his publications, starting from 1958; DBLP lists 48 papers and references to 86 publications can be found in Michael Rabin’s CV. The Science Citation Index listed 2849 citations to Michael Rabin’s work as of November, 2004. Citeseer identified 2169 citations to Michael Rabin’s work in June 2004. Based on these information sources, we are going to characterize Michael Rabin’s collaborators, citing (i.e., whom he cites) and cited patterns (i.e. who cites him). Limitations of the different information sources will also be discussed.
Adversarial Contention Resolution for Simple Channels
Michael Bender Department of Computer Science SUNY Stony Brook bender@cs.sunysb.edu
We present results analyzing the worstcase performance of randomized backoff. Specifically, an adversary chooses the packet arrival times. In contract, most analyses of backoff make statistical assumptions on packet arrivals. We give a thorough analysis of a range of backoff strategies for the special case in which all the jobs arrive at the same time. For the case of online arrivals, we assume an adversarialqueuingtheory model and prove upper and lower bounds on the average arrival rates for stability and instability of binary exponential backoff.
Joint work with: Martin FarachColton, Simai He, Bradley Kuszmaul, and Charles E. Leiserson. Prediction of Small RNA Conformational Switching Using FineGrain Graph Representations and the Wiener Index
Danny Barash University of Haifa and BenGurion University dbarash@research.haifa.ac.il
Assaf Avihoo
Conformational switching in the secondary structure of RNAs has been observed experimentally, and was recently shown to offer an economical procedure for regulation in bacteria by allosteric means. In order to detect RNA switches that occur in nature and also to devise novel artificial RNA switches, we use graph representations that correspond to the secondary structure of RNAs. Previously, it was shown that predicting selective mutations leading to topological transitions in the RNA secondary structure can be achieved by a coarsegrain Laplacian tree graph representation using its second eigenvalue. However, for small RNAs that are 50 nt long or less, such representations at the level of stems, bulges, and loops become ineffective. It is necessary to use finegrain graph representation at the level of nucleotides. Each nucleotide becomes a node in the graph and its equivalent Laplacian matrix is of the size NxN for a sequence of N nucleotides. Conformational rearrangements can be studied using measures to assess the differences between Laplacian matrices of finegrain graph representations. In finegrain graph representations, the second eigenvalue of the Laplacian matrix does not have a clear intuitive meaning as in coarsegrain tree graphs. However, it is possible to calculate the Wiener index (Merris, Linear & Multilinear Algebra 25 (1989), 291296) in order to assess the similarities between two RNA secondary structures. We show convincing results using the Wiener index along with some other similarity measures. On Matroids and Nonideal Secret Sharing
Amos Beimel Department of Computer Science BenGurion University beimel@cs.bgu.ac.il
Noam Livne
A secret sharing scheme involves a dealer who has a secret, a finite set of participants, and a collection A of subsets of the set of participants called the access structure. A secretsharing scheme for A is a method by which the dealer distributes shares to the parties such that any subset in A can reconstruct the secret from its shares, while any subset not in A cannot reveal any partial information about the secret in the information theoretic sense. Certain access structures give rise to very economical secret sharing schemes. A secret sharing scheme is called ideal if the shares are taken from the same domain as the secrets. An access structure is called ideal if there is an ideal secret sharing scheme which realizes the access structure over some finite domain of secrets. Brickell and Davenport (J. of Cryptology, 1991) have shown that ideal access structures are closely related to matroids over a set containing the participants plus the dealer. They give a necessary condition for an access structure to be ideal – the access structure must be induced by a matroid – and a somewhat stronger sufficient condition – the matroid should be representable over some finite field. Seymour (J. of Combinatorial Theory B, 1992) showed that the necessary condition is not sufficient: There exists an access structure induced by a matroid that does not have an ideal scheme. In this work we continue the research on access structure induced by matroids. Our main result in the work is strengthening the result of Seymour. We show that in any secret sharing scheme realizing the access structure induced by the Vamos matroid with domain of the secret of size k, the size of the domain of the shares is at least Our second result considers nonideal secret sharing schemes realizing access structures induced by matroids. We prove that the fact that an access structures is induced by a matroid implies lower and upper bounds on the size of the domain of shares of subsets of participants even in nonideal schemes (this generalized results of Brickell and Davenport for ideal schemes). Fast Quantum Byzantine Agreement
Michael BenOr Hebrew University benor@cs.huji.ac.il
We present a fast quantum Byzantine Agreement protocol that can reach agreement in constant expected communication rounds against a strong full information dynamic adversary, tolerating up to the optimal t faulty players in the synchronous setting, and up to t faulty players for asynchronous systems. This should be contrasted with the known classical synchronous lower bound of (\sqrt{n/\log n}) and the classical asynchronous lower bound of (n/log^{2 }n) when t=(n).
Joint work with Avinatan Hassidim. Autonomous Ontology Extraction using Hierarchical UNSO Hypercube Graph
Yosi BenAsher University of Haifa
Shlomo Berkovsky University of Haifa slavax@cs.haifa.ac.il
Yaniv Eytani University of Haifa
Data Integration is a complex process focusing on matching between similar (or identical) concepts that describe data originated from heterogeneous sources. Importance of Data Integration increases with the amount of available information as different information sources describe similar (or identical) data they provide in various different ways. In previous works we developed UNSO (UNSpecified Ontology). UNSO allows to integrate heterogeneous semantic descriptions of resources (given in form of attribute:value pairs) to a graph topology called MultiLayered Hypercube (MLH). MLH topology can be illustrated as a hypercube where each node is recursively comprised of another hypercube. UNSO effectively creates a mapping between semantic concepts and the underlying MLH graph. Similar (or identical) are mapped to vertexes in the graph that are found in close proximity. The hypercube topology inherently facilitates distributed and completely decentralized management of the resources. In this work we extend the topology developed in UNSO to create an adaptive autonomous hierarchical graph topology. We achieve it by dynamically changing the graph topology using the previously learned properties of the semantic descriptions' attributes. The graph topology evolves automatically by applying a predefined set of operators (such as splitting, shrinkage, and swapping of two adjacent hierarchical levels) on the MLH graph. This effectively creates a hierarchical graph topology where each hierarchical level correlates the relevant attributes with their relative importance in resources' descriptions. Our structure leverages the process of Data Integration through providing an efficient mean for dynamic ontology extraction basing on statistical properties of the attributes in the semantic descriptions of the resources. Connectivity and Parity
András Frank Eötvös University frank@cs.elte.hu
Parity (matching theory) and connectivity (network flows) are two main branches of combinatorial optimization. In this talk I try to overview the interrelation of these topics. We study problems where both parity and connectivity requirements are imposed. For example, a characterization is given for undirected graphs having a kedgeconnected orientation for which the indegree of every node v is congruent to q(v) (mod 2) for every ”compatible” parity prescriptions q : V {0, 1}.
Tighter Approximations on Greedy for Maximum Induced Matchings in Regular Graphs
Tzvi Gotthilf BarIlan University
and
Moshe Lewenstein BarIlan University moshe@macs.biu.ac.il
An induced matching is a matching for which each two edges in the matching are at distance >= 2. Induced matchings are wellstudied combinatorial objects and a lot of consideration has been given to finding maximum induced matchings, which is an NPcomplete problem. Specifically, finding maximum induced matchings in regular graphs is wellknown to be NPcomplete. A couple of papers lately showed a couple of simple greedy algorithm that approximate a maximum induced matching with a factor of d1/2 and d1 (different papers  different factors), where d is the degree of regularity. We show a simple greedy approach that yields an 0.8d approximation factor.
Some Relationships between Probabilistic Performance Evaluation Models
Sergey Frenkel The Institute of Informatics Problems Russian Academy of Sciences slfipiran@mtunet.ru
Probabilistic performance evaluation models are used to predict execution time of a program with stochastic behavior. In general, the probabilistic performance modelling of distributed and parallel CS includes both semantic and computational aspects. “Semantic” models are used for formal specification of the target CS. The “computational” ones are some mathematical models of the target system, quantifying the relationships established by the formal specifications. Schematically, all the analytical computational models can be sorted over task graphs and state transition based ones. In task graphs modeling a program is decomposed into modules called tasks that are executed according to some precedence constraints. State Transitionbased models are based formally on wellknown conception of “labeled transition system”. The task graph model is very convenient tool of CS description, but, there is a difficult to compute and predict the distribution of the execution time of an application by convolving density functions of individual tasks execution times. Overall computation consumptions depend essentially on the task graph structures. In particular, sometimes we can reduce the consumptions using either way of the task graph levelizing. However, in many cases it is more reasonable (from the point of view of computational consumption) to use some statebased models, like FSM, “Stochastic automation network”(SAN), etc. This talk shows some relationships between different mathematical models of performance evaluation that allows to choose a tradeoff between various mathematical design tools. In particular, it will be shown a way to map a task graph performance model to a statebased one, which deals with a semiMarkov process. This semiMarkov process may be built correctly if, besides the traditional precedence constraints, a description of the tasks relationship involves also some probabilistic characteristics of a dynamic of running and waiting of tasks in the task graph nodes. On the Chromatic Spectrum of Decompositions of Graphs
Robert E. Jamison Department of Mathematical Sciences Clemson University rejam@clemson.edu
Eric Mendelsohn Department of Mathematics University of Toronto mendelso@math.utoronto.ca
The idea of a decomposition of graph occurs both in the study of intersection graphs and in combinatorial design theory. The former deals mostly with sparse graphs, the latter with complete and complete multipartite graphs. Here we will explore a theory for decompositions of general graphs which incorporates both these endeavours. Let K be a family of graphs. A K decomposition D of a graph H = (V,E) is a partition of the edge set E of H so that for each part P of the partition, the subgraph of H induced by P is isomorphic to a graph in K. The graph H is called the host graph for the decomposition. The subgraphs of H induced by the parts of the partition are called the blocks of the partition, and the graphs in K are called the block prototypes for the decomposition. The intersection graph I(D) of the decomposition D has a vertex for each block of the partition and two blocks A and B are adjacent iff they share a common node. The chromatic index of a decomposition D is the chromatic number of I(D). Thus the chromatic index X’(D) of an K decomposition D of H is the minimum number of colors required to color the subgraphs in the decomposition so that subgraphs which share a node get different colors. The Kchromatic spectrum Spec_{K} (H) is the set of all values of X’(D) over all K decompositions D of H. We will show that if the host graph is a tree T, then all Sdecompositions of T have the same chromatic index and this can be computed in polynomial time. By contrast, for every tree S the problem of determining the chromatic index of an Sdecomposition of a bipartite graph is NPcomplete as is the problem of deciding if an integer is in the Sspectrum of a bipartite graph. We will also investigate such questions as 1) Which sets of positivre integers are the spectra of graphs? and 2) How can spectra be constructed with large lacunae? Braid group cryptanalysis
David Garber Holon Academic Institute of Technology garber@hait.ac.il
An important problem in combinatorial group theory is: Given a system of equations in a finitely generated group, find (in an efficient manner) a solution to this system of equations. This problem generalizes many problems of combinatorial group theory (the conjugacy problem, the membership problem, etc.). In the last few years, several publickey cryptosystems where suggested, who rely on the difficulty of this problem in the braid group. In the talk, we will present an efficient algorithmic way for finding a small ordered list of elements in the subgroup which contains a solution to the equation with a significant probability. In many cases, the solution will be the first in this list. This approach actually shows the vulnerability of all mentioned cryptosystems. This is a joint work with S. Kaplan, M. Teicher, B. Tsaban and U. Vishne.
