# Theoretical Computer Science @ IIT Bombay

## Theory Seminar and Reading Group

The talks are announced in the theory-seminar mailing-list.
• The Chasm at Depth Four, and Tensor Rank : Old results, new insights [Oct 25 2017 +]

Date: October 25, 2017.
Time: 11:00am to 12:00pm.
Venue: Conference room, 1st Floor, CSE Kanwal Rekhi Bldg

Proving "good" lower bounds on the size of the arithmetic formulas computing an explicit polynomial is one of the central themes in the study of algebraic complexity. But the best known lower bound on the size of an arithmetic formula computing an explicit polynomial is quadratic in the number of variables, due to Kalorkoti [SIAM J. Comp. 1985]. There hasn’t been any progress on that front in the last 32 years.

But in a surprising result, Raz [J. ACM 2013] showed that for any n and d where d is sub-logarithmic in n, constructing explicit tensors of high enough rank would imply superpolynomial lower bounds for general arithmetic formulas. We first give a new and arguably simpler proof of this connection. We do this by showing a structured depth reduction to depth four for arithmetic formulas. This is a simpler proof of the depth reduction results of Agrawal and Vinay [FOCS 2008], Koiran [TCS 2012], and Tavenas [MFCS 2013]. We also extend the result of Raz to homogeneous formulas. In this setting, wee show that such a connection holds for any d that is sub-polynomial in n. As a corollary of our extension, we show that for any n and d where d is O(log n) (as opposed to the almost-logarithmic in n as in Raz’s result), constructing explicit tensors of high enough rank would imply superpolynomial lower bounds for general arithmetic formulas.

Joint work with Mrinal Kumar, Ramprasad Saptharishi and V. Vinay Available at https://eccc.weizmann.ac.il/report/2016/096/.

• An approach to Distributed Synthesis [Oct 18 2017 +]

Date: October 18, 2017.
Time: 11:00am to 12:00pm.
Venue: Conference room, 1st Floor, CSE Kanwal Rekhi Bldg

The Distributed Synthesis Problem(DSP) refers to the question of algorithmically synthesizing distributed systems from specifications. We consider some specification classes known to have a decidable DSP and show that these decidability results can be explained alternatively, in terms of the "bounded-model property" of a particular class of structures. Using this approach, we are able to show that DSP is decidable on a larger class of specifications than known previously.

• A finitary analogue of the downward Lowenheim-Skolem property [Sep 20 2017 +]

Date: September 20, 2017.
Time: 11:00am to 12:00pm.
Venue: Room 105, New CSE Building.

We present a model-theoretic property of finite structures, that can be seen as a finitary analogue of the well-studied downward Lowenheim-Skolem property from classical model theory. We call this property the *equivalent bounded substructure property*, denoted EBSP. Intuitively, EBSP states that a large finite structure contains a small "logically similar" substructure, where logical similarity means indistinguishability with respect to sentences of FO/MSO having a given quantifier nesting depth. It turns out that this simply stated property is enjoyed by a variety of classes of interest in computer science: examples include regular languages of words, trees (unordered, ordered, ranked or partially ranked) and nested words, and various classes of graphs, such as cographs, graph classes of bounded tree-depth, those of bounded shrub-depth and m-partite cographs. Further, EBSP remains preserved in the classes generated from the above using various well-studied operations, such as complementation, transpose, the line-graph operation, disjoint union, join, and various products including the Cartesian and tensor products. Furthermore, by considering relations other than "substructure" in the EBSP definition, many more computationally interesting classes turn out to satisfy (the corresponding variant of) EBSP: these include graph classes of bounded tree-width, those of bounded clique-width, and those of bounded rank-width.

All of the aforementioned classes admit natural tree representations for their structures. We use this fact to show that the small and logically similar substructure of a large structure in any of these classes, can be computed in time linear in the size of the tree representation of the structure, giving linear time fixed parameter tractable (f.p.t.) algorithms for checking FO/MSO definable properties of the large structure (algorithmic meta-theorems). We conclude by presenting a strengthening of EBSP, that asserts "logical self-similarity at all scales" for a suitable notion of scale. We call this the *logical fractal* property and show that most of the classes mentioned above are indeed, logical fractals.

• Approximating Geometric Knapsack via L-packings [Aug 23 2017 +]

Date: August 23, 2017.
Time: 11:30am to 12:30pm.
Venue: Conference room, KReSIT, first floor.

We study the two-dimensional geometric knapsack problem (2DK), a geometric variant of the classical knapsack problem. In this problem we are given a set of axis-aligned rectangular items, each one with an associated profit, and an axis-aligned square knapsack. The goal is to find a (non-overlapping) packing of a maximum profit subset of items inside the knapsack without rotating items. This is a very well-studied optimization problem and finds applications in scheduling, memory allocation, advertisement placement etc. The best-known polynomial-time approximation factor for this problem (even just in the cardinality case) is $$2+\epsilon$$ [Jansen and Zhang, SODA 2004].

After more than a decade, in this paper we break the $$2$$-approximation barrier, achieving a polynomial-time $$17/9+\epsilon$$ (which is less than $$1.89$$) approximation, which improves to $$558/325+\epsilon$$ (i.e $$1.72$$) in the cardinality case.

We also consider the variant of the problem with rotations (2DKR) , where the items can be rotated by 90 degrees. Also in this case the best-known polynomial-time approximation factor (even for the cardinality case) is $$2+\epsilon$$ [Jansen and Zhang, SODA 2004]. Exploiting part of the machinery developed for 2DK plus a few additional ideas, we obtain a polynomial-time $$3/2+\epsilon$$-approximation for 2DKR, which improves to $$4/3+\epsilon$$ in the cardinality case.

This is a joint work with Waldo Galvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala and Andreas Wiese. This result will appear in FOCS 2017.

• General Strong-Polarization [Aug 11 2017 +]

Date: August 11, 2017.
Time: 11:30am to 12:30pm.
Venue: 105, New CC, first floor.

A martingale is a sequence of random variables that maintain their future expected value conditioned on the past. A $$[0,1]$$-bounded martingale is said to polarize if it converges in the limit to either $$0$$ or $$1$$ with probability $$1$$. A martingale is said to polarize strongly, if in $$t$$ steps it is sub-exponentially close to its limit with all but exponentially small probability. In 2008, Arikan built a powerful class of error-correcting codes called Polar codes. The essence of his theory associates a martingale with every invertible square matrix over a field (and a channel) and showed that polarization of the martingale leads to a construction of codes that converge to Shannon capacity. In 2013, Guruswami and Xia, and independently Hassani et al. showed that strong polarization of the Arikan martingale leads to codes that converge to Shannon capacity at finite block lengths, specifically at lengths that are inverse polynomial in the gap to capacity, thereby resolving a major mathematical challenge associated with the attainment of Shannon capacity.

We show that a simple necessary condition for an invertible matrix to polarize over any non-trivial channel is also sufficient for strong polarization over all symmetric channels over all prime fields. Previously the only matrix which was known to polarize strongly was the $$2\times 2$$ Hadamard matrix. In addition to the generality of our result, it also leads to arguably simpler proofs. The essence of our proof is a local definition'' of polarization which only restricts the evolution of the martingale in a single step, and a general theorem showing the local polarization suffices for strong polarization.

In this talk I will introduce polarization and polar codes and, time permitting, present a full proof of our main theorem. No prior background on polar codes will be assumed.

Based on joint work with Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran and Atri Rudra.

• Derandomizing Isolation Lemma: A geometric approach [Jul 31 2017 +]

Date: July 31, 2017.
Time: 2pm to 3pm
Venue: Conference Room, Kanwal Rekhi Building, first floor.

We present a geometric approach towards derandomizing the Isolation lemma for a given family of subsets, i.e., deterministically constructing a weight assignment which ensures a unique minimum weight set in the family. The idea is to work with a polytope corresponding to the family of sets. In this talk, we present the approach in terms of general polytopes and describe a sufficient condition on the polytope for this approach to work. The approach gives a quasi-polynomially bounded weight assignment. Finally, we show that two specific families - perfect matchings in bipartite graphs and common base sets of two matroids - satisfy the required condition and thus, we get an isolating weight assignment for these cases. This also puts the two problems in quasi-NC.
Based on joint works with Stephen Fenner and Thomas Thierauf.