# Gabriel Istrate

### Short CV – in Romanian.

Events I have been recently (or will be) involved with as a P.C. member/organizer include SOFSEM 2019, MCU 2018, FOIKS 2018, ALGOCLOUD 2017, Diaspora Științifică 2016, MCU 2015 and, of course, many editions of SYNASC.

A list of recent funded research projects includes:

• ATCO “Advanced Techniques in Combinatorial Optimization and Computational Complexity”. 2017-2019.
• STRUCTCOMB,  “Structure and computational difficulty in combinatorial optimization: an interdisciplinary approach”. 2012-2016.
•  PHASETRANS, “Phase transitions in computational complexity and formal verification: towards generic and realistic approaches”.  Marie Curie IRG project. 2007-2009.

## Recent 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 😀)

For a list of all my research interests (including past), please see here.

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

### 1. The Design and Analysis of Algorithms

[-]
[+]

The Minimum Entropy Set Cover Problem (MESC) and its submodular generalization.

#### 1. Approximability of the Minimum Entropy Set Cover on sparse instances.

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.

#### 2. The Minimum Entropy Submodular Set Cover problem and its approximability.

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

[-]
[+]

combinatorial, approximation, online algorithms.

To complete.

### 2. Combinatorics (often motivated by  Complex Systems)

[-]
[+]

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

#### 1. Heapability of random permutations.

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.

#### 2. Heapability of partial orders. Connection with graph algorithms.

In paper [10] we extend heapability to partial orders, proving some results and listing several open problem.

We continue this line of research in paper [12], where heapability of partial orders is related to maximum independent sets and colorings of special classes of graphs. An unexpected connection with Dilworth’s theorem is proved as well.

#### 3. Heapability, formal languages and power series.

In paper [13] we sketch (the beginnings of) an attack on the “golden-ratio conjecture” using formal languages and noncommutative formal power series. Specifically, we study languages and formal power series associated to several variants of Hammersley’s process. We show that:

– the language associated to the ordinary Hammersley process is regular.

– the languages associated to Hammersley’s tree process(es) are deterministic context-free but not regular.

– for the similar processes associated to interval orders there are two version of the language associated to the Ulam-Hammersley problem for random intervals (studied in paper [12]). One of these languages turns out to be equal to the language of the Hammersley tree process. The other version is shown to be non-context-free via an application of Ogden’s lemma.

– we also give algorithms that compute the coefficients of the corresponding formal power series. Using these algorithms we obtain exact distributions of parameters of the Hammersley tree process for a small number of steps. We perform such an analysis for a parameter, called , whose value predicts the location of the transition point in the “golden ratio” conjecture. Unfortunately, Monte Carlo estimations of this parameter show that the convergence of the parameter to its conjectured value, the golden ratio, while consistent with experiments is slow (and cannot be observed from the exact distributions obtained above)

[-]
[+]

Lights-out games.

To write …

### 3. Computational complexity.

[-]
[+]

The complexity of statements from Combinatorial Topology

#### 1. The proof 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.

### 4. Algorithmic Game Theory.

[-]
[+]

Worst-case fairness in algorithmic cooperative game theory.

In paper [10] we adapt our results for the minimum entropy submodular set cover [9] to a framework we call the worst-case fairness in cooperative games.
[-]
[+]

### 5. Discrete Models in Complex Systems and Social Dynamics.

[-]
[+]

The Monopolist Model.

In paper [11] below we study (using experimental and “physics-like” methods) an extension to arbitrary topologies of a discrete model first studied in the Computer Science literature: the monopolist model (first introduced by Domingo and Watanabe and Yamazaki, and further studied by Amano, Tromp, Vitanyi and Watanabe,Bach and Ross) n players compete in a game as follows: each player starts with an arbitary integer amount. In each round each player with nonzero capital puts 1 dollar into a common pot. The pot is won by a random player. Those that are left with zero dollars are eliminated.

On a complete graph the game ends with a single player winning all the money (the monopolist). On other graph topologies (of which Erdos-Renyi graphs are, perhaps, the simplest case) the final outcome is not quite that simple. We find (nonrigorous) formulas tbat describe the final outcome and verify it via Monte Carlo simulations.

[-]
[+]

The Dynamics of Social Balance.

To write …
[-]
[+]

Adversarial scheduling analysis.

To write …

### 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.

### SOME RECENT PAPERS:

[13] Cosmin Bonchiș, Gabriel Istrate, Vlad Rochian. The language (and series) of Hammersley-type processes. In Proceedings of the 8th Conference on Machines, Computations and Universality (MCU’2018), June 28-30, 2018, Fontainebleau, France (to appear) .

[12] J. Balogh, C. Bonchiș, D. Diniș, G. Istrate, I. Todinca. Manuscript, 2018.

[11] Z. Néda, L. Davydova, S. Újvari, G. Istrate. Gambler’s ruin problem on Erdös-Rényi graphs. Physica A, 468, p.147-157, 2017.

[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 to appear 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.

### OTHER PAPERS:

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