Noticias en español
Binary codes via 4D discrete Ihara-Selberg function
Abstract: We show how to express weight enumerator of each binary linear code as an infinite product. In the beginning of 60’s, this was done for a special case of the cycle space of the planar graphs by R. Feynman.
Read MoreStrict majority bootstrap percolation on augmented rings, tori and random regular graphs.
Abstract: We study the strict majority bootstrap percolation process on graphs. Vertices may be active or passive. Initially, active vertices are chosen independently with probability p. Each passive vertex v becomes active if at least ceil((deg(v)+1)/2) of its neighbors are active (and thereafter never changes its state). If at the end of the process all vertices become active then we say that the initial set of active vertices percolates on the graph. We address the problem of finding graphs for which percolation is likely to occur for small values of p. We call p_c the least p which makes...
Read MoreOn the metric dimension for random graphs
The metric dimension of a graph G is the minimum number of vertices in a subset S of the vertex set of G such that all other vertices are uniquely determined by their distances to the vertices in S. In this paper we investigate the metric dimension of the random graph G(n,p) for a wide range of probabilities p=p(n).
Read MoreHard-core predicate and list decoding
Abstract A hard-core predicate P of a one-way function f is a predicate of the input of f which is not leaked by f. There are many classical results regarding hard-core predicates of the most common cryptographically useful one-way functions such as RSA, discrete exponentiation or the Rabin function. A classical result by Goldreich and Levin states that every one-way function has a hard-core predicate. At FOCS 2003, Akavia, Goldwasser and Safra gave a coding theoretic interpretation of Goldreich and Levin’s result and an elegant list decoding methodology to prove that a predicate is a...
Read MoreLarge Induced Subgraphs Via Triangulations and CMSO
Many classical graph problems consist in finding a maximum induced subgraph with some property. We can cite the Maximum Independent Set, Maximum Induced Forest, Longest Induced Path, Maximum Induced Matching, etc. We generalize them through the following optimization problem. Let φ be a Counting Monadic Second Order Logic formula and t be an integer. Given a graph G=(V,E), the task is to find a maximum induced subgraph G[F] of treewidth at most t, that models φ. Using the theory of potential maximal cliques, we show that the general problem ant thus all the particular cases can be solved in...
Read MoreIX Escuela de Verano en Matemáticas Discretas
La Escuela se lleva a cabo del 6 al 17 de enero de 2014 en el Instituto de Sistemas Complejos de Valparaíso (ISCV)
Read More