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)
2026
Instance complexity of Boolean functions
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
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, 42 pages. 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, 20 pages. 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 44TH IARCS ANNUAL CONFERENCE ON FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE, FSTTCS 2024 Vol. 323 (pp. 20 pages). 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 APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION. ALGORITHMS AND TECHNIQUES, APPROX/RANDOM 2024 Vol. 317 (pp. 23 pages). 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 43RD IARCS ANNUAL CONFERENCE ON FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE, FSTTCS 2023 Vol. 284 (pp. 18 pages). 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 42ND IARCS ANNUAL CONFERENCE ON FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE, FSTTCS 2022 Vol. 250 (pp. 22 pages). 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