The Cardinal Complexity of Comparison-based Online Algorithms (Nick Gravin)


The talk concerns ordinal online problems, i.e., those tasks that only depend on the pairwise comparisons between elements in the input. Such as the secretary problem and the game of googol.  The natural approach to these tasks is to use ordinal online algorithms that at each step only consider relative ranking among the arrived elements, without looking at the numerical values of the input. 

We formally study the question of how cardinal algorithms (that can use numerical values of the input) can improve upon ordinal algorithms. 

We show that if the value range of the input elements is big enough (specifically, a tower of exponents of hight n-1 with base 1/epsilon for an input sequence of length n), then the advantage of cardinal algorithms over ordinal algorithms is at most 1+ epsilon and it vanishes as epsilon approaches 0. We also identify a natural family of hardcore problems that achieve a matching  advantage of 1+1/ log* N, where  log* is the iterative logarithm of the maximum range N. For a simpler variant of the hardcore problem, which is closely related to the game of googol, we provide a more efficient construction with only exponential cardinal complexity.

Based on joint work with Zhihao Tang and  Enze Sun.


2022-5-24  13:30 - 14:30   


Nick Gravin,  ITCS@SUFE


Tencent meeting ID: 861-8393-9675; PW: 123456