Guy Even, Jon Feldman, Guy Kortsarz, Zeev Nutov
the edge-connectivity of a graph from 1 to 2 using a subset of a given edge set
Sponsored Search Auctions with Markovian Users (2009)
Gagan Aggarwal, Jon Feldman, S. Muthukrishnan, Martin Pál
Abstract. Sponsored search involves running an auction among advertisers who bid in order to have their ad shown next to search results for specific keywords. The most popular auction for sponsored...
Using many machines to handle an enormous error-correcting code (2009)
Abstract — We investigate the problem of using many machines to represent, encode and decode an error-correcting code with an extremely large block length. Standard algorithms for encoding and...
Abstract We study the problem of using a multicast network code to transmit information securely in the pres-ence of a "wire-tap " adversary who can eavesdrop on a bounded number of network...
1 A Noise-Adaptive Algorithm for First-Order Reed-Muller Decoding (2009)
Jon Feldman, Ibrahim Abou-faycal, Matteo Frigo
Abstract — We consider the problem of decoding First-Order Reed-Muller codes efficiently. We give an algorithm that implicitly adapts to the noise conditions, runs significantly faster than known...
Secure Network Coding via Filtered Secret Sharing ∗ (2009)
Jon Feldman, Tal Malkin, Rocco A. Servedio, Cliff Stein
We study the problem of using a multicast network code to transmit information securely in the presence of a “wire-tap ” adversary who can eavesdrop on a bounded number of network edges. We...
Online Stochastic Matching: Beating 1-1/e (2009)
Feldman, Jon, Mehta, Aranyak, Mirrokni, Vahab, Muthukrishnan, S.
We study the online stochastic bipartite matching problem, in a form motivated by display ad allocation on the Internet. In the online, but adversarial case, the celebrated result of Karp, Vazirani...
Jon Feldman, Martin Wainwright, David R. Karger
In recent work (Feldman and Karger [8]), we introduced a new approach to decoding turbo-like codes based on linear programming (LP). We gave a precise characterization of the noise patterns that...
Jon Feldman, Cliff Stein, Tal Malkin, Rocco A. Servedio, Martin J. Wainwright
We show that for low-density parity-check (LDPC) codes with sufficient expansion, the
On the Capacity of Secure Network Coding (2008)
Jon Feldman, Tal Malkin, Rocco A. Servedio, Cliff Stein
We consider the problem of using a multicast network code to transmit information securely in the presence of a "wire-tap " adversary who can eavesdrop on a bounded number of...
PAC Learning Mixtures of Axis-Aligned Gaussians with No Separation Assumption (2008)
Jon Feldman, Rocco A. Servedio
Abstract. We propose and analyze a new vantage point for the learning of mixtures of Gaussians: namely, the PAC-style model of learning probability distributions introduced by Kearns et al. [12]....
On Distributing Symmetric Streaming Computations (2008)
Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Cliff Stein
A common approach for dealing with large data sets is to stream over the input in one pass, and perform computations using sublinear resources. For truly massive data sets, however, even making a...
A Truthful Mechanism for Offline Ad Slot Scheduling (2008)
Jon Feldman, S. Muthukrishnan, Evdokia Nikolova
Abstract. We consider the Offline Ad Slot Scheduling problem, where advertisers must be scheduled to sponsored search slots during a given period of time. Advertisers specify a budget constraint, as...
Abstract We study the problem of using a multicast network code to transmit information securely in the pres-ence of a "wire-tap " adversary who can eavesdrop on a bounded number of...
A Fast Maximum-Likelihood Decoder for Convolutional Codes (2008)
Jon Feldman, Ibrahim Abou-faycal, Matteo Frigo
Abstract—The lazy Viterbi decoder is a maximum-likelihood decoder for block and stream convolutional codes. For many codes of practical interest, under reasonable noise conditions, the lazy decoder...
PAC Learning Mixtures of Axis-Aligned Gaussians with No Separation Assumption (2008)
Jon Feldman, Rocco A. Servedio
Abstract. We propose and analyze a new vantage point for the learning of mixtures of Gaussians: namely, the PAC-style model of learning probability distributions introduced by Kearns et al. [12]....
ABSTRACT Growth Codes: Maximizing Sensor Network Data Persistence ∗ (2008)
Sensor networks are especially useful in catastrophic or emergency scenarios such as floods, fires, terrorist attacks or earthquakes where human participation may be too dangerous. However, such...
A Truthful Mechanism for Offline Ad Slot Scheduling (2008)
Jon Feldman, S. Muthukrishnan, Evdokia Nikolova, Martin Pál
Abstract. We consider the Offline Ad Slot Scheduling problem, where advertisers must be scheduled to sponsored search slots during a given period of time. Advertisers specify a budget constraint, as...
On Distributing Symmetric Streaming Computations (2008)
Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Cliff Stein
A common approach for dealing with large data sets is to stream over the input in one pass, and perform computations using sublinear resources. For truly massive data sets, however, even making a...
Algorithmic Methods for Sponsored Search Advertising (2008)
Feldman, Jon, Muthukrishnan, S.
Modern commercial Internet search engines display advertisements along side the search results in response to user queries. Such sponsored search relies on market mechanisms to elicit prices for...
Online Ad Slotting With Cancellations (2008)
Constantin, Florin, Feldman, Jon, Muthukrishnan, S., Pal, Martin
Many advertisers buy advertisements (ads) on the Internet or on traditional media and seek simple, online mechanisms to reserve ad slots in advance. Media publishers represent a vast and varying...
Sponsored Search Auctions with Markovian Users (2008)
Aggarwal, Gagan, Feldman, Jon, Muthukrishnan, S., Pal, Martin
Sponsored search involves running an auction among advertisers who bid in order to have their ad shown next to search results for specific keywords. Currently, the most popular auction for sponsored...
Journal of Graph Algorithms and Applications (2008)
Reuven Bar-yehuda, Guy Even, Jon Feldman, Joseph (seffi Naor
vol. 5, no. 4, pp. 1–27 (2001) Computing an optimal orientation of a balanced decomposition tree for linear arrangement problems
Jon Feldman, Rocco A. Servedio
We consider the problem of learning mixtures of product distributions over discrete domains in the distribution learning framework introduced by Kearns et al. [18]. We give a poly(n/ɛ) time...
ABSTRACT Growth Codes: Maximizing Sensor Network Data Persistence ∗ (2008)
Sensor networks are especially useful in catastrophic or emergency scenarios such as floods, fires, terrorist attacks or earthquakes where human participation may be too dangerous. However, such...
Bidding to the Top: VCG and Equilibria of (2008)
Position-based Auctions, Gagan Aggarwal, Jon Feldman, S. Muthukrishnan
Abstract. Many popular search engines run an auction to determine the placement of advertisements next to search results. Current auctions at Google and Yahoo! let advertisers specify a single amount...
Abstract LP Decoding Achieves Capacity (2008)
We give a linear programming (LP) decoder that achieves the capacity (optimal rate) of a wide range of probabilistic binary communication channels. This is the first such result for LP decoding. More...
Abstract Parallel Processor Scheduling with Delay Constraints (2008)
Daniel W. Engels, Jon Feldman, David R. Karger, Matthias Ruhl
We consider the problem of scheduling unit-length jobs on identical parallel machines such that the makespan of the resulting schedule is minimized. Precedence constraints impose a partial order on...
• High Honors given for undergraduate thesis work. • Received academic citations for course work in Algorithms, Digital Engineering. • Cum Laude with overall GPA 3.6/4.0. • Computer Science...
A Truthful Mechanism for Offline Ad Slot Scheduling (2008)
Feldman, Jon, Muthukrishnan, S., Nikolova, Evdokia, Pal, Martin
We consider the "Offline Ad Slot Scheduling" problem, where advertisers must be scheduled to "sponsored search" slots during a given period of time. Advertisers specify a budget constraint, as well...
1 A Fast Maximum-Likelihood Decoder for Convolutional Codes (2007)
Jon Feldman, Ibrahim Abou-faycal, Matteo Frigo
Abstract---The lazy Viterbi decoder is a maximum-likelihood decoder for block and stream convolutional codes. For many codes of practical interest, under reasonable noise conditions, the lazy decoder...
Reuven Bar-yehuda, Guy Even, Jon Feldman, Joseph (se# Naor
vol. 5, no. 4, pp. 1--27 (2001) Computing an optimal orientation of a balanced decomposition tree for linear arrangement problems
Reuven Bar-yehuda, Guy Even, Jon Feldman, Joseph (se Naor
vol. x, no. x, pp. x{x (xxxx) Computing an optimal orientation of a balanced decomposition tree for linear arrangement problems
Abstract We consider the DIRECTED STEINER NETWORK problem, (2007)
also called the POINT-TO-POINT CONNECTION problem, where given a directed graph G and p pairs f(s 1; t 1); : : : ; (s p; t p)g of nodes in the graph, one has to find the smallest subgraph H of G that...
Guy Even, Jon Feldman, Guy Kortsarz, Zeev Nutov
A 3=2-approximation algorithm for augmenting the edge-connectivity of a graph from 1 to 2 using a subset of a given edge set (extended abstract)
Budget Optimization in Search-Based Advertising Auctions (2006)
Feldman, Jon, Muthukrishnan, S., Pal, Martin, Stein, Cliff
Internet search companies sell advertisement slots based on users' search queries via an auction. While there has been a lot of attention on the auction process and its game-theoretic aspects, our...
On the Complexity of Processing Massive, Unordered, Distributed Data (2006)
Feldman, Jon, Muthukrishnan, S., Sidiropoulos, Anastasios, Stein, Cliff, Svitkina, Zoya
An existing approach for dealing with massive data sets is to stream over the input in few passes and perform computations with sublinear resources. This method does not work for truly massive data...
PAC Learning Mixtures of Axis-Aligned Gaussians with No Separation Assumption (2006)
Feldman, Jon, O'Donnell, Ryan, Servedio, Rocco A.
We propose and analyze a new vantage point for the learning of mixtures of Gaussians: namely, the PAC-style model of learning probability distributions introduced by Kearns et al. Here the task is to...
Bidding to the Top: VCG and Equilibria of Position-Based Auctions (2006)
Aggarwal, Gagan, Muthukrishnan, S., Feldman, Jon
Many popular search engines run an auction to determine the placement of advertisements next to search results. Current auctions at Google and Yahoo! let advertisers specify a single amount as their...
Monte Carlo Modeling for Gamma Rays Bursts Detection Monitoring Algorithms (2006)
Itzhak Orion, Jon Feldman, Yehuda Drorri
In this study an efficiency comparison was made for three different monitoring algorithms in order to simulate the response of rotating monitoring systems. Burst-events counting on a spherical...
Monte Carlo Modeling for Gamma Rays Bursts Detection Monitoring Algorithms (2006)
Itzhak Orion, Jon Feldman, Yehuda Drorri
In this study an efficiency comparison was made for three different monitoring algorithms in order to simulate the response of rotating monitoring systems. Burst-events counting on a spherical...
PAC learning mixtures of Gaussians with no separation assumption (2006)
Jon Feldman, Rocco A. Servedio
Abstract. We propose and analyze a new vantage point for the learning of mixtures of Gaussians: namely, the PAC-style model of learning probability distributions introduced by Kearns et al. [12]....
On the complexity of processing massive, unordered, distributed data (2006)
Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Cliff Stein, Zoya Svitkina
The popular model for processing massive data sets is the streaming model in which the processor makes a pass over the input with polylog(n)-space. However, with current data sets, even making a...
A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2. ∗ (2006)
Guy Even, Jon Feldman, Guy Kortsarz, Zeev Nutov
We present a 1.8-approximation algorithm for the following NP-hard problem: given a connected graph G = (V, E) and an additional edge set E, find a minimum size subset of edges F ⊆ E such that (V,...
Data Persistence for Zero-Configuration Sensor Networks (2006)
Abhinav Kamra, Jon Feldman, Vishal Misra, Dan Rubenstein
Sensor networks are especially useful in catastrophic or emergency scenarios such as floods, fires, terrorist attacks or earthquakes where human participation may be too dangerous. However, such...
PAC learning mixtures of Gaussians with no separation assumption (2006)
Jon Feldman, Rocco A. Servedio
Abstract. We propose and analyze a new vantage point for the learning of mixtures of Gaussians: namely, the PAC-style model of learning probability distributions introduced by Kearns et al. [12]....
The Benefit of Thresholding in LP Decoding of LDPC Codes (2005)
Feldman, Jon, Koetter, Ralf, Vontobel, Pascal O.
Consider data transmission over a binary-input additive white Gaussian noise channel using a binary low-density parity-check code. We ask the following question: Given a decoder that takes...
Learning mixtures of product distributions over discrete domains (2005)
Feldman, Jon, O'Donnell, Ryan, Servedio, Rocco A.
We consider the problem of learning mixtures of product distributions over discrete domains in the distribution learning framework introduced by Kearns et al. We give a $\poly(n/\eps)$ time algorithm...
Using linear programming to decode binary linear codes (2005)
Jon Feldman, Martin J. Wainwright, David R. Karger, Associate Member
Abstract—A new method is given for performing approximate maximum-likelihood (ML) decoding of an arbitrary binary linear code based on observations received from any discrete memoryless symmetric...
LP decoding achieves capacity (2005)
We give a linear programming (LP) decoder that achieves the capacity (optimal rate) of a wide range of probabilistic binary communication channels. This is the first such result for LP decoding. More...
Abhinav Kamra, Jon Feldman, Vishal Misra, Dan Rubenstein
Sensors networks are capable of collecting an enormous amount of data over space and time. Often, the ultimate objective is to “sample, store and forward”, that is to sense the data, store it...
LP decoding corrects a constant fraction of errors (2004)
Jon Feldman, Tal Malkin, Rocco A. Servedio, Cli Stein, Martin J. Wainwright
We show that for low-density parity-check (LDPC) codes with sucient expansion, the Linear Programming (LP) Decoder of Feldman, Karger and Wainwright (Allerton, 2003) can correct a constant fraction...
LP Decoding Achieves Capacity (2004)
We give a linear programming (LP) decoder that achieves the capacity (optimal rate) of a wide range of probabilistic binary communication channels. This is the first such result for LP decoding. More...
LP decoding corrects a constant fraction of errors (2004)
Jon Feldman, Tal Malkin, Rocco A. Servedio, Cliff Stein, Martin J. Wainwright
Abstract—We show that for low-density parity-check (LDPC) codes whose Tanner graphs have sufficient expansion, the linear programming (LP) decoder of Feldman, Karger, and Wainwright can correct a...
On the capacity of secure network coding (2004)
Jon Feldman, Tal Malkin, Rocco A. Servedio, Cliff Stein
We consider the problem of using a multicast network code to transmit information securely in the presence of a “wire-tap ” adversary who can eavesdrop on a bounded number of network edges. Cai...
Using linear programming to decode linear codes (2003)
Jon Feldman, Martin Wainwright, David R. Karger
Abstract--- Given a linear code and observations from a noisy channel, the decoding problem is to determine the most likely (ML) codeword. We describe a method for approximate ML decoding of an...
Jon Feldman, Martin J. Wainwright, David R. Kargerý
Abstract. Linear programming (LP) relaxation is a common technique used to find good solutions to complex optimization problems. We present the method of “LP decoding”: applying LP relaxation to...
Using linear programming to decode linear codes (2003)
Abstract — Given a linear code and observations from a noisy channel, the decoding problem is to determine the most likely (ML) codeword. We describe a method for approximate ML decoding of an...
Jon Feldman, Martin J. Wainwright, David R. Karger
Abstract. Linear programming (LP) relaxation is a common technique used to find good solutions to complex optimization problems. We present the method of “LP decoding”: applying LP relaxation to...
Decoding Error-Correcting Codes via Linear Programming (2003)
Abstract. Error-correcting codes are fundamental tools used to transmit digital information over unreliable channels. Their study goes back to the work of Hamming [Ham50] and Shannon [Sha48], who...
Jon Feldman, David R. Karger, Martin Wainwright
In recent work (Feldman and Karger [8]), we introduced a new approach to decoding turbo-like codes based on linear programming (LP). We gave a precise characterization of the noise patterns that...
Decoding turbo-like codes via linear programming (2002)
We introduce a novel algorithm for decoding turbo-like codes based on linear programming. We prove that for the case of Repeat-Accumulate (RA) codes, under the binary symmetric channel with a certain...
Parallel processor scheduling with delay constraints (2001)
Daniel W. Engels, Jon Feldman, David R. Karger, Matthias Ruhl
We consider the problem of scheduling unit-length jobs on identical parallel machines such that the makespan of the resulting schedule is minimized. Precedence constraints impose a partial order on...
Parallel processor scheduling with delay constraints (2001)
Daniel W. Engels, Jon Feldman, David R. Karger, Matthias Ruhl
We consider the problem of scheduling unit-length jobs on identical parallel machines such that the makespan of the resulting schedule is minimized. Precedence constraints impose a partial order on...
The directed steiner network problem is tractable for a constant number of terminals (1999)
David R. Karger, Jon Feldman, Jon Feldman
at the
The Directed Steiner Network problem is tractable for a constant number of terminals (1999)
We consider the DIRECTED STEINER NETWORK problem, also called the POINT-TO-POINT CONNECTION problem, where given a directed graph G and p pairs f(s 1 ; t 1 ); : : : ; (s p ; t p )g of nodes in the...
The directed steiner network problem is tractable for a constant number of terminals (1999)
We consider the DIRECTED STEINER NETWORK problem, also called the POINT-TO-POINT CONNECTION problem, where given a directed graph G and p pairs s1 t1 sp tp of nodes in the graph, one has to find the...