This paper considers the tradeoff between divisibility and the hardness of approximating
equilibrium prices. Tight bounds are obtained for smooth Fisher markets that obey a relaxed
weak gross substitutes property (WGS). A smooth market is one in which small changes in
prices cause only proportionately small changes ... more >>>

Locally Decodable codes(LDC) support decoding of any particular symbol of the input message by reading constant number of symbols of the codeword, even in presence of constant fraction of errors.

In a recent breakthrough, Yekhanin designed $3$-query LDCs that hugely improve over earlier constructions. Specifically, for a Mersenne prime $p ... more >>>

We initiate a general study of the randomness complexity of
property testing, aimed at reducing the randomness complexity of
testers without (significantly) increasing their query complexity.
One concrete motovation for this study is provided by the
observation that the product of the randomness and query complexity
of a tester determine ... more >>>