NMNitya Mani

Nitya Mani

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Nitya Mani has a total of 11 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications

    by Zongchen Chen, Kuikui Liu, Nitya Mani, Ankur Moitra

    Strong spatial mixing (SSM) is an important quantitative notion of correlation decay for Gibbs distributions arising in statistical physics, probability theory, and theoretical computer science. A longstanding conjecture is that the uniform distribution on proper q -colorings on a Δ -regular tree exhibits SSM whenever q ≥ Δ + 1. Moreover, it is widely believed that as long as SSM holds on bounded-degree trees with q colors, one would obtain an efficient sampler for q -colorings on all bounded-degree graphs via simple Markov chain algorithms. It is surprising that such a basic question is still open, even on trees, but then again it also highlights how much we still have to learn about random colorings. In this paper, we show the following: (1) For any Δ ≥ 3, SSM holds for random q -colorings on trees of maximum degree Δ whenever q ≥ Δ + 3. Thus we almost fully resolve the aforementioned conjecture. Our result substantially improves upon the previously best bound which requires q ≥ 1.59 Δ + γ * for an absolute constant γ * > 0. (2) For any Δ ≥ 3 and \(g=\Omega _\Delta (1) \) , we establish optimal mixing of the Glauber dynamics for q -colorings on graphs of maximum degree Δ and girth g whenever q ≥ Δ + 3. Our approach is based on a new general reduction from spectral independence on large-girth graphs to SSM on trees that is of independent interest. Using the same techniques, we also prove near-optimal bounds on weak spatial mixing (WSM), a closely-related notion to SSM, for the antiferromagnetic Potts model on trees.

  • Nearly all $k$-SAT functions are unate

    by József Balogh, Dingding Dong, Bernard Lidický, Nitya Mani, Yufei Zhao

    We prove that a 1-o(1) fraction of all k -SAT functions of n Boolean variables are unate (i.e., monotone after first negating some variables), for any fixed positive integer k and as n \to \infty . This resolves a conjecture by Bollobás, Brightwell, and Leader from 2003.

  • Open Access

    Nearly all $k$-SAT functions are unate

    by József Balogh, Dingding Dong, Bernard Lidický, Nitya Mani, Yufei Zhao

    We prove that $1-o(1)$ fraction of all $k$-SAT functions on $n$ Boolean variables are unate (i.e., monotone after first negating some variables), for any fixed positive integer $k$ and as $n \to \infty$. This resolves a conjecture by Bollob\'as, Brightwell, and Leader from 2003.

  • On the number of error correcting codes

    by Dingding Dong, Nitya Mani, Yufei Zhao

    We show that for a fixed $q$ , the number of $q$ -ary $t$ -error correcting codes of length $n$ is at most $2^{(1 + o(1)) H_q(n,t)}$ for all $t \leq (1 - q^{-1})n - 2\sqrt{n \log n}$ , where $H_q(n, t) = q^n/ V_q(n,t)$ is the Hamming bound and $V_q(n,t)$ is the cardinality of the radius $t$ Hamming ball. This proves a conjecture of Balogh, Treglown, and Wagner, who showed the result for $t = o(n^{1/3} (\log n)^{-2/3})$ .


  • Open Access

    An Interpretable Approach to Hateful Meme Detection

    by Tanvi Deshpande, Nitya Mani

    Hateful memes are an emerging method of spreading hate on the internet, relying on both images and text to convey a hateful message. We take an interpretable approach to hateful meme detection, using machine learning and simple heuristics to identify the features most important to classifying a meme as hateful. In the process, we build a gradient-boosted decision tree and an LSTM-based model that achieve comparable performance (73.8 validation and 72.7 test auROC) to the gold standard of humans and state-of-the-art transformer models on this challenging task.