Nitya Mani
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Nitya Mani has a total of 11 co-authors. Here are the top co-authors by number of shared publications:
- Dingding Dong
Harvard University
3 shared publications - Bernard Lidický
Department of Mathematics Iowa State University Ames Iowa USA
2 shared publications - Ankur Moitra
Massachusetts Institute of Technology, Cambridge, USA
1 shared publication - József Balogh
Department of Mathematics and University of Illinois Urbana-Champaign Urbana IL USA
1 shared publication - József Balogh
University of Illinois Urbana-Champaign, USA
1 shared publication - Kuikui Liu
Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology
1 shared publication
Latest Publications
- Open Access
- 21 August 2026
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications
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.- 21 August 2026
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
Open AccessStrong Spatial Mixing for Colorings on Trees and its Algorithmic Applications
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. - 14 May 2026
- Published by European Mathematical Society - EMS - Publishing House GmbH in Journal of the European Mathematical Society
Nearly all $k$-SAT functions are unate
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.
- 14 May 2026
- Published by European Mathematical Society - EMS - Publishing House GmbH in Journal of the European Mathematical Society
Nearly all $k$-SAT functions are unate
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
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.Open AccessNearly all $k$-SAT functions are unate
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. - 9 June 2023
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 32 (5) , 819-832
On the number of error correcting codes
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})$ .- 9 June 2023
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 32 (5) , 819-832
On the number of error correcting codes
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
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.
Open AccessAn Interpretable Approach to Hateful Meme Detection
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.