Here is an IN PROGRESS listing of every area I have worked on, roughly in the order of adoption (most ancient first) :
1. Formal Languages and Combinatorics on Words
Results in formal language theory.
1. Contextual languages.
to write.
2. Structural equivalence notions for L-systems.
to write
Results in Combinatorics on Words.
1. Self-reading sequences.
to write.
2. Recursive function theory, later Computational Complexity
Effective category in recursive function theory.
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
Dichotomy theorems in Computational Complexity.
To complete.
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 
3. Real Analysis
Weak intermediate-value (Darboux) type properties.
1. Approximability of the Minimum Entropy Set Cover on sparse instances.
2. The Minimum Entropy Submodular Set Cover problem and its approximability.
Additive (a.k.a Hamel) functions.
To complete.
4. Phase transitions in Combinatorial Optimization.
Threshold properties of random Horn Satisfiability.
Classification of threshold properties of random CSP.
5. The Design and Analysis of Algorithms
Analysis of Markov Chain models.
To complete.
Combinatorial and Algorithmic Aspects of Networking and Mobile Computing.
To complete.
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
6. Combinatorial Discrete models in Complex Systems and Social Dynamics.
Adversarial scheduling analysis.
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.
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.
Lights-out games.
7. Networking.
8. Social Networks and Social Simulation.
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.
9. Algorithmic Game Theory.
Worst-case fairness in algorithmic cooperative game theory.
CHRONOLOGICAL PAPER LIST:
[12] J. Balogh, C. Bonchiș, D. Diniș, G. Istrate, I. Todincă. Computing a minimal partition of partial orders into heapable subsets. Manuscript, 2017.
[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.