Theoretical Computer Science Group

Gabriel Istrate



 Short CV – in Romanian.

Research interests (and some recent papers)

I am interested in Theoretical Computer Science at large, with a focus on discrete and probabilistic methods. Some of the models and problems I care about have an interdisciplinary nature, relating  to the Physics of Complex Systems or to Social Dynamics (or both :))

Here is an incomplete listing of some of the more interesting recent areas/problems I have been concerned with:

1. Combinatorics (often motivated by  Complex Systems)


heapable sequences and related notions, including variants of interacting particle systems and Young tableaux.

In paper [8] I study (jointly with Cosmin Bonchis) the concept of heapable sequences (previously introduced by Byers et al.). Informally a sequence is heapable if it can be inserted into a binary (not necessarily complete) tree that respects the heap property.I view heapability as a relaxation of the monotonicity. Given that the length of the longest increasing subsequence of a random permutation (equal to the number of classes in a partition of a permutation into increasing sequences) is a classical problem, we were looking for the scaling of the number of heapable subsequences in an optimal decomposition of a permutation.This number, we show, is computable via a generalization of patience sorting. A nice conjecture in the paper is that this number scales as follows

E[MinHeap[\pi]\sim \frac{1+\sqrt{5}}{2}\cdot \ln(n)

It’s not merely a nice conjecture backed by experimental evidence: we connect the parameter to a variation on Hammersley’s interactive particle process.

“Physics-like” computations and further experiments confirm the above conjecture. We are in the process of preparing a paper with these computations.

The paper also introduces a “heap-like” version of Young tableaux. This part already led to many interesting further developments. Stay tuned.

2. Interactive particle systems. Applications to Satisfiability and Social Dynamics.


Hypergraph generalizations of coalescing/annihilating random walks and particle systems, odd cut expansion properties and applications.

3. Discrete Models of Social Dynamics.


Adversarial scheduling analysis.

To write …

4. Combinatorial Topology (and its applications to Computational Complexity).


The propositional complexity of the Kneser-Lovasz Theorem

Together with Adrian Craciun I investigated (in paper [3]) the proof complexity of the (propositional translation) of the so-called Kneser-Lovasz theorem (and variants of this result, such as the one obtained by Schrijver). We showed that the existing lower bounds for the pigeonhole principle extend to these tautologies. Then we showed that the case k=2 has polynomial size Frege proofs, while the case k=3 has polynomial size extended Frege proofs.

We dealt with the general case k\geq 4 in the subsequent paper ([5]), written in collaboration with James Aisenberg, Maria Luisa Bonet and Sam Bus: surprisingly, one can give polynomial size extended Frege proofs and polynomial size Frege proofs that bypass Algebraic Topology. On the other hand the octahedral Tucker lemma (that was used to prove Kneser’s conjecture) has a polynomial size miniaturization for which this approach no longer works, apparently.

5. Submodularity and (its applications to) Algorithmic Game Theory.


The Minimum Entropy Set Cover Problem (MESC), its submodular generalization and applications to algorithmic cooperative game theory.

MESC is a problem initially studied by Halperin and Karp (and Cardinal et al.), initially motivated by a problem from computational biology (haplotype resolution)
In paper [2] we give a better approximation guarantee for sparse instances of MESC.In paper [9] (chronologically the first we wrote on this topic) we generalize the problem to Minimal Entropy Submodular Set Cover (MESSC), a framework that captures many interesting combinatorial subproblems.We give a guarantee for the performance approximation guarantee of the GREEDY algorithm that is almost as good as the one available for (the same algorithm on) MESC.In paper [10] we apply this problem to worst-case fairness in cooperative games.

6. Phase transitions in Combinatorial Optimization.


an old favorite, no longer my main interest

Though I still care about random structures and algorithms and will occasionally publish papers related to phase transitions, I no longer consider this area the main focus of my interests. 


[11] Z. Néda, L. Davydova, S. Újvari, G. Istrate. Gambler’s ruin problem on Erdös-Rényi graphs. Physica A, (to appear).

[10] G. Istrate, C. Bonchiș. Heapability, interactive particle systems, partial orders: results and open problems, In Proceedings of the 18th Annual Symposium on Descriptive Complexity of Formal Systems (DCFS’ 2016). Lecture Notes in Computer Science, Springer Verlag, 2016.

[9] G. Istrate, C. Bonchis and L.P. Dinu. The Minimum Entropy Submodular Set Cover Problem. In Proceedings of the 10th Annual Symposium on Languages, Automata and Applications (LATA’ 2016). Lecture Notes in Computer Science, Springer Verlag, 2016.

[8] Gabriel Istrate, Cosmin Bonchis. Partition into heapable sequences, heap tableaux and a multiset extension of Hammersley’s process. In Proceedings of the 26th Annual Symposium on Combinatorial Pattern Matching (CPM’ 2015). Lecture Notes in Computer Science, Springer Verlag, 2015.

[7] Gabriel Istrate. Identifying almost-sorted permutations from TCP buffer dynamics. Scientific Annals of Computer Science (special issue dedicated to professor Sergiu Rudeanu’ s 80th birthday), XXV (1), pp. 133-154, 2015.

[6] Gabriel Istrate. Reachability and Recurrence in a Modular Generalization of Annihilating Random Walks (and lights-out games) to hypergraphs. Theoretical Computer Science , 580, pp. 83-93, 2015.

[5] James Aisenberg, Samuel Buss, Maria-Luisa Bonet, Adrian Crãciun, Gabriel Istrate. Short Proofs for the Kneser -Lovasz Coloring Principle. Proceedings of the 42nd International Workshop on Automata, Languages and Programming (ICALP’2015). Lecture Notes in Computer Science, Springer.  Journal version submitted to special issue dedicated to ICALP of Information and Computation.

[4] Gabriel Istrate, Cosmin Bonchis, Mircea Marin. Interactive Particle Systems and Random Walks on Hypergraphs. Presented at 10th International Workshop on Developments in Computational Models (DCM’ 14). 2014. Complete version under submission to Random Structures and Algorithms.

[3] Gabriel Istrate, Adrian Craciun. Proof complexity and the Lovasz-Kneser Theorem. In Proceedings of the 17th International Conference on Theory and Applications of Satisfiability Testing (SAT’ 14), vol. 8561 , pp. 138-153. Lecture Notes in Computer Science, Springer Verlag, 2014.

[2] C. Bonchis and G. Istrate. Improved approximation algorithms for low-density instances of the Minimum Entropy Set Cover Problem. Information Processing Letters, 114(7), p. 360–365, 2014.

[1] G. Istrate, M.V. Marathe and S.S. Ravi. Adversarial scheduling in discrete models of social dynamics. Mathematical Structures in Computer Science, 22(5), pp. 788-815, 2012.


[10] C. Bonchis and G. Istrate. Worst-case fairness in TU-cooperative games: A parametric approach
currently in revise and resubmit status.