Gabriel Istrate

My CV.

Scientific Videos & Media appearances.

I have recently published papers at conferences such as AAMAS (2019,2020,2021), ICALP, TARK, ESA, SAT, IPEC, CPM.
I have recently been 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).

Here a list of all my research papers , and another one of papers grouped by research topic.



[21] Gabriel Istrate, Cosmin Bonchis, Adrian Craciun. Kernelization, Proof Complexity and Social Choice. Proceedings of the 48th International Conference on Automata, Languages and Programming (ICALP’2021), July 12-16, 2021, Glasgow UK (online), Leipzig Proceedings in Informatics (LIPICS), to appear.

[20] Gabriel Istrate. Game-theoretic Models of Moral and Other-Regarding Agents. Proceedings of the 18th Conference on Theoretical Aspects of Rationality and Knowledge (TARK’2021), June 25-27, 2021, Tsinghua University, Beijing, China (online),  (to appear).

[19] Gabriel Istrate. Models We Can Trust: Towards a Systematic Discipline of (Agent-Based) Model Interpretation and Validation. Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems, AAMAS’2021, 6-11, 2021.


[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, paper #7, 2020.

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

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


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