Articolele autorului Gabriel Istrate
Link la profilul stiintific al lui Gabriel Istrate

The Maximum Binary Tree Problem
On the heapability of finite partial orders
It’s not whom you know, it’s what you (or your friends) can do: Coalitional Frameworks for Network Centralities.

We investigate the representation of game-theoretic measures of network centrality using a framework that blends a social network representation with the formalism of cooperative skill games. We discuss the expressiveness of the new framework and highlight some of its advantages, including a fixed-parameter tractability result for computing centrality measures under such representations. As an application we introduce new network centrality measures

Read more
De ce să finanțăm cercetarea românească ? Citiți un (scurt) eseu cu acest titlu.

Read more
Attacking Power Indices by Manipulating Player Reliability

We investigate the manipulation of power indices in TU-cooperative games by stimulating (subject to a budget constraint) changes in the propensity of other players to participate to the game. We display several algorithms that show that the problem is often tractable for so-called network centrality games and influence attribution games, as well as an example when optimal manipulation is intractable, even though computing power indices is feasible.

Read more
Short Proofs of the Kneser-Lovász Coloring Principle

We prove that the propositional translations of the Kneser-Lovasz theorem have polynomial size extended Frege proofs and quasi-polynomial size Frege proofs. We present a new counting-based combinatorial proof of the Kneser-Lovasz theorem that avoids the topological arguments of prior proofs. We introduce a miniaturization of the octahedral Tucker lemma, called the truncated Tucker lemma. The propositional translations of the truncated Tucker lemma

Read more
Stochastic Stability in Schelling’s Segregation Model with Markovian Asynchronous Update

  We investigate the dependence of steady-state properties of Schelling's segregation model on the agents' activation order. Our basic formalism is the Pollicott-Weiss version of Schelling's segregation model. Our main result modifies this baseline scenario by 1. employing a log-linear response rule 2. incorporating "contagion" in the decision to move: agents are connected by a second, "word-of-mouth", network. Agents' activation is specified by

Read more
The language (and series) of Hammersley-type processes

We study languages and formal power series associated to (variants of) Hammersley's process. We show that the ordinary Hammersley process yields a regular language and the Hammersley tree process yields deterministic context-free (but non-regular) languages. For the extension to intervals of the Hammersley process we show that there are two relevant formal language variants. One of them leads to the same class of languages as the ordinary Hammersley

Read more
Gambler’s ruin problem on Erdos-Renyi graphs

A simple ruin-game is studied on Erdos-Renyi type graphs. Initially the players have the same wealth. At each time step a monopolist game is played on all active links (links that connects nodes with nonzero wealth). In such a game each player puts a unit wealth in the pot and the pot is won with equal probability by one of the players. The game ends when there are no connected players such that both of them have non-zero wealth. In order to characterize

Read more
The Minimum Entropy Submodular Set Cover Problem

We study minimum entropy submodular set cover, a variant of the submodular set cover problem (Wolsey, Fujito, etc) that generalizes the minimum entropy set cover problem (Halperin and Karp, Cardinal et al.) We give a general bound of the approximation performance of the greedy algorithm using an approach that can be interpreted in terms of a particular type of biased network flows. As an application we rederive known results for the Minimum Entropy

Read more