### 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, Abstract

The 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, n-r_1]$. We mention some applications to the decision tree and communication complexity of symmetric functions.

• The NOF Multiparty Communication Complexity of Composed Functions
International Conference on Automata, Languages and Programming (ICALP), 2012
To appear in Computational Complexity
PDF, Abstract

We 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 non-simultaneous 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 well-known 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:137--166, 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 non-trivial bound on the corresponding Ramsey number. Furthermore, we give an explicit coloring of $[N] \times [N]$ without a monochromatic 2-dimensional corner and use this to obtain an explicit 3-party 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
IEEE Conference on Computational Complexity (CCC), 2012
To appear in Transactions on Computation Theory
PDF, Abstract

In 1989 Kushilevitz (FOCS) initiated the study of information-theoretic 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 worst-case as well as average-case 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 worst-case and average-case approximate privacy of protocols and their communication cost for Vickrey-auctions.

Further, we relate the notion of average-case 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
Electronic Colloquium on Computational Complexity (ECCC), 2008
PDF, Abstract

We obtain a lower bound of $\Omega\bigg(\frac{n^{\frac{1}{k+1}}}{2^{2^k} (k-1)2^{k-1}}\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 tree-like, degree $k-1$ threshold systems and superpolynomial size lower bounds for Lovász-Schrijver proofs.

Sherstov (ECCC 2007) recently developed a novel technique to obtain lower bounds on two-party communication using the approximate polynomial degree of boolean functions. We obtain our results by extending his technique to the multi-party setting using ideas from Chattopadhyay (FOCS 2007).

A similar bound for Disjointness has been recently and independently obtained by Lee and Shraibman.

• On the Non-Deterministic Communication Complexity of Regular Languages
International Journal of Foundations of Computer Science, 2010
Special issue for Developments in Language Theory (DLT), 2008
PDF, Abstract

In this paper we study the non-deterministic communication complexity of regular languages. We show that a regular language has either constant or at least logarithmic non-deterministic 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 non-deterministic setting.

• On Bus Graph Realizability
with Melanie Coggan, Paul Di Marco, Alain Doyon, Liam Flookes, Samuli Heilala, Ethan Kim, Jonathan Li On Wing, Louis-Francois Preville-Ratelle, Sue Whitesides, Nuo Yu
Canadian Conference on Computational Geometry (CCCG), 2007
PDF, Abstract

We 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 NP-complete, as well as related problems.

### Teaching

Office Hours: Wednesdays 4pm-5pm 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 Programming

### Contact 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