Abstract

In this talk, I will discuss the following two results:

Our main result shows that the class of polynomials of polynomially bounded degree that can be approximated by monotone circuits of polynomial size can also be computed by monotone circuits of polynomial size. As a Cororally, we extend and prove such a result to other well-studied complexity classes VBP and VNP as well.

The second part of our result is the study of a variant of the determinant polynomial, called the "Determinant without-k cycles" obtained by summing over all signed cycle covers that avoid length k cycles. We show that such a variant is complete for VBP when k=1 and is complete for VNP for all k>=2 (over all fields).

These results will appear in LATIN 2022.

Abstract

We show that given a SM instance G as input we can find a largest collection of pairwise edge-disjoint stable matchings of G in time linear in the input size. This extends two classical results:

1.The Gale-Shapley algorithm, which can find at most two ("extreme") pairwise edge-disjoint stable matchings of G in linear time

2.The polynomial-time algorithm for finding a largest collection of pairwise edge-disjoint perfect matchings (without the stability requirement) in a bipartite graph, obtained by combining König's characterization with Tutte's f-factor algorithm.

Abstract

We study algorithms and data structures for problems related to group theory. We design linear and nearly linear-time algorithms for the group isomorphism problem for some restricted group classes. We also design space efficient data structures for groups and compact data structures for Dedekind groups and finite rings. More precisely,

1) We design a linear-time algorithm to factor Hamiltonian groups. This allows us to obtain an $\mathcal{O}(n)$ algorithm for the isomorphism problem of Hamiltonian groups, where $n$ is the order of the groups.

2) We design a nearly linear-time algorithm to find a maximal abelian direct factor of an input group. As a byproduct we obtain an $\tilde{\mathcal{O}}(n)$ isomorphism for groups that can be decomposed as a direct product of a nonabelian group of bounded order and an abelian group, where $n$ is the order of the groups.

3) We show that for any $\delta, 1/\log n \le \delta \le 1$, there is an $\mathcal{O}(n^{1+\delta}/\delta)$ space representation for groups of order $n$ with $\mathcal{O}(1/\delta)$ query-time.

Abstract

We consider manipulation strategies for the rank-maximal matching problem. Let G=(A \cup P, E) be a bipartite graph such that A denotes a set of applicants and P a set of posts. Each applicant a \in A has a preference list over the set of his neighbours in G, possibly involving ties. A matching M is any subset of edges from E such that no two edges of M share an endpoint. A rank-maximal matching is one in which the maximum number of applicants is matched to their rank one posts, subject to this condition, the maximum number of applicants is matched to their rank two posts and so on. A central authority matches applicants to posts in G using one of rank-maximal matchings. Let a_1 be the sole manipulative applicant, who knows the preference lists of all the other applicants and wants to falsify his preference list, so that he has a chance of getting better posts than if he were truthful, i.e., than if he gave a true preference list.

We give three manipulation strategies for a_1 in this paper. In the first problem ‘best nonfirst’, the manipulative applicant a_1 wants to ensure that he is never matched to any post worse than the most preferred post among those of rank greater than one and obtainable, when he is truthful. In the second strategy ‘min max’ the manipulator wants to construct a preference list for a_1 such that the worst post he can become matched to by the central authority is best possible or in other words, a_1 wants to minimize the maximal rank of a post he can become matched to. To be able to carry out strategy ‘best nonfirst’, a_1 only needs to know the most preferred post of each applicant, whereas putting into effect ‘min max’ requires the knowledge of whole preference lists of all applicants. The last manipulation strategy ‘improve best’ guarantees that a_1 is matched to his most preferred post in at least one rank-maximal matching.

Abstract

Given a bipartite graph G=(A∪B,E) with strict preference lists and e∗∈E,we ask if there exists a popular matching in G that contains the edge e∗. We call this the popular edge problem. A matching M is popular if there is no matching M′ such that the vertices that prefer M′ to M outnumber those that prefer M to M′. It is known that every stable matching is popular; however G may have no stable matching with the edge e∗ in it. In this paper we identify another natural subclass of popular matchings called “dominant matchings” and show that if there is a popular matching that contains the edge e∗, then there is either a stable matching that contains e∗ or a dominant matching that contains e∗. This allows us to design a linear time algorithm for the popular edge problem. We also use dominant matchings to efficiently test if every popular matching in G is stable or not.

Abstract

Greedy algorithms are algorithms where a globally optimal solution can be reached by making a series of locally optimal steps. While the algorithms themselves tend to be straightforward, proving them correct can be tricky at times. In this talk, we will look at one approach to developing greedy algorithms in Haskell. Haskell is a functional programming language where it is possible to develop a program as a sequence of refinements, along with equational reasoning proving its correctness.
In this talk, we shall illustrate this approach by considering various examples of greedy algorithms on lists, including sorting, and a problem involving fractions in TeX.

Abstract

We begin with a brief overview of disjoint paths problems. Our main focus will be on discussing the recent breakthrough of finding shortest 2 disjoint paths (S2DP), and then developing tools to evaluate the permanent of a matrix of integer polynomials, modulo 2^k, in parallel, thereby reducing the complexity of the S2DP from P/poly to ParityL/poly. After recognizing the S2DP problem as a special case of finding shortest k-disjoint cycles via p-points, we shall also present an upper bound on the complexity of (k=1), (k=2, p=2) and (k=2, p=3) cases. For all other values of (k,p) no non-trivial upper bounds are known, and the problem still remains open.

Abstract

Colour coding is an algorithmic technique which was invented [1] around 25 years ago for solving an open problem which lies on the boundary of classical and parameterized algorithms. This talk is a gentle introduction to this technique. We will start with the story which led to its discovery, see one or two simple applications of the technique (including the solution to that previously open problem), and take a brief look at a couple of newer algorithmic techniques which are variations on the general idea behind colour coding.

[1] Alon, Yuster and Zwick. "Color-coding.". Journal of the ACM 42(4), 1995.

Abstract

A graph is planar if it can be drawn on a plane such that its edges intersect only at their endpoints. The Planarity Testing problem asks whether a given graph is planar. We will see an algorithm for planarity testing and embedding in the dynamic complexity setting under small changes. In the static complexity world, we assume that the input is given to us as a whole at the beginning itself while in the dynamic complexity setting, input structure may change at any point in time. We will see an introduction to a relatively new field of study - Dynamic Complexity, in general, which finds its formal origins in the works of Immerman and Patnaik [1997].
Note: This is a work in progress with Prof. Samir Datta and Anish Mukherjee

Abstract

Given a directed graph G and two vertices s and t, the reachability problem asks if there exists a path from s to t or not. Reachability is a complete problem for class NL. The question whether reachability can be solved by an unambiguous nondeterministic logspace machine (UL) is a longstanding open question.. In the perfect matching problem, we would like to decide if a graph has a perfect matching or not. There is an efficient sequential algorithm known for the perfect matching problem. However, the question, whether there exists an efficient parallel algorithm (NC) for perfect matching, is still open. The desired bound for both these problems can be achieved using a common tool, known as the isolation lemma. It was shown that if we can efficiently derandomize the isolation lemma for paths and perfect matchings then reachability can be solved in UL and perfect matching can be solved in SPL (which is a subclass of NC). In this talk, I will present our result where we derandomize the isolation lemma for paths and bipartite perfect matchings in $O(\log n)$ Genus Graphs.

Abstract

We will give a gentle introduction to extensive form games with imperfect recall, and describe some new complexity results. Using a one-to-one correspondence between these games on one side and multivariate polynomials on the other side, we show that in general, solving games with imperfect recall is as hard as solving certain problems of the first order theory of reals. We establish square-root-sum hardness for a specific class called A-loss games. On the positive side, we find restrictions on games and strategies motivated by Bridge bidding that give polynomial-time complexity.

Abstract

We look at the problem of fairly allocating a set of indivisible items to agents. If the items are desirable (i.e. goods), then Lipton et al. give an algorithm to obtain an approximately fair allocation. If the items are undesirable (i.e. chores), we show how to obtain similar guarantees. If time permits, we will look at fairly allocating divisible items as well.

Abstract

We will discuss an old result of Torben Hagerup that gives a parallel algorithm for the problem of depth first search in undirected planar graphs that runs in O(log n) time with polynomial number of processors. The model used in his paper is CRCW PRAM machines. We'll observe that his algorithm can be implemented in logspace with an oracle for distance computation in planar graphs. If time permits, we'll look briefly at ideas from our ongoing work here we attempt to extend techniques used in this paper for DFS in directed planar graphs.

Abstract

Sperner's Lemma is a very useful tool to algorithmically find approximate fixed points. Using Sperner's, we will see an elegant way to (approximately) fairly allocate a cake to children.

Abstract

Koiran’s real tau-conjecture asserts that if a non-zero real univariate polynomial $f(x)$ can be written as $\sum_{i=1}^k \prod_{j=1}^m f_{ij}$ where each $f_{ij}$ contains at most $t$ monomials, then the number of distinct real roots of f is polynomially bounded in kmt. Assuming the conjecture with parameter $m = \omega(1)$, one can show that $VP \neq VNP$ (i.e. symbolic permanent requires superpolynomial-size circuit).
In this talk, we propose a tau-conjecture for sum-of-squares (SOS) model (equivalently, $m = 2$). For a univariate polynomial $f$ , we study the sum-of-squares representation (SOS), i.e. $f = c_1f_1^2 +.... + c_s f_s^2$, where $c_i$ are field elements and the $f_i$’s are univariate polynomials. The size of the representation is the number of monomials that appear across the $f_i$’s. Its minimum is the support-sum $S(f)$ of $f$. We conjecture that any real univariate $f$ can have at most $O(S(f))$-many real roots. A random polynomial satisfies this property. We connect this conjecture with two central open questions in algebraic complexity– matrix rigidity and VP vs. VNP.
Furthermore, strengthening the conjecture to sum-of-cubes (SOC) implies a polynomial time algorithm for blackbox-PIT (Polynomial Identity Testing). This is the first time a tau-conjecture has been shown to give a polynomial-time PIT.
I will provide the details depending on the time. The talk is intended for a general theory audience. This talk is mostly based on the paper "Real tau-Conjecture for sum-of-squares: A unified approach to lower bound and derandomization" [ pdf], accepted at CSR'21. I will also be referring and using results from the paper "A Largish Sum-of-Squares Implies Circuit Hardness and Derandomization" [pdf], which is a joint work with Nitin Saxena (IIT Kanpur) & Thomas Thieruaf (Aalen University), published in ITCS'21.

Abstract

Valiant (1980) showed that general arithmetic circuits with negation can be exponentially more powerful than monotone ones. We give the first improvement to this classical result: we construct a family of polynomials $P_n$ in $n$ variables, each of its monomials has non-negative coefficient, such that $P_n$ can be computed by a polynomial-size \emph{depth-three formula} but every monotone circuit computing it has size $2^{\Omega(n^{1/4}/\log(n))}$. The polynomial $P_n$ embeds the $\text{SINK}\circ \text{XOR}$ function devised recently by Chattopadhyay, Mande and Sherif (2020) to refute the Log-Approximate-Rank Conjecture in communication complexity. To prove our lower bound for $P_n$, we develop a general connection between corruption of combinatorial rectangles by any function $f \circ \text{XOR}$ and corruption of product polynomials by a certain polynomial $P^f$ that is an arithmetic embedding of $f$. This connection should be of independent interest. Using further ideas from communication complexity, we construct another family of set-multilinear polynomials $f_{n,m}$ such that both $F_{n,m} - \epsilon\cdot f_{n,m}$ and $F_{n,m} + \epsilon\cdot f_{n,m}$ have monotone circuit complexity $2^{\Omega(n/\log(n))}$ if $\epsilon \geq 2^{- \Omega( m )}$ and $F_{n,m} \coloneqq \prod_{i=1}^n \big(x_{i,1} +\cdots+x_{i,m}\big)$, with $m = O( n/\log n )$. The polynomials $f_{n,m}$ have 0/1 coefficients and are in VNP. Proving such lower bounds for monotone circuits has been advocated recently by Hrube\v{s} (2020) as a first step towards proving lower bounds against \emph{general circuits} via his new approach.

Abstract

Young Tableaux are combinatorial objects which get used in representation theory. We will start by defining the family of semi-standard Young tableaux parameterised by three parameters $n$, $r$ and $d$, and then state the factoring problem for this family. Semistandard Young tableaux index a basis of the coordinate ring of the Grassmannian. Factoring rectangular semi-standard tableau into factors which have the combinatorial property of being T-invariant has geometric implications. Here T is the the group of diagonal $n \times n$ matrices. We show that tableaux which cannot be factored are in bijection with the Hilbert basis of a rational polyhedral cone. Rectangular T-invariant tableaux index a basis of the coordinate ring of the T-quotient of the Grassmannian for the Plucker embedding. Tableaux which cannot be factored index a generating set of this ring. When $n=7$ and $r=3$, we show using Plucker relations that the generating set can be further reduced, This translates into projective normality of the T-quotient of the Grassmannian. Our proof is computational.

Abstract

The problem of constructing depth-first search trees in planar graphs was shown to be in NC by Kao. We present an algorithm building on ideas from Hagerup's paper on undirected planar DFS to find a path separator and then apply divide and conquer to construct a DFS tree in parallel. The algorithm can be implemented in the complexity class AC1($UL \cap co-UL)$, which is contained in $AC2$ .

Abstract

A catalytic Turing machine is a Turing machine equipped with an auxiliary tape that is initially filled with arbitrary content; the machine can read or write anything on the auxiliary tape during the computation, however, it is restricted to halt with the same content on the auxiliary tape as the original. We consider several natural variants of catalytic Turing machines with O(log n) size work space and O(n^c) size auxiliary space. We study the notion of unambiguous catalytic computation. Unambiguous computation is a well-studied and natural restriction of nondeterministic computation in which a Turing machine accepts ‘Yes’ instances along a unique path. We show that, under a widely believed derandomization assumption, unambiguous catalytic Turing machines are as powerful as nondeterministic catalytic Turing machines. Our result is analogous to a previously known result on conventional Turing machines. The proof is a combination of ideas used in earlier work on nondeterministic catalytic computation work, Reinhardt and Allender’s double-counting techniques, and some other ideas. We also explore the power of the catalytic computational model with the relaxation to lose some bits of the auxiliary space. We define catalytic Turing machines that are allowed to lose constant many arbitrary bits of the auxiliary tape as k-lossy catalytic Turing machines. We prove that, somewhat surprisingly, the k-lossy catalytic Turing machines are not more powerful than the standard catalytic Turing machines. Our proof involves traversing the undirected configuration graph of a k-lossy catalytic Turing machine in a standard catalytic Turing machine using the Euler tour technique and FKS hashing scheme.

Abstract

We prove two results that shed new light on the monotone complexity of the spanning tree polynomial, a classic polynomial in algebraic complexity and beyond. First, we show that the spanning tree polynomials defined over constant-degree expander graphs, have strongly exponential monotone arithmetic complexity. This yields the first strongly exponential lower bound on the monotone arithmetic circuit complexity for a polynomial in VP. Recently, Pavel Hrubes proposed a program to prove lower bounds against general arithmetic circuits by proving a certain type of lower bounds for monotone arithmetic circuits. We prove first such lower bound for a family of polynomials inside VP (which is the family of spanning tree polynomials). This is proved via a new connection to communication complexity which could be of interest beyond algebraic complexity. This is based on a joint work with Arkadev Chattopadhyay (TIFR), Rajit Datta (Goldman-Sachs), and Partha Mukhopadhyay (CMI). The paper is going to appear in ITCS 2022.

Abstract

In this talk, we look at an elegant way to improve on Steiner Tree and related problems using a very familiar technique namely, Inclusion-Exclusion. First, we see how to solve the Hamiltonian path problem using Inclusion-Exclusion [Richard M. Karp, 1982] in $O^*(2^n)$ time and polynomial space where n is the number of vertices. Then, we look at the following result by [J. Nederlof, Algorithmica 2013]: Given a graph $G=(V,E)$ with n vertices, a subset of vertices $k \subseteq V$ (called terminals) and positive integer weights not larger than $c$, to compute a minimum Steiner Tree in $O^*(2^k c)$ time and $O^*(c)$ space, where the $O^*$ notation omits terms bounded by a polynomial in the input-size. To obtain the result, a generalization of walks, called branching walks, is considered and combined with the Inclusion-Exclusion technique. This talk is based on the paper "Fast Polynomial-Space Algorithms Using Inclusion-Exclusion" Algorithmica 65, 868–884 (2013) by Jesper Nederlof. The link for the paper can be found here.

Abstract

Factoring a semiprime number into a product of its prime factors is a difficult problem. The difficulty of this problem forms the base of many cryptographic protocols such as RSA. The function that multiplies two given semiprime numbers and many other functions used in cryptographic protocols, which are 'easy' to compute but are 'difficult' to invert, are candidates for the class of functions called: 'One-way Functions'. The existence of one-way functions is still an open conjecture. Closely related to these one-way functions, is the notion of hard-core predicates. A hard-core predicate b of a one-way function f is a predicate such that b(x) cannot be efficiently guessed given only f(x). In this talk, I will discuss one-way functions and hard-core predicates, and their relevance to cryptography. I will then present the classic theorem by Goldreich and Levin which provides a hard-core predicate for every one-way function. We will also look at some applications of this theorem. This talk is based on the paper 'A Hard-Core Predicate for All One-Way Functions' by Oded Goldreich and Leonid A. Levin. The paper can be accessed here.

Abstract

A visibly pushdown automaton is a special kind of pushdown automaton in which the input letter being read uniquely determines the stack operation. The input alphabet is partitioned into 3 sets - call actions, return actions and internal actions. We call such an alphabet, a pushdown alphabet. On every call action being read, a push operation is performed on the stack. On every return action a pop operation is performed, and on every internal action the stack is left unchanged. These automata are ideal to model monolithic programs with nested function call (and possibly recursive) structure. A language over a pushdown alphabet for which there is a visibly pushdown automaton that accepts it is called a visibly pushdown language (VPL). VPLs are known to have following natural properties: Closure: VPLs are closed under union, intersection, concatenation, kleene star and renaming operations. Determinization: For every non-deterministic VPA, there is a deterministic VPA that accepts the same language. Decision Problems: Universality problem and inclusion problem are decidable for VPLs (and are known to be EXPTIME-complete) MSO Definability: The MSO theory over natural numbers with successor, unary predicates and a special binary matching predicate (that matches call actions to corresponding return actions) is expressively equivalent to VPAs (under natural semantics of finite words over a pushdown alphabet). Relation to regular tree languages: There is a mapping f of words over a pushdown alphabet to trees (over the same pushdown alphabet) s.t a language L is a VPL iff f(L) is a regular tree language. VPAs over infinite words: $\omega$ VPLs (defined as the class of languages accepted by non-deterministic VPAs with Buchi acceptance conditions) are closed under union, intersection, complementation, renaming, concatenation and $\omega$ power. $\omega$ VPAs are non determinizable (not even with Muller conditions, unlike $\omega$ regular languages). $\omega$ VPLs can also be characterized by MSO theory (interpreted over infinite words) and Regular Tree languages (of infinite trees) similar to finite word VPLs. This talk is based on the work by Rajeev Alur (University of Pennsylvania) and Madhusudan Parthasarathy (University of Illinois at Urbana-Champaign) which appeared in STOC' 04. The paper is available here

Abstract

Given a permutation $\pi$ of length $k$, an array $A$ is $\pi$-free if there are no $k$ array values that, when considered from left to right, have the same relative order as that of the permutation. For example, the array $A$ is (2,1)-free if there are no two indices $i < j$ such that $A[i] > A[j]$ and the array is (1,3,2)-free if there are no three indices $i < j < k$ such that $A[j] > A[k] > A[i]$. In particular, the set of (2,1)-free arrays are simply the set of all sorted arrays.

The problem of testing $\pi$-freeness is to distinguish arrays that are $\pi$-free from arrays that need to be modified in at least a constant fraction of their values to be $\pi$-free. This problem was first studied systematically by Newman, Rabinovich, Rajendraprasad and Sohler (Random Structures and Algorithms; 2019), where they proved that for all permutations $\pi$ of length at most 3, one can test for $\pi$-freeness in $\text{polylog}~n$ many queries, where $n$ is the array length. For permutations of length $k > 3$, they described a simple testing algorithm that makes $O(n^{1-1/k})$ queries. Most of the followup work has focused on improving the query complexity of testing $\pi$-freeness for monotone $\pi$.

In this talk, I will present a recent algorithm with query complexity $O(n^{o(1)})$ that tests $\pi$-freeness for arbitrary permutations of constant length, which significantly improves the state of the art. I will also give an overview of the analysis that involves several combinatorial ideas.

Joint work with Ilan Newman

Abstract

A function $f : D -> R$ mapping a metric space $(D,d_D)$ to a metric space $(R,d_R)$ is said to be Lipschitz if for all pairs $x, y$ in the domain $D$, the distance between their images in the range $R$ is less than or equal to the distance between $x$ and $y$ in the domain $D$. A tester for the Lipschitz property distinguishes Lipschitz functions from functions that differ from every Lipschitz function on some fraction of the domain. A local filter, given oracle access to a function $f$ and a query $x$, returns $g(x)$, where g is Lipschitz and $g$ is equal to $f$ whenever $f$ is Lipschitz. In this talk, we will mainly focus on how to design a tester for the Lipschitz property of real-valued functions over the domain $[n]$ that runs efficiently, non-adaptively and with one-sided error. We will also provide a brief overview of the results on local filters for the Lipschitz property. Additionally, we will discuss some applications of these results.

Abstract

Given an undirected graph and two pairs of vertices $(s_i, t_i)$ for $i \in \{1, 2\}$, the shortest two disjoint paths problem is to find a pair of disjoint paths of smallest total length joining $s_i$ and $t_i$ for $i \in \{1, 2\}$. In this talk, I will be presenting an algebraic approach to solving this problem that involves computation of permanents over the polynomial ring ${\mathbb{Z}}_4[X]$. In fact, we will look at a polynomial time algorithm for computing permanents over the ring ${\mathbb{Z}}_t[X]$ where $t$ is any power of 2. We will also look at a few related results and generalizations of these results in the talk.

Abstract

We introduce a model for transforming strings, that provides fine control over what modifications are allowed. The model consists of actions, each of which is enabled only when the input string conforms to a predefined template. A template can break the input up into multiple fields, and constrain the contents of each of the fields to be from pre-defined regular languages. The template can also constrain two fields to be duplicates of each other. If the input string conforms to the template, the action can be performed to modify the string. The output consists of the contents of the fields, possibly in a different order, possibly with different numbers of occurrences. Optionally, the action can also apply transductions on the contents of the fields before outputting.

We want to check that whenever the input comes from a given regular language, the output of any action also belongs to that language. We call this problem regular invariance checking. We show that this problem is decidable and is PSPACE-complete in general. For some restricted cases where there are no variable repetitions in the source and target templates (or patterns) and the regular language is given by a DFA, we show that this problem is co-NP-complete. We show that even in this restricted case, the problem is W[1]-hard with the length of the pattern as the parameter.

Abstract

In this talk, we will see a temporal logic with usual boolean connectives and temporal operators Since and Until. This logic is useful to express temporal specifications that talk about past, present and future. An important result is separation theorem which states that any complex formula in this logic can be expressed as a boolean combination of pure past, pure present and pure future formulas. In other words, it is possible to separate a formula into 3 parts that talk about only past, only present and only future. An important application of this result is an alternative proof of Kamp's theorem which states that this logic is expressively equivalent to monadic first order logic over (N, <) with free set variables. This talk is partly based on the paper titled, "The Declarative Past and Imperative Future" by Dov Gabbay which appeared in 'Temporal Logic in Specification', 1987. Proceedings published as LNCS 398, Springer in 1989. The paper is available here.

Abstract

We establish an $\epsilon$-sensitive hierarchy separation for monotone arithmetic computations. The notion of $\epsilon$-sensitive monotone lower bounds was recently introduced by Hrube\v{s}. We show the following:

1. There exists a monotone polynomial over $n$ variables in VNP that cannot be computed by $2^{o(n)}$ size monotone circuits in an $\epsilon$-sensitive way as long as $\epsilon \ge 2^{-\Omega(n)}$.
2. There exists a polynomial over $n$ variables that can be computed by polynomial size monotone circuits but cannot be computed by any monotone arithmetic branching program (ABP) of $n^{o(\log n)}$ size, even in an $\epsilon$-sensitive fashion as long as $\epsilon \ge n^{-\Omega(\log n)}$.
3. There exists a polynomial over $n$ variables that can be computed by polynomial size monotone ABP but cannot be computed in $n^{o(\log n)}$ size by monotone formulas even in an $\epsilon$-sensitive way, when $\epsilon \ge n^{-\Omega(\log n)}$.
4. There exists a polynomial over $n$ variables that can be computed by width-$4$ polynomial size monotone arithmetic branching programs (ABPs) but cannot be computed in $2^{o(n^{1/d})}$ size by monotone, unbounded fan-in formulas of product depth $d$ even in an $\epsilon$-sensitive way, when $\epsilon \ge 2^{-\Omega(n^{1/d})}$. This yields an $\epsilon$-sensitive separation of constant-depth monotone formulas and constant-width monotone ABPs. It seems that even an ordinary separation of the two classes was not known.

An interesting feature of our separations is that in each case the polynomial exhibited is obtained from a graph inner-product polynomial by choosing an appropriate graph topology. The closely related graph inner-product Boolean function for expander graphs was invented by Hayes, also independently by Pitassi, in the context of best-partition multiparty communication complexity. THis is based on a joint work with Arkadev Chattopadhyay (TIFR) and Partha Mukhopadhyay (CMI).