List of publications

List of Publications of Ferdinando Cicalese

    Book

  1. Fault Tolerant Search Algorithms, Series: Monographs in Theoretical Com- puter Science. An EATCS Series, ISBN: 978-3-642-17326-4, Springer-Verlag, 2013.


    Volumes Edited

  2. Group Testing and Compressed Sensing,
    Special issue of Algorithmica, vol. 67 (3), 2013
    (co-edited with E. Porat).

  3. Information Theory, Combinatorics, and Search Theory,
    Lecture Notes in Computer Science, vol. 7777, 2013
    (co-edited with H. Aydinian and C. Deppe).

  4. Search Methodologies,
    Dagstuhl Seminar Proceedings vol. 09281, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany, 2009
    (Co-edited with R. Ahlswede and U. Vaccaro).

  5. COSSAC: Combinatorics of Sorting, Searching, and Coding,
    Special Issue of Discrete Applied Mathematics, vol. 137, Issue 1, February 27, 2004.
    (Co-edited with D. Mundici and U. Vaccaro).


    Papers in Journals

  6. "Improved Approximation Algorithms for the Average-Case Tree Searching Problem'',
    Algorithmica, vol. 68, pp. 1045-1074, 2014.
    (With T. Jacobs, E. Laber, and M. Molinaro)

  7. "Perfect Strategies for the Ulam-R #enyi Game with Multi-interval Questions'',
    Theory of Computing Systems, vol. 54, pp. 578-594, 2014.

  8. "Approximating the Maximum Consecutive Subsums of a Sequence'',
    Theoretical Computer Science, vol. 525, pp.130-137, 2014.
    (With. E. Laber, R. Yuster, and O. Weimann)

  9. "On the approximability and exact algorithms for vector domination and related problems in graphs'',
    Discrete Applied Mathematics, vol. 161, pp. 750-767, 2013.
    (With M. Milanič, U. Vaccaro)

  10. "The Binary Identification Problem for Weighted Trees'',
    Theoretical Computer Science, vol. 459, pp. 100-112, 2012.
    (With T. Jacobs, E. Laber, C. Valentim)

  11. "A Linear Algorithm for String Reconstruction in the Reverse Complement Equivalence Model'',
    Journal of Discrete Algorithms, vol. 14, pp. 37-54, 2012.
    (With P.L. Erdős, Zs. Lipták)

  12. "Graphs of separability at most two'',
    Discrete Applied Mathematics, vol. 160, pp. 685-696, 2012.
    (With M. Milanič)

  13. "On Approximate Jumbled Pattern Matching in Strings'',
    Theory of Computing Systems, vol. 50, pp. 35-51, 2012.
    (With P. Burcsi, G. Fici, Zs. Lipták)

  14. "Algorithms for Jumbled Pattern Matching in Strings'',
    International Foundations of Computer Science, vol. 23, No. 1, pp. 357-374, 2012.
    (With P. Burcsi, G. Fici, Zs. Lipták)

  15. "The Competitive Evaluation Complexity of Monotone Boolean Functions'',
    Journal of the ACM, vol. 58, No. 3, Article 9, 2011.
    (With E. Laber)

  16. "On the complexity of searching in trees and partially ordered structures'',
    Theoretical Computer Science, vol. 412, pp. 6879-6896, 2011.
    (With T. Jacobs, E. Laber, M. Molinaro)

  17. "Competitive Boolean Function Evaluation. Beyond Monotonicity and the Symmetric case'',
    Discrete Applied Mathematics, vol. 159, No. 11, pp. 1070-1078, 2011
    (With T. Gagie, E. Laber, M. Milanič)

  18. "Competitive Evaluation of Threshold Functions in the Priced Information Model'',
    Annals of Operations Research, vol. 188, No. 1, pp. 111-132, 2011.
    (With M. Milanič)

  19. "Two Batch Search with Lie Cost'',
    IEEE Transactions on Information Theory,, vol. 55, No. 4, pp. 1433-1439, 2009.
    (With R. Ahlswede, C. Deppe, U. Vaccaro).

  20. "Faster Centralized Communication in Radio Networks'',
    Algorithmica, vol. 54, No. 2, pp. 226-242, 2009.
    (With F. Manne and Q. Xin)

  21. "Searching with lies under error cost constraints'',
    Discrete Applied Mathematics, vol. 156, n. 9, pp. 1444-1460, 2008.
    (With R. Ahlswede and C. Deppe)

  22. ``Overlaps Help: Improved Bounds for Group Testing with Interval Queries'',
    Discrete Applied Mathematics, vol. 155, pp. 288-299, 2007.
    (With P. Damaschke, L. Tansini, S. Werth).

  23. ``A Note on Approximation of Uniform Distributions from Variable-to-Fixed Length Codes'',
    IEEE Transactions on Information Theory, vol. 52, No. 8, pp. 3772-3777, 2006.
    (With L. Gargano and U. Vaccaro)

  24. ``Perfect Minimally Adaptive q-ary Search with Unreliable Tests'',
    Journal of Statistical Planning and Inference, vol. 137, pp. 162-175, 2007.
    (With C. Deppe)

  25. ``Optimal Group Testing Strategies with Interval Queries and their Application to Splice Site Detection''
    International Journal of Bioinformatics Research and Applications (IJBRA) , vol. 1, n. 4, pp. 363-388, 2005.
    (With P. Damaschke and U. Vaccaro).

  26. "Searching with lies under error cost constraints'',
    Electronic Notes in Discrete Mathematics, vol. 21, pp. 173-179, 2005
    (With R. Ahlswede and C. Deppe)

  27. "Ulam-Rényi game with constrained lies'',
    Electronic Notes in Discrete Mathematics, vol. 21, pp. 255-261, 2005
    (With C. Deppe)

  28. ``Bounding the Average Length of Optimal Source Codes via Majorization Theory'',
    IEEE Transactions on Information Theory, vol. 50, Issue 4, 2004.
    (With U. Vaccaro)

  29. "On Searching Strategies, Parallel Questions, and Delayed Answers'',
    Discrete Applied Mathematics, vol. 144, n. 3, pp. 229-382, 2004
    (With L. Gargano and U. Vaccaro)

  30. ``Binary Search with Delayed and Missing Answers'',
    Information Processing Letters, vol. 85, n. 5, pp. 239-247, 2003
    (With U. Vaccaro).

  31. ``Supermodularity and Subadditivity Properties of the Entropy on the Majorization Lattice'',
    IEEE Transactions in Information Theory, Vol. 48, Issue 4, pp. 933-938, 2002.
    (With U. Vaccaro).

  32. ``Least adaptive optimal search with unreliable tests'',
    Theoretical Computer Science, vol. 270, no. 1-2, pp. 877-893, 2001.
    (With D. Mundici and U. Vaccaro).

  33. ``Perfect 2-fault tolerant search with minimum adaptiveness'',
    Advanced in Applied Mathematics, vol. 25, pp. 65--101, 2000.
    (With D. Mundici).

  34. ``An Improved Heuristic for `Ulam-Rényi Game''',
    Information Processing Letters, vol. 73, no. 3-4, pp. 119-124, 2000.
    (With U. Vaccaro).

  35. ``Optimal Strategies Against a Liar'',
    Theoretical Computer Science, vol. 230, no. 1-2, pp. 167-193, 2000.
    (With U. Vaccaro).

  36. ``A Fuzzy Evolutionary Approach to the Classification Problem'',
    Journal of Intelligent and Fuzzy Systems, vol. 6, pp. 117-129, 1998.
    (With E. Loia).

  37. ``Classifying through a fuzzy algebraic structure'',
    Fuzzy Sets and Systems, vol. 78, pp. 317-331, 1996.
    (With A. Gisolfi)



    Book Chapters

  38. ``Recent Developments of Feedback Coding and its Relations with Many-Valued Logic'',
    in: Logic at the Crossroads - An Interdisciplinary View
    A./ Gupta, R./ Parikh, J. van Benthem (Eds.) Allied Publishers (2007), pp. 222-240.

  39. ``Q-ary Ulam-Rényi game with constrained lies'',
    to appear in: General Theory of Information Transfer and Combinatorics
    R. Ahlswede (Ed.), Lecture Notes in Computer Science, vol. 4123, Springer--Verlag (2006), pp. 663-679.
    (With C. Deppe)

  40. ``Learning and the Art of Fault-tolerant Guesswork'',
    in: Adaptivity and Learning - An Interdisciplinary Debate
    Kühn, R./ Menzel, R./ Menzel, W./ Ratsch, U./ Richter, M.M./ Stamatescu, I.O. (Eds.) Springer--Verlag (2003), pp. 117-143.
    (With D. Mundici)

  41. ``Rota-Metropolis cubic logic and Ulam-Rényi games'',
    in: Algebraic Combinatorics and Computer Science · A Tribute to Giancarlo Rota
    Senato, D.; Crapo, H., (Eds.), Springer--Verlag (2000), pp. 193-240.
    (With D. Mundici and U. Vaccaro)



    Papers in Proceedings

  42. "Indexes for Jumbled Pattern Matching in Strings, Trees and Graphs'',
    in: Proc. of the 20th String Processing and Information Retrieval Symposium (SPIRE 2013), to appear.
    (With T. Gagie, E. Giaquinta, E. Laber, Zs. Lipták, R. Rizzi, A.I. Tomescu)

  43. "Information Theoretic Distance Measures between Income Distributions'',
    in: Proc. of International Symposium in Information Theory (ISIT 2013), IEEE Press, to appear.
    (With L. Gargano, U. Vaccaro)

  44. "Latency-Bounded Target Set Selection in Social Networks'',
    in: Proc. of CiE 2013: Computability in Europe - The Nature of Computation,
    Lecture Notes in Computer Science, Springer-Verlag, to appear.
    (With G. Cordasco, L. Gargano, M. Milanič, U. Vaccaro)

  45. "Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence'',
    in: Proc. of the 23rd Annual Symposium on Combinatorial Pattern Matching (CPM 2012),
    Lecture Notes in Computer Science, Springer-Verlag, vol. 7354, pp. 149-158, 2012.
    (With E. Laber, O. Weimann, R. Yuster)

  46. "The Multi-interval Ulam-Rényi Game'',
    in: Proc. of the 6th International Confer- ence on Fun with Algorithms (FUN 2012),
    Lecture Notes in Computer Science, Springer-Verlag, vol. 7288, pp. 69-80, 2012.

  47. "Hardness, approximability, and exact algorithms for vector domination,
    and total vector domination in graphs '',
    in: Proc. of the 18th International Symposium on Fundamentals of Computer Theory (FCT 2011),
    Lecture Notes in Computer Science, Springer-Verlag, vol. 6914, pp. 288-297, 2011.
    (With M. Milanič, U. Vaccaro)

  48. "Binary Identification Problems for Weighted Trees'',
    in: Proc. of the $12$th Algorithms and Data Structures Symposium (WADS 2011),
    Lecture Notes in Computer Science, Springer-Verlag, vol. 6844, pp. 255-266, 2011.
    (With T. Jacobs, E. Laber, C. Valentim)

  49. "Superselectors: Efficient Constructions and Applications'',
    in: Proc. of the 18th Annual European Symposium on Algorithms (ESA 2010),
    Lecture Notes in Computer Science, Springer-Verlag, vol. 6346, pp. 207-218, 2010.
    (With U. Vaccaro)

  50. "On Greedy Algorithms for Decision Trees'',
    in: Proc. of the $21$st nternational Symposium on Algorithms and Computation (ISAAC 2010),
    Lecture Notes in Computer Science, Springer-Verlag, vol. 6507, pp. 206-217, 2010.
    (With T. Jacobs, E. Laber, M. Molinaro)

  51. "On the Complexity of Searching in Trees: Average-case Minimization'',
    in: Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP 2010),
    Lecture Notes in Computer Science, Springer--Verlag, vol. 6198, pp. 527-539, 2010.
    (With T. Jacobs, E. Laber, M. Molinaro)

  52. "Graphs of Separability at Most Two: Structural Characterizations and Their Consequences'',
    in: Proceedings of the 21st International Workshop on Combinatoria Algorithms (IWOCA 2010),
    Lecture Notes in Computer Science, Springer--Verlag, vol. 6460, pp. 291-302, 2011.
    (With M. Milanič).

  53. "Efficient Reconstruction of RC-Equivalent Strings'',
    in: Proceedings of the 21st International Workshop on Combinatoria Algorithms (IWOCA 2010),
    Lecture Notes in Computer Science, Springer--Verlag, vol. 6460, pp. 349-362, 2011.
    (With P.L. Erdős, Zs. Lipták).

  54. "On Table Arrangements, Scrabble Freaks, and Jumbled Pattern Matching'',
    in: Proc. of the Fifth International Conference on Fun with Algorithms (FUN 2010),
    Lecture Notes in Computer Science, Springer--Verlag, vol. 6099, pp. 89-101, 2010.
    (With P. Burcsi, G. Fici, Zs. Lipták).

  55. "A Better Bouncer's Algorithm'',
    in: Proc. of the Fifth Internatioeeal Conference on Fun with Algorithms (FUN 2010),
    Lecture Notes in Computer Science, Springer--Verlag, vol. 6099, pp. 113-120, 2010.
    (With T. Gagie, A.j. Macula, M. Milanič, E. Triesch).

  56. "Searching for Jumbled Patterns in Strings'',
    in: Proc. of the Prague Stringology Conference 2009, pp. 105-117, 2009.
    (With G. Fici, Zs. Lipták).

  57. ``Computing with Priced Information: When the Value Makes the Price'',
    in:Proceedings of the 19th International Symposium on Algorithms and Computation (ISAAC 2008),
    Lecture Notes in Computer Science, vol. 5369, pp. 378-389, Springer-Verlag, 2008.
    (With M. Milanič).

  58. ``Function Evaluation via Linear Programming in the Priced Information Model'',
    in:Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008),
    Lecture Notes in Computer Science, vol. 5125, pp. 173-185, Springer-Verlag, 2008.
    (With E. Laber).

  59. ``2-Stage Fault Tolerant Interval Group Testing'',
    in:Proceedings of the 18th International Symposium on Algorithms and Computation (ISAAC 2007),
    Lecture Notes in Computer Science, vol. 4835, pp. 858-868, Springer-Verlag, 2007.
    (With J. Quitzau).

  60. ``Tunstall Parse Trees Optimum under Various Criteria''.
    in: Proceedings of 2007 International Symposium in Information Theory (ISIT2007), pp. 81-85, Nice, 2007.
    (With L. Gargano and U. Vaccaro).

  61. ``Analysis and Comparison of Information Theory-Based Distances for Genomic Strings'',
    In: Proc. of Collective Dynamics: Topics on Competition and Cooperation in the Biosciences (BIOCOMP 2007),
    AIP Conference Proceedings vol. 1028, pp. 292-310.
    (With W. Balzano, M. Del Sorbo, and U. Vaccaro).

  62. ``Faster Centralized Communication in Radio Networks'',
    in:Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC 2006),
    Lecture Notes in Computer Science, vol. 4288 , pp. 339-348, Springer-Verlag, 2006.
    (With F. Manne and Q. Xin).

  63. ``On the Competitive Ratio of Evaluating Priced Functions'',
    in:Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 944-953, ACM Press, 2006.
    (With E. Laber).

  64. ``An Optimal Algorithm for Querying Priced Information: Monotone Boolean Functions and Game Trees'',
    in:Proceedings of the 13th Annual European Symposium on Algorithms (ESA 2005),
    Lecture Notes in Computer Science, vol. 3669 , pp. 664-676, Springer-Verlag, 2005.
    (With E. Laber).

  65. ``A New Strategy for Querying Priced Information'',
    in:Proceedings of the 37th ACM Symposium on Theory of Computing (STOC 2005) , pp. 674-683, ACM Press, 2005.
    (With E. Laber).

  66. ``Overlaps Help: Improved Bounds for Group Testing with Interval Queries'',
    in:Proceedings of the 11th International Computing and Combinatorics Conference (COCOON 2005),
    Lecture Notes in Computer Science, vol. 3595 , pp. 935-944, Springer-Verlag, 2005.
    (With P. Damaschke, L. Tansini, S. Werth).

  67. ``Optimal Group Testing Algorithms with Interval Queries and Their Application to Splice Site Detection'',
    to appear in:Proceedings of the International Workshop on Bioinformatics Research and Applications (IWBRA 2005) , 2005.
    (With P. Damaschke and U. Vaccaro).

  68. ``Q-ary Ulam-Rényi Game with Weighted Constrained Lies'',
    in:Proceedings of the 10th International Computing and Combinatorics Conference (COCOON 2004),
    Lecture Notes in Computer Science, vol. 3106, pp. 82-91, Springer-Verlag, 2004.
    (With C. Deppe and D. Mundici).

  69. ``Quasy-Perfect Minimally Adaptive q-ary Search with Unreliable Tests'',
    in:Proceedings of the 14th International Symposium on Algorithms (ISAAC2003),
    Lecture Notes in Computer Science, vol. 2906, pp. 527-536, Springer-Verlag, 2003.
    (With C. Deppe).

  70. ``Bounding the Average Length of Optimal Source Codes'',
    in:Proceedings of International Symposium in Information Theory (ISIT2002), p. 177, IEEE Press, 2002.
    (With U. Vaccaro).

  71. ``On Searching Strategies, Parallel Questions, and Delayed Answers'',
    in: Proceedings of Fun with Algorithms (FUN01),
    E. Lodi, L. Pagli and N. Santoro (Eds.), pp. 27--42, Carleton Scientific Press, 2001.
    (With L. Gargano and U. Vaccaro).

  72. ``The Entropy is Supermodular on the Majorization Lattice'',
    in: Proceedings of 2001 International Symposium in Information Theory (ISIT2001), p. 230, IEEE Press, 2001.
    (With U. Vaccaro)

  73. ``Coping with Delays and Time-Outs in Binary Search Procedures'',
    in: Eleventh Annual International Symposium on Algorithms and Computation (ISAAC2000) D. T. Lee and Shang-Hua Teng (Eds.),
    Lectures Notes in Computer Science, vol. 1969, pp. 96--107, Springer--Verlag, (2000).
    (With U. Vaccaro).

  74. ``Optimal Approximation of Uniform Distributions with a Biased Coin'',
    in: Proceedings of RANDOM2000, A. Broder (Ed.), Carleton University Press, pp. 23-37, 2000.
    (With L. Gargano and U. Vaccaro).

  75. ``Optimal coding with one asymmetric error: below the Sphere Packing bound '',
    in: Proceedings of 6th Annual International Conference on Computing and Combinatorics-- COCOON'2000,
    Lecture Notes in Computer Science, vol. 1858 , pp. 159--169, Springer--Verlag, 2000.
    (With D. Mundici).

  76. ``Least Adaptive Optimal Search with Unreliable Tests'',
    in: Algorithm Theory - SWAT2000,
    M. Halldorsson (Ed.), Lectures Notes in Computer Science, vol. 1851, pp. 547-562, Springer-Verlag, 2000.
    (With D. Mundici and U. Vaccaro).

  77. ``Perfect, Minimally Adaptive, Error-Correcting Searching Strategies'',
    in: International Symposium in Information Theory (ISIT2000), pp. 377, IEEE Press, 2000.
    (With D. Mundici and U. Vaccaro).

  78. ``Optimal binary search with two unreliable tests and minimum adaptiveness'',
    in: Proceedings of 7th Annual European Symposium on Algorithms-- ESA'99,
    J. Nesetril (Eds.), Lectures Notes in Computer Science, vol. 1643, pp. 257--266, Springer--Verlag, 1999.
    (With D. Mundici).

  79. ``Fuzzy Evolutionary Framework for Adaptive Agents'',
    in : Proceedings of ACM SAC'99 , February 1999, San Antonio, Texas.
    (With A. Di Nola, V. Loia).

  80. ``Q-ary Searching with Lies'',
    in: Proceedings of 6th Italian Conference on Theoretical Computer Science-- ICTCS'98,
    P. Degano, U. Vaccaro, G. Pirillo (Eds.), pp. 228-240, World Scientific, 1998.

  81. ``Can Actor learn by evolving models of fuzzy reasoning?''
    in: Proceedings of Journees Francophones des Langages applicatifs-- JFLA'98,
    S. Cerri and C. Queinnec (Eds.), pp. 215-226, INRIA, 1998.
    (With V. Loia).

  82. ``Actor-Based Paradigm for Fuzzy Adaptive Hypermedia''
    in: Proceedings of Workshop ``Advanced in Language for User Modeling''-- UM'97,
    June 1997, Chia laguna, pp. 63-72.
    (With A. Dattolo, V. Loia)

  83. ``A Distributed, Concurrent Architecture for Fuzzy Evolutionary Models'',
    in: Proceedings of European Symposium on Intelligent Techniques,
    March 1997, Bari, pp. 171--182.
    (With A. Gisolfi, V. Loia).

  84. ``Implementing a Fuzzy Classifier in GIS'',
    in: Proceedings of 2nd International ICSC Symposium on Fuzzy Logic and Application-- ISFL'97,
    February 1997, Zurich, pp. 327-332.
    (With A. Gisolfi, V. Loia).



    In Preparation and/or under review

  85. "On lower bounds for the Maximum Consecutive Subsums Problem and the (min,+)-convolution'', pdf
    submitted to: IEEE International Symposium on Information Theory (ISIT 2014).
    (With E. Laber, W. Bardales)