Computer Science/Discrete Mathematics

We prove nearly quadratic (in the dimension) lower bounds for randomized algorithms for two basic problems: linear optimization and uniform sampling over convex bodies in the membership oracle model (a convex body K is specified by a point in K, the...

A locally correctable code (LCC) is an error-correcting code where one can recover any symbol of the original codeword by querying only a small number of randomly chosen symbols from the received corrupted codeword. In recent years, there has been...

We study bitwise-optimal cryptographic primitives: functions in NC⁰ (where each output bit depends on only a constant number of input bits) that achieve exponential security, together with linear stretch for pseudorandom generators (PRGs) and linear...