|
02/08, Jim Schmerl, University of Connecticut, Some Ramsey theory (as suggested by some model theory)
Abstract:
I will discuss some partition properties of representations of finite lattices.
Typical results in the simplest cases of Boolean lattices are much like the
canonical version of Ramsey's Theorem (\`{a} la Erd\H{o}s-Hajnal). These results
are used in the study of nonstandard models of arithmetic, but I will not
dwell upon these applications.
|
|
| 03/01, Goran Konjevod, Department of CSE, Online Ramsey Theory
|
|
03/22, Andrzej Czygrinow, Department of Mathematics, Distributed algorithms for sparse graphs
Abstract:
I will discuss distributed approximation algorithms for the maximum matching problem and the minimum dominating set problem in trees and planar graphs.
|
|
03/28, Fatih Gelgi, Department of CSE, Josephus: An Improved Algorithm for Finding the Sole Survivor
Abstract:
The Josephus problem is a historic relative of the currently
popular televison show 'Survivor'. In the Josephus problem,
the numbers from 1 to n are arranged in a circle, and starting
from position 1, every m th number around the circle is
eliminated until only one number, the sole survivor,
remains. In this talk, we give an algorithm for determining the
sole survivor in time O(max{m, m log(n/m)}).
Prior results have running times of O(m log n) and O(n).
|
|
04/05,
Melih Onus, Department of CSE,
Constant Density Spanners for Wireless Ad-Hoc Networks
Abstract:
An important problem for ad hoc networks is to design overlay networks that
allow time and energy efficient routing. We present a new communication model
that models transmission and interference issues and provides a realistic
model for physical carrier sensing. According to this model, we propose a
local algorithm to construct a constant density dominating set.
|
|
|
