My CV.
I have recently published papers at conferences such as AAMAS (twice), ICALP, ESA, SAT, IPEC, CPM.
I have recently been (or will be) a P.C. member (or organizer) of events such as AAMAS 2021, AAAI 2021, SOFSEM 2019, MCU 2018, FOIKS 2018, ALGOCLOUD 2017, Diaspora Științifică 2016, MCU 2015 and, of course, many editions of SYNASC and MATCOS.
I was funded by research projects such as:
- 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 see myself as a generalist,with a long and eclectic list of interests. I have published papers in physics journals, in computer networking and artificial intelligence conferences, I have worked on proof complexity, analysis of real functions, hope to publish some day in journals in economics (mainly game theory) and analytic philosophy.
Still, a significant fraction of my interests lies in Theoretical Computer Science, mainly in algorithms and computational complexity. On the other hand, many of the models and problems I cared about have an interdisciplinary nature, relating to the Physics of Complex Systems or to Social Dynamics (or both 😀). Through my recent work on Game Theory I also became interested in Artificial Intelligence (particularly from a symbolic perspective).
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
Approximation, parameterized, online algorithms.
3. The Maximum Binary Tree problem.
2. The Minimum Entropy Submodular Set Cover problem and its approximability.
1. Approximability of the Minimum Entropy Set Cover on sparse instances.
Combinatorial 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)](http://s0.wp.com/latex.php?latex=E%5BMinHeap%5B%5Cpi%5D%5Csim+%5Cfrac%7B1%2B%5Csqrt%7B5%7D%7D%7B2%7D%5Ccdot+%5Cln%28n%29&bg=ffffff&fg=000&s=0 "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.
3. Computational complexity.
Proof Complexity.
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 
4. Algorithmic Game Theory.
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.
Game-theoretic models on networks.
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.
Adversarial scheduling analysis.
6. Phase transitions in Combinatorial Optimization.
an old favorite, no longer my main interest
SOME RECENT PAPERS:
[18] Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubang Kulkarni, Young-San Lin, Minshen Zhou. Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree. In Proceedings of the 15 International Symposium on Parameterized and Exact Computation (IPEC’20), Leibniz Institute Proceedings in Computer Science (LIPICS), vol. 180 (to appear).
[17] Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubhang Kulkarni, Young-San Lin, Minshen Zhu, The Maximum Binary Tree Problem. In Proceedings of the 28th European Symposium on Algorithms (ESA’2020), LIPICS vol. 173, paper #30, 2020.
[16] J. Balogh, C. Bonchiș, D. Diniș, G. Istrate, I. Todinca. On the heapability of finite partial orders. Discrete Mathematics and Theoretical Computer Science, vol 22, no 1, 2020, paper #17.
[15] Gabriel Istrate, Cosmin Bonchiș, Claudiu Gatina, It’s not whom you know, it’s what you (or your friends) can do: Coalitional Frameworks for Network Centralities, Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS’2020, pp. 566-574, 2020.
[14] Gabriel Istrate, Cosmin Bonchis, Alin Brindusescu, Attacking Power Indices by Manipulating Player Reliability, Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’19), 2019.
[13] James Aisenberg, Samuel Buss, Maria-Luisa Bonet, Adrian Crãciun, Gabriel Istrate. Short Proofs for the Kneser -Lovasz Coloring Principle. Information and Computation, 2018. Earlier conference version in the Proceedings of the 42nd International Workshop on Automata, Languages and Programming (ICALP’2015). Lecture Notes in Computer Science, Springer.
[12] Gabriel Istrate, Stochastic Stability in Schelling’s Segregation Model with Markovian Asynchronous Update, Proceedings of the Fifth International Workshop on Asynchronous Cellular Automata and Asynchronous Discrete Models (ACA’18), Satelite Workshop of ACRI’2018, Lecture Notes in Computer Science, vol. 11115, Springer Nature, 2018.
[11] 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.
[10] 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.
[9] 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.
[8] 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.
[7] 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.
[6] 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.
[5] 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.
[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 (UNPUBLISHED) PAPERS:
[U2] Gabriel Istrate, Cosmin Bonchis, Mircea Marin. Interactive Particle Systems on Hypergraphs, Drift Analysis and the WalkSAT algorithm. Submitted.
[U1] C. Bonchis and G. Istrate. Worst-case fairness in TU-cooperative games: A parametric approach. Currently in revise and resubmit status.