Noticias en español
Efficient Implementation of a Practical Leakage-Resilient ID Scheme
Abstract: Instead of viewing cryptographic algorithms as simple black-boxes, leakage-resilient cryptography accepts that certain traditionally secret parts of the algorithm will be available to the attacker through side channel attacks and aims to ensure the security of these algorithms in the presence of such leakage. We present a leakage resilient identification scheme based on the continuous memory leakage model, which assumes that the leakage of information is unrestricted in time and space. We design a three message sigma protocol, secure under the symmetric external diffie-hellman...
Read MoreGeneralizations of the geometric de Bruijn Erdős Theorem
Abstract: A classic Theorem of de Bruijn and Erdős states that every noncollinear set of n points in the plane determines at least n distinct lines. The line L(u, v) determined by two points u, v in the plane consists of all points p such that dist(p, u) + dist(u, v) = dist(p, v) (i.e. u is between p and v) or • dist(u, p) + dist(p, v) = dist(u, v) (i.e. p is between u and v) or • dist(u, v) + dist(v, p) = dist(u, p) (i.e. v is between u and p). With this definition of line L(uv) in an arbitrary metric space (V, dist), Chen and Chvátal conjectured that every metric space on n points, where n...
Read MoreGraph decompositions using group actions
Abstract: I will present some recent results on graph decompositions. To this end, we find a very `nice’ subgraph H in a host graph we would like to decompose into copies of H. Then we employ a group action to `rotate’ H. This rotation yields a decomposition of the host graph into copies of H. We construct this `nice’ subgraph using probabilistic tools, a well-known hypergraph matching theorem due to Pippenger and Spencer and an absorption method. This is joint work with Stefan Ehard and Stefan Glock.
Read MoreFinding 2-factors without triangles
Abstract: A 2-factor is a set of edges M of a graph G such that each vertex is incident to exactly two edges of M. Thus M determines a set of cycles in G. One can efficiently compute minimum cost 2-factors in weighted graphs. It is open whether one can do the same, if we forbid triangles, i.e., each cycle has at least four edges. For the unweighted case, a complicated result of Hartvigsen shows that one can find such a 2-matching in polynomial time. In the talk, we will review known results related to finding triangle free 2-factors, see its relation to the traveling salesman...
Read MoreSet-based Lagrangean decomposition methods for mathematical programming
Abstract: We present generic Lagrangean frameworks for primal (variable) and dual (constraint) decomposition algorithms for nonlinear mathematical programs with generalized inequalities. Akin to the Dantzig-Wolfe (DW) method and the Benders Decomposition (BD), we solve a succession of restricted problems/Lagrangean relaxations in a primal setting or relaxed problems/second stage problems in a dual standpoint. Our approach is generic in the sense that it takes as user-defined inputs 1) a structured subset of the primal (dual) feasibility set, and 2) a mechanism to update it at each...
Read MoreMaximizing Covered Area in a Euclidean Plane with Connectivity Constraint
Abstract: Given a set of unit disks in the plane and an integer K, the maximum area connected subset problem asks for a subset of K disks covering the maximum area, under the constraint that the area covered by the K disks is connected. This problem is motivated by wireless router deployment and is a special case of maximizing a submodular function under a connectivity constraint.
Read More