I am a postdoctoral researcher at Simon Fraser University hosted by Valentine Kabanets. I am interested in Complexity Theory. More specifically, I am interested in circuit complexity and communication complexity and the interplay between these two seemingly different areas.

Mobile: +1 604 704 3901 (alt: +1 206 355 9372)

Office: TASC1 8201

School of Computing Science, Simon Fraser University, 8888 University Drive, Burnaby, B.C., Canada V5A 1S6

Earlier I was a postdoctoral fellow at the University of Haifa hosted by Or Meir. During this time I attended the Simons program on Lowerbounds in Computational Complextiy at University of California, Berkeley as a visiting postdoc. I completed my PhD (thesis, joint winner of IBM India Outstanding PhD Thesis Award) from Indian Institute of Technology, Madras under the guidance of Jayalal Sarma. Prior to that I obtained my masters degree (thesis) also from Indian Institute of Technology, Madras under the guidance of Shankar Balachandran.

- [
*Upcoming*] Query-to-communication lifting for BPP using inner product -- jointly with Arkadev Chattopadhyay, Yuval Filmus, Or Meir, Toniann Pitassi**Abstract**We prove a new query-to-communication lifting for randomized protocols, with inner product as gadget. This allows us to use a much smaller gadget, leading to a more efficient lifting. Prior to this work, such a theorem was known only for deterministic protocols, due to Chattopadhyay et al. and Wu et al.. The only query-to-communication lifting result for randomized protocols, due to G"o"os, Pitassi and Watson, used the much larger indexing gadget.

Our proof also provides a unified treatment of randomized and deterministic lifting. Most existing proofs of deterministic lifting theorems use a measure of information known as*thickness*. In contrast, G"o"os, Pitassi and Watson used blockwise min-entropy as a measure of information. Our proof uses the blockwise min-entropy framework to prove lifting theorems in both settings in a unified way.

- Improved composition theorems for functions and relations -- jointly with Or Meir
**Abstract**One of the central problems in complexity theory is to prove super-logarithmic depth bounds for circuits computing a problem in \(\text{P}\), i.e., to prove that \(\text{P} \not\subseteq \text{NC}^{1}.\) As an approach for this question, Karchmer, Raz and Wigderson proposed a conjecture called the KRW conjecture, which if true, would imply that \(\text{P} \not\subseteq \text{NC}^{1}\).

Since proving this conjecture is currently considered an extremely difficult problem, previous works by Edmonds, Impagliazzo, Rudich and Sgall, Håstad and Wigderson and Gavinsky, Meir, Weinstein and Wigderson considered weaker variants of the conjecture. In this work we significantly improve the parameters in these variants, achieving almost tight lower bounds.- Conference version, appeared in Random 2018
- Full version -- coming soon,

- Characterization and Lower Bounds for Branching Program Size Using Projective Dimension -- jointly with Krishnamoorthy Dinesh and Jayalal Sarma
**Abstract**We study projective dimension, a graph parameter, denoted by \(\mathsf{pd}(G)\) for a bipartite graph \(G\), introduced by Pudlák and Rödl. For a Boolean function \(f\) (on \(n\) bits), Pudl\'ak and R"odl associated a bipartite graph \(G_f\) and showed that size of the optimal branching program computing \(f\), denoted by \(\mathsf{bpsize}(f)\), is at least \(\mathsf{pd}(G_f)\) (also denoted by \(\mathsf{pd}(f)\)). Hence, proving lower bounds for \(\mathsf{pd}(f)\) imply lower bounds for \(\mathsf{bpsize}(f)\). Despite several attempts (Pudlák and Rödl, Rónyai et.al,), proving super-linear lower bounds for projective dimension of explicit families of graphs has remained elusive.

We observe that there exist a Boolean function \(f\) for which the gap between the \(\mathsf{pd}(f)\) and \(\text{bpsize}(f)\) is \(2^{\Omega(n)}\). Motivated by the argument in Pudlák and Rödl, we define two variants of projective dimension -*projective dimension with intersection dimension 1*, denoted by \(\mathsf{upd}(f)\), and*bitwise decomposable projective dimension*, denoted by \(\mathsf{bitpdim}(f)\). We show the following results :- We observe that there exist a Boolean function \(f\) for which the gap between \(\mathsf{upd}(f)\) and \(\text{bpsize}(f)\) is \(2^{\Omega(n)}\). In contrast, we also show that the bitwise decomposable projective dimension characterizes size of the branching program up to a polynomial factor. That is, there exists a constant \(c>0\) and for any function \(f\), \[\mathsf{bitpdim}(f)/6 \le \textrm{bpsize}(f) \le (\mathsf{bitpdim}(f))^c\]
- We introduce a new candidate family of functions \(f\) for showing super-polynomial lower bounds for \(\mathsf{bitpdim}(f)\). As our main result, for this family of functions, we demonstrate gaps between \(\mathsf{pd}(f)\) and the above two new measures for \(f\) : \[\mathsf{pd}(f) = O(\sqrt{n})\] \[\mathsf{upd}(f) = \Omega(n)\] \[\mathsf{bitpdim}(f)= \Omega\left(\frac{n^{1.5}}{\log n}\right)\] We adapt Nechiporuk's techniques for our linear algebraic setting to prove the best known \(\text{bpsize}\) lower bounds for \(\text{bpdim}\). Motivated by this linear algebraic setting of our main result, we derive exponential lower bounds for two restricted variants of \(\mathsf{pd}(f)\) and \(\mathsf{upd}(f)\), by observing that they are exactly equal to well-studied graph parameters - bipartite clique cover number and bipartite partition number, respectively.

- Conference version, appeard in FSTTCS 2016
- Journal version, appeared in ACM Transactions on Computation Theory
- Full Version

- Depth Lower Bounds against Circuits with Sparse Orientation -- jointly with Jayalal Sarma
**Abstract**We study depth lower bounds against non-monotone circuits, parametrized by a new measure of non-monotonicity: the orientation of a function \(f\) is the characteristic vector of the minimum sized set of negated variables needed in any DeMorgan circuit (circuits where negations appear only at the leaves) computing \(f\). We prove trade-off results between the depth and the weight/structure of the orientation vectors in any circuit \(C\) computing the \(\textrm{CLIQUE}\) function on an \(n\) vertex graph. We prove that if \(C\) is of depth \(d\) and each gate computes a Boolean function with orientation of weight at most \(w\) (in terms of the inputs to \(C\)), then \(d \times w\) must be \(\Omega(n)\). In particular, if the weights are \(o(\frac{n}{\log^k n})\), then \(C\) must be of depth \(\omega(\log^k n)\).

We prove a barrier for our general technique. However, using specific properties of the \(\textrm{CLIQUE}\) function (used in Amano and Maruoka) and the Karchmer--Wigderson framework (Karchmer and Wigderson), we go beyond the limitations and obtain lower bounds when the weight restrictions are less stringent. We then study the depth lower bounds when the structure of the orientation vector is restricted. Asymptotic improvements to our results (in the restricted setting) separates \(\text{NP}\) from \(\text{NC}\).

As our main tool, we generalize Karchmer--Wigderson games (Karchmer and Wigderson) for monotone functions to work for non-monotone circuits parametrized by the weight/structure of the orientation. We also prove structural results about orientation and prove connections between number of negations and weight of orientations required to compute a function.- Conference version, appeard in COCOON 2014
- Journal version, appeared in Fundamenta Informaticae
- Full Version

- Subclasses of Baxter Permutations Based on Pattern Avoidance -- jointly with Shankar Balachandran
**Abstract**Baxter permutations are a class of permutations which are in bijection with a class of floorplans that arise in chip design called mosaic floorplans. We study a subclass of mosaic floorplans called \(\text{hfo}-k\) defined from mosaic floorplans by placing certain geometric restrictions. This naturally leads to studying a subclass of Baxter permutations. This subclass of Baxter permutations are characterized by pattern avoidance. We establish a bijection, between the subclass of floorplans we study and a subclass of Baxter permutations, based on the analogy between decomposition of a floorplan into smaller blocks and

*block*decomposition of permutations. Apart from the characterization, we also answer combinatorial questions on these classes. We give an algebraic generating function (but without a closed form solution) for the number of permutations, an exponential lower bound on growth rate, and a linear time algorithm for deciding membership in each subclass. Based on the recurrence relation describing the class, we also give a polynomial time algorithm for enumeration. We finally prove that Baxter permutations are closed under inverse based on an argument inspired from the geometry of the corresponding mosaic floorplans. This proof also establishes that the subclass of Baxter permutations we study are also closed under inverse. Characterizing permutations instead of the corresponding floorplans can be helpful in reasoning about the solution space and in designing efficient algorithms for floorplanning.- Conference version, appeard in CSR 2016
- Full Version

Naive \(\stackrel{?}{=}\) Optimal - A course on KRW conjecture and lifting theorems