Research
People
- Leadership
- People
- Jobs
- Awards
- Blogs
About
- About
- Worldwide Sites

www.PseudoCodewords.info

Papers on Linear Programming Decoding

»Main Page
»Papers
- »all papers
- »on pseudo-codewords
- »on LP decoding
- »on stopping sets, etc.
- »on EMD and ACE
- »on HDPC codes
- »on comb. optimization
»Presentations
»Workshop Announcement
»Feedback

This page lists papers on pseudo-codewords. Note that the assignment of a paper to a certain category is not always clear-cut and sometimes arbitrary.

Any suggestions for additions to this page are highly welcome. Please send an email to Pascal Vontobel [email: firstname dot lastname at hp dot com]. Thank you!

2009

A.G. Dimakis and P.O. Vontobel
LP decoding meets LP decoding: a connection between channel coding and compressed sensing [arxiv]
Proc. of the 47th Allerton Conference on Communications, Control, and Computing, Allerton House, Monticello, Illinois, USA, Sep. 30 - Oct. 2, 2009.

M.F. Flanagan, V. Skachek, E. Byrne, and M. Greferath
Linear-programming decoding of nonbinary linear codes [ieeexplore]
IEEE Trans. Inf. Theory, vol. 55, no. 9, pp. 4134-4154, Sept. 2009.

A.G. Dimakis, A.A. Gohari, and M.J. Wainwright
Guessing facets: polytope structure and improved LP decoder [ieeexplore]
IEEE Trans. Inf. Theory, vol. 55, no. 8, pp. 3479-3487, Aug. 2009.

M. Miwa, T. Wadayama, and I. Takumi
A cutting-plane method based on redundant rows for improving fractional distance [ieeexplore]
IEEE J. Selected Areas in Comm., vol. 27, no. 6, pp. 1005-1012, Aug. 2009.

E. Rosnes
On the pairwise error probability of linear programming decoding on independent Rayleigh flat-fading channels [ieeexplore]
IEEE Trans. Inform. Theory, vol. IT-55, no. 7, pp. 2942-2955, July 2009.

S. Heupel
Cycle polytopes and their application in coding theory [.pdf]
MSc. Thesis, Technical University Kaiserslautern, Germany, July 2009.

T. Wadayama
An LP decoding algorithm based on primal path-following interior point method [ieeexplore]
Proc. IEEE Int. Symp. Information Theory, Seoul, Korea, pp. 389-393, June 28-July 3, 2009.

V. Skachek
On LP decoding of nonbinary expander codes [ieeexplore]
Proc. IEEE Int. Symp. Information Theory, Seoul, Korea, pp. 384 - 388, June 28-July 3, 2009.

S. K. Chilappagari, B. Vasic, M. Stepanov, and M. Chertkov
Analysis of error floors of LDPC codes under LP decoding over the BSC [ieeexplore]
Proc. IEEE Int. Symp. Information Theory, Seoul, Korea, pp. 379-383, June 28-July 3, 2009.

S. Arora, C. Daskalakis, and D. Steurer
Message passing algorithms and improved LP decoding [acm]
Proc. 41st Annual ACM Symposium on Theory of Computing (STOC), Bethesda, MD, USA, May 31 - June 2, 2009.

M.F. Flanagan
A unified framework for linear-programming based communication receivers [arxiv]
submitted, Feb. 2009.

2008

M.H. Taghavi, A. Shokrollahi, and P.H. Siegel
Efficient implementation of linear programming decoding [arxiv]
submitted to IEEE Transactions on Information Theory, Dec. 2008.

M.-H. Taghavi N. and P.H. Siegel
Adaptive methods for linear programming decoding [ieeexplore]
IEEE Trans. Inform. Theory, vol. 54, no. 12, pp. 5396-5410, Dec. 2008.

A. Tanatmis, S. Ruzika, H.W. Hamacher, M. Punekar, F. Kienle, and N. Wehn
A separation algorithm for improved LP-decoding of linear block codes [arxiv]
submitted to IEEE Transactions on Information Theory, Dec. 2008.

M. Lunglmayr, J. Berkmann, and M. Huemer
LP decoding of LDPC codes in HARQ systems [ieeexplore]
Proc. 6th International Symposium on Communication Systems, Networks, and Digital Signal Processing, pp. 535-539, July 25, 2008.

A. Cohen, F. Alajaji, N. Kashyap, and G. Takahara,
LP Decoding for joint source-channel codes and for the non-ergodic Polya channel [ieeexplore]
IEEE Comm. Letters, vol. 12, no. 9, pp. 678-680, Sept. 2008.

M. F. Flanagan
Linear-Programming Receivers [arxiv]
Proc. 46th Annual Allerton Conference on Communication, Control and Computing, Monticello, Illinois, September 23-26, 2008.

M. Miwa, T. Wadayama, I. Takumi
A cutting plane method based on redundant rows for improving fractional distance [ieeexplore]
Proc. 5th International Symposium on Turbo Codes and Related Topics, Lausanne, Switzerland, pp. 43-48, Sept. 1-5, 2008.

A. Tanatmis, S. Ruzika, H.W. Hamacher, M. Punekar, F. Kienle, and N. Wehn
A separation algorithm for improved LP-decoding of linear block codes [ieeexplore]
Proc. 5th International Symposium on Turbo Codes and Related Topics, Lausanne, Switzerland, pp. 37-42, Sept. 1-5, 2008.

T. Wadayama
Interior point decoding for linear vector channels based on convex optimization [ieeexplore]
Proc. IEEE Intern. Symp. Inform. Theory, Toronto, Canada, pp. 1493-1497, July 6-11, 2008.

D. Burshtein
Linear complexity approximate LP decoding of LDPC codes: Generalizations and improvements [ieeexplore]
Proc. 5th International Symposium on Turbo Codes and Related Topics, Lausanne, Switzerland, pp. 31-36, Sept. 1-5, 2008.

S.K. Chilappagari, M. Chertkov, and B. Vasic
Provably efficient instanton search algorithm for LP decoding of LDPC codes over the BSC [arxiv]
submitted to IEEE Transactions on Information Theory, Aug. 2008.

C. Daskalakis, A.G. Dimakis, R.M. Karp, and M.J. Wainwright
Probabilistic analysis of linear programming decoding [ieeexplore]
IEEE Trans. Inform. Theory, vol. 54, no. 8, pp. 3565-3578, Aug. 2008.

N. Kashyap
A decomposition theory for binary linear codes [ieeexplore]
IEEE Trans. Inform. Theory, vol. IT-54, no. 7, pp. 3035-3058, July 2008.

V. Skachek, M.F. Flanagan, E. Byrne, and M. Greferath
Polytope representations for linear-programming decoding of non-binary linear codes [ieeexplore]
Proc. IEEE Intern. Symp. Inform. Theory, Toronto, Canada, pp. 1508-1512, July 6-11, 2008.

M.F. Flanagan
Codeword-independent performance of nonbinary linear codes under linear-programming and sum-product decoding [arxiv]
Proc. IEEE International Symposium on Information Theory (ISIT 2008), Toronto, Canada, July 6-11, 2008.

D. Burshtein
Iterative approximate linear programming decoding of LDPC codes with linear complexity [ieeexplore]
Proc. IEEE Intern. Symp. Inform. Theory, Toronto, Canada, pp. 1498-1502, July 6-11, 2008.

P.O. Vontobel
Interior-point algorithms for linear-programming decoding [arxiv]
Proc. Information Theory and its Applications Workshop, UC San Diego, La Jolla, CA, USA, Jan./Feb., 2008.

M.F. Flanagan, V. Skachek, E. Byrne, and M. Greferath
Linear-programming decoding of non-binary linear codes [arxiv]
Proc. 7-th International ITG Conference on Source and Channel Coding (SCC'08), Ulm, Germany, Jan. 2008.

2007

K. Yang, X. Wang, and J. Feldman
Fast ML decoding of SPC product code by linear programming decoding [ieeexplore]
Proc. IEEE GLOBECOM, Washington, DC, USA, pp. 1577-1581, Nov. 2007.

S.C. Draper, J.S. Yedidia, and Y. Wang
ML decoding via mixed-integer adaptive linear programming [MERL]
Proc. IEEE Intern. Symp. on Inform. Theory, June 2007.

T. Wadayama
Interior point decoding for linear vector channels [arxiv]
submitted, May 2007.

J. Feldman, T. Malkin, R.A. Servedio, C. Stein, and M.J. Wainwright
LP decoding corrects a constant fraction of errors [ieeexplore]
IEEE Trans. Inform. Theory, vol. 53, no. 1, pp. 82-89, Jan. 2007.

2006

M. Chertkov and V.Y. Chernyak
Loop calculus helps to improve belief propagation and linear programming decodings of low-density-parity-check codes [arxiv]
Proc. 44th Annual Allerton Conf. on Communications, Control and Computing, Monticello, IL, USA, Sep. 27-29, 2006.

K. Yang, J. Feldman, X. Wang
Nonlinear programming approaches to decoding low-density parity-check codes [ieeexplore]
IEEE J. Sel. Areas in Comm., vol. 24, no. 8, pp. 1603-1613, Aug. 2006.

A.G. Dimakis and M.J. Wainwright
Guessing facets: polytope structure and improved LP decoder [ieeexplore]
Proc. IEEE Intern. Symp. on Inform. Theory, Seattle, WA, pp. 1369-1373, July 2006.

P.O. Vontobel and R. Koetter
Towards low-complexity linear-programming decoding [arxiv]
Proc. 4th Intern. Conf. on Turbo Codes and Related Topics, Munich, Germany, Apr. 3-7, 2006.

P.O. Vontobel and R. Koetter
Bounds on the threshold of linear programming decoding [arxiv]
Proc. IEEE Inform. Theory Workshop, Punta Del Este, Uruguay, Mar. 13-16, 2006.

R. Koetter and P.O. Vontobel
On the block error probability of LP decoding of LDPC codes [arxiv]
Proc. Inaugural Workshop of the Center for Information Theory and its Applications, UCSD, La Jolla, CA, USA, Feb. 6-10, 2006.

M. Chertkov and M.G. Stepanov,
Looping linear programming decoding of LDPC codes [arxiv]
submitted to IEEE Trans. on Inform. Theory, Jan. 2006.

M.H. Taghavi N. and P.H. Siegel
Adaptive linear programming decoding [arxiv]
Proc. IEEE Intern. Symp. on Inform. Theory 2006, Seattle, WA, USA, July 9 - 14, 2006.

2005

J. Feldman, R. Koetter, and P.O. Vontobel
The benefit of thresholding in LP decoding of LDPC codes [arxiv]
Proc. IEEE Intern. Symp. on Inform. Theory 2005, Adelaide, Australia, pp. 307-311, Sept. 4-9, 2005.

J. Feldman, M.J. Wainwright, and D.R. Karger
Using linear programming to decode binary linear codes [ieeexplore]
IEEE Trans. on Inform. Theory, vol. IT-51, no. 3, pp. 954-972, Mar. 2005.

J. Feldman and C. Stein
LP decoding achieves capacity [acm]
Symposium on Discrete Algorithms (SODA '05), Vancouver, Canada, Jan. 23-25, 2005.

N. Halabi and G. Even
Improved bounds on the word error probability of RA(2) codes with linear-programming-based decoding [ieeexplore]
IEEE Trans. on Inform. Theory, vol. IT-51, no. 1, pp. 265-280, Jan. 2005.

2004

P.O. Vontobel and R. Koetter
On the relationship between linear programming decoding and min-sum algorithm decoding [.pdf]
Proc. ISITA 2004, Parma, Italy, p. 991-996, October 10-13, 2004.
(A typo on page 1 has been corrected: "max-sum" -> "min-sum".)

J. Feldman, T. Malkin, C. Stein, R.A. Servedio, and M.J. Wainwright
LP decoding corrects a constant fraction of errors [.pdf]
Proc. IEEE Intern. Symp. on Inform. Theory, Chicago, IL, USA, p. 68, June 27-July 2, 2004.

J. Feldman and D.R. Karger
Decoding turbo-like codes via linear programming [ScienceDirect]
Journal of Computer and System Sciences (FOCS '02 Special Issue), vol. 68, no. 4, pp. 733-752, June 2004.

2003

J. Feldman, D.R. Karger, and M.J. Wainwright
LP decoding [.pdf]
Proc. 41st Allerton Conf. on Communications, Control, and Computing, Monticello, IL, USA, October 1-3, 2003.

J. Feldman
Decoding Error-Correcting Codes via Linear Programming [.pdf]
PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, 2003.

J. Feldman, D.R. Karger, and M.J. Wainwright
Using linear programming to decode linear codes [.pdf]
Proc. 37th annual Conference on Information Sciences and Systems (CISS '03), Baltimore, MD, USA, Mar. 12-14, 2003.

M.J. Wainwright and M.I. Jordan
Variational inference in graphical models: the view from the marginal polytope [.ps]
Proc. 41st Allerton Conf. on Communications, Control, and Computing, Monticello, IL, USA, Oct. 1-3, 2003.

2002

J. Feldman and D.R. Karger
Decoding turbo-like codes via linear programming [ieeexplore]
Proc. 43rd Annual IEEE Symp. Found. of Comp. Sci., pp. 251-260, Nov. 16-19, 2002

J. Feldman, D.R. Karger, and M.J. Wainwright
Linear programming-based decoding of turbo-like codes and its relation to iterative approaches [.pdf]
Proc. 40th Allerton Conf. on Communications, Control, and Computing, Monticello, IL, USA, October 2-4, 2002.

Last Modified: Tuesday, 15-Sep-2009 02:33:10 PDT