Publications
Selected publications
- 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)
2024
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
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
Instance complexity of Boolean functions
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 (pp. 867-880). ACM. doi:10.1145/3564246.3585199
2022
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
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
Exact quantum query complexity of computing Hamming weight modulo powers of two and three
2020
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
2019
Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead
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
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