1. Online Coloring Known Graphs

Hi,

I have problems with understanding some terms and algorithms.

I have a PDF with some dissertation (as in title) and I don't understand:
• Why Alice reveals the color of vertex and how she computes is? And why she even colors them if Bob is supposed to give correct coloring?
The same lower bound holds also for randomized algorithm against an oblivious
adversary; in this version, Bob is allowed to base his color decisions on coin ﬂips
which are hidden from Alice. It also holds for a further restricted model, where Alice
immediately commits a presented vertex to be a particular vertex in the underlying
graph as soon as Bob decides on his color. This implies that Alice is eectively
coloring the vertices online as well, and revealing those choices.
Terminology We say that Bob assigns vertices to bins while Alice colors.The hue
of a bin is the set of colors among the vertices in the bin. We say that progress is
made on a vertex if the color assigned to that vertex increases the hue of the bin to
which the vertex was assigned.
• What means "oblivious" in context of that dissertation?
• I don't understand what it has in common, ie. I think we should search for codes with Hamming distance > 3k/8.
We call a collection dispersed if any pair of sets have at most 3k/8 elements in
common. Thus, we seek a binary code of length k with Hamming distance k/4.
• What's the difference between adaptive construction and oblivious construction?

I've spent a few days trying to understand it.

2. Originally Posted by zoska
Hi,

I have problems with understanding some terms and algorithms.

I have a PDF with some dissertation (as in title) and I don't understand:
• Why Alice reveals the color of vertex and how she computes is? And why she even colors them if Bob is supposed to give correct coloring?

• What means "oblivious" in context of that dissertation?
• I don't understand what it has in common, ie. I think we should search for codes with Hamming distance > 3k/8.
• What's the difference between adaptive construction and oblivious construction?

I've spent a few days trying to understand it.
EDIT:
Sorry I forgot to put a link to PDFs:
Index of /~tarsa/math