List of publications

List of Publications of Ferdinando Cicalese

    Proceedings and Special Issue Edited

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

  2. 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

  3. "On the Competitive Ratio of Evaluating Priced Functions'',
    Journal of the ACM, vol. 58, No. 3, Article 9, 2011.
    (With E. Laber)

  4. "Graphs of separability at most two'',
    Discrete Applied Mathematics, to appear.
    (With M. Milanič)

  5. "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č)

  6. "On the complexity of searching in trees and partially ordered structures'',
    Theoretical Computer Science, to appear.
    (With T. Jacobs, E. Laber, M. Molinaro)

  7. "On Approximate Jumbled Pattern Matching in Strings'',
    Theory of Computing Systems, to appear.
    (With P. Burcsi, G. Fici, Zs. Lipták)

  8. "Algorithms for Jumbled Pattern Matching in Strings'',
    International Foundations of Computer Science, to appear.
    (With P. Burcsi, G. Fici, Zs. Lipták)

  9. "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č)

  10. "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).

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

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

  13. ``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).

  14. ``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)

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

  16. ``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).

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

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

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

  20. "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)

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

  22. ``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).

  23. ``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).

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

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

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

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

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



    Book Chapters

  29. ``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.

  30. ``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)

  31. ``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)

  32. ``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

  33. "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)

  34. "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)

  35. "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)

  36. "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)

  37. "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)

  38. "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č).

  39. "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).

  40. "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).

  41. "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).

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

  43. ``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č).

  44. ``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).

  45. ``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).

  46. ``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).

  47. ``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).

  48. ``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).

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

  50. ``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).

  51. ``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).

  52. ``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).

  53. ``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).

  54. ``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).

  55. ``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).

  56. ``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).

  57. ``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).

  58. ``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)

  59. ``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).

  60. ``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).

  61. ``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).

  62. ``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).

  63. ``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).

  64. ``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).

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

  66. ``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.

  67. ``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).

  68. ``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)

  69. ``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).

  70. ``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).