Papers by Ricard Gavaldà

Papers available here may be subject to copyright and are intended for personal, non-commercial use only. In particular, papers published in the Lecture Notes in Computer Science and Lecture Notes in Artificial Intelligence are subject to copyright by Springer Verlag, and available from the LNCS/ LNAI homepages.

1. Optimal Resource Allocation in a Virtualized Software Aging Platform with Software Rejuvenation. Javier Alonso, Íñigo Goiri, Jordi Guitart, Ricard Gavaldà, Jordi Torres. 11 IEEE 22nd International Symposium on Software Reliability Engineering (ISSRE 2011). Hiroshima, Japan November 29-December 02.
2. Adaptive Scheduling on Power-Aware Managed Data-Centers Using Machine Learning. Josep Ll. Berral, Ricard Gavaldà, Jordi Torres. 12th IEEE/ACM International Conference on Grid Computing (GRID 2011). Lyon, september 2011. IEEE Press, 66-73.
3. Non-intrusive Estimation of QoS Degradation Impact on E-commerce User Satisfaction. Nicolás Poggi, David Carrera, Ricard Gavaldà, Eduard Ayguadé. To be presented at the 10th IEEE Symposium on Network Computing and Applications (IEEE NCA 2011), Cambridge (USA), august 2011.
4. Mining Frequent Closed Graphs on Evolving Data Streams. Albert Bifet, Geoffrey Holmes, Bernhard Pfahringer, Ricard Gavaldà. To be presented at the 17th annual ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'11), San Diego, august 2011.
5. Learning Read-Constant Polynomials of Constant Degree Modulo Composites. Arkadev Chattopadhyay, Ricard Gavaldà, Kristoffer Arnsfelt Hansen, Denis Thérien. 6th International Computer Science Symposium in Russia (CSR 2011). Springer Lecture Notes in Computer Science 6651 (2011), 29-42.
6. Mining frequent closed trees in evolving data streams. Albert Bifet, Ricard Gavaldà. Intelligent Data Analysis 15(1), IOS Press, 29-43. January 2011. This paper supersedes the KDD'08 paper below, extending the results there on unlabelled trees to labelled trees as well.
7. SalamboMiner - A Biomedical Literature Mining Tool for Inferring the Genetics of Complex Diseases. Leonor Rib, Ricard Gavaldà, Jose Manuel Soria, Alfonso Buil. BIOINFORMATICS 2011: Intl. Conf. on Bioinformatics Models, Methods, and Algorithms (part of the BIOSTEC Joint Conference, Rome, 26-29 january 2011).
8. A Lower Bound for Learning Distributions Generated by Probabilistic Automata. Borja Balle, Jorge Castro, Ricard Gavaldà. 21st International Conference on Algorithmic Learning Theory (ALT'10), Springer LNCS 6331 (2010), 179-193.
9. Learning PDFA with Asynchronous Transitions. Borja Balle, Jorge Castro, Ricard Gavaldà. 10th International Colloquium on Grammatical Inference (ICGI'10), Springer LNCS 6339 (2010), 271-275.
10. Characterization of Workload and Resource Consumption for an Online Travel and Booking Site. Nicolás Poggi, David Carrera, Ricard Gavaldà, Jordi Torres, Eduard Ayguadé: 2010 IEEE Intl. Symp. on Workload Characterization (IISWC) IEEE Press, 2010.
11. Adaptive on-line software aging prediction based on Machine Learning. Javier Alonso, Josep Ll. Berral, Ricard Gavaldà, Jordi Torres. 40th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN 2010). June 28th - July 1st 2010, Chicago (USA).
12. Towards energy-aware scheduling in data centers using Machine Learning Josep Ll. Berral, Iñigo Goiri, Ramon Nou, Ferran Julià, Jordi Guitart, R. Gavaldà, J. Torres. First Intl. Conf. on Energy-Efficient Computing and Networking. Passau, april 13-15, 2010.
13. Improving adaptive bagging methods for evolving data streams. Albert Bifet, Geoffrey Holmes, Bernhard Pfahringer, Ricard Gavaldà. First Asian Conference on Machine Learning (ACML 2009). Springer Lecture Notes in Computer Science 5828, 23-37, 2009. Albert's slides.
14. An algebraic perspective on Boolean function learning. Ricard Gavaldà and Denis Thérien. 20th Intl. Conf. on Algorithmic Learning Theory (ALT'09). Springer Lecture Notes in Computer Science 5809, 201-215, 2009. Slides.
15. Adaptive XML Tree Classification on Evolving Data Streams. Albert Bifet and Ricard Gavaldà. European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD 2009). Springer Lecture Notes in Computer Science 5781, 147-162, 2009. Slides.
16. Adaptive parameter-free learning from evolving data streams. Albert Bifet and Ricard Gavaldà. Shorter version in Proc. 8th International Symposium on Intelligent Data Analysis (IDA'09), Springer Lecture Notes in Computer Science 5772, 249-260, 2009. Slides.
17. Adaptive XML Tree Mining on Evolving Data Streams. Albert Bifet and Ricard Gavaldà. 7th International Workshop on Mining and Learning with Graphs (MLG'09), july 2009.
18. New ensemble methods for evolving data streams. Albert Bifet, Geoffrey Holmes, Bernhard Pfahringer, Richard Kirkby, Ricard Gavaldà. Proc. 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'09), 139-148. Albert's slides.
19. Note: More Efficient Conversion of Equivalence-Query Algorithms to PAC Algorithms. Ricard Gavaldà. Research Report LSI-09-16-R, Department of Software (LSI), UPC, may 2009.
20. The frequency spectrum of finite samples from the intermittent silence process. Ramon Ferrer-i-Cancho, Ricard Gavaldà. Journal of the American Society for Information Science and Technology (JASIST) 60:4 (2009), 837-843.
21. Self-Adaptive Utility-Based Web Session Management. Nicolás Poggi, Toni Moreno, Josep Lluis Berral, Ricard Gavaldà, and Jordi Torres. Computer Networks 53:10 (2009), 1712-1721.
22. Adaptive Distributed Mechanism Against Flooding Network Attacks Based on Machine Learning. Josep L. Berral, Nicolás Poggi, Javier Alonso, Ricard Gavaldà, Jordi Torres, and Manish Parashar. The First ACM Workshop on Artificial Intelligence on Security (AISec'08), Alexandria (VA, USA), october 27th 2008.
23. Towards feasible PAC-learning of probabilistic deterministic finite automata. Jorge Castro and Ricard Gavaldà. 9th International Colloquium on Grammatical Inference (ICGI'08). St. Malo (France), september 2008. © Springer-Verlag. Slides.
24. Mining adaptively frequent closed unlabeled rooted trees in data streams. A. Bifet and R. Gavaldà. 14th ACM SIGKDD Intl. Conference on Knowledge Discovery and Data Mining (KDD'08). Albert keeps slides, software, and datasets.
25. Reducing wasted resources to help achieve green data centers. Jordi Torres, David Carrera, Kevin Hogan, Ricard Gavaldà, Vicenç Beltran, and Nicolás Poggi. The Fourth Workshop on High-Performance, Power-Aware Computing (HPPAC 2008), Miami, april 14th, 2008.
26. Automatic detection and banning of content stealing bots for e-commerce. Nicolás Poggi, Josep Lluis Berral, Toni Moreno, Ricard Gavaldà, and Jordi Torres. NIPS 2007 Workshop on Machine Learning in Adversarial Environments for Computer Security, december 2007.
27. Web customer modeling for automated session prioritization on high traffic sites. Nicolás Poggi, Toni Moreno, Josep Lluis Berral, Ricard Gavaldà, and Jordi Torres. Proc. 11th Intl. Conf. on User Modelling (UM2007). Springer Lecture Notes in Computer Science 4511, 450-454. © Springer-Verlag.
28. Learning from time-changing data with adaptive windowing. Albert Bifet and Ricard Gavaldà. Shorter version appears in Proc. 7th SIAM Intl. Conf. on Data Mining (SDM'07), 443-449. SIAM, 2007.
29. Kalman filters and adaptive windows for learning in data streams. Albert Bifet and Ricard Gavaldà. Shorter version in Proc. 9th International Conference on Discovery Sicence (DS 2006). Springer Lecture Notes in Artificial Intelligence 4265, 29-40. © Springer-Verlag. Slides (by A. Bifet).
30. PAC-learning of Markov models with hidden state. Ricard Gavaldà, Philipp W. Keller, Joelle Pineau, and Doina Precup. Proc. 11th European Conference on Machine Learning (ECML 2006). Springer Lecture Notes in Artificial Intelligence 4212, 150-161. © Springer-Verlag. Slides.
31. Tractable clones of polynomials over semigroups, Víctor Dalmau, Ricard Gavaldà, Pascal Tesson, and Denis Thérien. Proc. 11th International Conference on Principles and Practice of Constraint Programming (CP 2005). Springer Lecture Notes in Computer Science 3709, 196-210. © Springer-Verlag. Older version in ECCC report TR-059. Slides.
32. Learning expressions and programs over monoids, Ricard Gavaldà, Pascal Tesson, and Denis Thérien. Information and Computation 204:2 (2006), 177-209. A preliminary, far shorter, version: R. Gavaldà and D. Thérien, Learning expressions over monoids, Proc. 18th Intl. Symposium on Theoretical Aspects of Computer Science (STACS'01). Springer Lecture Notes in Computer Science 2010 (2001), 283-293. © Springer-Verlag.
33. An optimal anytime estimation algorithm, R. Gavaldà. Technical Report LSI--04--56--R, Dept. LSI, UPC, 2004. A revised version here.
34. Algebraic characterizations of small classes of boolean functions, Ricard Gavaldà and Denis Thérien. Preliminary version in Proc. 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS'03). Springer Lecture Notes in Computer Science 2607 (2003), 331-342. © Springer-Verlag.
35. Some results in exact learning of Boolean functions, Jorge Castro, Ricard Gavaldà and David Guijarro. Guest contribution in the Complexity Theory Column, SIGACT News, vol. 32 (2), june 2001, 32-43.
36. Adaptive sampling methods for scaling up knowledge discovery algorithms, Carlos Domingo, Ricard Gavaldà, and Osamu Watanabe. Data Mining and Knowledge Discovery 6 (2002), 131-152. Preliminary version in Proc. Second International Conference on Discovery Science (DS'99). Springer Lecture Notes in Artificial Intelligence 1721 (1999), 172-183. © Springer-Verlag. A slightly shorter version appeared in the book Instance Selection and Construction for Data Mining, Huan Liu and Hiroshi Motoda (eds.), Kluwer Academic Publishers (2001), 131-132.
37. Sequential sampling algorithms: Unified analysis and lower bounds, Ricard Gavaldà and Osamu Watanabe. Proc. 1st Intl. Symposium on Stochastic Algorithms: Foundations and Applications (SAGA'01). Springer Lecture Notes in Computer Science 2264 (2001), 173-187. © Springer-Verlag.
38. Non-Automatizability of Bounded-Depth Frege Proofs, Maria Luisa Bonet, Carlos Domingo, Ricard Gavaldà, Alexis Maciel, and Toniann Pitassi. Computational Complexity 13:1-2 (2004), 47-68. Preliminary version in Proc. 14th Annual IEEE Conference on Computational Complexity (CCC'99), IEEE Computer Society Press (1999), 15-23.
39. Monotone proofs of the Pigeonhole principle, Albert Atserias, Nicola Galesi, and Ricard Gavaldà. Proc. 27th International Colloquium on Automata, Languages, and Programming (ICALP'00), Springer Lecture Notes in Computer Science 1853, 151-162. Final version in Mathematical Logic Quarterly 47:4 (2001), 461-474.
40. Discontinuities in Recurrent Neural Networks, Ricard Gavaldà and Hava T. Siegelmann. Neural Computation 11:3 (1999), 715-745. An obsolete version is Technical Report LSI-97-15-R, LSI Department, UPC.
41. Practical Algorithms for On-line Sampling, Carlos Domingo, Ricard Gavaldà, and Osamu Watanabe. Proc. First International Conference on Discovery Science (DS'98). Springer Lecture Notes in Artificial Intelligence 1532 (1998), 150-161. © Springer-Verlag. Available here if you want, but basically superseeded by Adaptive sampling methods for scaling up knowledge discovery algorithms, above.
42. Bounding the Expected Length of Longest Common Subsequences and Forests, Ricardo A. Baeza-Yates, Ricard Gavaldà, Gonzalo Navarro, and Rodrigo Scheihing. Theory of Computing Systems 32:4 (1999), 435-452.
    A preliminary version (TR LSI-96-29-R) was Ricardo's invited talk at the Third South American Workshop on String Processing (WSP'96).
43. Computational power of neural networks: A characterization in terms of Kolmogorov complexity, J.L. Balcázar, R. Gavaldà, and H.T. Siegelmann. IEEE Transactions on Information Theory 43:3 (1997), 1175-1183. (Note: this is the title of the final, published version. It differs slightly from that of the Tech. Rep. version available in these pages.)
44. Algorithms for Learning Finite Automata from Queries: A Unified View, José L. Balcázar, Josep Díaz, Ricard Gavaldà, and Osamu Watanabe. Chapter in Advances in Algorithms, Languages, and Complexity, D.-Z. Du and K.-I. Ko (eds.), Kluwer Academic Publishers, 1997, 73-91.
45. An optimal parallel algorithm for learning DFA, J.L. Balcázar, J. Díaz, R. Gavaldà, and O. Watanabe. Journal of Universal Computer Science, vol. 2, n. 3 (march 28, 1996), 97-112. Preliminary version in Proc. 7th ACM Conference on Computational Learning Theory. ACM Press (1994), 208-217.
46. Coding Complexity: The Computational Complexity of Succinct Descriptions, José L. Balcázar, Ricard Gavaldà, and Osamu Watanabe. Chapter in Advances in Algorithms, Languages, and Complexity, D.-Z. Du and K.-I. Ko (eds.), Kluwer Academic Publishers, 1997, 53-72.
47. Learning ordered binary decision diagrams, R. Gavaldà and D.Guijarro. Proc. Sixth International Workshop on Algorithmic Learning Theory (ALT'95). Springer-Verlag Lecture Notes in Artificial Intelligence 997 (1995), 228-238. © Springer-Verlag.
48. Oracles and Queries That Are Sufficient for Exact Learning, N.H. Bshouty, R. Cleve, R. Gavaldà, S. Kannan, and C. Tamon. Journal of Computer and System Sciences 52, 1996, 421-433. Also available as ECCC TR95-15. This version needs a correction.
49. Compressibility of Infinite Binary Sequences, J.L. Balcázar, R. Gavaldà, and M. Hermo. Chapter in Complexity, Logic, and Recursion Theory, A. Sorbi (editor), Marcel Dekker Inc., Lecture Notes in Pure and Applied Mathematics Series, 1997, pp. 75-91. An old version (LSI-94-24-R), ``On infinite sequences (almost) as easy as pi'', was presented at the Workshop on Applications of Descriptional Complexity to Inductive, Statistical, and Visual Inference, Rutgers University (New Jersey), 10 july 1994.
50. The complexity of learning with queries, R. Gavaldà. Proc. 9th IEEE Conference on Structure in Complexity Theory. IEEE Computer Society Press (1994), 324-337.
51. Bounding the complexity of advice functions, R. Gavaldà. Journal of Computer and System Sciences 50 (1995), 468-475. Preliminary version in 7th IEEE Structures (1992).
52. An approach to correctness of data parallel algorithms, J. Gabarró and R. Gavaldà. Journal of Parallel and Distributed Computing 22 (1994), 185-201.
53. The query complexity of learning DFA, J.L. Balcázar, J. Díaz, R. Gavaldà, and O. Watanabe. New Generation Computing 12 (1994), 337-358. Preliminary version in ALT'92.
54. Structural analysis of polynomial-time query learnability, O. Watanabe and R. Gavaldà. Mathematical Systems Theory 27 (1994), 231-256.
55. On the power of equivalence queries, R. Gavaldà. First European Conference on Computational Learning Theory, Royal Holloway, University of London, december 1993. Proceedings appeared as Computational Learning Theory: EuroCOLT'93, The Institute of Mathematics and its Applications Conference Series, new series number 53, Oxford University Press (1994), 193-203. On-line is a slightly extended version.
56. On the computational complexity of small descriptions, R. Gavaldà and O. Watanabe. SIAM Journal on Computing 22 (1993), 1257-1275. Preliminary version in 6th IEEE Structures (1991).
57. Some structural complexity aspects of neural computation, J.L. Balcázar, R. Gavaldà, H.T. Siegelmann, and E.D. Sontag. Proc. 8th IEEE Conference on Structure in Complexity Theory, IEEE Computer Society Press (1993), 253-265.
58. Kolmogorov Randomness and its Applications to Structural Complexity Theory. Doctoral Thesis, LSI Department, UPC, april 1992. Advisor: José L. Balcázar.
59. A positive relativization of polynomial time versus polylog space, R. Gavaldà. Information Processing Letters 46 (1993), 119-123.
60. Generalized Kolmogorov complexity in relativized separations, R. Gavaldà, L. Torenvliet, O. Watanabe, and J.L. Balcázar. Proc. 15th Symposium on Mathematical Foundations of Computer Science, Springer-Verlag Lecture Notes in Computer Science 452 (1990), 269-276.
61. Strong and robustly strong polynomial time reducibilities to sparse sets, R. Gavaldà and J.L. Balcázar. Theoretical Computer Science 88 (1991), 1-14. Preliminary version in 13th MFCS, Springer-Verlag Lecture Notes in Computer Science 324 (1988). Errata: The proof of Theorem 11 in this paper is wrong, as pointed out by J.-Y. Cai, L. A. Hemaspaandra, and G. Wechsung ("Robust Reductions". Theory of Computing Systems, 32:4, 625-647), who establish it.