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

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
Heapability, interactive particle systems, partial orders: results and open problems

We outline results and open problems concerning partitioning of integer sequences and partial orders into heapable subsequences (previously defined and established by Byers et al.)

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
Partition into heapable sequences, heap tableaux and a multiset extension of Hammersley’s process

We investigate partitioning of integer sequences into heapable subsequences (previously defined and studied by Byers et al. We show that an extension of patience sorting computes the decomposition into a minimal number of heapable subsequences (MHS). We connect this parameter to an interactive particle system, a multiset extension of Hammersley’s process, and investigate its expected value on a random permutation. In contrast with the (well studied)

Read more
Reachability and Recurrence in a Modular Generalization of Annihilating Random Walks (and lights-out games) to hypergraphs

We study a discrete asynchronous dynamical system on hypergraphs that can be regarded as a natural extension of annihilating walks along two directions: first, the interaction topology is a hypergraph; second, the number of particles at a vertex of the hypergraph is an element of a finite ring Z_p of integers modulo an odd number p>= 3. Equivalently, particles move on a hypergraph, with a moving particle at a vertex being replaced by one indistinguishable

Read more
Identifying almost-sorted permutations from TCP buffer dynamics

Associate to each sequence A of integers (intending to model packet IDs in a TCP/IP stream) a sequence of positive integers of the same length M(A). The i’th entry of M(A) is the size (at time i) of the smallest buffer needed to hold out-of-order packets, where space is accounted for unreceived packets as well. Call two sequences A, B equivalent (written A =_{FB} B) if M(A) = M(B). For a sequence of integers A define SUS(A) to be the shuffled-up-sequences

Read more
Interactive Particle Systems and Random Walks on Hypergraphs

We study hypergraph analogues of interacting particle systems and random walks, notably generalizations of coalescing and annihilating random walks. Their definition is motivated by the problem of analyzing the expected running time of a local search procedure for the k-XOR SAT problem, as well as a certain constrained triad dynamics in the theory of social balance.

Read more
Learning cover context-free grammars from structural data

We consider the problem of learning an unknown context-free grammar when the only knowledge available and of interest to the learner is about its structural descriptions with depth at most l. The goal is to learn a cover context-free grammar (CCFG) with respect to l, that is, a CFG whose structural descriptions with depth at most l agree with those of the unknown CFG. We propose an algorithm, called LA^l, that efficiently learns a CCFG using two

Read more