Dan Hirschberg's Publications

A. Book Chapters

  1. D.S. Hirschberg, Recent results on the complexity of common subsequence problems, in Time Warps, String Edits, and Macromolecules, D. Sankoff and J.B. Kruskal, ed., Addison-Wesley, 1983, 323-328.
  2. D.S. Hirschberg and D.A. Lelewer, Context modeling for text compression, in Image and Text Compression, J. A. Storer, ed., Kluwer Academic Publishers, Boston, Mass., 1992, 113-145.
  3. D.S. Hirschberg, M.J. Pazzani and K. Ali, Average case analysis of k-CNF and k-DNF learning algorithms, in Computational Learning Theory and Natural Learning Systems: Constraints and Prospects, S. Hanson, M. Kearns, T. Petsche and R. Rivest, eds., MIT Press, Cambridge, Mass., 1994, 15-28.
  4. D. Hirschberg and G. Myers, eds., Combinatorial Pattern Matching, Proceedings 1996, Lecture Notes in Computer Science, vol. 1075, Springer-Verlag, Berlin, 1996, 392 pp.
  5. D.S. Hirschberg, Serial computations of Levenshtein distances, in Pattern Matching Algorithms, A. Apostolico and Z. Galil, eds., Oxford University Press, 1997, 123-141.

B. Journal Articles

  1. D.S. Hirschberg, A class of dynamic memory allocation algorithms, Comm. ACM 16,10 (1973) 615-618.
  2. D.S. Hirschberg, A linear space algorithm for computing maximal common subsequences, Comm. ACM 18,6 (1975) 341-343.
  3. A.V. Aho, D.S. Hirschberg and J.D. Ullman, Bounds on the complexity of the longest common subsequence problem, Journal ACM 23,1 (1976) 1-12.
  4. D.S. Hirschberg and C.K. Wong, A polynomial-time algorithm for the knapsack problem with two variables, Journal ACM 23,1 (1976) 147-154.
  5. D.S. Hirschberg, An insertion technique for one-sided height-balanced trees, Comm. ACM 19,8 (1976) 471-473.
  6. A.K. Chandra, D.S. Hirschberg and C.K. Wong, Approximate algorithms for some generalized knapsack problems, Theoretical Computer Science 3,3 (1976) 293-304.
  7. D.S. Hirschberg, Algorithms for the longest common subsequence problem, Journal ACM 24,4 (1977) 664-675.
  8. D.S. Hirschberg, An information theoretic lower bound for the longest common subsequence problem, Information Processing Letters 7,1 (1978) 40-41.
  9. D.S. Hirschberg, Fast parallel sorting algorithms, Comm. ACM 21,8 (1978) 657-661.
  10. A.K. Chandra, D.S. Hirschberg and C.K. Wong, Bin packing with geometric constraints in computer network design, Operations Research 26,5 (1978) 760-772.
  11. D.S. Hirschberg and C.K. Wong, Upper and lower bounds for graph-diameter problems, Journal of Comb. Theory (B) 26,1 (1979) 66-74.
  12. D.S. Hirschberg, A.K. Chandra and D.V. Sarwate, Computing connected components on parallel computers, Comm. ACM 22,8 (1979) 461-464.
  13. D.S. Hirschberg, On the complexity of searching a set of vectors, SIAM Journal on Computing 9,1 (1980) 126-129.
  14. D.S. Hirschberg and J.B. Sinclair, Decentralized extrema-finding in circular configurations of processors, Comm. ACM 23,11 (1980) 627-628.
  15. M. Kumar and D.S. Hirschberg, An efficient implementation of Batcher's odd-even merge algorithm and its application in parallel sorting schemes, IEEE Trans. on Computers C-32,3 (1983) 254-264.
  16. L.L. Larmore and D.S. Hirschberg, Efficient optimal pagination of scrolls, Comm. ACM 28,8 (1985) 854-856.
  17. J. Hester and D.S. Hirschberg, Self-organizing linear search, Computing Surveys 17,3 (1985) 295-311.
  18. J.H. Hester, D.S. Hirschberg, S.-H.S. Huang, and C.K. Wong, Faster construction of optimal binary split trees, Journal of Algorithms 7,3 (1986) 412-424.
  19. D.S. Hirschberg and L.L. Larmore, Average case analysis of marking algorithms, SIAM Journal on Computing 15,4 (1986) 1069-1074.
  20. D.S. Hirschberg and L.L. Larmore, The Set LCS problem, Algorithmica 2 (1987) 91-95.
  21. D.S. Hirschberg and D.J. Volper, Improved update/query algorithms for the interval valuation problem, Information Processing Letters 24 (1987) 307-310.
  22. D.S. Hirschberg and L.L. Larmore, New applications of failure functions, Journal ACM 34,3 (1987) 616-625.
  23. D.S. Hirschberg and L.L. Larmore, The least weight subsequence problem, SIAM J. on Computing 16,4 (1987) 628-638.
  24. J. Hester and D.S. Hirschberg, Self-organizing search lists using probabilistic backpointers, Comm. ACM 30,12 (1987) 1074-1079.
  25. D.A. Lelewer and D.S. Hirschberg, Data compression, Computing Surveys 19,3 (1987) 261-297. Reprinted in Japanese BIT Special issue in Computer Science (1989) 165-195. (in HTML)
  26. J.H. Hester, D.S. Hirschberg, and L.L. Larmore, Construction of optimal binary split trees in the presence of bounded access probabilities, Journal of Algorithms 9,2 (1988) 245-253.
  27. D.S. Hirschberg and L.L. Larmore, The Set-Set LCS problem, Algorithmica 4,4 (1989) 503-510.
  28. C. Ng and D.S. Hirschberg, Lower bounds for the stable marriage problem and its variants, SIAM J. on Computing 19,1 (1990) 71-77.
  29. D.S. Hirschberg and D.A. Lelewer, Efficient decoding of prefix codes, Comm. ACM 33,4 (1990) 449-459.
  30. L.L. Larmore and D.S. Hirschberg, A fast algorithm for optimal length-limited codes, Journal ACM 37,3 (1990) 464-473.
  31. C. Ng and D.S. Hirschberg, Three-dimensional stable matching problems, SIAM J. Discr. Math. 4,2 (1991) 245-252.
  32. D.S. Hirschberg and L.L. Larmore, The traveler's problem, Journal of Algorithms 13 (1992) 148-160.
  33. D.S. Hirschberg and S.S. Seiden, A bounded-space tree traversal algorithm, Information Processing Letters 47 (1993) 215-219.
  34. S.S. Seiden and D.S. Hirschberg, Finding succinct minimal perfect hashing functions, Information Processing Letters 51 (1994) 283-288.
  35. L.M. Stauffer and D.S. Hirschberg, Systolic self-organizing lists under transpose, IEEE Trans. on Parallel and Distributed Systems 6,1 (1995) 102-105.
  36. D.S. Hirschberg and L.M. Stauffer, Dictionary compression on the PRAM, Parallel Processing Letters 7,3 (1997) 297-308.
  37. D. Eppstein and D.S. Hirschberg, Choosing subsets with maximum weighted average, Journal of Algorithms 24 (1997) 177-193.
  38. M. Dillencourt, D. Eppstein, and D. S. Hirschberg, Geometric thickness of complete graphs, J. Graph Algorithms and Applications 4,3 (2000) 5-17. (original version) Reprinted in Graph Algorithms and Applications 2, Giuseppe Liotta, Robert Tamassia, and Ioannis G Tollis, ed., (2004).
  39. D.S. Hirschberg and M. Regnier, Tight bounds on the number of string subsequences, Journal of Discrete Algorithms 1,1 (2000) 123-132.
  40. M. Mamidipaka, D. Hirschberg, and N. Dutt, Adaptive low power address encoding techniques using self-organizing lists, IEEE Trans. on Very Large Scale Integration Systems 11,5 (2003) 827-834.
  41. D. Eppstein, M.T. Goodrich, and D.S. Hirschberg, Improved combinatorial group testing algorithms for real-world problem sizes, SIAM J. on Computing 36,5 (2007) 1360-1375.
  42. G.I. Bell, D.S. Hirschberg, and P. Guerrero-Garcia, The minimum size required of a solitaire army, Integers: Electronic Journal of Combinatorial Number Theory 7 (2007), #G07 http://www.integers-ejcnt.org/vol7.html (22 pages).
  43. P. Baldi, R. Benz, D.S. Hirschberg, and S.J. Swamidass, Lossless compression of chemical fingerprints using integer entropy codes improves storage and retrieval, Journal of Chemical Information and Modeling 47,6 (2007) 2098-2109.
  44. M.T. Goodrich and D.S. Hirschberg, Improved adaptive group testing algorithms with applications to multiple access channels and dead sensor diagnosis, Journal of Combinatorial Optimization 15,1 (2008) 95-121.
  45. P. Baldi, D.S. Hirschberg, and R. Nasr, Speeding up chemical database searches using a proximity filter based on the logical exclusive-or, Journal of Chemical Information and Modeling 48,7 (2008) 1367-1378.
  46. P. Baldi and D.S. Hirschberg, An intersection inequality sharper than the triangle inequality for the Tanimoto similarity measure, Journal of Chemical Information and Modeling 49,8 (2009) 1866-1870.
  47. R. Nasr, D.S. Hirschberg, and P. Baldi, Hashing algorithms and data structures for rapid searches of fingerprint vectors, Journal of Chemical Information and Modeling 50,8 (2010) 1358-1368.
  48. D. Eppstein and D. Hirschberg, From discrepancy to majority, Algorithmica 80,4 (2018) 1278-1297.

C. Conference Articles

  1. A.V. Aho, D.S. Hirschberg and J.D. Ullman, Bounds on the complexity of the longest common subsequence problem, Proc. 15th Annual Symp. on Switching and Automata Theory, New Orleans LA, IEEE (1974) 104-109.
  2. D.S. Hirschberg, A slightly better bound for the vertex connectivity problem, Proc. Conf. of Info. Sci. and Systems, Baltimore MD, Johns Hopkins Univ. (1975) 257-258.
  3. D.S. Hirschberg, Parallel algorithms for the transitive closure and the connected component problems, Proc. 8th Annual Symp. on Theory of Computing, Hershey PA, ACM (1976) 55-57.
  4. D.S. Hirschberg, Complexity of common subsequence problems, Fundamentals of Computation Theory, Poznan Poland, Lecture Notes in Computer Science, 56, Springer-Verlag, Berlin (1977) 393-398.
  5. D.S. Hirschberg, A lower worst-case complexity for searching a dictionary, Proc. 16th Annual Allerton Conf. on Comm., Control, and Computing, Monticello IL, Univ. of Ill. (1978) 50-53.
  6. D.S. Hirschberg, Election processes in distributed systems, Proc. 18th Annual Allerton Conf. on Comm., Control, and Computing, Monticello IL, Univ. of Ill. (1980) p.823.
  7. M. Kumar and D.S. Hirschberg, An efficient implementation of Batcher's odd-even merge algorithm and its application in parallel sorting schemes, Proc. Conf. of Info. Sci. and Systems, Baltimore MD, Johns Hopkins Univ. (1981).
  8. D.S. Hirschberg, Parallel graph algorithms without memory conflicts, Proc. 20th Annual Allerton Conf. on Comm., Control, and Computing, Monticello IL, Univ. of Ill. (1982) 257-263.
  9. D.S. Hirschberg and D.J. Volper, A parallel solution for the minimum spanning tree problem, Proc. Conf. of Info. Sci. and Systems, Baltimore MD, Johns Hopkins Univ. (1983) 680-684.
  10. D.S. Hirschberg and L.L. Larmore, Average case analysis of marking algorithms, Proc. 22nd Annual Allerton Conf. on Comm., Control, and Computing, Monticello IL, Univ. of Ill. (1984) 508-509.
  11. L.L. Larmore and D.S. Hirschberg, Breaking a paragraph into lines in linear time, Proc. 22nd Annual Allerton Conf. on Comm., Control, and Computing, Monticello IL, Univ. of Ill. (1984) 478-487.
  12. D.S. Hirschberg and L.L. Larmore, The Least Weight Subsequence Problem, Proc. 26th Annual Symp. on Foundations of Computer Science, Portland Oregon, IEEE (1985) 137-143.
  13. R.R. Razouk and D.S. Hirschberg, Tools for efficient analysis of concurrent software systems, Proc. of SOFTFAIR II, A Second Conference on Software Development Tools, Techniques, and Alternatives, San Francisco CA (1985).
  14. J.H. Hester and D.S. Hirschberg, Generation of optimal binary split trees, Proc. 24th Annual Allerton Conf. on Comm., Control, and Computing, Monticello IL, Univ. of Ill. (1986) 308-313.
  15. L.L. Larmore and D.S. Hirschberg, Length-limited coding, Proc. First Annual Symposium on Discrete Algorithms, San Francisco, SIAM, Phil. (1990) 310-318.
  16. D.A. Lelewer and D.S. Hirschberg, Streamlining context models for data compression, Proc. IEEE Data Compression Conference, Snowbird UT, IEEE (1991) 313-322.
  17. D.S. Hirschberg, M.J. Pazzani and K. Ali, Average case analysis of k-CNF and k-DNF learning algorithms, Second Annual Workshop on Computational Learning Theory and Natural Learning Systems: Constraints and Prospects, Berkeley CA (1991).
  18. S. Bhatia, D.S. Hirschberg and I.D. Scherson, Shortest paths in orthogonal graphs, Proc. 29th Annual Allerton Conf. on Comm., Control, and Computing, Monticello IL, Univ. of Ill. (1991) 488-497.
  19. L.M. Stauffer and D.S. Hirschberg, Transpose coding on the systolic array, Proc. IEEE Data Compression Conference, Snowbird UT, IEEE (1992) 162-171.
  20. D.S. Hirschberg and M.J. Pazzani, Average case analysis of learning k-CNF concepts, Proc. Ninth International Machine Learning Conference, Aberdeen Scotland, Morgan Kaufmann, San Mateo (1992) 206-211.
  21. D.S. Hirschberg and L.M. Stauffer, Parsing algorithms for dictionary compression on the PRAM, Proc. IEEE Data Compression Conference, Snowbird UT, IEEE (1994) 136-145.
  22. L.M. Stauffer and D.S. Hirschberg, PRAM algorithms for static dictionary compression, Proc. International Parallel Processing Symposium, Cancun Mexico, IEEE (1994) 344-348.
  23. D. Eppstein and D.S. Hirschberg, Choosing subsets with maximum weighted average, Proc. 5th MSI Workshop on Computational Geometry, Stonybrook NY (1995) 7-8.
  24. J.K. Martin and D.S. Hirschberg, On the complexity of learning decision trees, Proc. 4th Int. Symp. on Artif. Intell. and Math., Fort Lauderdale, FL (1996) 112-115.
  25. M.B. Dillencourt, D.E. Eppstein and D.S. Hirschberg, Geometric thickness of complete graphs, Graph Drawing: 6th Int'l Symp. (GD '98), Montreal Canada, Lecture Notes in Computer Science, vol. 1547, Springer-Verlag, Berlin (1998) 102-110.
  26. D.S. Hirschberg, Bounds on the number of string subsequences, Proc. Symp. on Combinatorial Pattern Matching, Warwick UK, Lecture Notes in Computer Science, Springer-Verlag, Berlin (1999) 115-122.
  27. M. Mamidipaka, D. Hirschberg, and N. Dutt, Low power address encoding using self-organizing lists, Proc. ACM/IEEE Int'l Symp. on Low Power Electronics and Design, Huntington Beach CA (2001) 188-193.
  28. M. Mamidipaka, D. Hirschberg, and N. Dutt, Efficient power reduction techniques for time multiplexed address buses, Proc. 15th ACM Int'l Symp. on System Synthesis, Kyoto (2002) 207-212.
  29. D. Eppstein, M.T. Goodrich, and D.S. Hirschberg, Improved combinatorial group testing for real-world problem sizes, Workshop on Algorithms and Data Structures (WADS) (2005), in Lecture Notes in Computer Science, vol. 3608, Springer-Verlag, Berlin, 2005, 86-98.
  30. M.T. Goodrich and D.S. Hirschberg, Efficient parallel algorithms for dead sensor diagnosis and multiple access channels, Proc. 18th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA '06), Cambridge MA (2006) 118-127.
  31. D.S. Hirschberg and P. Baldi, Effective compression of monotone and quasi-monotone sequences of integers, Proc. IEEE Data Compression Conference, Snowbird UT, IEEE (2008) 520.
  32. D.S. Hirschberg, Constructing problems of geometric combinatorics, Gathering for Gardner 9 (G4G9), Atlanta GA (2010), 8 pp.
  33. M.T. Goodrich, D.S. Hirschberg, M. Mitzenmacher, and J. Thaler, Cache-oblivious dictionaries and multimaps with negligible failure probability, Proc. Mediterranean Conference on Algorithms, Kibbutz Ein-Gedi Israel (2012), Lecture Notes in Computer Science, vol. 7659, Springer-Verlag, Berlin (2012) 203-218.
  34. D. Eppstein, M. Goodrich, and D. Hirschberg, Combinatorial pair testing: distinguishing workers from slackers, Algorithms and Data Structures Symposium (WADS) 2013, Lecture Notes in Computer Science, vol. 8037, Springer-Verlag, Berlin (2013) 316-327.
  35. D. Eppstein and D. Hirschberg, From discrepancy to majority, Proc. 12th Latin American Theoretical Informatics Symposium (LATIN'16), Ensenada, Mexico (2016) 390-402.

D. Selected Additional Publications

  1. D.S. Hirschberg and E.C. Horvath, Permutations of the elements of a matrix by column and row rotations, Comp. Sci. Lab. TR-111, Princeton University (July 1972).
  2. D.S. Hirschberg and M. Edelberg, On the complexity of computing graph isomorphism, Comp. Sci. Lab. TR-130, Princeton University (Aug. 1973).
  3. D.S. Hirschberg, Searching a dictionary within tighter time bounds, Tech Rpt, Rice University (Jan. 1979).
  4. D.S. Hirschberg, L.L. Larmore and M. Molodowitch, Subtree weight ratios for optimal binary search trees, Tech. Rpt. 86-02, ICS Dept., UC Irvine (Jan. 1986).
  5. D.A. Lelewer and D.S. Hirschberg, An order-2 context model for data compression with reduced time and space requirements, Tech. Rpt. 90-33, ICS Dept., UC Irvine (Oct. 1990).
  6. L.M. Stauffer and D.S. Hirschberg, Systolic implementations for transpose coding, Tech. Rpt. 91-69, ICS Dept., UC Irvine (1991).
  7. L.M. Stauffer and D.S. Hirschberg, Self-organizing lists on the Xnet, Tech. Rpt. 92-81, ICS Dept., UC Irvine (1992).
  8. D.S. Hirschberg, Data compression, 1993 McGraw-Hill Yearbook of Science and Technology, McGraw-Hill, New York, 1992, 91-93.
  9. L.M. Stauffer and D.S. Hirschberg, Parallel data compression, Tech. Rpt. 91-44, ICS Dept., UC Irvine (1991). Revised (1993).
  10. J.K. Martin and D.S. Hirschberg, The time complexity of decision tree induction, Tech. Rpt. 95-27, ICS Dept., UC Irvine (1995).
  11. J.K. Martin and D.S. Hirschberg, Small sample statistics for classification error rates, I: Error rate measurements, Tech. Rpt. 96-21, ICS Dept., UC Irvine (1996).
  12. J.K. Martin and D.S. Hirschberg, Small sample statistics for classification error rates, II: Confidence intervals and significance tests, Tech. Rpt. 96-22, ICS Dept., UC Irvine (1996).
  13. D.S. Hirschberg, Data compression, McGraw-Hill Encyclopedia of Science and Technology (8th ed.) vol. 5, McGraw-Hill, New York, 1997, pp. 31-33.
Last modified: Jun 22, 2018