[Colloquium] THEORY SEMINAR TALK TODAY: Subhash Khot
Donna Brooms
donna at cs.uchicago.edu
Fri Feb 11 08:08:29 CST 2011
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF CHICAGO - THEORY SEMINAR
Date: Friday, February 11, 2011
Time: 10:00 a.m.
Place: Ryerson 277, 1100 E. 58th Street
----------------------------------------------
Speaker: Subhash Khot
From: New York University
Web page: http://www.cs.nyu.edu/~khot/
Title: A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
Abstract: We present a simple deterministic gap-preserving reduction from SAT to the Minimum Distance of Code Problem over GF(2). We also show how to extend the reduction to work over any finite field. Previously a randomized reduction was known due to Dumer, Micciancio, and Sudan [1999], which was recently derandomized by Cheng and Wan [2009]. These reductions rely on highly non-trivial coding theoretic constructions whereas our reduction is elementary.
As an additional feature, our reduction gives a constant factor hardness even for asymptotically good codes, i.e., having constant rate and relative distance. Previously it was not known how to achieve deterministic reductions for such codes.
Joint work with Per Austrin.
Host: Prof. Laszlo Babai
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20110211/479ca6a4/attachment.htm
More information about the Colloquium
mailing list