Research
My research area is theoretical computer science. More specifically, currently I am interested in communication complexity, circuit complexity, analysis of boolean functions and matrices, pseudorandomness  structure vs randomness in computer science and mathematics, and additive combinatorics.
Publications

Spectral Norm of Symmetric Functions
with Omar Fawzi, Hamed Hatami
International Workshop on Randomization and Computation (RANDOM), 2012
PDF, AbstractThe spectral norm of a Boolean function $f:\{0,1\}^n \to \{1,1\}$ is the sum of the absolute values of its Fourier coefficients. This quantity provides useful upper and lower bounds on the complexity of a function in areas such as learning theory, circuit complexity, and communication complexity. In this paper, we give a combinatorial characterization for the spectral norm of symmetric functions. We show that the logarithm of the spectral norm is of the same order of magnitude as $r(f)\log(n/r(f))$ where $r(f) = \max\{r_0,r_1\}$, and $r_0$ and $r_1$ are the smallest integers less than $n/2$ such that $f(x)$ or $f(x) \cdot parity(x)$ is constant for all $x$ with $\sum x_i \in [r_0, nr_1]$. We mention some applications to the decision tree and communication complexity of symmetric functions.

The NOF Multiparty Communication Complexity of Composed Functions
with Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen
International Conference on Automata, Languages and Programming (ICALP), 2012
To appear in Computational Complexity
PDF, AbstractWe study the $k$party `number on the forehead' communication complexity of composed functions $f \circ \vec{g}$, where $f:\{0,1\}^n \to \{\pm 1\}$, $\vec{g} = (g_1,\ldots,g_n)$, $g_i : \{0,1\}^k \to \{0,1\}$ and for $(x_1,\ldots,x_k) \in (\{0,1\}^n)^k$, $f \circ \vec{g}(x_1,\ldots,x_k) = f(\ldots,g_i(x_{1,i},\ldots,x_{k,i}), \ldots)$. When $\vec{g} = (g,g,\ldots,g)$ we denote $f \circ \vec{g}$ by $f \circ g$. We show that there is an $O(\log^3 n)$ cost simultaneous protocol for $sym \circ g$ when $k > 1+\log n$, $sym$ is any symmetric function and $g$ is any function. When $k > 1 + 2 \log n$, our simultaneous protocol applies to $sym \circ \vec{g}$ with $\vec{g}$ being a vector of $n$ arbitrary functions. We also get a nonsimultaneous protocol for $sym \circ \vec{g}$ of cost $O(n/2^k \cdot \log n+ k \log n)$ for any $k \geq 2$. In the setting of $k \leq 1+\log n$, we study more closely functions of the form $majority \circ g$, $mod_m \circ g$, and $nor \circ g$, where the latter two are generalizations of the wellknown and studied functions Generalized Inner Product and Disjointness respectively. We characterize the communication complexity of these functions with respect to the choice of $g$. In doing so, we answer a question posed by Babai et al. (SIAM Journal on Computing, 33:137166, 2003) and determine the communication complexity of $majority \circ qcsb_k$, where $qcsb_k$ is the ``quadratic character of the sum of the bits'' function.
In the second part of our paper we utilize the connection between the 'number on the forehead' model and Ramsey theory to construct a large set without a $k$dimensional corner ($k$dimensional generalization of a $k$term arithmetic progression) in $(\mathbb{F}_2^n)^k$, thereby obtaining the first nontrivial bound on the corresponding Ramsey number. Furthermore, we give an explicit coloring of $[N] \times [N]$ without a monochromatic 2dimensional corner and use this to obtain an explicit 3party protocol of cost $O(\sqrt{n})$ for the $EXACT_N$ function. For $x_1,x_2,x_3$ $n$bit integers, $EXACT_N(x_1,x_2,x_3) = 1$ iff $x_1 + x_2 + x_3 = N$.

The Hardness of Being Private
with Arkadev Chattopadhyay, Stephen Cook, Lila Fontes, Michal Koucký, Toniann Pitassi
IEEE Conference on Computational Complexity (CCC), 2012
To appear in Transactions on Computation Theory
PDF, AbstractIn 1989 Kushilevitz (FOCS) initiated the study of informationtheoretic privacy within the context of communication complexity. Unfortunately, it has been shown that most interesting functions are not privately computable. The unattainability of perfect privacy for many functions motivated the study of approximate privacy. Feigenbaum et al. (EC 2010) define notions of worstcase as well as averagecase approximate privacy, and present several interesting upper bounds, and some open problems for further study. In this paper, we obtain asymptotically tight bounds on the tradeoffs between both the worstcase and averagecase approximate privacy of protocols and their communication cost for Vickreyauctions.
Further, we relate the notion of averagecase approximate privacy to other measures based on information cost of protocols. This enables us to prove exponential lower bounds on the subjective approximate privacy of protocols for computing the Intersection function, independent of its communication cost. This proves a conjecture of Feigenbaum et al.

Multiparty Communication Complexity of Disjointness
with Arkadev Chattopadhyay
Electronic Colloquium on Computational Complexity (ECCC), 2008
PDF, AbstractWe obtain a lower bound of $\Omega\bigg(\frac{n^{\frac{1}{k+1}}}{2^{2^k} (k1)2^{k1}}\bigg)$ on the $k$party randomized communication complexity of the Disjointness function in the `Number on the Forehead' model of multiparty communication. In particular, this yields a bound of $n^{\Omega(1)}$ when $k$ is a constant. The previous best lower bound for three players until recently was $\Omega(\log n)$.
Our bound separates the communication complexity classes $NP^{CC}_k$ and $BPP^{CC}_k$ for $k=o(\log \log n)$. Furthermore, by the results of Beame, Pitassi and Segerlind (SIAM Journal on Computing 2007), our bound implies proof size lower bounds for treelike, degree $k1$ threshold systems and superpolynomial size lower bounds for LovászSchrijver proofs.
Sherstov (ECCC 2007) recently developed a novel technique to obtain lower bounds on twoparty communication using the approximate polynomial degree of boolean functions. We obtain our results by extending his technique to the multiparty setting using ideas from Chattopadhyay (FOCS 2007).
A similar bound for Disjointness has been recently and independently obtained by Lee and Shraibman.

On the NonDeterministic Communication Complexity of Regular Languages
International Journal of Foundations of Computer Science, 2010
Special issue for Developments in Language Theory (DLT), 2008
PDF, AbstractIn this paper we study the nondeterministic communication complexity of regular languages. We show that a regular language has either constant or at least logarithmic nondeterministic communication complexity. We prove several linear lower bounds which we know cover a wide range of regular languages with linear complexity. Furthermore we find evidence that previous techniques (Tesson and Thérien 2005) for proving linear lower bounds, for instance in deterministic and probabilistic models, do not work in the nondeterministic setting.

On Bus Graph Realizability
with Melanie Coggan, Paul Di Marco, Alain Doyon, Liam Flookes, Samuli Heilala, Ethan Kim, Jonathan Li On Wing, LouisFrancois PrevilleRatelle, Sue Whitesides, Nuo Yu
Canadian Conference on Computational Geometry (CCCG), 2007
PDF, AbstractWe consider the following graph embedding problem: Given a bipartite graph $G = (V_1, V_2;E)$, where the maximum degree of vertices in $V_2$ is 4, can $G$ be embedded on a two dimensional grid such that each vertex in $V_1$ is drawn as a line segment along a grid line, each vertex in $V_2$ is drawn as a point at a grid point, and each edge $e = (u, v)$ for some $u \in V1$ and $v \in V_2$ is drawn as a line segment connecting $u$ and $v$, perpendicular to the line segment for $u$? We show that this problem is NPcomplete, as well as related problems.
Teaching
Office Hours:
Wednesdays 4pm5pm in McConnell 337.
Thursdays after class in the lecture room.
Any student is welcome to drop by my office (McConnell 337) at a random time to ask questions or just talk about basketball, soccer and stuff like that.
Teaching this term:
COMP 202  Foundations of ProgrammingContact Information
Email: aada followed by cs {dot} mcgill {dot} ca
Office: McConnell Engineering Building, Room 337
Snail Mail:
School of Computer Science
McGill University
3480 University Street
McConnell Engineering Building, Room 318
Montreal, QC, CANADA
H3A 2A7
Tel: 5143987071 x 00576