Dombb Yair

Research Description: I am working under the supervision of Prof. Yonatan Aumann.

My Master's thesis (also with Prof. Aumann) dealt with analyzing the parameterized complexity of various fundamental computational problems when the parameter is taken to be the combinatoric structure part of the input (rather then the number part, which is usually considered as the parameter), which we named "Fixed-Structure" problems. In this work we also defined fixed-structure graph families in order to obtain interesting fixed-structure variants of classical graph problems.

My current research is concerned with the (online) paging problem. We attempt to avoid the dismal lower bounds on the competitiveness of algorithms for the problem by considering a model where the page calls are generated by a probabilistic source rather by an adversary.