Publications and Presentations by Ricard Gavaldà

Listed in reverse chronological order. Versions found here are intended for personal, non-commercial use only. Some are final versions are subject to copyright, some are preprints of those. The usual legal restrictions apply.
  1. A New Spectral Method for Latent Variable Models. Matteo Ruffini, Marta Casanellas, Ricard Gavaldà. Preprint arXiv:1612.03409, Dec 11th, 2016.
  2. From Training to Match Performance: A Predictive and Explanatory Study on Novel Tracking Data. J. Fernández, D. Medina, A. Gómez, M. Arias, R. Gavaldà. Workshop on Data mining for the Analysis of Performance and Success, held in conjunction with ICDM 2016.
  3. Rehabilitation Profiles of Older Adult Stroke Survivors Admitted to Intermediate Care Units: A Multi-Centre Study. Laura M. Pérez, Marco Inzitari, Terence J. Quinn, Joan Montaner, Ricard Gavaldà, Esther Duarte, Laura Coll-Planas, Mercè Cerdà, Sebastià Santaeugenia, Conxita Closa, Miquel Gallofré. PLoS ONE 11(11): e0166304. doi:10.1371/journal.pone.0166304.
  4. Learning Probability Distributions Generated by Finite-State Machines. Jorge Castro and Ricard Gavaldà. In Topics in Grammatical Inference, Jeffrey Heinz, Josè M. Sempere (eds.), Springer 2016. Extended version of the ICGI 2012 tutorial. Preprint version.
  5. Fraud Detection in Energy Consumption: A Supervised Approach. Bernat Coma-Puig, Josep Carmona, Ricard Gavaldà, Santiago Alcoverro, Victor Martin. 2016 IEEE International Conference on Data Science and Advanced Analytics (DSAA). Preprint.
  6. Identifiability and Transportability in Dynamic Causal Networks. G. Blondel, M. Arias, R. Gavaldá. The 2016 ACM SIGKDD Workshop on Causal Discovery, held in conjunction with KDD 2016. Final version accepted for publication at International Journal of Data Science and Analytics.
  7. Machine Learning Assists the Classification of Reports by Citizens on Disease-Carrying Mosquitoes. Antonio Rodriguez, Frederic Bartumeus and Ricard Gavaldà. Presented at the Workshop on Data Science for Social Good (SoGood 2016), associated to ECML PKDD 2016. Ton's slides.
  8. Does Training Affect Match Performance? A Study Using Data Mining And Tracking Devices. Javier Fernández, Daniel Medina, Antonio Gómez, Marta Arias and Ricard Gavaldà. Presented at the workshop on Machine Learning and Data Mining for Sports Analytics (MLSA 2016), associated to ECML PKDD 2016. Javier's slides.
  9. Characterizing Chronic Disease and Polymedication Prescription Patterns from Electronic Health Records. Martí Zamora, Manel Baradad, Ester Amado, Silvia Cordomí, Esther Limón, Juliana Ribera, Marta Arias, Ricard Gavaldà. Presented at 2nd IEEE Intl. Conf. on Data Science and Advanced Analytics (IEEE DSAA 2015). Slides.
  10. Talk on The Data Stream Model: Sketches and Probability Tools at the Summer School on Data Sciences for Big Data - Resource Aware Data Mining.
  11. An Efficient Closed Frequent Itemset Miner for the MOA Stream Mining System. Massimo Quadrana, Albert Bifet, Ricard Gavaldà. AI Communications, vol. 28 (2015), 143-158. This extended version replaces the CCIA 2013 one.
  12. A methodology for the evaluation of high response time on E-commerce users and sales. Nicolas Poggi, David Carrera, Ricard Gavaldà, Eduard Ayguadé, Jordi Torres. Information Systems Frontiers, Information Systems Frontiers 16(5): 867-885 (2014). Preprint
  13. Computational Learning of Weighted Automata. Survey talk at the 7th Int. Workshop on Weighted Automata: Theory and Applications, WATA 2014. Leipzig, May 5-9, 2014.
  14. Adaptively learning probabilistic deterministic automata from data streams. Borja Balle, Jorge Castro, and Ricard Gavaldà. Machine Learning 96:1-2 (2014), 99-127. Preprint. Note: This paper largely overlaps the ICGI 2012 one, but on the one hand it contains substantially more details and addresses concept drift, and on the other hand it does not cover the topic of bootstrap estimation.
  15. Building Green Cloud Services at Low Cost. Josep Lluis Berral, Íñigo Goiri, Thu D. Nguyen, Ricard Gavaldà, Jordi Torres, Ricardo Bianchini. 34th IEEE Intl. Conf. on Distributed Computing Systems (ICDCS 2014), 449-460. Preprint.
  16. Learning Read-Constant Polynomials of Constant Degree Modulo Composites. Arkadev Chattopadhyay, Ricard Gavaldà, Kristoffer Arnsfelt Hansen, Denis Thérien. Theory of Computer Systems 55(2): 404-420 (2014). Preprint. A preliminary version was published in 6th International Computer Science Symposium in Russia (CSR 2011), Springer Lecture Notes in Computer Science 6651 (2011), 29-42.
  17. Power-aware Multi-DataCenter Management using Machine Learning. Josep Ll. Berral, Ricard Gavaldà, Jordi Torres. 2nd Intl. Workshop on Power-aware Algorithms, Systems, and Architectures (PASA 2013) (held in parallel with ICPP 2013). Lyon, october 1st, 2013. Josep Lluis' slides.
  18. An Efficient Closed Frequent Itemset Miner for the MOA Stream Mining System. Massimo Quadrana, Albert Bifet, Ricard Gavaldà. CCIA 2013, IOS Press Frontiers in Artificial Intelligence and Applications, vol. 256, 157-166. Slides.
  19. The Architecture of a Churn Prediction System Based on Stream Mining. Borja Balle, Bernardino Casas, Alex Catarineu, Ricard Gavaldà, David Manzano-Macho. CCIA 2013, IOS Press Frontiers in Artificial Intelligence and Applications, vol. 256, 203-212. Slides.
  20. Empowering Automatic Data-Center Management with Machine Learning. Josep Ll. Berral, Ricard Gavaldà, Jordi Torres. Poster presentation at the ACM Symposium on Applied Computing (SAC 2013), Data Mining Track. Abstract in proceedings, pages 170-172.
  21. Learning Probabilistic Automata: A Study In State Distinguishability. Borja Balle, Jorge Castro, Ricard Gavaldà. Theoretical Computer Science 473: 46-60 (2013).
  22. Online Techniques for Dealing with Concept Drift in Process Mining. Josep Carmona and Ricard Gavaldà. 11th Intl. Symp. on Intelligent Data Analysis (IDA 2012). Springer LNCS 7619 (2012), 90-102. Josep's slides and a proof of Theorem 1.
  23. Advanced Topics on Data Stream Mining. Albert Bifet, João Gama, Ricard Gavaldà, Georg Krempl, Mykola Pechenizkiy, Bernhard Pfahringer, Myra Spiliopoulou, Indrė Žliobaitė. Tutorial given at ECML PKDD 2012 (Bristol, september 2012).
  24. Learning Probability Distributions Generated by Finite-State Machines. Jorge Castro and Ricard Gavaldà. Tutorial given at the 11th Intl. Conf. on Grammatical Inference (ICGI 2012) (Washington, september 2012). Reference list.
  25. Bootstrapping and Learning PDFA in Data Streams. Borja Balle, Jorge Castro, Ricard Gavaldà. 11th Intl. Conf. on Grammatical Inference (ICGI 2012) (Washington, september 2012). JMLR Workshop and Conference proceedings, vol. 21, pp. 34-48. Borja received the conference Best student paper award.
  26. Towards Energy-Aware Scheduling using Machine Learning. Josep Ll. Berral, Íñigo Goiri, Ramon Nou, Ferran Julià, Josep O. Fité, Jordi Guitart, Ricard Gavaldà, Jordi Torres. Chapter 8 of the book Energy Efficient Distributed Computing Systems, Albert Y. Zomaya, Young Choon Lee (eds.), Wiley 2012.
  27. Applying trust metrics based on user interactions to recommendation in social networks. Alberto Lumbreras and Ricard Gavaldà. Workshop on Social Knowledge Discovery and Utilization, associated to IEEE/ACM ASONAM'2012. This paper is based on Alberto's M.Sc. thesis; get it, slides, and code from his site.
  28. Energy-efficient and multifaceted resource management for profit-driven virtualized data centers. Íñigo Goiri, Josep Ll. Berral, J. Oriol Fité, Ferran Julià, Ramon Nou, Jordi Guitart, Ricard Gavaldà, Jordi Torres. Future Generation Computer Systems, vol. 28:5, May 2012, 718-731.
  29. 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.
  30. 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. Josep Lluis' slides.
  31. 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.
  32. 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.
  33. 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.
  34. 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).
  35. 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.
  36. 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.
  37. 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.
  38. 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).
  39. Towards energy-aware scheduling in data centers using Machine Learning Josep Ll. Berral, Íñ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.
  40. 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.
  41. 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.
  42. 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.
  43. 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.
  44. 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.
  45. 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.
  46. 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.
  47. 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.
  48. 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.
  49. 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.
  50. 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.
  51. 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.
  52. 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.
  53. 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.
  54. 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.
  55. 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.
  56. 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).
  57. 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.
  58. 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.
  59. 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.
  60. An optimal anytime estimation algorithm, R. Gavaldà. Technical Report LSI--04--56--R, Dept. LSI, UPC, 2004. A revised version here.
  61. 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.
  62. 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.
  63. 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.
  64. 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.
  65. 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.
  66. 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.
  67. 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.
  68. 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.
  69. 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).
  70. 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.)
  71. 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.
  72. 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.
  73. 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.
  74. 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.
  75. 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.
  76. 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.
  77. The complexity of learning with queries, R. Gavaldà. Proc. 9th IEEE Conference on Structure in Complexity Theory. IEEE Computer Society Press (1994), 324-337.
  78. 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).
  79. An approach to correctness of data parallel algorithms, J. Gabarró and R. Gavaldà. Journal of Parallel and Distributed Computing 22 (1994), 185-201.
  80. 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.
  81. Structural analysis of polynomial-time query learnability, O. Watanabe and R. Gavaldà. Mathematical Systems Theory 27 (1994), 231-256.
  82. 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.
  83. 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).
  84. 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.
  85. Kolmogorov Randomness and its Applications to Structural Complexity Theory. Doctoral Thesis, LSI Department, UPC, april 1992. Advisor: José L. Balcázar.
  86. A positive relativization of polynomial time versus polylog space, R. Gavaldà. Information Processing Letters 46 (1993), 119-123.
  87. 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.
  88. 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.
Back to Ricard's home page
Last update: February 27th, 2017.
http://www.cs.upc.edu/~gavalda/papers.html