Jon Feldman's Publications

• Conference/Workshop Papers
• Journal Papers
• Theses
• Technical Reports and Manuscripts

Conference/Workshop Papers, Submissions

• Yield Optimization of Display Advertising with Ad Exchange
  Santiago Balseiro, Jon Feldman, Vahab Mirrokni, S. Muthukrishnan
  Submitted to: , February 2011.
  See Tech Report on arXiv
  
  
• Online Stochastic Packing Applied to Display Ad Allocation
  Jon Feldman, Monika Henzinger, Nitish Korula, Vahab Mirrokni, Cliff Stein
  In: Sixth Workshop on Ad Auctions (July 2010), European Symposium on Algorithms (ESA), September 2010.
  See Tech Report on arXiv
  
  
• Auctions with Intermediaries
  Jon Feldman, Vahab Mirrokni, S. Muthukrishnan, Mallesh Pai
  In: ACM Conference on Electronic Commerce (EC), 2010, June 2010.
  
  
• Online Ad Assignment with Free Disposal
  Jon Feldman, Nitish Korula, Vahab Mirrokni, S. Muthukrishnan, Martin Pál
  In: Workshop on Internet and Network Economics (WINE), 2009, December 2009.
  
  
• Online Stochastic Matching: Beating 1 - 1/e
  Jon Feldman, Aranyak Mehta, Vahab Mirrokni, S. Muthukrishnan
  In: Proc. IEEE Symposium on Foundations of Computer Science (FOCS). Also in Fifth Workshop on Ad Auctions (2009)., October 2009.
  See Tech Report on arXiv
  
  
• Online Ad Slotting with Cancellations
  Florin Constantin, Jon Feldman, S. Muthukrishnan, Martin Pál
  In: Fourth Workshop on Ad Auctions (July 2008), Symposium on Discrete Algorithms (SODA), January 2009.
  See Tech Report on arXiv
  
  
• Sponsored Search Auctions with Markovian Users
  Gagan Aggarwal, Jon Feldman, S. Muthukrishnan, Martin Pál
  In: Fourth Workshop on Ad Auctions (July 2008), Workshop on Internet and Network Economics (WINE), December 2008.
  See Tech Report on arXiv
  
  
• Position Auctions with Bidder-Specific Minimum Prices
  Eyal Even-Dar, Jon Feldman, Yishay Mansour, S. Muthukrishnan
  In: Fourth Workshop on Ad Auctions (July 2008), Workshop on Internet and Network Economics (WINE), December 2008.
  [workshop papers]
  [slides]
  
  
• Algorithmic Methods for Sponsored Search Advertising
  Jon Feldman, S. Muthukrishnan
  In: International Conference on Measurement and Modeling of Computer Systems (ACM SIGMETRICS), June 2008.
  See Tech Report on arXiv
  
  
• A Truthful Mechanism for Offline Ad Slot Scheduling
  Jon Feldman, S. Muthukrishnan, Evdokia Nikolova, Martin Pál
  In: 2008 Symposium on Algorithmic Game Theory (SAGT), May 2008.
  See Tech Report on arXiv
  Download Slides
  
  
• On Distributing Symmetric Streaming Computations
  Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Cliff Stein, Zoya Svitkina
  In: 2008 ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2008.
  See Tech Report on arXiv
  
  
• Budget Optimization in Search-Based Advertising Auctions
  Jon Feldman, S. Muthukrishnan, Martin Pál, Cliff Stein
  In: ACM Conference on Electronic Commerce (EC), June 2007.
  See Tech Report on arXiv
  
  
• Bidding to the Top: VCG and Equilibria of Position-Based Auctions
  Gagan Aggarwal, Jon Feldman, S. Muthukrishnan
  In: Workshop on Approximation and Online Algorithms (WAOA), 2006, June 2006.
  See Tech Report on arXiv
  
  
• Growth Codes: Maximizing Sensor Network Data Persistence
  Abhinav Kamra, Vishal Misra, Dan Rubinstein, Jon Feldman
  In: Proc. Special Interest Group on Data Communication (SIGCOMM), September 2006.
  
  
• PAC Learning Mixtures of Gaussians with No Separation Assumption
  Jon Feldman, Ryan O'Donnell, Rocco A. Servedio
  In: Proc. 19th Annual Conference on Learning Theory (COLT), June 2006.
  
  
• Using Many Machines to Handle an Enormous Error-Correcting Code
  Jon Feldman
  In: Proc. IEEE Information Theory Workshop (ITW), March 2006.
  Download: [PS] [PDF]
  
  
• Learning Mixtures of Product Distributions over Discrete Domains
  Jon Feldman, Ryan O'Donnell, Rocco A. Servedio
  In: Proc. IEEE Symposium on Foundations of Computer Science (FOCS), October 2005.
  CU Tech Report: (ps) (pdf)
  
  
• Local Decoding of Walsh Codes to Reduce CDMA Despreading Computation
  Albert Chan, Jon Feldman, Raghu Madyastha, Piotr Indyk, David R. Karger
  In: Software Defined Radio Technical Conference, November 2005.
  
  
• Towards Optimal Encoding for Data Recovery in Sensor Network Failures
  Abhinav Kamra, Vishal Misra, Dan Rubinstein, Jon Feldman
  In: Proc. 43rd Annual Allerton Conference on Communication, Control, and Computing, September 2005.
  
  
• Non-Linear Approaches to Decoding Low-Density Parity-Check Codes
  Kai Yang, Jon Feldman, Xiaodong Wang
  In: Proc. 43rd Annual Allerton Conference on Communication, Control, and Computing, September 2005.
  
  
• The Benefit of Thresholding in LP Decoding of LDPC Codes
  Jon Feldman, Ralf Koetter, Pascal Vontobel
  In: IEEE International Symposium on Information Theory, September 2005.
  See Tech Report on arXiv
  
  
• Secure Network Coding via Filtered Secret Sharing
  Jon Feldman, Tal Malkin, Cliff Stein, Rocco A. Servedio
  Manuscript.
  November 2004
  Download: [PS] [PDF]
  Download Slides: [PS] [PDF]
  
  
• On the Capacity of Secure Network Coding
  Jon Feldman, Tal Malkin, Cliff Stein, Rocco A. Servedio
  In: Proc. 42nd Annual Allerton Conference on Communication, Control, and Computing, September 2004.
  Download: [PS] [PDF]
  Download Slides: [PS] [PDF]
  
  
• LP Decoding Achieves Capacity
  Jon Feldman, Cliff Stein
  In: 2005 ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2005.
  Download: [PS] [PDF]
  Download Slides: [PS] [PDF]
  (see tech report below)
  
  
• LP Decoding Corrects a Constant Fraction of Errors
  Jon Feldman, Tal Malkin, Cliff Stein, Rocco A. Servedio, Martin J. Wainwright
  In: Proc. IEEE International Symposium on Information Theory (ISIT), June 2004.
  Download: [PS] [PDF]
  Download Slides: [PS] [PDF]
  (see tech report below)
  
  
• LP Decoding
  Jon Feldman, David R. Karger, Martin J. Wainwright
  In: Proc. 41st Annual Allerton Conference on Communication, Control, and Computing, October 2003.
  Download: [PS] [PDF]
  Download Slides: [PS] [PDF]
  
  
• Using Linear Programming to Decode Linear Codes
  Jon Feldman, David R. Karger, Martin J. Wainwright
  In: Proc. 37th annual Conference on Information Sciences and Systems (CISS '03), Baltimore, MD, March 2003.
  Download: [PS] [PDF]
  Download Slides: [PS] [PDF]
  
  
• Linear Programming-Based Decoding of Turbo-Like Codes and its Relation to Iterative Approaches
  Jon Feldman, David R. Karger, Martin J. Wainwright
  In: Proc. 40th Annual Allerton Conference on Communication, Control, and Computing, October 2002.
  Download: [PS] [PDF]
  Download Slides: [PS] [PDF]
  
  
• Decoding Turbo-Like Codes via Linear Programming
  Jon Feldman, David R. Karger
  In: Proc. IEEE Symposium on Foundations of Computer Science (FOCS), November 2002.
  Download: [PS] [PDF]
  Download Slides: [PS] [PDF]
  
  
• A Fast Maximum-Likelihood Decoder for Convolutional Codes
  Jon Feldman, Matteo Frigo, Ibrahim Abou-Faycal
  In: Proc. IEEE Vehicular Technology Conference (VTC), September 2002.
  Download: [PS] [PDF]
  Download Slides: [PS] [PDF]
  
  
• A Noise-Adaptive Algorithm for First-Order Reed-Muller Decoding
  Jon Feldman, Matteo Frigo, Ibrahim Abou-Faycal
  In: Proc. IEEE Vehicular Technology Conference (VTC), September 2002.
  Download: [PS] [PDF]
  Download Slides: [PS] [PDF]
  
  
• A 3/2-approximation algorithm for augmenting the connectivity of a graph from 1 to 2 using edges from a given set
  Guy Even, Jon Feldman, Guy Kortsarz, Zeev Nutov
  In: 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX '01), Berkeley, CA, August 2001.
  Download: [PS] [PDF]
  
  
• Parallel Processor Scheduling With Delay Constraints
  Daniel W. Engles, Jon Feldman, David R. Karger, Matthias Ruhl
  In: Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2001.
  Download: [PS] [PDF]
  
  
• The Directed Steiner Network problem is tractable for a constant number of terminals
  Jon Feldman, Matthias Ruhl
  In: Proc. IEEE Symposium on Foundations of Computer Science (FOCS), October 1999.
  Download: [PS] [PDF]
  
  

Journal Papers

• Learning Mixtures of Product Distributions over Discrete Domains
  Jon Feldman, Ryan O'Donnell, Rocco A. Servedio
  SIAM J. on Computing, 37(5), February 2008.
  Link to paper
  
• Nonlinear Programming Approaches to Decoding Low-Density Parity-Check Codes
  Kai Yang, Jon Feldman, Xiaodong Wang
  IEEE Journal on Selected Areas In Communications, 24(8), August 2006.
  
  
• LP Decoding Corrects a Constant Fraction of Errors
  Jon Feldman, Tal Malkin, Cliff Stein, Rocco A. Servedio, Martin J. Wainwright
  IEEE Transactions on Information Theory, 53(1), January 2007.
  Link to paper on IEEE Xplore
  
  
• Using Linear Programming to Decode Binary Linear Codes
  Jon Feldman, Martin J. Wainwright, David R. Karger
  IEEE Transactions on Information Theory, 51(3), pp. 954--972 , March 2005.
  Link to paper on IEEE Xplore
  
  
• Decoding Turbo-Like Codes via Linear Programming
  Jon Feldman, David R. Karger
  Journal of Computer and System Sciences (FOCS '02 Special Issue), 68(4), June 2004.
  Link to Journal
  
  
• Computing an optimal orientation of a balanced decomposition tree for linear arrangement problems
  Reuven Bar-Yehuda, Guy Even, Jon Feldman, Seffi Naor
  Journal of Graph Algorithms and Applications, 5(4), pp. 1--27 , June 2001.
  Download
  Project Website
  
  
• A 3/2-approximation algorithm for augmenting the connectivity of a graph from 1 to 2 using edges from a given set
  Guy Even, Jon Feldman, Guy Kortsarz, Zeev Nutov
  Submitted to: SIAM J. on Computing, February 2004.
  
  
• The Directed Steiner Network problem is tractable for a constant number of terminals
  Jon Feldman, Matthias Ruhl
  SIAM J. on Computing, 36(2), August 2006.
  
  

Theses

• Decoding Error-Correcting Codes via Linear Programming
  Jon Feldman
  Ph.D. thesis. Massachusetts Institute of Technology.
  September 2003
  Advisor: David R. Karger
  Download: [PS] [PDF]
  Download Slides: [PS] [PDF]
  
  
• The Directed Steiner Network problem is tractable for a constant number of terminals
  Jon Feldman
  Masters thesis. Massachusetts Institute of Technology.
  June 2000
  Advisor: David R. Karger
  Download: [PS] [PDF]
  
  
• The Complexity of Clerkship Scheduling
  Jon Feldman
  Undergraduate thesis. Dartmouth College.
  June 1997
  Advisor: Cliff Stein
  Download: [PS] [PDF]
  Dartmouth Technical Report PCS-TR97-316. Received High Honors from the department.
  

Technical Reports and Manuscripts

• LP Decoding Achieves Capacity
  Jon Feldman, Cliff Stein
  CORC Technical Report, TR-2004-04
  April 2004
  Download: [PS] [PDF]
  
  
• LP Decoding Corrects a Constant Fraction of Errors
  Jon Feldman, Tal Malkin, Cliff Stein, Rocco A. Servedio, Martin J. Wainwright
  CORC Technical Report, TR-2003-08
  October 2003
  Download: [PS] [PDF]
  
  

---

Back Home

---