| Horário | |
Palestra |
| 14:00 | |
Stability of Consensus Functions |
| |
|
Sergio Rajsbaum Universidad Nacional Autónoma de México |
| 15:00 | |
coffee break |
| 15:15 | |
New Upper Bound on Vertex Folkman Numbers |
| |
|
Andrzej Dudek Emory University |
Stability of Consensus Functions
Sergio Rajsbaum
Universidad Nacional Autónoma de México
Sexta, 4 de abril, 14:00
Consider a system composed of $n$ sensors operating in synchronous rounds. In each round an \emph{input vector} of sensor readings $x$ is produced, where the $i$-th entry of $x$ is a binary value produced by the $i$-th sensor. The sequence of input vectors is assumed to be \emph{smooth}: exactly one entry of the vector changes from one round to the next one. The system implements a fault-tolerant averaging \emph{consensus function} $f$. This function returns, in each round, a representative \emph{output value} $v$ of the sensor readings $x$. Assuming that at most $t$ entries of the vector can be erroneous, $f$ is required to return a value that appears at least $t+1$ times in $x$. It is desired that such a function has good stability, changing its output value as few times as possible. We describe results and open questions about this research area.
This is joint work with L. Davidovitch, S. Dolev (Ben-Gurion U., Israel) F. Becker (Lyon), I. Rapaport (U. Chile), E. Rémila (Lyon). Publications in J. Comp. and System Sciences 2003, and SIAM J. on Comp. 2007.
New Upper Bound on Vertex Folkman Numbers
Andrzej Dudek
Emory University
Sexta, 4 de abril, 15:15
In 1970, Folkman proved that for a given integer $r$ and a graph $G$ of order $n$ there exists a graph~$H$ with the same clique number as $G$ such that every $r$ coloring of vertices of $H$ yields at least one monochromatic copy of $G$. His proof gives no good bound on the order of graph~$H$, \textit{i.e.}, the order of $H$ is bounded by an iterated power function of $n$. A related problem was studied by {\L}uczak, Ruci\'nski and Urba\'nski, who gave some explicit bound on the order of $H$ when $G$ is a clique. In this talk we will give an alternative proof of Folkman's theorem with the relatively small order of $H$ bounded from above by $\mathcal{O}(n^3\log^3 n)$.
This is joint work with Vojt\v{e}ch R\"odl (Emory University).
Atividades dentro do
FOCOS - Foundations of Computer Science:
FOCOS - Combinatorial Algorithms
and Discrete Structures
Projeto Temático/ProNEx FAPESP/CNPq (Proc. FAPESP 2003/09925-5)
e do
NUMEC - Núcleo de Apoio à Pesquisa em
NUMEC - Modelagem Estocástica e Complexidade