Professor Madhu Sudan
from the School of Engineering and Applied Sciences at Harvard
University will be visiting IIT Bombay as NR Kamath Chair Professor
during the dates Dec 19, 2016 to Jan 6, 2017. During his time here, he
will give talks and interact with students and faculty on research
topics. Please find below a list of public events that have been scheduled. (If you would like to have a research-related discussion with Prof. Sudan, please do set up an appointment by sending me an email at srikanth AT math DOT iitb DOT ac DOT in.) |

Madhu Sudan's research interests revolve around theoretical studies of communication and computation. Specifically his research focusses on concepts of reliability and mechanisms that are, or can be, used by computers to interact reliably with each other. His research draws on tools from computational complexity, which studies efficiency of computation, and many areas of mathematics including algebra and probability theory. He is best known for his works on probabilistic checking of proofs, and on the design of list-decoding algorithms for error-correcting codes.

In 2002, Madhu Sudan was awarded the Nevanlinna Prize, for outstanding contributions to the mathematics of computer science, at the International Congress of Mathematicians in Beijing. He is also the recipient of the 2014 Infosys Foundation Prize in Mathematical Sciences. Madhu Sudan is a fellow of the ACM, the IEEE, the AMS and the American Academy of Arts and Sciences. He was a Radcliffe Fellow from 2003-2004.

Mathematics Department Colloquium

Workshop on Mathematics and Information (Registration free but *required*!).

Venue: Prof. B Nag Auditorium, VMCC, IIT Bombay.

Title: Proofs and Computation

Abstract: While it is well-understood that Proofs form the foundations of Mathematics, it is less well-known that Proofs and Computers are intimately related. Indeed a common perception is that the only link between Proofs and Computing is that sometimes computers can assist in the search for proofs. In this talk I will describe a more historically significant, and intrinsic, connection. Proofs are by definition "Computational Objects" - and to understand to the difference between a theorem and its proof, one needs to understand computational complexity of tasks - namely the number of steps on a computer needed to solve a given task. In this talk, I will talk about the historical role of proofs in computation, leading to the "prototype" of the modern computer in the 1930s, to the conception of the famous "Is P = NP?" question in the 1970s and some modern variation like interactive proofs, zero-knowledge proofs and probabilistically checkable proofs. I will explain how at each stage the study of proofs has revolutionized our understanding of what computers can or can not do!

Venue: Ramanujan Hall, Department of Mathematics, IIT Bombay.

Title: The Polynomial Method and Variations

Abstract: The polynomial method in combinatorics has recently emerged as a simple but strikingly powerful method to answer many fundamental questions about combinatorial parameters associated with geometric objects. I will survey some of the old and new applications of this method (focussing on the simpler proofs!) including:

1) "List-decoding bounds for Reed-Solomon codes": Given $n$ points in the plane, how many polynomials of degree $d$ can pass through $t$ of them? (Guruswami and S. '98)

2) "Bounds on Kakeya and Nikodym sets": How small can a subset of $F_q^n$ (the $n$-dimensional vector space over the finite field of cardinality $q$) be so that it contains a line in every direction. (Dvir 2008)

3) "Bounds on Joints in R^3": What is the largest number of "joints" (non-coplanar intersection of three lines) that can be formed by a set of L lines? (Guth and Katz, 2008)

4) "Bound on capsets in F_3^n": How large can a subset in F_3^n so that it contains no complete line? (Ellenberg, Gijswijt; based on Croot-Lev-Pach 2016).

The workshop will take place during the dates January 2 to 4, 2017 at Ramanujan Hall, Department of Mathematics, IIT Bombay.

Registration: Participants are requested to register in order that we might be prepared for seating space, food, etc.. There is NO registration fee. The registration deadline is December 28, 2016. After this deadline, please send registration requests to srikanth AT math DOT iitb DOT ac DOT in.

List of speakers:

- Madhu Sudan (Harvard University)
- S Akshay (CSE, IIT Bombay)
- Varsha Dani (University of New Mexico)
- Tom Hayes (University of New Mexico)
- Bikash Kumar Dey (EE, IIT Bombay)
- Sudhir Ghorpade (Math., IIT Bombay)
- Fernando Pinero (University of Puerto Rico)
- Manoj Prabhakaran (CSE, IIT Bombay)
- Jaikumar Radhakrishnan (STCS, TIFR)
- Ramprasad Saptharishi (STCS, TIFR)

Jan 2 | Jan 3 | Jan 4 | |

10.30 AM to 11 AM | Tea | ||

11 AM to 12 noon | Madhu Sudan | Bikash Kumar Dey | Fernando Pinero |

12 noon to 1 PM | Manoj Prabhakaran | Jaikumar Radhakrsihnan | Tom Hayes |

1 PM to 2.30 PM | Lunch | ||

2.30 PM to 3.30 PM | Sudhir Ghorpade | Varsha Dani | S Akshay |

3.30 PM to 4.30 PM | Ramprasad Saptharishi |

There will be tea and snacks after the last talk on each day.

On Jan 4, at 5.15 PM, Madhu Sudan will give the Institute Colloquium. Please do attend!

Talk abstracts:

Madhu Sudan

Title: Communication with Functional Uncertainty

Abstract: Modern computers are increasingly interacting more like humans do: They incorporate massive context into their communication; and assume that a lot of this context is shared, even if somewhat imprecisely, by other devices they interacts with. Communications are typically short, and the context often enables this brevity despite it being imperfectly shared. Most of these interactions have gone unstudied mathematically: Indeed it is still unclear as to what is the right model to express and study some of these problems.

In a recent sequence of works we have suggested that these questions are best studied in the "communication complexity" model of Yao: Here two interacting agents "Alice" and "Bob" have private information x and y respectively and interact to compute some joint function f(x.y). Allowing the context to be part of x and y suggests ways in which imperfectly shared context can be incorporated into the study of communication. The abundance of functions f for which f(x,y) can be determined with relatively little communication can be viewed as a positive feature of the model.

In this talk I will describe some of the above concerns and conclusions in greater detail, before moving on to study yet another source of uncertainty: What happens if Alice and Bob don't even agree on the function f(x,y) being computed? I will describe some positive and negative results.

Based on joint work with Badih Ghazi, Ilan Komargodski and Pravesh Kothari.

Manoj Prabhakaran

Title: Renyi Information Complexity and an Information Theoretic Characterization of the Partition Bound

Abstract: We introduce a new information-theoretic complexity measure IC∞ for

2-party functions which is a lower-bound on communication complexity,

and has the two leading lower-bounds on communication complexity as

its natural relaxations: (external) information complexity (IC) and

logarithm of partition complexity (prt). These two lower-bounds had so

far appeared conceptually quite different from each other, but we show

that they are both obtained from IC∞ using two different, but natural

relaxations:

* The relaxation of IC∞ that yields IC is to change the order of Renyi

mutual information used in its definition from ∞ to 1.

* The relaxation of IC∞ that yields log prt is to replace protocol

transcripts used in the definition of IC∞ with what we term

"pseudotranscripts," which omits the interactive nature of a

protocol, but only requires that the probability of any transcript

given inputs x and y to the two parties, factorizes into two terms

which depend on x and y separately.

We also show that if both the above relaxations are simultaneously

applied to IC∞, we obtain a complexity measure that is lower-bounded

by the (log of) relaxed partition complexity, a complexity measure

introduced by Kerenidis et al. (FOCS 2012). We obtain a similar (but

incomparable) connection between (external) information complexity and

relaxed partition complexity as Kerenidis et al., using an arguably

more direct proof.

This is joint work with Vinod Prabhakaran.

Sudhir Ghorpade

Title: Some interactions between coding theory and algebraic geometry

Abstract: Coding theory, or more specifically, the study of linear error

correcting codes emerged mainly from Shannon's 1948 article on a

mathematical theory of communication. Over the years it has blossomed

into a rich and vibrant area of research. There have been many

interactions with algebraic geometry going back at least to the

introduction of Goppa

codes associated to algebraic curves over finite fields in the early 1980's.

We will mainly consider interactions with algebraic varieties of higher

dimensions, and outline some of the results and problems that arise

from these interactions. We shall begin by discussing the notion of

projective

systems that provides an alternative language to discuss codes and

illustrate how a classical family codes such as the Reed-Muller codes

can be viewed in this manner. Next, we consider related families of codes,

known as projective Reed-Muller codes, Grassmann codes, and Schubert

codes, that are naturally related to certain classical algebraic varieties.

We will particularly focus on the problem of determination of generalized

Hamming weights and report on some interesting recent developments.

Ramprasad Saptharishi

Title: TBA

Abstract: TBA

Bikash Kumar Dey

Title: Distributed Rate Adaptation and Power Control in Fading Multiple Access Channels

Abstract: In a wireless fading channel, the channel gain varies with time.

In a fading multiple access channel (MAC), there are two

transmitters and one receiver. The receiver receives

the sum of two faded transmitted signals, corrupted by Gaussian

noise. Traditionally, the capacity region of a coherent

fading multiple access channel (MAC) is analyzed in two popular

contexts. In the first, a centralized system with full channel

state information at the transmitters (CSITs) is assumed, and

the transmit power and data-rate can be jointly chosen for

every fading vector realization. On the other hand, in fast-fading

links with distributed CSIT, the lack of full CSI is compensated

by performing ergodic averaging over sufficiently many channel

realizations. Notice that the distributed CSI may necessitate

decentralized power-control for optimal data-transfer. Apart

from these two models, the case of slow-fading links and

distributed CSIT, though relevant to many systems, has received

much less attention. In this talk, a block-fading additive

white Gaussian noise MAC with full CSI at the receiver and

distributed CSI at the transmitters will be considered. The links

undergo independent fading, but otherwise have arbitrary fading

distributions. The channel statistics and respective long-term

average transmit powers are known to all parties. We will first consider

the case where each encoder has knowledge only of its own

link quality, and not of others. For this model, we will compute the

adaptive capacity region, i.e., the collection of average rate-tuples

under blockwise coding/decoding such that the rate-tuple for

every fading realization is inside the instantaneous MAC capacity

region. The key step in our solution is an optimal rate allocation

function for any given set of distributed power control laws at the

transmitters. This also allows us to structurally characterize the

optimal power control for a wide class of fading models. Further

extensions will also be made for the case where each encoder has

additional partial CSI about the other links.

(Joint work with Sreejith Sreekumar and Sibi Raj B. Pillai)

Jaikumar Radhakrishnan

Title: Set membership with two bit probes

Abstract: We consider the bit-probe complexity of the set membership problem,

where a set S of size at most n from a universe of size m is to be

represented as a short bit vector in order to answer membership

queries of the form ``Is x in S?'' by probing the bit vector at t

places. Let s(m,n,t) be the minimum number of bits of storage needed

for such a scheme.

We will analyse s(m,n,t) for small values of t, mainly 2 and 3, and

show upper and lower bounds.

(This is joint work with Mohit Garg.)

Varsha Dani

Title: Interactive Communication Over a Noisy Channel

Abstract: Alice and Bob want to hold a conversation over a noisy channel on which adversarially chosen bits may be flipped. How can they communicate robustly despite such an attack?

When the conversation is one-way, i.e. Alice wants to send Bob a single message, this is a well studied problem, solved by error-correcting codes. However, these codes are not useful, for instance, when Alice and Bob need to take turns sending single bits. To solve this problem, Schulman (1992) invented tree codes, showing that for sufficiently small noise rates the conversation can be robustly simulated using a constant factor blowup in communication. Subsequently there were a number of improvements, culminating in a recent result of Haeupler (2014) conjectured to be optimal.

The drawback in the above is that it depends on knowing the noise rate. We approach the problem from a different angle, asking what Alice and Bob can do if they have no estimate for the noise on the channel (indeed, if they do not even know if there *is* any noise). We show that, with some caveats, even in this setting Alice and Bob can robustly hold their conversation, with a communication rate comparable to Haeupler's with respect to the actual (a posteriori) noise rate.

Fernando Pinero

Title: Encoding linear codes on graphs using graph theoretical models of the spread of information on a network.

Abstract: In this talk we will discuss the problem of encoding linear codes based on graphs. By modelling the encoding algorithm as the spread of the bit values on the graph itself, we can determine in some cases which sets of vertices are good for encoding. We apply this encoding model to linear codes on graphs from algebraic geometry, as for example, linear codes on the Grassmannian, Schubert codes and Schubert union codes. We also discuss the possibility of permutation set decoding.

Tom Hayes

Title: TBA

Abstract: TBA

S Akshay

Title: TBA

Abstract: TBA