Noticias en español
Super-logarithmic cliques in dense inhomogeneous random graphs
Abstract: In the theory of dense graph limits, a graphon is a symmetric measurable function W from [0,1]^2 to [0,1]. Each graphon gives rise naturally to a random graph distribution, denoted G(n,W), that can be viewed as a generalization of the Erdos-Renyi random graph. Recently, Dolezal, Hladky, and Mathe gave an asymptotic formula of order log(n) for the size of the largest clique in G(n,W) when W is bounded away from 0 and 1. We show that if W is allowed to approach 1 at a finite number of points, and displays a moderate rate of growth near these points, then the clique number of G(n,W)...
Read MoreBalancing Vectors in any Norm
Abstract: In the vector balancing problem, we are given symmetric convex bodies C and K in R^n, and our goal is to determine the minimum number β ≥ 0, known as the vector balancing constant from C to K, such that for any sequence of vectors in C there always exists a signed combination of them lying inside βK. Many fundamental results in discrepancy theory, such as the Beck-Fiala theorem (Discrete Appl. Math ‘81), Spencer’s “six standard deviations suffice” theorem (Trans. Amer. Math. Soc ‘85) and Banaszczyk’s vector balancing theorem (Random Structures & Algorithms ‘98) correspond to...
Read MoreEfficient 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 More