Ad Astra Awards
Ad Astra Journal
Science library
White book
University rankings
Who's who
Theses and dissertations
Ad Astra association
Press releases
Funding opportunities
>> Românã

Gabriel Istrate

West University of Timisoara and the e-Austria Research Institute , Timisoara, Romania

Institution web page:
Personal web page:
Send email

Born: 1970

Interests: computational complexity, probabilistic analysis of algorithms, phase transitions in combinatorial problems, theoretical foundations of complex systems, simulation of multiagent systems, game theory, combinatorial and algorithmic methods in economics and networks

West University of Timisoara: Formally joined as an associate professor in 2013.

IEAT: Joined in March 2007, as a fellow of a Marie Curie International Reintegration Grant. Between October 2010 and May 2012 I was also affiliated with the Center for the Study of Complexity, Babes-Bolyai University, Cluj, Romania.

Technical Staff Member, Los Alamos
National Laboratory, September 2001 - February 2007.

Director's Fellow (postdoc), Los Alamos
National Laboratory, (September 1999-
August 2001).

Ph.D., Computer Science, University of Rochester (1999).

B.D. Mathematics, University of Bucharest (1994)

Selected publications:
• Gabriel Istrate, Cosmin Bonchis, Liviu P. Dinu. The Minimum Entropy Submodular Set Cover Problem . In Proceedings of the 10th International Conference on Language and Automata Theory and Applications (LATA' 2016), pp. 295-306. Lecture Notes in Computer Science, vol. 9618, Springer Verlag , 2016.
• Gabriel Istrate. Two notes on generalized Darboux properties and related features of additive functions. Analele Universitatii Bucuresti Ser. Informatica, special issue dedicated to Professor Solomon Marcus' s 90th birthday , LXII (2), pp. 61-76, 2015.
• James Aisenberg, Maria Luisa Bonet, Sam Buss, Adrian Craciun and Gabriel Istrate. Short Proofs of the Kneser-Lovász Coloring Principle. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015) , Lecture Notes in Computer Science vol. 9135, pp. 44-55. 2015.
• 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 9133, pp. 261-271. Springer Verlag, 2015.
• 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.
• 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.
• Gabriel Istrate, Cosmin Bonchis, Mircea Marin. Interactive Particle Systems and Random Walks on Hypergraphs. In 10th International Workshop on Developments in Computational Models (DCM' 14). 2014.
• Mircea Marin and Gabriel Istrate. Learning cover context-free grammars from structural data. In Proceedings of the 11th International Colloquium on Theoretical Aspects of Computing, (ICTAC'14). Springer Verlag, Lecture Notes in Computer Science, 2014.
• 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.
• 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.
• Gabriel Istrate, Madhav 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.
• Gabriel Istrate. Geometric Properties of Satisfying Assignments of random $epsilon$-1-in-k SAT. International Journal of Computer Mathematics, 86(12), pp. 2029-2039, 2009.
• Gabriel Istrate. On the dynamics of Social Balance on general networks (with an application to XOR-SAT). Fundamenta Informaticae, 91 (2), pp. 341-356, 2009.
• Allon Percus, Gabriel Istrate, Bruno Tavares Gonçalves, Robert Z. Sumi, Stefan Boettcher . The Peculiar Phase Structure of Random Graph Bisection. Journal of Mathematical Physics, 49 (12), p. 125219, 2008.
• Gabriel Istrate. Dissecting the Artificial: The Adversarial Scheduling approach to validating Game-Theoretic models and Social Simulations. In Proceedings of the Fifth Conference of the European Social Simulation Association (ESSA' 08), Brescia, Italy, September 1-5. 2008.
• Gabriel Istrate. Stochastic Stability in Schelling's Segregation Model with Contagion. In 5th European Conference on Complex Systems (ECCS' 08), Jerusalem, Israel, September 14-19 . 2008.
• Gabriel Istrate. Grammatical Inference and Symbolic Dynamics. In 5th European Conference on Complex Systems (ECCS' 08), Jerusalem, Israel, September 14-19, 2008. 2008.
• Gabriel Istrate, Madhav V. Marathe, S. S. Ravi. Adversarial Scheduling Analysis of Game-Theoretic Models of Norm Diffusion. In Arnold Beckmann, Costas Dimitracopoulos, and Benedikt Löwe (eds.), Proceedings of the Fourth Computability in Europe Conference (CIE' 2008), Lecture Notes in Computer Science vol. 5028, pp. 273-282. Springer Verlag, 2008.
• Anders Hansson, Gabriel Istrate. Counting preimages of TCP reordering patterns. Discrete Applied Mathematics, 156(17), pp. 3187-3193, 2008.
• Gabriel Istrate. Satisfying assignments of boolean random Constraint Satisfaction Problems: Clusters and Overlaps. Journal of Universal Computer Science, 13(11), pp. 1655-1670, 2007.
• Cristopher Moore, Gabriel Istrate, Demetrios Demopoulos and Moshe Y. Vardi. A Continuous-Discontinuous Second-Order Transition in the Satisfiability of Random Horn-SAT Formulas. Random Structures and Algorithms, 31(2), pp. 173-185, 2007.
• Gabriel Istrate, Anders Hansson, Charles D. Tallman, Leticia Cuellar-Hengartner and Nicolas Hengartner. Towards Generative Activity-based Models for Large-scale Socio-technical Simulations. In D. Sallach, C. Macal and M. North (eds.), Proceedings of The AGENT 2006 Conference " Social Agents. Results and Prospects" , ANL/DIS-06-7, ISBN 0-9679178-7-9, co-sponsored by Argonne National Laboratory and The University of Chicago. 2006.
• Gabriel Istrate, Anders Hansson and Guanhua Yan. Packet Reordering Metrics: Some Methodological Considerations. In Proceedings of the Second International Conference on Networking and Services (ICNS' 06), Workshop on Internet Packet Dynamics, San Jose CA. IEEE Computer Society Press, ISBN 0-7695-2622-5, 2006.
• Anders Hansson, Gabriel Istrate and Shiva Prasad Kasiviswanathan. Combinatorics of TCP Reordering. Journal of Combinatorial Optimization, 12 (1-2), pp. 57-70, 2006.
• Gabriel Istrate, Anders Hansson, Madhav V. Marathe, Sunil Thulasidasan and Christopher L. Barrett. Semantic compression of TCP traces. In Proceedings of the IFIP NETWORKING Conference, F. Boavida et al. (editors), pp. 123-135. Lecture Notes in Computer Science, vol. 3976, Springer Verlag, 2006.
• Christopher L. Barrett, Gabriel Istrate, V. S. Anil Kumar, Madhav V. Marathe, Shripad Thite and Sunil Thulasidasan. Strong Edge Coloring for Channel Assignment in Wireless Radio Networks. In Proceedings of the Fourth IEEE International Conference on Pervasive Computing (PERCOMW' 06), Workshop on Foundations and Algorithms for Wireless Networking, pp. 106-110. IEEE Computer Society Press, ISBN 0-7695-2520-2, 2006.
• Allon Percus, Gabriel Istrate and Cristopher Moore. When Statistical Physics Meets Computation. In Computational Complexity and Statistical Physics, pp. 3-30. Oxford University Press, Santa Fe Institute Lectures in the Sciences of Complexity, ISBN 019517738X, 2005.
• Allon Percus, Gabriel Istrate and Cristopher Moore (editors). Computational Complexity and Statistical Physics. Oxford University Press, Santa Fe Institute Studies in the Sciences of Complexity, ISBN 019517738X, 2005.
• Gabriel Istrate. Threshold properties of random boolean constraint satisfaction problems. Discrete Applied Mathematics, 153 (1-3), pp. 141-152, 2005.
• Gabriel Istrate, Stephan Boettcher and Allon Percus. Spines of Random Constraint Satisfaction Problems: Definition and Connection with Computational Complexity. Annals of Mathematics and Artificial Intelligence, 44 (4), pp. 353 - 372, 2005.
• Gabriel Istrate. On the satisfiability of random k-Horn formulae. In P. Winkler and J. Nesetril (eds.), " Computational Complexity and Statistical Physics" , pp. 113-136. AMS-DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 2004.
• Leslie A. Goldberg, Catherine Greenhill, Martin Dyer, Gabriel Istrate and Mark Jerrum. The convergence of the Iterated Prisoner' s Dilemma game. Combinatorics, Probability and Computing, 11, pp. 135-157, 2002.
• Gabriel Istrate. The Phase Transition in Random Horn satisfiability and its algorithmic implications. Random Structures and Algorithms, vol. 20 no. 4, pp. 483-506, 2002.
• Dimitris Achlioptas, Arthur Chtcherba, Gabriel Istrate and Cristopher Moore. The phase transition in 1-in-k SAT and NAE 3SAT. In Proceedings of the Twelfth ACM-SIAM Symposium on Discrete Algorithms (SODA' 01), Washington, DC, USA. 2001.
• Gabriel Istrate. Computational Complexity and Phase Transitions. In Proceedings of the 15th I. E. E. E. Conference on Computational Complexity, pp. 104-115. 2000.
• Russell Bent, Michael Schear, Lane Hemaspaandra and Gabriel Istrate. A Note on Bounded-Weight Error-Correcting Codes. Journal of Universal Computer Science, 5 (12), pp. 817-827, 1999.
• Gabriel Istrate. The Strong Equivalence of ET0L Grammars. Information Processing Letters, 62(4), pp. 171-176, 1997.
• Gabriel Istrate. Counting, Structure Identification and Maximum Consistency for Binary Constraint Satisfaction Problems. In G. Smolka (ed.), Proceedings of the Third International Conference on Principles and Practice of Constraint Programming - CP 1997, Linz, Austria, pp. 136-149. Springer Verlag, Lecture Notes in Computer Science 1330, 1997.
• Gabriel Istrate. Sums of continuous and Darboux functions. Real Analysis Exchange, 20 (2), pp. 842-846, 1995.
• Gabriel Istrate, Gheorghe Paun. Some Combinatorial Properties of Self-reading Sequences. Discrete Applied Mathematics, 55(1), 1994.
• Gabriel Istrate. Self-reading sequences. Discrete Applied Mathematics, 50(2), 1994.
• Gabriel Istrate. On two generalizations of the Darboux property. Real Analysis Exchange, 17(2), pp. 535-544, 1992.
• Cristian Calude, Gabriel Istrate and Marius Zimand. Recursive Baire Classification and Speedable Functions. Zeitschrift fur Mathematical Logik und Grundlagen der Mathematik (now called Mathematical Logic Quarterly), 38(1), pp. 169-178, 1992.
• Cristian Calude and Gabriel Istrate. Determining and Stationary Sets for Some Classes of Partial Recursive Functions. Theoretical Computer Science, 82(1), pp. 151-155, 1991.
• Gabriel Istrate. On a problem about contextual languages. Bulletin mathématique de la Société des Sciences Mathématiques de Roumanie Nouvelle Série, 33 (81), No. 4 , pp. 335-338, 1989.
• Gabriel Istrate. On a problem about contextual languages. Bulletin mathématique de la Société des Sciences Mathématiques de Roumanie Nouvelle Série, 33 (81), No. 4 , pp. 335-338, 1989.
• Gabriel Istrate. ON A PROBLEM ABOUT CONTEXTUAL LANGUAGES. Bulletin mathématique de la Société des Sciences Mathématiques de Roumanie Nouvelle Série, 33 (81), No. 4 , pp. 335-338, 1989.

Publications from the ISI database, indexed between 2002-2011, produced in Romania:
• Istrate, G, Satisfying assignments of random boolean constraint satisfaction problems: Clusters and overlaps. JOURNAL OF UNIVERSAL COMPUTER SCIENCE, 13 (11), pp. 1655-1670, 2007.
• Hansson, A; Istrate, G, Counting preimages of TCP reordering patterns. DISCRETE APPLIED MATHEMATICS, 156 (17), pp. 3187-3193, 2008.
• Percus, AG; Istrate, G; Goncalves, B; Sumi, RZ; Boettcher, S, The peculiar phase structure of random graph bisection. JOURNAL OF MATHEMATICAL PHYSICS, 49 (12), p. , 2008.
• Istrate, G, On the Dynamics of Social Balance on General Networks (with an application to XOR-SAT). FUNDAMENTA INFORMATICAE, 91 (2), pp. 341-356, 2009.
• Istrate, G, Computational Complexity: a Conceptual Perspective. JASSS-THE JOURNAL OF ARTIFICIAL SOCIETIES AND SOCIAL SIMULATION, 12 (4), pp. A278-A281, 2009.
• Istrate, G, Geometric properties of satisfying assignments of random epsilon-1-in-k SAT. INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 86 (12), pp. 2029-2039, 2009.
More information


© Ad Astra 2001-2013