Yogesh Dahiya

Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay et al.

A major open problem in quantum communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols for computing total Boolean functions; the prevailing conjecture is that they cannot be so. In a seminal work, Razborov (2002) resolved this question for AND-functions of the form $$ F(x,y) = f(x_1 \land y_1, \ldots, x_n \land y_n), $$ when the outer function $f$ is symmetric, by proving that their bounded-error quantum and classical communication complexities are polynomially related. Since then, extending this result to all AND-functions has remained open and has been posed by several authors. In this work, we settle this problem in a strong way. We show that for every Boolean function $f$, the bounded-error quantum and classical deterministic communication complexities of the function $f \circ \mathrm{AND}_2$ are polynomially related, up to polylogarithmic factors in $n$. We prove this by showing that both are characterized--up to polynomial loss--by the logarithm of the De Morgan sparsity of $f$. Our results build on the recent work of Chattopadhyay, Dahiya, and Lovett (2025) on structural characterizations of non-sparse Boolean functions, which we extend to resolve the conjecture for general AND-functions.

Danish, Yogesh Dahiya, Partha Talukdar

Questions form an integral part of our everyday communication, both offline and online. Getting responses to our questions from others is fundamental to satisfying our information need and in extending our knowledge boundaries. A question may be represented using various factors such as social, syntactic, semantic, etc. We hypothesize that these factors contribute with varying degrees towards getting responses from others for a given question. We perform a thorough empirical study to measure effects of these factors using a novel question and answer dataset from the website Reddit.com. To the best of our knowledge, this is the first such analysis of its kind on this important topic. We also use a sparse nonnegative matrix factorization technique to automatically induce interpretable semantic factors from the question dataset. We also document various patterns on response prediction we observe during our analysis in the data. For instance, we found that preference-probing questions are scantily answered. Our method is robust to capture such latent response factors. We hope to make our code and datasets publicly available upon publication of the paper.