Research

Teaching

Contact Information

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
    with Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen
    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
    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, 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
    with Arkadev Chattopadhyay
    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:.

Tuesday 4-5pm (for COMP 531)
Monday, Thursday 4:30-5:30pm (for COMP 202)

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
COMP 531 - Advanced Theory of Computation

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
Montreal, QC, CANADA
H3A 2A7

Tel: 514-398-7071 x 00576

Back to Top