Commented papers.
all my papers, in reverse chronological order; in construction; does not include some technical reports I no longer want to eventually publish.
2012:
[37] Gabriel Istrate, Madhav V. Marathe, S.S. Ravi. Adversarial Scheduling in Discrete Models of Social Dynamics. Mathematical Structures in Computer Science
2009:
[36] Gabriel Istrate. Geometric Properties of Satisfying Assignments of random ε-1-in-k SAT. International Journal of Computer Mathematics, 2009.
From previous work I knew that 1-in-k SAT is somewhat "similar" to 2-SAT, which has a single cluster of solutions in its satisfiable phase. I tried to prove the same result for 1-in-k SAT. I couldn't (for technical reasons), but here are my results bringing evidence for this intuition. They apply to a generalization of this problem studied by Zdeborova et al.
[35]. Gabriel Istrate. On Hadwiger's number of a graph with partial information, submitted to Applied Mathematics Letters, 2009. Can you convert an upper bound for the chromatic number of a graph into an upper bound for the Hadwiger number ? Sometimes yes, sometimes no. When is the answer positive ? Find out the (beginning of an) answer in this (rather simple) note.
[34]. G. Istrate. On the dynamics of Social Balance on general networks (with an application to XOR-SAT). Fundamenta Informaticae, (special issue on Machines, Computation and Universality), 91 (2), pp. 341-356, 2009.
I study a discrete dynamical system introduced by Sid Redner, motivated by Heider's social balance theory. Unlike Sid, I study the dynamics on a general graph and am interested in how the structure of the graph impacts the convergence/convergence time. I obtain some partial results in this direction. One of the nicest outcomes of this is a connection with a generalization of annihilating random walks to hypergraphs. Curiously, the same dynamics can be interpreted as a local search algorithm for solving the so-called 3-XOR-SAT problems. One of my nicer papers so far.
2008:
[33] Allon Percus, Gabriel Istrate, Bruno Goncalves, Robert Z. Sumi, Steffan Boettcher. The peculiar phase structure of random graph bisection, Journal of Mathematical Physics, 49 (12), p. 125219, 2008.
My first "Physics" (a.k.a. non-rigorous math) paper. We deal with an old problem: bisection of random graphs. We prove an upper bound on the bisection width based on the analysis of a "core peeling" algorithm, together with some heuristic arguments that a more complex form of this algorithm should find optimal solutions close to the phase transition, due to a replica symmetry property.
[32]. Anders Hansson, Gabriel Istrate.Counting preimages of TCP reordering patterns.Discrete Applied Mathematics, 156(17), pp. 3187-3193, 2008. 2008.
Similar problem as in paper [26], this time for the "real" buffer size measure. Results are much nicer, in particular you can count preimages in polynomial time. This is one the cutest little papers I have written.
[31]. Gabriel Istrate, Stochastic Stability in Schelling's Segregation Model with Contagion. Presented at the 5th European Conference on Complex Systems (ECCS'08), Jerusalem, Israel, September 14-19 2008
Well the title says it all: I study the stochastic stability (a la Peyton Young) of segregated states in Schelling's Segregation Model with a (somewhat) non-trivial influence mechanism. A copy of the paper is forthcoming soon.
[30]. Gabriel Istrate. Grammatical Inference and Symbolic Dynamics. Presented at the 5th European Conference on Complex Systems (ECCS'08), Jerusalem, Israel, September 14-19, 2008. 2008.
Can you learn ET0L like grammars from queries (a la Angluin) ? Yes, in the presence of the correct structural information. It's even better when this formal language result is motivated by learning symbolic representations of dynamical systems. Look for a preprint soon.
[29]. 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.
This is another paper in dire need for a journal version. Its purpose was to sell the idea of adversarial scheduling to the Social Simulation Community. As for the technical contribution, I developed the approach on a bottom-up model, that starts very simple and gradually adds more realistic features.
[28]. Gabriel Istrate, M.V. Marathe, S.S. Ravi."Adversarial Scheduling Analysis of Game-Theoretic Models of Norm Diffusion", Proceedings of the Fourth Computability in Europe Conference (CIE'2008), A. Beckmann et al (editors), Lecture Notes in Computer Science, vol. 5028, pp. 273-282 (2008)
What happens to Peyton Young model of norm diffusion when the order in which agents are given the chance to update changes from random scheduler to an adversarially specified one ? It all depends on the scheduler properties. The most interesting result considers a scheduling model that incorporates "contagion": agents' scheduling is given by a random walk on a certain graph (not the same as the original graph employed in the model).
2007:
[27]. Gabriel Istrate. "Satisfying assignments of Random Boolean CSP: Clusters and Overlaps", Journal of Universal Computer Science, vol. 13, no.11 (2007), pp. 1655-1670. A preliminary version of this paper has appeared in the Proceedings of the Third European Conference on Complex Systems (ECCS'07)
Mezard et al. have invented a neat method to prove the existence of clusterings of solutions in random k-satisfiability, for large k. Their method involves two steps:
- proving that a certain "q-overlap" version of k-SAT has a sharp threshold for all k.
- proving that the threshold location is a non-monotone function of q.
I investigate the applicability of this method for general constraint satisfaction problems, specified using Molloy's framework. I give two results:
- First, the first step of Mezard's approach can be applied whenever the constraint satisfaction problem has a sharp threshold.
- I show that the second condition fails for random 2-satisfiability (which was expected, from replica symmetry considerations).
2006:
[26]. Anders Hansson, Gabriel Istrate and Shiva Prasad Kasiviswanathan. Combinatorics of TCP Reordering. Journal of Combinatorial Optimization, 12 (1-2), pp. 57-70, 2006.
Work done as a summer research project with a student. It deals with the following problem: suppose a sequence of packet ID's comes at the receiver. A buffer is used to store out-of-order packets. Can one decide whether a sequence of buffer sizes corresponds to a sequence of ID's and, moreover count the number of such sequences ?
The paper used a model of buffer information with a practical motivation. It gave a polynomial decision algorithm and FPRAS'es in some special cases. It turns out (paper 32 in the list) that results are much nicer for real buffer sizes (though less practically relevant).
[25]. 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.
When is a metric for packet reordering useful ? Of course, it all depends on your purpose (if you can tolerate some amount of reorder then the number of inversions is not a very good metric). On the other hand a measure that takes different values on two sequences that you regard as "equivalent for practical purposes" is obviously not a good one. The paper puts forth this idea and illustrates it in the context of the following equivalence notion: two sequences of packet IDs are equivalent if they lead to the same ACKs. The paper proves several results regarding the consistency of metrics from the literature with respect to this equivalence notion.
[24]. 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
If you model a radio network by unit disk graphs you can use distance-two matchings as a proxy for network capacity (this was invented in a JSAC paper by Marathe, Balakrishnan et al.). This paper gives approximation algorithms for distance-two matchings for various classes of graphs relevant in the networking problem. This is a nice area, though results of Moscibroda show that the unit-disk graph model is not realistic as a mathematical abstraction of interference.
[23]. 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.
Despite the fact that I'm a theoretician, this is a primarily "experimental" paper. We wanted to model large TCP traces, as seen using receiver information only. One requirement was to model packet dynamics, in a way that captures packet reordering. The goal is to substantially "compress" traces, in a way that preserves the semantics of TCP.
In all fairness we did not come with a full model (though it can be completed to a full model using more recent work by Jayasumana et al.). On the other hand, the paper (that took a good deal of soul and a few years to complete) introduced a number of nice modeling ideas, in a field that is about as far from my competence as I could think of.
[22]. 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.
The introductory chapter to our book. I believe it offers a nice outline of some of the main issues of the area of phase transitions in combinatorial optimization, circa 2006.
[21]. Gabriel Istrate. Threshold properties of random boolean constraint satisfaction problems. Discrete Applied Mathematics, 153 (1-3), pp. 141-152, 2005.
I use Friedgut's results to classify the threshold properties of random boolean constraint satisfaction problems in Molloy's model. Nice, but Nadia Creignou and Herve Daude have a paper on the same problem that appeared in print slightly earlier.
[20]. 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.
My nicest paper so far (but a very hard sell).
Why is it that first-order phase transitions are often correlated with exponential behavior of certain algorithms(e.g. Davis Putnam) ? The answer is that often there is a common cause that implies both: the emergence of a large minimally unsatisfiable subformula at the phase transition. So in a sense the complexity-theoretic implications of first-order phase transitions are somewhat dissapointing: it's the combinatorial structure of the formula, no deep physics explanation.
[19]. 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.
I compute the satisfaction probability of a random Horn formula generated using the following random model: all clauses of length at most k are chosen uniformly at random as a new clause to include in the formula.
Also, I give a (pretty nice) explanation of the following property, similar to one conjectured based on experimental evidence for k-SAT: (when suitably rescaled) the curves for the "finite k" cases converge (as k goes to infinity) to the curve for uniform satisfiability (determined in paper [17] below). The reason has to do with a property of positive unit resolution: w.h.p. it will accept a formula (if at all) in the first constantly many steps. Thus large clauses do not have the time to become unit clauses (and influence the acceptance decision).
[18]. 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.
A non-reversible Markov chain with an interesting dynamics (and dependence on the graph topology). A paper that started with a conversation at a DIMACS conference.
[17]. 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.
This is part of my Ph.D. thesis, and got me a citation in this book (the main result is an exercise there). Needless to say, I am extremely happy !
The result answers the following question: what is the probability that a random Horn formula is satisfiable ?
[16]. Gabriel Istrate, Madhav V. Marathe and S. S. Ravi. Adversarial models in evolutionary game dynamics. In Proceedings of the Twelfth Annual Symposium on Discrete Algorithms (SODA'01), Washington, DC, USA. 2001.
Early work on adversarial analysis. You can grab the final version (submitted to a journal) from here.
[15]. 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.
My most cited paper. 'nuff said. Really have to complete the journal version.
[14] Gabriel Istrate. Computational Complexity and Phase Transitions. In Proceedings of the 15th I. E. E. E. Conference on Computational Complexity. 2000.
Technically the most difficult paper I wrote. Sadly, the random model I was proposing has lost the battle with the random CSP model of Mike Molloy.
[13]. 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.
An undergraduate research project I cosupervised turned into a research note. And a collaboration with a nice Rochester complexity theorist :).
[12]. Gabriel Istrate. Looking for a version of Schaefer's Dichotomy Theorem when each variable appears at most twice. TR , University of Rochester, 1997.Well, what can I say ? Seems I was the first one to study the complexity of this problem. I didn't solve it (but part of it is still unsolved today). I didn't believe the results were worth publishing, but probably will publish them now that the paper started being cited.
[11]. 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.My only published paper in Computational Complexity really (and in an A.I. conference). It deals with the complexity of some constraint satisfaction problems, specifically with some framwork invented by Cooper, Cohen and Jeavons. I extend their results to some other types of problems (counting, maximum satisfiability, inverse satisfiability). A nice little paper, but superseded by now by stronger results in the literature.
[10]. G. Istrate .The Strong Equivalence of ET0L Grammars,Information Processing Letters, vol. 62(1997), 171--177. This is a paper essentially completed during my undergraduate years, in fact its conference version has appeared in the Proceedings of the First Developments in Language Theory conference (1993). In essence I prove a result about "strong" notion of equivalence applied to Lindenmayer systems. For such systems, usual language equivalence is undecidable. To obtain a decidable property one has to provide some information about the structure of parse trees of the unknown grammar. I give one notion of equivalence that is decidable. Strangely enough, I found an application of the ideas in this paper more than ten years after the paper was completed :) ...
[9]. Gabriel Istrate. Sums of continuous and Darboux functions. Real Analysis Exchange, 20 (2), pp. 842-846, 1995.
A paper written essentially in 1993, it is part of my bachelors thesis in Romania.
[8]. G. Istrate.Some remarks on almost periodic strings and sequences, in G. Paun (editor), Mathematical Linguistics and Related topics, Ed. Academiei, Bucharest 1994.
I actually don't have a copy of this paper anymore ! It's a short note, which essentially uses the pumping lemma to prove the fact that the language of prefixes of an infinite quasiperiodic word cannot be context-free but nonregular. This solves an open problem by Marcus. This (and much more) has been independently proved more than 10 years afterwards by ... (RAIRO).
[7] G. Istrate, Gh. Paun Some combinatorial properties of self-reading sequences. Discrete Applied Mathematics, 55(1), 1994, pp. 83-86.
This is also a rather short, paper, completed while I was still an undergraduate student :). Like the previous paper, this one has appplications to symbolic dynamics, namely in studying the disjunctiveness of kneading sequences. See this article for an overview of disjunctiveness in Theoretical Computer Science, and this for the (symbolic dynamics related) good stuff :).
[6]. G. Istrate, Self-reading sequences, Discrete Applied Mathematics Volume 50, Issue 2 (1994), Pages 201-203.
OK, this is a short one, but I was an undergraduate student at the time :). Basically, I was traveling between Galati and Bucharest, Romania (a four hour train trip), the only thing to read was an issue of the Bulletin of the EATCS, that contained an article due to A. Salomaa and G. Paun with several open problems. By the time the train reached Bucharest (despite not having any pen and paper) I had solved one of the open problems in their article :). Namely, so-called self-reading sequences are not ultimately periodic. Despite its length/somewhat frivolous history, the paper turns out to be useful, especially in gauging the complexity of kneading sequences in Applied Symbolic Dynamics.
[5]. C. Calude, G. Istrate, M. 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.
[4]. G. Istrate On two generalizations of the Darboux Property, Real Analysis Exchange (1991/92).
[3]. G. Istrate, C. Calude. Determining and stationary sets for some classes of partial recursive functions.Theoretical Computer Science 82(1), pp. 151-155 (1991).
Translate (and adapt) the concepts of determining and stationary sets from real analysis (where they were defined by Solomon Marcus) to recursive function theory. Nice concepts, fairly easy results.
[2]. G. Istrate, On the size of boolean-valued partial recursive functions. Analele Universitatii din Bucuresti.
[1]. G. Istrate, On a problem about contextual languages, Bulletin mathematique de la Societe des Sciences Mathematiques de Roumanie, 33 (81), 1989.
My first attempt at scientific research, I was still not even an undergraduate student at the moment of submitting it. It deals with the problem of showing that every regular language is inner contextual (an open problem at the time).
2009
2008
2007
2006
2005
2004
2002
2001
2000
1997
1994
1992
1991
1989