Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Matroid Secretary for Regular and Decomposable Matroids
event speaker icon
Armando Castaneda (CS, Technion)
event date icon
Wednesday, 12.06.2013, 12:30
event location icon
Taub 201
The M-renaming task requires n+1 processes, each starting with a unique input name (from an arbitrary large range), to coordinate the choice of new output names from a range of size M. This talk presents the first upper bound on the complexity of 2n-renaming, when n + 1 is not a prime power.

It is known that 2n-renaming can be solved if and only if n+1 is not a prime power; however, the previous proof of the ``if" part was non-constructive, involving an approximation theorem; in particular, it did not yield a concrete upper bound on the complexity of the resulting protocol.