Research and Publications of Michael B. Baer

[redundancy plot of codes with a geometric distribution and exponential penalty]

[a short introduction: Rényi's siege problem]
[a longer introduction: Personal view]

[dissertation] [journal papers] [conference papers]
[notes] [talks] [abstracts]

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.

Dissertation and Research Summary

Introduction (Research Summary)

[intro]
Michael B. Baer, "Another Personal View of Generalized Huffman Coding"
(Updated 2013, up-to-date as of 2016)

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

Dissertation

[thesis]
Michael B. Baer, Coding for General Penalties
Stanford University

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

Publications

Journal Papers

[J5]
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]

[J4]
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]

[J3]
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]

[J2]
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]

[J1]
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]

Conference Papers

[C11]
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]

[C10]
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]

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

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

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

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

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

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

[C6]
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)

[C5]
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]

[C4]
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)

[C3]
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]

[C2]
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)

[C1]
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]

Other Works

Notes on Information Theory

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

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

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

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

Invited Talks

[T6]
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]
[T5]
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)
[T4]
Google Tech Talk
("On Conditional Branches in Optimal Decision Trees (or Improving 'Optimal' Decision Trees)," February 2007) [Abstract]
[T3]
USC talk
("Optimal Huffman Coding with Nonlinear Costs," February 2005) [Abstract]
[T2]
UCLA talk
("Optimal Source Coding with Nonlinear Costs," June 2004) [Abstract]
[T1]
CalTech talk
("Source Coding for General Penalties", October 2003) [Abstract]

Topics of Current Interest

[DCT]
Alphabetic coding, robust lossless coding, search


All material © 1998-2016 Michael B. Baer or the respective copyright holder given above

Emails used on publications now defunct; instead use: