Our keynote speaker this year is Himanshu Tyagi.
He will speak on

Time  Friday (29th March)  Saturday (30th March) 

09:3010:00  Breakfast  Breakfast 
10:0010:30  Suneel Sarswat  Phani Raj Lolakapuri 
10:3011:00  Kshitij Gajjar  Umang Bhaskar 
11:0011:30  Tea  Tea 
11:3012:00  Sandeep Juneja  Ramprasad Saptharishi 
12:0012:30  Somnath Chakraborty  Varun Narayanan 
12:3014:00  Lunch  Lunch 
14:0014:30  Arkadev Chattopadhyay  Tulasimohan Molli 
14:3015:00  Himanshu Tyagi  Prahladh Harsha 
15:0015:30  Himanshu Tyagi  Marc Vinyals 
15:3016:00  Evening Tea  Evening Tea 
16:0016:30  Rajshekhar Bhat  Aditya Nema 
16:3017:00  Abhishek Kr Singh  Pranab Sen 
Post 17:00  Korero  Banquet Dinner 

Breakfast
Back to the schedule 
Formalization of double sided auctions
Suneel Sarswat
In this talk, we introduce a formal framework for analyzing double sided auction mechanisms in a theorem prover. In double sided auctions multiple buyers and sellers participate for trade. Any mechanism for double sided auctions to match buyers and sellers should satisfy certain properties of matching. For example, fairness, percievedfairness, individual rationality are some of the important properties. They are critical properties and to reason out them we need a formal setting. We formally define all of these notions in a theorem prover. This provides us a formal setting in which we prove some useful results on matching in a double sided auction. Finally we use this framework to analyse properties of two important class of double sided auction mechanism. All the properties that we discuss in this talk are fully formalised in the Coq proof assistant without adding any axiom to it.
Back to the schedule 
Parametric Shortest Paths in Planar Graphs
Kshitij Gajjar
Suppose you have a road network with $n$ traffic signals such that the amount of traffic on each road varies as a linear function of time. Then the shortest path from a source $s$ to a destination $t$ might be different at different points of time. It was well known (Gusfield, 1980) that the number of different shortest $s$$t$ paths is at most $n^{O(\log n)}$. In this talk, we will show that there exists a planar road network for which the number of different shortest $s$$t$ paths is at least $n^{\Omega(\log n)}$, refuting a conjecture of Nikolova (2009). This is based on joint work with Jaikumar.
Back to the schedule 
Sample complexity of partition identification using multiarmed bandits
Sandeep Juneja
Given a vector of probability distributions, or arms, each of which can be sampled independently, we consider the problem of identifying the partition to which this vector belongs from a finitely partitioned universe of such vector of distributions. We study this as a pure exploration problem in multi armed bandit settings and develop sample complexity bounds on the total mean number of samples required for identifying the correct partition with high probability. This framework subsumes well studied problems in the literature such as finding the best arm or the best few arms. The partitions considered include half spaces, polytopes or their complements, or more generally, convex sets or their complements. In these settings, exploiting problem geometry, we characterise the lower bounds on mean number of samples for each arm. Further, we propose algorithms that can match these bounds asymptotically with decreasing probability of error.
Back to the schedule 
Generating an equidistributed net on an nsphere (symmetric space)
Somnath Chakraborty
We develop a randomized algorithm (that succeeds with high probability) for generating an $\epsilon$net in a sphere of dimension n. The basic scheme is to pick ${\tilde O}(n \ln(1/\epsilon) + \ln(1/\delta))$ random rotations and take all possible words of length $O(n \ln(1/\epsilon))$ in the same alphabet and act them on a fixed point. We show this set of points is equidistributed at a scale of $\epsilon$. Our main application is to approximate integration of Lipschitz functions over an nsphere.
Back to the schedule 
Lunch
Back to the schedule 
The LogApproximateRank Conjecture is False
Arkadev Chattopadhyay
The LogRank Conjecture (LRC) of Lovasz and Saks (1988) asserts the following: the 2party 'deterministic' communication complexity of a total bipartite boolean function $f$ is at most a fixed polynomial of the logarithm of the rank of its communication matrix $M_f$. Resolving this conjecture remains one of the most fundamental challenges in the field. Analogously, Lee and Shraibman (2007) formulated the LogApproximateRank Conjecture (LARC): the 2party 'randomized' communication complexity of $f$ is at most a fixed polynomial of the logarithm of the 'approximaterank' of $M_f$. Besides being very natural, the LARC implied a host of other important conjectures, including the LogRank Conjecture. We show that there is a simple counterexample to the LARC. (Joint work with Nikhil Mande and Suhail Sherif.)
Back to the schedule 
Inference Under Local Information Constraints
Himanshu Tyagi
We consider statistical inference when we are allowed to retain only limited information about each sample. Such a limitation can be imposed by communication constraints or privacy constraints, among other possibilities. We present a general framework for deriving lower bounds on sample complexity and develop practical algorithms that match these bounds for specific examples. Perhaps the most striking of our findings is that sample complexity is orderwise smaller for distribution testing under local information constraints for publiccoin protocols when compared to privatecoin protocols. Timepermitting, we will provide a brief preview of our results in the general area of resource constrained statistics.
Back to the schedule 
Inference Under Local Information Constraints
Himanshu Tyagi
We consider statistical inference when we are allowed to retain only limited information about each sample. Such a limitation can be imposed by communication constraints or privacy constraints, among other possibilities. We present a general framework for deriving lower bounds on sample complexity and develop practical algorithms that match these bounds for specific examples. Perhaps the most striking of our findings is that sample complexity is orderwise smaller for distribution testing under local information constraints for publiccoin protocols when compared to privatecoin protocols. Timepermitting, we will provide a brief preview of our results in the general area of resource constrained statistics.
Back to the schedule 
Evening Tea
Back to the schedule 
Layered Coding in NonIdeal Energy Harvesting Transmitters Without Channel State Information
Rajshekhar Bhat
Modern Internet of Things devices will increasingly rely on energy harvested from the environment. In such systems, the harvested energy is usually stored (charged) in and drawn (discharged) from batteries for smoothening its inherent random fluctuations. In practical batteries, the charging and discharging processes incur energy losses, where the losses are nonlinear functions of charging and discharging powers. This necessitates low power charging and discharging for higher energy efficiency in the battery. Further, in many energy harvesting applications, the circuit power, the power required to run the circuitry, is in the order of the harvested power. This necessitates bursty transmissions with high power discharge for higher energy efficiency in the circuit. To account for the above conflicting effects, we jointly consider: (a) the nonzero circuit power and (b) the nonlinear battery charging and discharging losses. In this setting, we optimize an energy harvesting transmitter, communicating over a slow fading channel, using layered coding. The transmitter has access to the channel statistics, but does not know the exact channel state. In layered coding, the codewords are first designed for a given finite set of channel states at different rates, and then the codewords are superimposed before transmission. The receiver then decodes the information adaptively based on the realized channel state.
Back to the schedule 
Towards a constructive formalization of Perfect Graph Theorems
Abhishek Kr Singh
Interaction between clique number and chromatic number of a graph is a well studied topic in graph theory. Perfect Graph Theorems are probably the most important results in this direction. In this talk, we present a formal framework for verifying these results. We model finite simple graphs in the constructive type theory of Coq Proof Assistant without adding any axiom to it. Finally, we use this framework to present a constructive proof of the Lovasz Replication Lemma, which is the central idea in the proof of Weak Perfect Graph Theorem.
Back to the schedule 
Open problems discussion session
Korero
Inspired by the Maori word, 'korero' stands for conversation/discussion/meeting. The last session of 29th March will be an open problems session. Students/faculty would volunteer to present a concrete problem (even a simplistic version of it) that they are working on in 5 minutes, followed by short questions/discussions etc. This session is supposed to be fairly informal and ad hoc, but the presenters are of course to keep in mind that you have 5 minutes to present the question in a way that even people outside your field can follow.
Back to the schedule 
Breakfast
Back to the schedule 
Equilibria in Discrete Preference Games
Phani Raj Lolakapuri
We study the complexity of equilibrium computation in discrete preference games. These games were introduced by Chierichetti, Kleinberg, and Oren (EC '13, JCSS '18) to model decisionmaking by agents in a social network that choose a strategy from a finite, discrete set, balancing between their intrinsic preferences for the strategies and their desire to choose a strategy that is `similar' to their neighbours. There are thus two components: a social network with the agents as vertices, and a metric space of strategies. These games are potential games, and hence pure Nash equilibria exist. Since their introduction, a number of papers have studied various aspects of this model, including the social cost at equilibria, and arrival at a consensus. We show that in general, equilibrium computation in discrete preference games is PLScomplete, even in the simple case where each agent has a constant number of neighbours. If the edges in the social network are weighted, then the problem is PLScomplete even if each agent has a constant number of neighbours, the metric space has constant size, and every pair of strategies is at distance 1 or 2. Further, if the social network is directed, modelling asymmetric influence, an equilibrium may not even exist. On the positive side, we show that if the metric space is a tree metric, or is the product of path metrics, then the equilibrium can be computed in polynomial time.
Back to the schedule 
Partial Function Extension with Applications to Learning and Property Testing
Umang Bhaskar
In partial function extension, we are given a partial function consisting of points from a domain and a function value at each point. Our objective is to determine if this partial function can be extended to a function defined on the domain, that additionally satisfies a given property, such as convexity. This basic problem underlies research questions in many areas, such as learning, property testing, and game theory. We present bounds on the complexity of partial function extension to subadditive, submodular, and convex functions, and present some applications to learning as well as property testing for these functions. This is joint work with Gunjan Kumar.
Back to the schedule 
An Improved Depth Reduction for Syntactically Multilinear Circuits
Ramprasad Saptharishi
We show that any nvariate polynomial computable by a syntactically multilinear circuit of size poly(n) can be computed by a syntactically multilinear depth4 circuit of size at most $\exp(O(\sqrt{n\log n}))$. For degree $d = \omega(n/\log n)$, this improves upon the upper bound of $\exp(O(\sqrt{d}\log n))$ obtained by Tavenas for general (nonmultilinear) circuits, and is known to be asymptotically optimal in the exponent when $d < n^{\epsilon}$ for a small enough constant $\epsilon$. Our upper bound matches the lower bound of $\exp(\Omega(\sqrt{n\log n}))$ proved by Raz and Yehudayoff, and thus cannot be improved further in the exponent. Based on joint work with Mrinal Kumar and Rafael Oliveira.
Back to the schedule 
Private Index Coding
Varun Narayanan
We study the problem of index coding under the privacy requirement that receivers do not learn anything more than the messages they already have as side information and the message they want from the server. To achieve this private index coding, we consider the use of secret keys that are shared among various subsets of users and the server. We characterize key access structures that allow private index coding. For up to three receivers, we characterize the rate region of transmission and key rates and show that scalar coding is optimal; we also show that scalar linear codes are suboptimal for four receivers. Furthermore, when no keys are available, we consider a weaker notion of privacy analogous to weak security. Finally, for a different setting in which the server is allowed to send messages exclusively to a subset of users, we study the number of transmissions required to achieve errorfree decoding and privacy.
Back to the schedule 
Lunch
Back to the schedule 
On the probabilistic polynomial degree of OR over the Reals
Tulasimohan Molli
Polynomials are very well studied objects and have been around for a while. Polynomial representations of boolean functions are useful in understanding their complexity and have applications in proving lower bounds and in derandomization. OR is a basic boolean function which is a building block of a very natural model of computation called boolean circuits. This motivates the question of understanding the probabilistic polynomial degree of OR over Reals. In this talk, I will present some constructions of probabilistic polynomials and some lower bounds which show that these constructions are essentially the best as long as the probabilistic polynomials have a nice structure. This is joint work with Siddharth Bhandari, Prahladh Harsha from TIFR and Srikanth Srinivasan from IIT Bombay.
Back to the schedule 
List Decoding via Double Samplers
Prahladh Harsha
Samplers Graphs are bipartite graphs in which all reasonably sized subset of vertices on the left sample the right vertices well. Sampler graphs have been used in errorcorrecting code constructions to amplify the distance of an error correcting code (cf, the ABNNR construction). This construction has a unique decoding algorithm, but it is not known to be efficiently list decodable. In this talk, I will introduce the notion of "double samplers", which extend sampler graphs to three layers, and show a polynomial time algorithm which list decodes the ABNNR code construction on a double sampler. Double samplers can be constructed from high dimensional expanders, and currently is the only known construction of such objects. Joint work with Irit Dinur, Tali Kaufman Inbal Livni Navon and Amnon TaShma.
Back to the schedule 
Equality Alone Does not Simulate Randomness: Now with 20% More Theorems
Marc Vinyals
Randomness can provide an exponential saving in the amount of communication needed to solve a distributed problem, and the canonical example of this is equality. However, in all examples where randomness helps having access to an equality oracle would be enough to solve the problem efficiently. Is equality all there is to randomness? In this talk we show that equality is not enough. More precisely, we exhibit a function that can be solved efficiently using randomized protocols but not with only access to an equality oracle. Additionally we exhibit a natural and strict infinite hierarchy within BPP, starting with the class P with equality oracle. Joint work with Arkadev Chattopadhyay and Shachar Lovett.
Back to the schedule 
Evening Tea
Back to the schedule 
A one shot inner bound for private communication over a multiple access channel
Aditya Nema
In this talk we shall discuss one shot inner bounds or achievable rates for point to point and MAC channels. We shall start by giving an inner bound for point to point classical channel when the channel is used only once (referred to as one shot). The achievable rate in this case is hypothesis testing relative entropy, which is one shot analogue of mutual information. We then discuss a one shot achievable rate for point to point channel with privacy (as known as wire tap channel). For this talk, the privacy condition is to prohibit an eavesdropper from correctly decoding the message transmitted through the channel. Following this we will discuss achievable rate region for two sender and one receiver Multiple Access Channel (referred to as MAC) and it is the one shot analogue of the rate region in I.I.D. regime (where channel is used 'n' times and the rate region is obtained as 'n' approaches infinity). Following along these lines, we then discuss our work on an achievable rate region for MAC with privacy in one shot regime. This is joint work with Sayantan and Pranab.
Back to the schedule 
Unions, intersections and a oneshot quantum joint typicality lemma
Pranab Sen
A fundamental tool to prove inner bounds in classical network information theory is the socalled 'conditional joint typicality lemma'. In addition to the lemma, one often uses unions and intersections of typical sets in the inner bound arguments without so much as giving them a second thought. These arguments fail spectacularly in the quantum setting. This bottleneck shows up in the fact that socalled 'simultaneous decoders', as opposed to 'successive cancellation decoders', are known for very few channels in quantum network information theory. In this talk we shall see how to overcome the bottleneck by proving for the first time a oneshot quantum joint typicality lemma with robust union and intersection properties. To do so we develop two novel tools in quantum information theory, which we call tilting, and smoothing and augmentation, which should be of independent interest. Our joint typicality lemma allows us to construct simultaneous quantum decoders for many multiterminal quantum channels and gives a powerful tool to extend many results in classical network information theory to the oneshot quantum setting. We shall see a glimpse of this in the talk by constructing a oneshot simultaneous decoder for the quantum multiple access channel with an arbitrary number of senders. Our oneshot rates reduce to the known optimal rates when restricted to the asymptotic iid setting, which were previously obtained by successive cancellation and time sharing.
Back to the schedule
Credits
Organizers: Rahul Vaze, Kshitij Gajjar, Neha, Arghya ChakrabortySite design: Suhail Sherif
*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*