|1||11/04/2013||Dr. Ariel Stulman||Exchange in MANETs|
Abstract: As the capabilities of mobile technology such as PDAs, smartphones and tablets increases, theoretical ideas are materializing. One of these ideas under active development is a infrastructure free network, based solely on mobile devices (a.k.a. MANET - mobile ad hoc network). These networks would have the ability of running communications without the use of pre-existing infrastructure, allowing for a reduction of cost to carriers, setting up communication networks where no infrastructure is available (like disaster zones), etc. In this paper we propose an algorithm, based on the famous Diffie-Hellman key exchange (KE) algorithm, that will provide for confidentiality of KE during conversation initiation, from which a cryptographically secure channel can later be derived. The algorithm utilizes the constant fluctuation of MANET network topology to flush-out eavesdroppers (if they exist), assuming no prior knowledge and without active user intervention.
|2||03/04/2013||Dr. Noam Hazon||Don’t let the bad guys win:|
2 problems in multi agent systems
Abstract: In this talk I will present two problems which we modeled using disciplines from game-theory and social choice, and then analyzed their computational aspects. In the first part of the talk, I will deal with the problem of security of flows on networks. In many exciting multi-agent applications – including future battlefields, law enforcement and commerce – agents must communicate in inherently or potentially hostile environments in which an adversary disrupts or intercepts the communication between agents for malicious purposes. Intelligent agents must balance network performance with possible harm suffered from an adversary’s attack, while accounting for the broadcast nature of their communication and the heterogeneous vulnerabilities of communication links. I will show our network-flow-based approach for compactly representing this problem, and the polynomial time algorithms that we provided to find the equilibrium. In addition, I will present the definition of the inducible Stackelberg equilibrium, which was motivated by our settings. In the second part of my talk I will present our computational complexity results regarding the model of “safe manipulation”, which is a new model of coalitional manipulation that was recently put forward by Slinko and White. I will also describe two ways to extend the original notion of safe-manipulation, in order to capture some of the scenarios that may occur in practice.
|3||21/03/2013||Prof. Boris M.Scein||Semigroups characterizing hypergraphs|
Abstract: Various semigroups can be associated with graphs and hypergraphs. Mainly, they have been endomorphism monoids but other types of semigroups appeared too. The speaker will mention a survey of semigroups connected with graphs and written by his former Ph.D. student as well as other similar attempts - but the main emphasis of the lecture would be different: we consider a new type of semigroups connected with hypergraphs.
We use the most general definition of hypergraphs (it belongs to Claude Berge and A. Zykov). A hypergraph is a triple (V, E, I), where V and I are sets and I is a subset of V x I (that is, I is a binary relation between the elements of V and I). The elements of V are called "vertices", the elements of E are "edges", and I is the "incidence relation". If v and e are elements of V and E respectively and v and e are I-related, we interpret this as "v and e are incident", or "the vertex v belongs to the edge e", or "e contains v". Thus an edge can have any number of vertices from 0 and up. Different edges may have exactly the same vertices, so these hypergraphs generalize the idea of multigraphs where to vertices can be joined by different edges.
With each hypergraph A we associate a semigroup S(A). Its elements are all ordered pairs in V x E and a special element 0 that plays the role of zero.The multiplication in this semigroup is defined using the incidence relation of I. Then we consider semigroups with isomorphic semigroups S, the automorphisms of A and S and other things.
|4||13/03/2013||Dr. Tal Grinshpoun||Distributed Constraint Reasoning – can we learn something from it?|
Abstract: In this talk I will present two research advances in the vibrant field of Distributed Constraint Reasoning. From each of these advances I will extract some insight that is relevant for other algorithmic fields
|5||06/03/2013||Dr. Daniel Moskovich||Quantum topology of colored knots|
Abstract: A knot is a smooth embedding of a circle in 3-dimensional space. Each knot K corresponds to a non-associative algebraic object Q_K called a quandle. To "color the knot K by a quandle B" means to fix a representation r of this quandle Q_K to a fixed quandle B. The coloring map r inputs information to the knot, and a knot K can only contain nontrivial information if the knot itself is topologically nontrivial. Certain topologically natural modifications of the colored knot called `twist moves' preserve the information r. I will discuss the question of how to determine whether or not two given colored knots are related by twist moves, and the question of how the network of relationships between two given colored knots by finite sequences of twist moves allows us to recover information about the colored knot (K,r), thought of as a system. The talk assumes no prior background in topology.
Parts of this work are joint with Andrew Kricker and with Avishy Carmi of NTU in Singapore.
|6||28/12/2013||Dr. Amit Dvir||SDTP+: Securing a Distributed Transport Protocol for WSNs|
using Merkle Trees and Hash Chains
Abstract: Transport protocols for Wireless Sensor Networks are designed to fulfill both reliability and energy efficiency requirements. Distributed Transport for Sensor Networks (DTSN) is one of the most promising transport protocols designed for WSNs because of its effectiveness; however, it does not address any security issues, hence it is vulnerable to many attacks. The first secure transport protocol for WSN was the secure distributed transport protocol (SDTP), which is a security extension of DTSN. Unfortunately, it turns out that the security methods provided by SDTP are not sufficient; some tricky attacks get around the protection mechanism. In this tale, I will describe the security gaps in the SDTP protocol, and we introduce SDTP+ for patching the weaknesses. I will also show that SDTP+ resists attacks on reliability and energy efficiency of the protocol, and also present an overhead analysis for showing its effectiveness.
This is a collaboration work with Prof. Levente Buttyan and Ta Vinh Thong from
the CrySyS Lab.
|7||14/02/2013||Dr. Ofir Pele||New Distance Functions and Learning with General Distance Functions|
Abstract: Histogram distance functions are the cornerstone of numerous computer vision and machine learning tasks (e.g. image retrieval, descriptor matching and k-nearest neighbor classification). It is common practice to use distances such as the Euclidean and Manhattan norms to compare histograms. This practice assumes that the histogram domains are aligned. However, this assumption is violated through quantization, shape deformation, light changes, etc. The Earth Mover’s Distance (EMD) is a cross-bin distance that addresses this alignment problem. We present several new Earth Mover's Distance variants that are robust to outlier noise and global deformations. Additionally, we present efficient algorithms for their computation. We show state-of-the-art results for descriptor matching and image retrieval. These tools have already been used by other groups and demonstrated state-of-the-art results for a range of tasks such as superpixel matching, descriptor matching, image retargeting, image segmentation, social graph comparisons and population density comparison. Finally, we describe several future directions including learning with general (not necessarily positive-semidefinite) similarity functions.
|8||20/01/2013||Dr. Zur Izhakian||Supertropical Algebra and Representations|
Abstract: Tropical mathematics is carried out over idempotent semirings, a weak algebraic structure that on one hand allows descriptions of objects having a discrete nature, but on the other hand, its lack of additive inverse prevents the access to basic mathematical notions. To overcome these drawbacks, we use a supertropical semiring - a ``cover'' semiring structure having a distinguished ``ghost ideal'' that plays the role of the zero element in many of the theorems. This supertropical structure is rich enough and permits a systematic development of tropical algebraic theory, yielding direct analogs to many important results and notions from classical commutative algebra. These provide a suitable algebraic framework that allows natural representations of matroids and semigroups.
|9||10/01/2013||Dr. Esther Ezra||On Relative Approximations in Geometry and Their Variants|
Abstract: In range counting problems we are given a set of objects, and the goal is to preprocess them, so that given any query range, the number of objects that fall into that range is computed efficiently. For example, the objects are points corresponding to the coordinates of several cities, and we would like to compute how many cities lie within a certain region.
In many cases, it is too expensive to process the entire set of objects, which raises the necessity to resort to approximate range counting.
Motivated by this problem, relative approximations have become a central tool Computational Geometry. In fact, they were introduced by Har-Peled and Sharir, who derived them from the seminal work of Li, Long, and Srinivasan in the theory of Machine Learning. Informally, a relative approximation is a sample of the input objects that guarantees a bounded relative error for any given range when comparing its exact count (that is, with respect to the entire set of objects) to its approximate count that is, confined to the sample.
In this talk I will discuss the properties of relative approximations and their implications to the so-called "Epsilon-nets" and “Epsilon-approximations". I will also present improved upper bounds for the size of relative approximations, which eventually yields better performance for approximate range counting. Our approach is probabilistic, where we apply the constructive version of the general Local Lemma of Lovasz
|10||27/12/2012||Dr Gabi Ben-Simon||Quasi-morphisms in dynamics and also in geometry and geometric group theory|
Abstract: As simple as they are to define quasi-morphisms (homomorphism of a group to R "up to a bounded error"), are often hard to construct, in dynamics, and not easy either to construct in geometric group theory. Often they encode important information of a dynamical system, especially in the case of the Hamiltonian dynamical systems that relates to classical and quantum mechanics. In the talk I will focus on examples where is some cases I will describe the dynamical system and the construction of its quasi-morphism and in some other example I will describe the dynamical system and explain the context in which its quasi-morphisms were constructed.
I will try to say also a few words of the important role they play in geometric group theory-with application to hyperbolic geometry, here partial order on groups plays an important counterpart role.