Research and Publications of Michael B. Baer

My academic research is in the area of 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"
September 2008

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

Michael B. Baer, Coding for General Penalties
Stanford University, June 2003

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

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, "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, "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)

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

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, "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)

Michael Baer, "Rényi to Rényi -- Source Coding under Siege"
(ISIT 2006, extends Chapter 2 of dissertation)

Extended Abstract (124 KB, 5 pp., May 2006) [Abstract] [arXiv.org] [IEEE Xplore]
Full paper ("Prefix Coding under Siege") (200 KB, 10 pp., May 2006) [arXiv.org]

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]

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

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

Extended Abstract (110 KB, 5 pp., April 2008) [Abstract] [arXiv.org (2007 version)] [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, "Tight Bounds on Minimum Maximum Pointwise Redundancy"
(ISIT 2008)

Extended Abstract (120 KB, 5 pp., April 2008) [Abstract] [arXiv.org] [IEEE Xplore]
Full paper ("Redundancy-Related Bounds on Generalized Huffman Codes") (209 KB, 12 pp., March 2009) [Abstract] [arXiv.org]

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]

Michael B. Baer, "Alphabetic Coding with Exponential Costs"
PDF draft (110 KB, 7 pp., March 2009) [Abstract] [arXiv.org]

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

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

UCLA talk based on dissertation and independent research
("Optimal Source Coding with Nonlinear Costs," June 2004) [Abstract]

USC talk based on dissertation and independent research
("Optimal Huffman Coding with Nonlinear Costs," February 2005) [Abstract]

Google Tech Talk based on independent research
("On Conditional Branches in Optimal Decision Trees (or Improving 'Optimal' Decision Trees)," February 2007) [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)

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

Alphabetic coding, alphabet partitioning, video/image analysis, and the Euclidean algorithm

© 1998-2009 Michael B. Baer, 1998-2003 Stanford University, calbear @ ieee _· 0rg   
( Now-defunct emails used on publications: mbaer@ocarinanetworks.com, michael.baer@efi.com, calbear@stanford.edu, calbaer@stanford.edu )