Short Bio

The Life You Can Save


My research interests lie in theoretical computer science and in understanding the inherent limitations of computers and computation. 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.


  • On the Spectral Properties of Symmetric Functions
    with Omar Fawzi, Raghav Kulkarni
    Arxiv 2017
    PDF, Abstract

    We characterize the approximate monomial complexity, sign monomial complexity , and the approximate L1 norm of symmetric functions in terms of simple combinatorial measures of the functions. Our characterization of the approximate L1 norm solves the main conjecture in [AFH12]. As an application of the characterization of the sign monomial complexity, we prove a conjecture in [ZS09] and provide a characterization for the unbounded-error communication complexity of symmetric-xor functions.

  • 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.


Office Hours: Tue-Thu 4:30-6:00pm

Courses at Carnegie Mellon University:

  15-251: Great Theoretical Ideas in Computer Science (S15, F15, F16, S17)
  15-112: Fundamentals of Programming and Computer Science (F14, S16, M16)

Courses at McGill University:

  COMP 202: Foundations of Programming (Spring14, Summer14)
  COMP 531: Advanced Theory of Computation (Spring14)

Very Short Bio

I was born and raised up in Istanbul. I moved to Montreal after high school and received B.Sc. (Hon.) in Mathematics and Computer Science, M.Sc. in Computer Science, and Ph.D. in Computer Science all from McGill University. I was advised by Denis Thérien and Hamed Hatami. I'm currently an assistant teaching professor in the Computer Science Department of Carnegie Mellon University.

Back to Top