Research outputs
Selected research outputs
- A SHORT LIST OF EQUALITIES INDUCES LARGE SIGN-RANK (Journal article - 2022)
- Randomized versus Deterministic Decision Tree Size (Conference Paper - 2023)
- The Log-Approximate-Rank Conjecture Is False (Journal article - 2020)
2025
Sensitivity and Query Complexity Under Uncertainty
Benson, D., Komarath, B., Mande, N., Nalli, S. S., Sarma, J., & Sreenivasaiah, K. (2025). Sensitivity and Query Complexity Under Uncertainty. In Leibniz International Proceedings in Informatics Lipics Vol. 345. doi:10.4230/LIPIcs.MFCS.2025.17
Instance complexity of Boolean functions
Hardness of Finding Kings and Strong Kings
Alaoui, Z. I., & Mande, N. (2025). Hardness of Finding Kings and Strong Kings. In Leibniz International Proceedings in Informatics Lipics Vol. 360. doi:10.4230/LIPIcs.FSTTCS.2025.36
Improved Quantum Query Upper Bounds Based on Classical Decision Trees
Cornelissen, A., Mande, N. S., & Patro, S. (2025). Improved Quantum Query Upper Bounds Based on Classical Decision Trees. Quantum, 9, 1777. doi:10.22331/q-2025-06-23-1777
Lower bounds for quantum-inspired classical algorithms via communication complexity
Mande, N. S., & Shao, C. (2025). Lower bounds for quantum-inspired classical algorithms via communication complexity. Quantum, 9, 1593. doi:10.22331/q-2025-01-14-1593
2024
Lower bounds for quantum-inspired classical algorithms via communication complexity
Quantum Sabotage Complexity
Cornelissen, A., Mande, N. S., & Patro, S. (2024). Quantum Sabotage Complexity. In Leibniz International Proceedings in Informatics Lipics Vol. 323. doi:10.4230/LIPIcs.FSTTCS.2024.19
On the Communication Complexity of Finding a King in a Tournament
Mande, N. S., Paraashar, M., Sanyal, S., & Saurabh, N. (2024). On the Communication Complexity of Finding a King in a Tournament. In Leibniz International Proceedings in Informatics Lipics Vol. 317. doi:10.4230/LIPIcs.APPROX/RANDOM.2024.64
Quantum Sabotage Complexity
On parity decision trees for Fourier-sparse Boolean functions
Mande, N. S., & Sanyal, S. (2024). On parity decision trees for Fourier-sparse Boolean functions. ACM Transactions on Computation Theory, 16(2), 1-26. doi:10.1145/3647629
Lower bounds for quantum-inspired classical algorithms via communication complexity
Mande, N. S., & Shao, C. (2024). Lower bounds for quantum-inspired classical algorithms via communication complexity. Quantum, 9.
2023
Randomized and quantum query complexities of finding a king in a tournament
Mande, N., Paraashar, M., & Saurabh, N. (2023). Randomized and quantum query complexities of finding a king in a tournament. In FSTTCS: Foundations of Software Technology and Theoretical Computer Science. Hyderabad, India.
Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error
Lalonde, O., Mande, N. S., & De Wolf, R. (2023). Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error. In Leibniz International Proceedings in Informatics Lipics Vol. 284. doi:10.4230/LIPIcs.FSTTCS.2023.32
Tight Bounds for Quantum Phase Estimation and Related Problems
Mande, N. S., & de Wolf, R. (2023). Tight Bounds for Quantum Phase Estimation and Related Problems. In Leibniz International Proceedings in Informatics Lipics Vol. 274. doi:10.4230/LIPIcs.ESA.2023.81
Randomized versus Deterministic Decision Tree Size
Chattopadhyay, A., Dahiya, Y., Mande, N. S., Radhakrishnan, J., & Sanyal, S. (2023). Randomized versus Deterministic Decision Tree Size. In PROCEEDINGS OF THE 55TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2023 (pp. 867-880). doi:10.1145/3564246.3585199
Lifting to Parity Decision Trees via Stifling
Chattopadhyay, A., Mande, N. S., Sanyal, S., & Sherif, S. (2023). Lifting to Parity Decision Trees via Stifling. In 14TH INNOVATIONS IN THEORETICAL COMPUTER SCIENCE CONFERENCE, ITCS 2023 Vol. 251. doi:10.4230/LIPIcs.ITCS.2023.33
2022
Improved Quantum Query Upper Bounds Based on Classical Decision Trees
Cornelissen, A., Mande, N. S., & Patro, S. (2022). Improved Quantum Query Upper Bounds Based on Classical Decision Trees. In Leibniz International Proceedings in Informatics Lipics Vol. 250. doi:10.4230/LIPIcs.FSTTCS.2022.15
One-Way Communication Complexity and Non-Adaptive Decision Trees
Mande, N. S., Sanyal, S., & Sherif, S. (2022). One-Way Communication Complexity and Non-Adaptive Decision Trees. In 39TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, STACS 2022 Vol. 219. doi:10.4230/LIPIcs.STACS.2022.49
Symmetry and Quantum Query-To-Communication Simulation
Chakraborty, S., Chattopadhyay, A., Hoyer, P., Mande, N. S., Paraashar, M., & de Wolf, R. (2022). Symmetry and Quantum Query-To-Communication Simulation. In 39TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, STACS 2022 Vol. 219. doi:10.4230/LIPIcs.STACS.2022.20
A SHORT LIST OF EQUALITIES INDUCES LARGE SIGN-RANK
Chattopadhyay, A., & Mande, N. S. (2022). A SHORT LIST OF EQUALITIES INDUCES LARGE SIGN-RANK. SIAM JOURNAL ON COMPUTING, 51(3), 820-848. doi:10.1137/19M1271348
2021
Exact quantum query complexity of computing Hamming weight modulo powers of two and three
Sign-rank Can Increase under Intersection
Bun, M., Mande, N. S., & Thaler, J. (2021). Sign-rank Can Increase under Intersection. ACM TRANSACTIONS ON COMPUTATION THEORY, 13(4). doi:10.1145/3470863
Tight Chang’s-Lemma-Type Bounds for Boolean Functions
Chakraborty, S., Mande, N. S., Mittal, R., Molli, T., Paraashar, M., & Sanyal, S. (2021). Tight Chang’s-Lemma-Type Bounds for Boolean Functions. In Leibniz International Proceedings in Informatics Lipics Vol. 213. doi:10.4230/LIPIcs.FSTTCS.2021.10
2020
On parity decision trees for fourier-sparse boolean functions
Mande, N. S., & Sanyal, S. (2020). On parity decision trees for fourier-sparse boolean functions. In Leibniz International Proceedings in Informatics Lipics Vol. 182. doi:10.4230/LIPIcs.FSTTCS.2020.29
The Log-Approximate-Rank Conjecture Is False
Chattopadhyay, A., Mande, N. S., & Sherif, S. (2020). The Log-Approximate-Rank Conjecture Is False. JOURNAL OF THE ACM, 67(4). doi:10.1145/3396695
Quantum query-to-communication simulation needs a logarithmic overhead
Chakraborty, S., Chattopadhyay, A., Mande, N. S., & Paraashar, M. (2020). Quantum query-to-communication simulation needs a logarithmic overhead. In Leibniz International Proceedings in Informatics Lipics Vol. 169. doi:10.4230/LIPIcs.CCC.2020.32
Improved approximate degree bounds for k-distinctness
Mande, N. S., Thaler, J., & Zhu, S. (2020). Improved approximate degree bounds for k-distinctness. In Leibniz International Proceedings in Informatics Lipics Vol. 158. doi:10.4230/LIPIcs.TQC.2020.2
2019
Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead
Approximate degree, secret sharing, and concentration phenomena
Bogdanov, A., Mande, N. S., Thaler, J., & Williamson, C. (2019). Approximate degree, secret sharing, and concentration phenomena. In Leibniz International Proceedings in Informatics Lipics Vol. 145. doi:10.4230/LIPIcs.APPROX-RANDOM.2019.71
Sign-rank can increase under intersection
Bun, M., Mande, N. S., & Thaler, J. (2019). Sign-rank can increase under intersection. In Leibniz International Proceedings in Informatics Lipics Vol. 132. doi:10.4230/LIPIcs.ICALP.2019.30
The Log-Approximate-Rank Conjecture Is False
Chattopadhyay, A., Mande, N. S., & Sherif, S. (2019). The Log-Approximate-Rank Conjecture Is False. In PROCEEDINGS OF THE 51ST ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '19) (pp. 42-53). doi:10.1145/3313276.3316353
Approximate degree, secret sharing, and concentration phenomena
Sign-Rank Can Increase Under Intersection
Lower Bounds for Linear Decision Lists
2018
A Short List of Equalities Induces Large Sign Rank
Chattopadhyay, A., & Mande, N. S. (2018). A Short List of Equalities Induces Large Sign Rank. In 2018 IEEE 59TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS) (pp. 47-58). doi:10.1109/FOCS.2018.00014
A lifting theorem with applications to symmetric functions
Chattopadhyay, A., & Mande, N. S. (2018). A lifting theorem with applications to symmetric functions. In Leibniz International Proceedings in Informatics Lipics Vol. 93. doi:10.4230/LIPIcs.FSTTCS.2017.23
Separation of Unbounded-Error Models in Multi-Party Communication Complexity
Chattopadhyay, A., & Mande, N. S. (2018). Separation of Unbounded-Error Models in Multi-Party Communication Complexity. THEORY OF COMPUTING, 14. doi:10.4086/toc.2018.v014a021