Workshop on Complexity and Coding Theory

Article Content

Shachar Lovett

The first Computer Science and Engineering (CSE) workshop of 2014 gets underway on Wednesday, Jan. 8 in room 4004 of Atkinson Hall on the UCSD campus. The three-day Workshop on Complexity and Coding Theory will focus on recent topics at the intersection of theoretical computer science and coding theory, such as local codes, list-decodable codes, polar codes and network codes.

“Talks will consist of both survey talks and more specialized technical talks,” says CSE Prof. Shachar Lovett, who is organizing the event. “We will also have allocated time for collaboration and informal discussions.”  In addition to opening remarks by Lovett, two CSE faculty members are slated to present during the workshop. On Jan. 9, Prof. Daniele Micciancio has a presentation on “Locally Dense Codes,” and the following morning, Prof. Mihir Bellare will explore “Semantic Security for the Wiretap Channel.”

Micciancio’s talk is based on an August 2013 paper of the same title referring to a combinatorial object called a “locally dense code” – a linear code with large minimum distance d, that admits a ball of smaller radius r<d containing an exponential number of codewords, together with some auxiliary information used to map these codewords. These locally dense codes “have been a key element in essentially all known proofs that the Minimum Distance Problem [MDP] is NP-hard,” notes Micciancio, adding that MDP is a well-known NP-hard problem in coding theory. In his talk, he will discuss a generic method to explicitly construct locally dense binary codes, starting from an arbitrary linear code with sufficiently large minimum distance.

Daniele Micciancio

“Instantiating our construction with well-known linear codes yields a simple proof that MDP is NP-hard to approximate within any constant factor under deterministic polynomial time reductions, simplifying and explaining recent results of other researchers,” says Micciancio. “Our work is motivated by the construction of analogous combinatorial objects over integer lattices, which are used in NP-hardness proofs for the Shortest Vector Problem (SVP). We show that for the ‘max’ norm, locally dense lattices can also be easily constructed.” However, he adds, all currently known constructions of locally dense lattices in the standard Euclidean norm are probabilistic. Finding a deterministic construction of locally dense Euclidean lattices, analogous to the results presented in the August paper, would prove the NP-hardness of approximating SVP under deterministic polynomial time reductions – a longstanding open problem in the computational complexity of integer lattices.

Mihir Bellare’s talk on semantic security for the wiretap channel refers to a channel setting where the aim is to provide information-theoretic privacy of communicated data based solely on the assumption that the channel from sender to adversary is “noisier” than the channel from sender to receiver.

Mihir Bellare

According to Bellare, that assumption has developed in the information and coding community over the past 30 years largely divorced from the parallel development of modern cryptography. “Our work aims to bridge the gap with a cryptographic treatment involving advances on two fronts, namely definitions and schemes,” says Bellare. “On the first front, definitions, we explain that the mis-r definition in current use is weak, so we propose two alternatives: mis (based on mutual information) and ss (based on the classical notion of semantic security). We prove them equivalent, thereby connecting two fundamentally different ways of defining privacy and providing a new, strong and well-founded target for constructions.” On the second front (schemes), Bellare and colleagues Stefano Tessaro (UC Santa Barbara) and Alexander Vardy (UC San Diego) provide the first explicit scheme with all the following characteristics: proven ability to achieve both security (ss and mis, not just mis-r) and decodability; an optimal rate; with both encryption and decryption algorithms proven to be polynomial-time.

The opening speaker on Wednesday, UT Austin’s David Zuckerman, will survey “Codes and Pseudorandomness.” Other speakers that day will include Mary Wootters (University of Michigan), Anup Rao (University of Washington), Ankit Garg (Princeton), and Klim Efremenko (University of Chicago). The following day, in addition to CSE’s Micciancio, speakers will include Christina Fragouli (EPFL and UCLA), Swastik Kopparty and Shubhangi Saraf (both from Rutgers). Rounding out the roster on Friday, Jan. 10, will be Ran Gelles (UCLA) and Mohammad Bavarian (MIT).

Registration is free, but seating is limited. To register, visit the workshop web page at here.