Josep Díaz - Selected publications#

1. J. Díaz, L. Kirousis D. Mitsche and X. Pérez: On the Satisfiabilitay Threshold of Formulae with three Literals per Clause. Theoretical Computer Science, 410, 2920-2934, 2009 (This paper presents the best known rigorous up to date upper bound for the threshold of satisfiability for 3SAT. The proof by itself is of independent interest and combines several different techniques such as the second moment and the differential equation method.)
   
2. J. Díaz, D. Mitsche and X. Pérez: Connectivity for Dynamic Random Geometric Graphs. "IEEE Transactions on Mobile Computing", 8, 6, 821-835, 2009. (The paper provides a mathematical model for the connectivity in MANETS, the model is based in the random mobility of the nodes in a random geometric graph, and since its appearance it has been referenced by people in the field as pioneering work.)
   
3. J. Díaz, D. Mitsche and X. Pérez: On the probability of existence of mid-size components in random geometric graphs. Advances of Applied Probability, 41, 1-14, 2009. (The paper solves an open problem from the book of Mathiew Penrose: Random Geometric Graphs, Oxford UP 2002, it computes the probability of existence of components of logarithmic size, between the thermodynamical and the connectivity radius.)
   
4. J. Díaz, A.C. Kaporis, L.M. Kirousis, X. Pérez and N. Wormald: On the chromatic number of a random 5-regular graph.
   Journal of Graph Theory, 61, 157-191. 2009. (It was known that a random 4-regular graph whp was 3-colorable, it was know that a random 6-regular graph whp was 4-colorable, it was know that for random 4-regular was either 3 ot 4 colorable. The paper shows that whp 5-regular graphs are 3-colorable.)
   
5. J. Díaz, M. Serna and D. Thilikos: Efficient algorithms for counting parametrized list H-colouring. Journal of Computer and System Science, 74, 919-937, 2008. (The paper demonstrates the fixed parameter tractability of counting the number of list (H, C, K)-colorings, for the case in which (H, C, K) is simple. It introduces the concept of compactor and a new algorithmic technique, compactor enumeration, that allow to design fixed parameter algorithms for parameterized counting problems and has been used for some other people .)
   
6. J. Díaz, M. Karminski: Max-Cut and Max-Bisection are NP-hard on unit disk graph. Theoretical Computer Science, 377, 271-276, 2007. (Although there were approximation algorithms to compute the Max-Bisection on UDG, it was not know if the problem was NP-complete. This paper proves that The Max-Bisection is NPC on unit disk graphs.)
   
7. J. Díaz, J. Petit and M.J. Serna: A random graph model for optical networks of sensors. IEEE Transactions on Mobile Networks, 2,186-196, 2003. (Motivated by the "smart dust networks" of K.Pister, the paper proposes a new theoretical model based of the classical random geometric graphs, the sector random geometric graphs where each node chooses a random sector for communication. The paper provides a mathematical analysis of the empirical results concerning communications in the smart dust model.)
   
8. J. Díaz and J. Torán: Classes of bounded non-determinism. Mathematical System Theory, 23, pp. 21-32, 1990. (This is a classical paper which extends the notion of limited non-determinism into a whole hierarchy between P and NPC, the mu-hierarchy.)
   
9. J. L. Balcázar, J. Díaz y J. Gabarró: Structural Complexity~I. Springer-Verlag, Heidelberg, 1988. 2 Edición: Springer-Verlag, 1992. Japanese Edition: Springer-Verlag Tokyo, 1990 (there are non-official Chinese and Russian editions.) (This is a classic, which by today is out of date, as the field of structural complexity has changed quite a bit. However from 1988 until the middle 90's that was "the book" on complexity theory. It had over 1300 cites, it was used as textbook in many universities and many "generations of" researchers learned complexity theory from that book.