Browsing by Author "Marinkovic, Javier"

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Attention is Turing complete
    (2021) Pérez, Jorge; Barceló Baeza, Pablo; Marinkovic, Javier
    Alternatives to recurrent neural networks, in particular, architectures based on self-attention, are gaining momentum for processing input sequences. In spite of their relevance, the computational properties of such networks have not yet been fully explored. We study the computational power of the Transformer, one of the most paradigmatic architectures exemplifying self-attention. We show that the Transformer with hard-attention is Turing complete exclusively based on their capacity to compute and access internal dense representations of the data. Our study also reveals some minimal sets of elements needed to obtain this completeness result.
  • No Thumbnail Available
    Item
    Online combinatorial assignment in independence systems
    (2025) Marinkovic, Javier; Soto, Jose A.; Verdugo Silva, Victor Ignacio
    We consider an online multi-weighted generalization of several classic online optimization problems called the online combinatorial assignment problem. We are given an independence system over a ground set of elements and agents that arrive online one by one. Upon arrival, each agent reveals a weight function over the elements of the ground set. If the independence system is given by the matchings of a hypergraph, we recover the combinatorial auction problem, where every node represents an item to be sold, and every edge represents a bundle of items. For combinatorial auctions, Kesselheim et al. showed upper bounds of O (log log (k)/log (k) and O (log log (n)/log (n) on the competitiveness of any online algorithm, even in the random order model, where k is the maximum bundle size and n is the number of items. We provide an exponential improvement by giving upper bounds of O (log (k)/k, and O (log (n) for the prophet IID setting. Furthermore, using linear programming, we provide new and improved guarantees for the k-bounded online combinatorial auction problem (i.e., bundles of size at most k). We show a -competitive algorithm in the prophet IID model, a -competitive algorithm in the prophet-secretary model using a single sample per agent, and a -competitive algorithm in the secretary model. Our algorithms run in polynomial time and work in more general independence systems where the offline combinatorial assignment problem admits the existence of a polynomial-time randomized algorithm that we call certificate sampler. These systems include some classes of matroids, matroid intersections, and matchoids.