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

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
Proof complexity and the Lovasz-Kneser Theorem

We investigate the proof complexity of a class of propositional formulas expressing a combinatorial principle known as the Kneser-Lovasz Theorem. This is a family of propositional tautologies, indexed by an nonnegative integer parameter k that generalizes the Pigeonhole Principle (PHP, obtained for k=1). We show, for all fixed k, 2^{Omega(n)} lower bounds on resolution complexity and exponential lower bounds for bounded depth Frege proofs. These

Read more
Improved approximation algorithms for low-density instances of the Minimum Entropy Set Cover Problem

We study the approximability of instances of the minimum entropy set cover problem, parameterized by the average frequency of a random element in the covering sets. We analyze an algorithm combining a greedy approach with another one biased towards large sets. The algorithm is controlled by the percentage of elements to which we apply the biased approach. The optimal parameter choice leads to improved approximation guarantees when average element

Read more, platforma online si conferinta anuala a economistilor romani din mediul academic

Detalii: Data conferintei: 18-22 August 2014; Universitatea Babes-Bolyai, Cluj-Napoca CFP:

Read more
Polio risk looms over Europe

Read more
Tarile cu cele mai eficiente sisteme educationale pretuiesc profesorii si au „cultura educatiei”

Un clasament al sistemelor de invatamant, realizat de compania britanica Pearson, analizeaza date din 39 de tari. Potrivit articolului "Romania s-a numarat si ea printre tarile analizate, fiind plasata pe locul 32, in penultima grupa de tari cu un sistem educational sub medie, alaturi de Chile (locul 33)"

Read more