I am an assistant professor at the Department of Computer Science, University of Victoria.
My research interests are in algorithms and theory. I am particularly interested in circuit and communication complexity and the interplay between these two seemingly different areas.
Office Phone: +1-250-472-5737
Office: ECS 530, Faculty of Engineering and Computer Science, 3800 Finnerty Rd, Victoria, BC V8P 5C2
Earlier I was a postdoctoral researcher at Simon Fraser University, hosted by Valentine Kabanets and Igor Shinkar. Before that, 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 Ph.D. (thesis, joint winner of IBM India Outstanding Ph.D. Thesis Award) from Indian Institute of Technology, Madras under the guidance of Jayalal Sarma. I also did my masters (thesis) from Indian Institute of Technology, Madras under the guidance of Shankar Balachandran.
Link to Google Scholar , DBLP
Upcoming Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality -- jointly with Mohammad Jahanara and Igor Shinkar
Non-signaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoretical computer science, including to proving inapproximability results for linear programming and to constructing protocols for delegating computation. A central tool for these applications is probabilistically checkable proof (PCPs) systems that are sound against non-signaling strategies.
In this paper we show, assuming a certain geometrical hypothesis about noise robustness of non-signaling proofs (or, equivalently, about robustness to noise of solutions to the Sherali-Adams linear program), that a slight variant of the parallel repetition of the exponential-length constant-query PCP construction due to Arora et al. (JACM 1998) is sound against non-signaling strategies with constant locality.
Our proof relies on the analysis of the linearity test and agreement test (also known as the direct product test) in the non-signaling setting
Algorithms and lower bounds for de morgan formulas of low-communication leaf gates -- jointly with Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis, and Igor C. Oliveira
The class \(FORMULA[s] \circ \mathcal{G}\) consists of Boolean functions computable by size-\(s\) de Morgan formulas whose leaves are any Boolean functions from a class \(\mathcal{G}\). We give lower bounds and (SAT, Learning, and PRG) algorithms for \(FORMULA[n^{1.99}]\circ \mathcal{G}\), for classes \(\mathcal{G}\) of functions with low communication complexity. Let \(R^{(k)}(\mathcal{G})\) be the maximum \(k\)-party number-on-forehead randomized communication complexity of a function in \(\mathcal{G}\). Among other results, we show:
(1) The Generalized Inner Product function \(GIP^k_n\) cannot be computed in \(FORMULA[s]\circ \mathcal{G}\) on more than \(1/2+\varepsilon\) fraction of inputs for
\[
s = o \! \left ( \frac{n^2}{ \left(k \cdot 4^k \cdot {R}^{(k)}(\mathcal{G}) \cdot \log (n/\varepsilon) \cdot \log (1/\varepsilon) \right)^{2}} \right).
\]
This significantly extends the lower bounds against bipartite formulas obtained by [Tal17]. As a corollary, we get an average-case lower bound for \(GIP^k_n\) against \(FORMULA[n^{1.99}]\circ PTF^{k-1}\), i.e., sub-quadratic-size de Morgan formulas with degree-\((k-1)\) PTF (polynomial threshold function) gates at the bottom. Previously, only sub-linear lower bounds were known [Nis94, Vio15] for circuits with PTF gates.
(2) There is a PRG of seed length \(n/2 + O\left( \sqrt{s} \cdot R^{(2)}(\mathcal{G}) \cdot\log(s/\varepsilon) \cdot \log (1/\varepsilon) \right)\) that \(\varepsilon\)-fools \(FORMULA[s] \circ \mathcal{G}\). For the special case of \(FORMULA[s] \circ LTF\), i.e., size-\(s\) formulas with LTF (linear threshold function) gates at the bottom, we get the better seed length \(O\left(n^{1/2}\cdot s^{1/4}\cdot \log(n)\cdot \log(n/\varepsilon)\right)\). In particular, this provides the first non-trivial PRG (with seed length \(o(n)\)) for intersections of \(n\) half-spaces in the regime where \(\varepsilon \leq 1/n\), complementing a recent result of [OST19].
(3) There exists a randomized \(2^{n-t}\)-time \(\#\)SAT algorithm for \(FORMULA[s] \circ \mathcal{G}\), where
\[
t = \Omega\left(\frac{n}{\sqrt{s} \cdot \log^2(s)\cdot R^{(2)}(\mathcal{G})}\right)^{1/2}.
\]
In particular, this implies a nontrivial #SAT algorithm for \(FORMULA[n^{1.99}]\circ LTF\).
(4) The Minimum Circuit Size Problem is not in \(FORMULA[n^{1.99}] \circ XOR\); thereby making progress on hardness magnification, in connection with results from [OPS19, CJW19]. On the algorithmic side, we show that the concept class \(FORMULA[n^{1.99}] \circ XOR\) can be PAC-learned in time \(2^{O(n/\log n)}\).
Automating cutting planes is NP-hard -- jointly with Mika Göös, Ian Mertz, and Toniann Pitassi
We show that Cutting Planes (CP) proofs are hard to find: Given an unsatisfiable formula F,
1) It is NP-hard to find a CP refutation of F in time polynomial in the length of the shortest such refutation; and
2)unless Gap-Hitting-Set admits a nontrivial algorithm, one cannot find a tree-like CP refutation of F in time polynomial in the length of the shortest such refutation.
The first result extends the recent breakthrough of Atserias and Müller (FOCS 2019) that established an analogous result for Resolution. Our proofs rely on two new lifting theorems: (1) Dag-like lifting for gadgets with many output bits. (2) Tree-like lifting that simulates an r-round protocol with gadgets of query complexity \(O(logr)\) independent of input length.
Query-to-communication lifting for BPP using inner product -- jointly with Arkadev Chattopadhyay, Yuval Filmus, Or Meir, Toniann Pitassi
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
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.
Characterization and Lower Bounds for Branching Program Size Using Projective Dimension -- jointly with Krishnamoorthy Dinesh and Jayalal Sarma
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 :
Depth Lower Bounds against Circuits with Sparse Orientation -- jointly with Jayalal Sarma
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.
Subclasses of Baxter Permutations Based on Pattern Avoidance -- jointly with Shankar Balachandran
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.
CSC 482A / CSC 582A : Communication complexity and its applications