Tomasz Steifer
Especialidad:
Aleatoriedad algorítmica, cómputos probabilísticos y elecciones sociales
Email:
tsteifer@ippt.pan.pl
Tomasz es doctor del Instituto de Ciencia de Computación de la Academia Polaca de Ciencias. Sus intereses de investigación actuales incluyen aleatoriedad algorítmica, cómputos probabilísticos y elecciones sociales.
PUBLICACIONES
The notion of rank of a Boolean function has been a cornerstone in PAC learning, enabling quasipolynomial-time learning algorithms for polynomial-size decision trees. We present a novel characterization of rank, grounded in the well-known Transformer architecture. We show that the rank of a function corresponds to the minimum number of Chain of Thought (CoT) steps required by a single-layer Transformer with hard attention to compute . Based on this characterization we establish tight bounds on the number of CoT steps required for specific problems, showing that-fold function composition necessitates exactly CoT steps. Furthermore, we analyze the problem of identifying the position of the-th occurrence of 1 in a Boolean sequence, proving that it requires CoT steps.
In perpetual voting, multiple decisions are made at different moments in time. Taking the history of previous decisions into account allows us to satisfy properties such as proportionality over periods of time. In this paper, we consider the following question: is there a perpetual approval voting method that guarantees that no voter is dissatisfied too many times? We identify a sufficient condition on voter behavior ---which we call 'bounded conflicts' condition---under which a sublinear growth of dissatisfaction is possible. We provide a tight upper bound on the growth of dissatisfaction under bounded conflicts, using techniques from Kolmogorov complexity. We also observe that the approval voting with binary choices mimics the machine learning setting of prediction with expert advice. This allows us to present a voting method with sublinear guarantees on dissatisfaction under bounded conflicts, based on the standard techniques from prediction with expert advice.
We consider online learning in the model where a learning algorithm can access the class only via the \emph{consistent oracle}—an oracle, that, at any moment, can give a function from the class that agrees with all examples seen so far. This model was recently considered by Assos et al. (COLT’23). It is motivated by the fact that standard methods of online learning rely on computing the Littlestone dimension of subclasses, a computationally intractable problem. Assos et al. gave an online learning algorithm in this model that makes at most Cd mistakes on classes of Littlestone dimension d, for some absolute unspecified constant C>0. We give a novel algorithm that makes at most O(256d) mistakes. Our proof is significantly simpler and uses only very basic properties of the Littlestone dimension. We also show that there exists no algorithm in this model that makes less than 3d
mistakes. Our algorithm (as well as the algorithm of Assos et al.) solves an open problem by Hasrati and Ben-David (ALT’23). Namely, it demonstrates that every class of finite Littlestone dimension with recursively enumerable representation admits a computable online learner (that may be undefined on unrealizable samples).
Edificio de Innovación UC, Piso 2
Vicuña Mackenna 4860
Macul, Chile
Vicuña Mackenna 4860
Macul, Chile