Prof. Madhu Sudan's visit as N R Kamath Chair Professor

Madhu Sudan's photoProfessor 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.)


About Prof. Sudan:

Madhu Sudan is a Gordon McKay Professor in the John A. Paulson School of Engineering and Applied Sciences at Harvard University. Madhu Sudan got his Bachelors degree from IIT Delhi in 1987 and his Ph.D. from U.C. Berkeley in 1992. Between 1992 and 2015, Madhu Sudan worked at IBM Research (Research Staff Member 1992-1997), at MIT (Associate Professor 1997-2000, Professor 2000-2011, Fujitsu Chair Professor 2003-2011, CSAIL Associate Director 2007-2009, Adjunct Professor 2011-2015), and at Microsoft Research (Principal Researcher, 2009-2015). He has been at Harvard since October 2015.

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.


Events

Institute Colloquium

Mathematics Department Colloquium

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

Institute Colloquium

Date and time: Wednesday Jan 4, 2017. 5.15 PM.
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!

Mathematics Department Colloquium

Date and time: December 28, 2016, 4-5 PM.
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).


Workshop on "Mathematics and Information"

The departments of Computer Science and Engineering and Mathematics will host a workshop on the Mathematics of Information. The theme of the workshop will be aspects at the intersection of Mathematics and the theories of Communication and Computation.

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:
Program:


Jan 2Jan 3Jan 4
10.30 AM to 11 AMTea
11 AM to 12 noonMadhu SudanBikash Kumar DeyFernando Pinero
12 noon to 1 PMManoj PrabhakaranJaikumar RadhakrsihnanTom Hayes
1 PM to 2.30 PMLunch
2.30 PM to 3.30 PMSudhir GhorpadeVarsha DaniS Akshay
3.30 PM to 4.30 PMRamprasad 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