Workshop on Complexity and Coding Theory

Prof. Shachar Lovett

San Diego, Jan. 3, 2014  -- The first Computer Science and Engineering (CSE) workshop of 2014 is set to get underway on Wednesday, Jan. 8 in room 4004 of Atkinson Hall, the home of Calit2's Qualcomm Institute 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.

Prof. Daniele Micciancio

In his talk, Micciancio will discuss a generic method to explicitly construct locally dense binary codes, starting from an arbitrary linear code with sufficiently large minimum distance. “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 the CSE professor. “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. 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.

Prof. Mihir Bellare

“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.

Related Links

Workshop on Complexity and Coding Theory
August 2013 Paper: Locally Dense Codes
UCSD Computer Science and Engineering

Media Contacts

Doug Ramsey, 858-822-5825, dramsey@ucsd.edu