Research and Publications of Michael B. Baer

My academic research is in the area of lossless data compression, specifically problems in prefix coding that can be considered extensions to Huffman coding (and the related Hu-Tucker algorithm), with an emphasis on utilities other than expected codeword length. Applications include low bandwidth channels, security, search, queueing, diagnostic testing, and decision trees. I have written a lay introduction to this topic here, and a longer one here. Talk slides of my presentations and other works not available online are available upon request.

© COPYRIGHT NOTICE: Many of the below documents have been submitted by their author(s) to scholarly journals or conferences (as indicated); others contain summaries of and extensions to this work. The manuscripts are put online to facilitate non-commercial dissemination of scientific work. These manuscripts are copyrighted by the authors or the journals in which they were published. You may copy a manuscript for scholarly, non-commerical purposes, such as research or instruction, provided that you agree to respect these copyrights.

Michael B. Baer, "Another Personal View of Generalized Huffman Coding"
(Up-to-date as of 2021)

PDF (176 KB, 16 pp.) [Abstract]

Michael B. Baer, Coding for General Penalties
Stanford University

PDF (780 KB, 136 pp.) [Abstract]

Michael B. Baer, "Redundancy-Related Bounds on Generalized Huffman Codes"
IEEE Transactions on Information Theory, vol. IT-57, no. 4, pp. 2278-2290, April 2011

PDF (243 KB, 15 pp.) [PS.gz version, 163 KB] [Abstract] [arXiv.org] [IEEE Xplore]

Michael B. Baer, "Alphabetic Coding with Exponential Costs"
Information Processing Letters, vol. 110, issue 4, pp. 139-142, January 2010

PDF (107 KB, 4 pp.) [PS.gz version, 126 KB] [Abstract] [ScienceDirect]

Michael B. Baer, "Optimal Prefix Codes for Infinite Alphabets with Nonlinear Costs"
IEEE Transactions on Information Theory, vol. IT-54, no. 3, pp. 1273-1286, March 2008
(Extends Chapter 5 of dissertation)
Correction: The caption for Fig. 6 (pictured left) should have "d = {0,1,2,4,8,16}" rather than "d = {1,2,4,16,256,65536}."

PDF (568 KB, 14 pp.) [PS.gz version, 262 KB] [Abstract] [arXiv.org] [IEEE Xplore]

Michael B. Baer, "Source Coding for Quasiarithmetic Penalties"
IEEE Transactions on Information Theory, vol. IT-52, no. 10, pp. 4380-4393, October 2006
(Corresponds to Chapter 4 of dissertation)

PDF (256 KB, 14 pp.) [PS.gz version, 178 KB] [Abstract] [arXiv.org] [IEEE Xplore]

Michael B. Baer, "A General Framework for Codes Involving Redundancy Minimization"
IEEE Transactions on Information Theory, vol. IT-52, no. 1, pp. 344-349, January 2006
(Corresponds to Chapter 3 of dissertation)

PDF (133 KB, 7 pp.) [PS.gz version, 116 KB] [Abstract] [arXiv.org] [IEEE Xplore]

Michael B. Baer, "On the Redundancy of Huffman Codes with Exponential Objectives"
(ISIT 2013)

Extended Abstract (204 KB, 5 pp., April 2013) [Abstract] [arXiv.org (early version)] [IEEE Xplore]

Michael B. Baer, "Efficient Implementation of the Generalized Tunstall Code Generation Algorithm"
(ISIT 2009)

Extended Abstract (95 KB, 5 pp., April 2009) [Abstract] [arXiv.org] [IEEE Xplore]

Michael Baer, "Tight Bounds on Minimum Maximum Pointwise Redundancy"
(ISIT 2008)

Extended Abstract (120 KB, 5 pp., April 2008) [Abstract] [arXiv.org] [IEEE Xplore]

Michael Baer, "Prefix Codes for Power Laws"
(ISIT 2008)

Extended Abstract (112 KB, 5 pp., April 2008) [Abstract] [arXiv.org (2007 version)] [IEEE Xplore]

Michael Baer, "Reserved-length Prefix Coding"
(ISIT 2008)

Extended Abstract (110 KB, 5 pp., April 2008) [Abstract] [arXiv.org (2007 version)] [IEEE Xplore]

Michael B. Baer, "D-ary Bounded-Length Huffman Coding"
(ISIT 2007)

Extended Abstract (122 KB, 5 pp., March 2007) [Abstract] [arXiv.org] [IEEE Xplore]
Full paper ("Twenty (or so) Questions: D-ary Length-Bounded Prefix Coding") (220 KB, 12 pp., February 2008) [Abstract] [arXiv.org (2007 version)] (unpublished; not resubmitted after change of associate editor)

Michael B. Baer, "Infinite-Alphabet Prefix Codes Optimal for β-Exponential Penalties"
(ISIT 2007, results included in "Optimal Prefix Codes for Infinite Alphabets with Nonlinear Costs")

Extended Abstract (252 KB, 5 pp., April 2007) [Abstract] [arXiv.org] [IEEE Xplore]

Michael Baer, "On Conditional Branches in Optimal Decision Trees"
(ISIT 2007)

Extended Abstract (98 KB, 5 pp., November 2006) [Abstract] [arXiv.org] [IEEE Xplore]
Full paper ("On Conditional Branches in Optimal Search Trees") (160 KB, 14 pp., April 2007) [Abstract] [arXiv.org] (unpublished due to lack of suitable forum)

Michael Baer, "Rényi to Rényi -- Source Coding under Siege"
(ISIT 2006, extends Chapter 2 of dissertation, results included in "Alphabetic Coding with Exponential Costs")

Extended Abstract (124 KB, 5 pp., May 2006) [Abstract] [arXiv.org] [IEEE Xplore]

Michael Baer, "Source Coding for General Penalties"
(IEEE International Symposium on Information Theory [ISIT] 2003,
results included in "Source Coding for Quasiarithmetic Penalties")

Extended Abstract (157 KB, 5 pp., October 2002) [Abstract]
One-page Abstract (IEEE Xplore; also available upon request)

Elizabeth D. Mynatt, Maribeth Back, Roy Want, Michael Baer, Jason B. Ellis, "Designing Audio Aura"
(Special Interest Group on Computer-Human Interaction [SIGCHI] 1998, based on work done at Xerox PARC)

Full paper courtesy of PARC (93 KB, 8 pp.) [Abstract] [ACM Portal]

Michael Baer, "Convex optimization and a relative entropy problem"
PDF (32 KB, 1 p., 2010)

Michael Baer, "A simple countable infinite-entropy distribution"
PDF (34 KB, 1 p., 2008)

Michael Baer, "The asymmetry of relative entropy"
PDF (38 KB, 2 pp., 2007)

Michael Baer, "Kraft inequality and full trees"
PDF (52 KB, 3 pp., 2003)

Talks at the Chinese University of Hong Kong, the Hong Kong University of Science and Technology, and the University of Cyprus
("Redundancy-Related Bounds for Generalized Huffman Codes," based on the paper of the same title, June and November 2009) [Abstract]

Stanford "two-minute talk" in "Recent Results, Open Problems, and Mathematical Puzzles" session of Elements of Information Theory Workshop
("Reserved-length prefix coding: Coding with few codeword lengths," May 2008)

Google Tech Talk
("On Conditional Branches in Optimal Decision Trees (or Improving 'Optimal' Decision Trees)," February 2007) [Abstract]

USC talk
("Optimal Huffman Coding with Nonlinear Costs," February 2005) [Abstract]

UCLA talk
("Optimal Source Coding with Nonlinear Costs," June 2004) [Abstract]

CalTech talk
("Source Coding for General Penalties", October 2003) [Abstract]