Research
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.
Papers

On the Spectral Properties of Symmetric Functions
with Omar Fawzi, Raghav Kulkarni
Arxiv 2017
PDF, AbstractWe 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 unboundederror communication complexity of symmetricxor functions.

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: TBD
Courses at Carnegie Mellon University:
15251: Great Theoretical Ideas in Computer Science (S15, F15, F16, S17, F17, S18)15112: 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.