Charles River
Science of Information Day

Abstract:

One of the basic tenets in information theory, the data processing inequality, states that output divergence does not exceed the input divergence for any channel. For channels without input constraints, various estimates on the amount of such contraction are known, e.g., Dobrushin's coefficient for the total variation. This work investigates channels with average input cost constraint. It is found that while the contraction coefficient typically equals one, the information nevertheless dissipates. A certain non-linear function, a emph{Dobrushin curve} of the channel, is proposed to quantify the amount of dissipation. Tools for evaluating the Dobrushin curve of additive-noise channels are developed. Applications in stochastic control and uniqueness of Gibbs measures are discussed.

Download Slides (PDF)

Abstract:

The question of how and whether to join physical layer and network coding remains actively investigated. In this talk, we present some recent information-theoretic results and an application illustrating a view of this question. We begin by considering whether there are benefits, in capacity, from integrating network and physical layer coding. Network equivalence implies it is interference and broadcast effects, rather than the presence of noise, that might lead to such capacity benefits. However, in regimes of low SNR and of high SNR, where broadcast and interference, respectively, may be the dominant effects, integration appears to provide negligible benefits. We conclude with results from the first network coding chip. The benefit of both network and physical coding can be seen to be cumulative, even in the absence of coordination between the two.

Download Slides (PPTX)

Abstract:

Let H be a matrix whose elements are i.i.d. Under mild conditions, the asymptotic spectral properties of H are well-known. Now suppose that rows of H are generated from pseudorandom binary sequences and by changing 0 ---> 1 and 1 ---> -1. I will discuss spectral results for such H. This gives a concrete spectral test for pseudo-randomness.

The main tools in establishing our results are moment methods (Trace method), and Kolmogorov method of approximations of CDFs from moments. I will then briefly touch on generalization of our results/tests to multi-matrix scenarios, such as product and sum matrix tests for pseudo-randomness. Interestingly, pseudo-noise sequences (e.g. Golomb sequences) fail our tests, while Gold sequences satisfy our tests and are thus random-looking in the sense that I will describe.

This is joint work with Behtash Babadi (University of Maryland at College Park).

Abstract:

In a multi-user network, the standard approach for proving that a set of rates is achievable involves methods that are primarily statistical in nature. One canonical example of this approach is Shannon's i.i.d. random coding argument. Following such an existence argument, it is often of interest to develop more efficient encoding and decoding schemes and this has traditionally been the role of algebraic methods. However, an emerging body of work has demonstrated that algebraic methods also have an important role to play in establishing the capacity limits of networks. That is, in certain scenarios, structured random coding arguments have been able to achieve rates beyond what is possible using the best known i.i.d. random coding methods. This phenomenon was first noticed in 1979 by Korner and Marton for the distributed compression of the parity of two dependent sources. More recently, several groups have shown that algebraic structure can significantly enhance performance in relay networks, interference channels, distributed source coding, and distributed dirty-paper coding. In this talk, we overview recent efforts to develop an algebraic network information theory that incorporates the benefits of both algebraic and statistical code structure.

Download Slides (PDF)

Abstract:

Crowdsourcing systems, in which numerous tasks are electronically distributed to numerous "information piece-workers", have emerged as an effective paradigm for human-powered solving of large scale problems in domains such as image classification, data entry, optical character recognition, recommendation, and proofreading. Because these low-paid workers can be unreliable, nearly all crowd-sourcers must devise schemes to increase confidence in their answers, typically by assigning each task multiple times and combining the answers in some way such as majority voting.

We will discuss the problem of minimizing the total price (i.e., number of task assignments) that must be paid to achieve a target overall reliability. The answer we obtain is in the form of efficient task-allocation (through random regular graphs) coupled with a message-passing algorithm to aggregate answers for tasks reliably. Time-permitting, variations of basic problem in form of experimentation, adaptation, generality of the domain of answers and heterogeneity of workers will be discussed.

The talk is based on a joint work with David Karger (MIT) and Sewoong Oh (UIUC).

Download Slides (PPTX)

Abstract:

In this work we explore error-correcting codes derived from the lifting of affine-invariant codes. Affine-invariant codes are simply linear codes whose coordinates are a vector space over a field and which are invariant under affine-transformations of the coordinate space. Lifting takes codes defined over a vector space of small dimension and lifts them to higher dimensions by requiring their restriction to every subspace of the original dimension to be a codeword of the code being lifted. While the operation is of interest on its own, this work focuses on new ranges of parameters that can be obtained by such codes, in the context of local correction and testing.

This is joint work with Swastik Kopparty and Madhu Sudan.

Abstract:

We prove that, for all binary-input symmetric memoryless channels, Arikan's celebrated polar codes enable reliable communication at rates within epsilon > 0 of the Shannon capacity with block length (delay), construction complexity, and decoding complexity all bounded by a*polynomial* in the gap to capacity, i.e., by poly(1/epsilon). Polar coding gives the*first known explicit construction* with rigorous proofs of all these properties; except for the erasure channel, previous constructions were not known to approach capacity with less than exp(1/epsilon) decoding complexity.

We establish the capacity-achieving property of polar codes via a direct, elementary analysis of the underlying martingale of conditional entropies. This step gives rough polarization (noise levels ~ epsilon for the "good channels"), which can then be adequately amplified by tracking the decay of the channel Bhattacharyya parameters. Our effective bounds imply that polar codes can have block length bounded by poly(1/epsilon). The generator matrix of such polar codes can also be constructed in deterministic polynomial time by algorithmically computing an adequate approximation of the polarization process.

Based on joint work with Patrick Xia.

Download Slides (PDF)

Abstract:

A common application of distributed storage systems in distributed computing is to emulate a memory that is shared by multiple processors. In addition to fault tolerance, a critical requirement for such systems is the following property often known as "consistency": when the value stored is being updated often, and a client should be able to read the latest version of the value from the storage system. While consistent shared memory emulation algorithms form an integral part of distributed computing theory, their communication and storage are not well-studied. In this talk, we briefly overview literature in shared memory emulation algorithms, and present a new, low cost, erasure coding based algorithm. In particular, we discuss factors that influence communication and storage costs of the algorithms presented.

Joint work with Nancy Lynch, Muriel Médard and Peter Musial

Download Slides (PPTX)

Abstract:

We investigate an information theoretic problem motivated by storing multiple versions of a data object in distributed storage systems. Specifically, in a storage system with n server nodes, where there are nu independent message versions, each server receives message values corresponding to some arbitrary subset of the versions. The versions are assumed to be totally ordered. Each server is unaware of the set of versions at the other servers, and aims to encode the values corresponding to the versions it has. We investigate codes where, from any set of c nodes (c < n), the value corresponding to the highest common version, as per the version ordering, available at this set of c nodes is decodable. We aim to design codes that minimize the storage cost.

Download Slides (PDF)

Abstract:

Classical information theory, as set forth by Shannon in the 1940s, studies the problem of transmitting information from one point to another over a potentially noisy channel. This problem is by now very well understood (although some fascinating problems remain open): for example, Shannon's famous coding theorems exactly characterize the capacity channels of various types, and Huffman showed how to (almost) achieve this capacity even for a single transmission. In this talk I will survey recent developments in extending information theory to the interactive setting, where instead of simply sending information across a channel, the endpoints of the channel need to interact with each other over multiple rounds in order to achieve some shared goal. Some classical results in non-interactive information theory have analogues in the interactive setting, some do not, and several fundamental questions, such as whether an interactive conversation can be compressed down to its information content, remain open. I will also touch on applications to communication complexity and other topics in theoretical computer science.

Download Slides (PPTX)

Abstract:

The classical coding theory, pioneered by Shannon, addresses the question of how to deliver a message from one party to the other, while using an error-prone communication channel. Coding for interactive communication is the generalization where we are now given an interactive protocol between two parties, which is designed for the noiseless setting, and we want to transform it into a protocol that works in the presence of (adversarial) errors.

A key parameter in the study of coding for interactive communication is the maximum tolerable error-rate. Braverman and Rao [STOC'11] showed a coding scheme that tolerates any constant error rate below 1/4, and that this bound is optimal for the non-adaptive class of coding schemes, where it should be fixed ahead of time which party speaks in each round.

We show a coding scheme that tolerates any constant error rate below 2/7. This coding scheme is adaptive, i.e., parties decide who should speak next based on the history of the interaction. We also show this 2/7 bound to be optimal. The approach is quite general and it allows us to identify the optimal tolerable error rate for a number of other settings of interest, as well. If time permits, I will also explain how to make such coding schemes efficient, in terms of their computational and communication complexity.

Abstract:

An argument system for NP is a proof system that allows efficient verification of NP statements, given proofs produced by an untrusted yet computationally-bounded prover. Such a system is non-interactive and publicly-verifiable if, after a trusted party publishes a proving key and a verification key, anyone can use the proving key to generate non-interactive proofs for adaptively-chosen NP statements, and proofs can be verified by anyone by using the verification key.

We present an implementation of a publicly-verifiable non-interactive argument system for NP. The system, moreover, is a zero-knowledge proof-of-knowledge. It directly proves correct executions of programs on TinyRAM, a random-access machine tailored for efficient verification of nondeterministic computations. Given a program P and time bound T, the system allows for proving correct execution of P, on any input x, for up to T steps, after a one-time setup requiring \tilde{O}(|P| T) cryptographic operations. An honest prover requires \tilde{O}(|P| T) cryptographic operations to generate such a proof, while proof verification can be performed with only O(|x|) cryptographic operations. This system can be used to prove the correct execution of C programs, using our TinyRAM port of the GCC compiler.

This yields a zero-knowledge Succinct Non-interactive ARgument of Knowledge (zk-SNARK) for program executions in the preprocessing model -- a powerful solution for delegating NP computations, with several features not achieved by previously-implemented primitives.

Our approach builds on recent theoretical progress in the area. We present efficiency improvements and implementations of two main ingredients:

• Given a C program, we produce a circuit whose satisfiability encodes the correctness of execution of the program. Leveraging nondeterminism, the generated circuit's size is merely quasilinear in the size of the computation. In particular, we efficiently handle arbitrary and data-dependent loops, control flow, and memory accesses.
  
  This is in contrast with existing ``circuit generators'', which in the general case produce circuits of quadratic size.
• Given a linear PCP for verifying satisfiability of circuits, we produce a corresponding SNARK. We construct such a linear PCP (which, moreover, is zero-knowledge and very efficient) by building on and improving on recent work on quadratic arithmetic program

Abstract:

We present a device-independent randomness expansion protocol, involving only a constant number of non signaling quantum devices, that achieves infinite expansion: starting with m bits of uniform private randomness, the protocol can produce an unbounded amount of certified randomness that is exp(−Ω(m^1/3))-close to uniform and secure against a quantum adversary. The only parameters which depend on the size of the input are the soundness of the protocol and the security of the output (both are inverse exponential in m). This settles an open problem in the area of randomness expansion and device-independence.

We also present a protocol that achieves infinite randomness amplification using a constant number of devices. The input seed is not necessarily uniform, but can be generated from a Santha-Vazirani source, a type of weak randomness. The output is still nearly uniform, secure against a quantum adversary, and can be arbitrarily long. In contrast, it is well known that classically one cannot extract even a single near-uniform bit from a Santha-Vazirani source.

The analysis of our protocols involves overcoming fundamental challenges in the study of adaptive device-independent protocols. Our primary technical contribution is the design and analysis of device-independent protocols which are Input Secure; that is, their output is guaranteed to be secure against a quantum eavesdropper, even if the input randomness was generated by that same eavesdropper!

The notion of Input Security may be of independent interest to other areas such as device independent quantum key distribution.

Download Slides (PDF)

Abstract:

Given an algebraic function that is "simple", how many evaluations of this function are required to determine this function? Can one construct explicit sets of evaluation points, and efficiently reconstruct the algebraic function from these points?

I will discuss some recent work of mine addressing these questions, and will draw connections to compressed sensing, coding theory, and the polynomial identity testing problem from derandomization/complexity-theory.

Download Slides (PDF)