Theoretical Computer Science Group

PREPRINT Archive

All versions below are unrefereed (though subsequent versions may have been published), and have the status of a preprint version.

21. Zoltan Neda, Larissa Davidova, Szerena Ujvari, Gabriel Istrate. Gambler’s ruin game on Erdos-Renyi graphs

20. Gabriel Istrate, Cosmin Bonchiș. Heapability, interactive particle systems, partial orders: results and open problems

19. Mircea Marin, Temur Kutsia, Besik Dundua. A Rewrite-based Computational Model for Functional Logic Programming.

18. Gabriel Istrate, Cosmin Bonchiș, Liviu P. Dinu. The Minimum Entropy Submodular Set Cover Problem

17. Gabriel Istrate. Two notes on generalized Darboux properties and related features of additive functions.

16. Gabriel Istrate, Cosmin Bonchiș Parameterized complexity of computing power indices in cooperative skill games with agent failures.

15. Gabriel Istrate, Cosmin Bonchiș Partition into heapable sequences, heap tableaux and a multiset extension of Hammersley’s process.

14. James Aisenberg, Samuel Buss, Maria-Luisa Bonet, Adrian Crãciun, Gabriel Istrate. Short Proofs for the Kneser -Lovasz Coloring Principle.

13. Cosmin Bonchiș, Gabriel Istrate Worst-case fairness in TU-cooperative games: A parametric approach

12.  Gabriel Istrate Identifying almost sorted permutations from TCP buffer dynamics

11. Gabriel Istrate, Cosmin Bonchiș, Mircea Marin. Interactive Particle Systems, Explosive Random Walks on Hypergraphs and the WalkSAT algorithm.

10. Gabriel Istrate, Mircea Marin. Learning cover context-free grammars from structural data.

9. Besik Dundua, Mario Florido, Temur Kutsia, Mircea Marin. Constraint Logic Programming for Hedges: A Semantic Reconstruction.

8. Temur Kutsia, Mircea Marin. Regular-expression Order-sorted Unification and Matching. RISC-Linz Technical Report TR-12-14. RISC Institute, Schloss Hagenberg, 2013. 40 pages.

7.  Adrian Crãciun, Gabriel Istrate. Proof complexity and the Lovász-Kneser Theorem

6. Adrian Crãciun, Gabriel Istrate. Topological obstructions to the colorability of gain graphs.

5. Gabriel Istrate The dynamics of two triadic models of opinion formation.

4. Gabriel Istrate Reachability and Recurrence in a Modular Generalization of Annihilating Random Walks (and lights-out games) on hypergraphs.

3. T. Kutsia, M. Marin. Solving, Reasoning, and Programming in Common Logic. RISC-Linz Technical Report TR-12-15. RISC Institute, Schloss Hagenberg, 2013. 18 pages.

2. Gabriel Istrate, Madhav V. Marathe, S.S. Ravi. Adversarial Scheduling in Discrete Models of Social Dynamics Mathematical Structures in Computer Science 22(5), pp. 788-815, 2012. @Cambridge University Press. See Gabriel Istrate’s webpage for free full version.

1. Cosmin Bonchis, Gabriel Istrate. Improved Approximation Algorithms for Low-Density Instances of the Minimum Entropy Set Cover Problem