For any 0< R< 1 and e> 0, we present an explicit family of error-correcting codes with rate R which can be list decoded in polynomial time up to a fraction 1-R-e. This tradeoff between the rate and fraction of errors is optimal. Finding such an explicit code meets one of the central challenges in coding theory. The previous "best" explicit codes were Reed-Solomon codes which can be list decoded up to a fraction 1-(R)^{1/2} of errors (Guruswami and Sudan [GS99]). For rates R< 1/16, the codes of Paravresh and Vardy [PV05] can correct more errors the 1-(R)^{1/2} bound.
Suppose n play each other. After all the matches are played, a natural goal is to try and rank the players with as few inconsistencies. By an inconsistency we mean a lower ranked player actually defeated a higher ranked player. An obvious strategy would be to rank the player by their number of wins (with ties being broken arbitrarily). In this work, we show that this scheme is gives a 5 approximation algorithm. Our results also hold for the case when every pair of players play each other multiple number of times. This has application in rank aggregation. Finally, we show that every ordering which respects the ordering by number of wins is a 5 approximation, that is, the tie-breaking mechanism does not matter.
We consider the following simple model for how Priceline sets airline prices. Assume Priceline wants to sell tickets for a single flight (which are assumed to have unlimited supply) over (discrete) time. Each bidder submits a triple (s; e; b) where s is the time when the bidder will arrive, e is the time when the bidder will leave and b is the maximum amount the bidder is willing to pay for a ticket (every bidder is interested in only one ticket). On each day t, Priceline sets a price p(t) and every bidder buys a ticket on the first day t (at price p(t)) such that p(t) is less than or equal to its bid value and t is between its arrival and departure time. The goal for the Priceline is to set prices so as to maximize its revenue. We also consider a related model studied by Guruswami et al. [GHK+05], where each bidder buys the ticket at the minimum price p(t_{0}) (provided it is at most b) where t_{0} is between its arrival and departure time. We study the above optimization problems in both the offline and online settings. We show that the offline algorithm can be solved exactly in polynomial time. We also give upper and lower bounds for online algorithms (both deterministic and randomized) for this problem.
In this work we study the hardness of computing (approximate) Walrasian equilibrium in single minded auctions.
The list decoding algorithm of Guruswami and Sudan [GS99] for Reed-Solomon codes also work for the more general problem of polynomial reconstruction. In this work, we show that the Guruswami-Sudan algorithm is optimal for polynomial reconstruction (as in any algorithm which perform "better" would have to run in super-polynomial time). As a corollary, we show that any list decoding algorithm for Reed-Solomon codes must utilize the fact that evaluation positions are distinct.
Tolerant locally testable codes are code with constant rate and linear distance which come equipped with a tolerant tester. A tolerant tester on receiving a purported codeword, can tell (by probing a few locations) whether the received word is close to some codeword or is far from all codewords. This differs from the standard notion of Locally testable codes (LTCs) in that they have a stronger restriction on the acceptance criterion-- testers for LTCs are only required to accept codewords. In this work we define this notion and show that some of the well known LTCs are indeed tolerant (while some of them are not).
Ben-Sasson and Sudan in [BS04] asked if the following test is robust for the tensor product of a code with another code-- pick a row (or column) at random and check if the received word restricted to the picked row (or column) belongs to the corresponding code. Valiant showed that for general linear codes, the test is not robust [V05]. However the question remained open for the tensor product of a code with itself. We resolve this question in the negative. We also show a similar result for non-linear codes.
The floodlight illumination problem asks whether there exists a one-to-one placement of n floodlights illuminating infinite wedges of angles a_{1},....,a_{n} at n locations p_{1},....,p_{n} in a plane such that a given infinite wedge W of angle T located at point q is completely illuminated by the floodlights. We prove that this problem is NP-hard, closing an open problem from CCCG 2001 [DO01]. We also discuss various approximation algorithms and special cases where the problem has a polynomial time algorithm.
Given an oracle access to a function say f checking if f is a low degree polynomial is an important problem for PCPs. This problem has a rich body of work starting with the linearity testing of Blum, Luby and Rubeinfeld [BLR93]. However, till the recent work of Alon et. al [AKKLR03] which works over GF(2), all other tests work only if the field size is greater than the degree being tested. In this work we give a tester which works for any prime field. Our works also shows that Reed-Muller codes over prime fields are locally testable. Independently, [KR04] gave a tester which works for general fields.
Winkler and Zhang introduced the FIBER MINIMIZATION problem in [WZ03]. They showed that the problem is NP-complete but left the question of approximation algorithms open. We give a simple 2-approximation algorithm for this problem based on the work of Gergov [G99]. We also show how ideas from the Dynamic Storage Allocation algorithm of Buchsbaum et al [BKKR+03] can be used to give an approximation ratio arbitrarily close to 1 provided the problem instance satisfies certain criteria. We also show that these criteria are necessary to obtain an approximation scheme. Our 2-approximation algorithm achieves its guarantee unconditionally. We generalize the problem to a ring network and give a 2+o(1)-approximation algorithm for this topology. Our techniques also yield a factor-2 approximation for the related problem of PACKING INTERVALS IN INTERVALS, also introduced by Winkler and Zhang in [WZ03].
Goldberg et al. [GHW01] began the study of incentive-compatible auctions for digital goods, that is, goods which are available in unlimited supply. Bar-Yossef et al. [BHW02] defined a model for online auction of digital goods. They show that any randomized incentive-compatible auction is $\Omega(1)$-competitive relative to the optimal fixed price revenue. They also give a randomized auction which is O(log log h)-competitive relative to the optimal fixed price revenue, where h is the ratio between the highest and lowest bid.
We have designed an randomized auction which is O(1) competitive relative to the optimal fixed price revenue. The algorithm is based on the Weighted Majority algorithm [LW94].
We study mechanisms that can be modeled as coalition games with transferable utilities, and apply ideas from mechanism design and game theory to problems arising in a network design setting. Archer and Tardos introduced the concept of frugality in [AT02]. We establish an equivalence between the game-theoretic notion of agents being substitutes [BVSV01] and the notion of frugality of a mechanism. We characterize the core of the network design game and relate it to outcomes in a sealed bid auction with VCG payments. We show that in a game, agents are substitutes if and only if the core of the forms a complete lattice. We look at two representative games -- Minimum Spanning Tree and Shortest Path in this light. Finally, we design an ascending price mechanism for such games and study the strategic behavior of agents.
A popular technique for efficient implementation of algorithms using Finite fields is to do the computation in an isomorphic composite field. A key operation in this "method" is to transform the elements from the original field to the composite field. We study the circuit complexity of this operation and give a tight lower bound on the number of (constant fan-in exor) gates required.
Preliminary results appear in
This work included both software and hardware implementations, the performance figures of which are the best reported so far.
We generalized our ideas from the Rijndael Implementation here.