Nikhil S. Mande

According to our database, Nikhil S. Mande authored at least 33 papers between 2016 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2025

Complexity of learning matchings and half graphs via edge queries.

Nikhil S. Mande, Swagato Sanyal, Viktor Zamaraev

CoRR, July, 2025

Hardness of Finding Kings and Strong Kings.

Ziad Ismaili Alaoui, Nikhil S. Mande

CoRR, April, 2025

Lower bounds for quantum-inspired classical algorithms via communication complexity.

Nikhil S. Mande, Changpeng Shao

Quantum, 2025

Sensitivity and Query Complexity Under Uncertainty.

Deepu Benson, Balagopal Komarath, Nikhil S. Mande, Nalli Sai Soumya, Jayalal Sarma, Karteek Sreenivasaiah

Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science, 2025

2024

Query Complexity with Unknowns.

Nikhil S. Mande, Karteek Sreenivasaiah

CoRR, 2024

Quantum Sabotage Complexity.

Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro

Proceedings of the 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2024

On the Communication Complexity of Finding a King in a Tournament.

Nikhil S. Mande, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh

Proceedings of the Approximation, 2024

2023

Instance complexity of Boolean functions.

Alison Hsiang-Hsuan Liu, Nikhil S. Mande

CoRR, 2023

Randomized versus Deterministic Decision Tree Size.

Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil S. Mande, Jaikumar Radhakrishnan, Swagato Sanyal

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Lifting to Parity Decision Trees via Stifling.

Arkadev Chattopadhyay, Nikhil S. Mande, Swagato Sanyal, Suhail Sherif

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Randomized and Quantum Query Complexities of Finding a King in a Tournament.

Nikhil S. Mande, Manaswi Paraashar, Nitin Saurabh

Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error.

Olivier Lalonde, Nikhil S. Mande, Ronald de Wolf

Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

Tight Bounds for Quantum Phase Estimation and Related Problems.

Nikhil S. Mande, Ronald de Wolf

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

One-Way Communication Complexity and Non-Adaptive Decision Trees.

Nikhil S. Mande, Swagato Sanyal, Suhail Sherif

Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science, 2022

Symmetry and Quantum Query-To-Communication Simulation.

Sourav Chakraborty, Arkadev Chattopadhyay, Peter Høyer, Nikhil S. Mande, Manaswi Paraashar, Ronald de Wolf

Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science, 2022

Improved Quantum Query Upper Bounds Based on Classical Decision Trees.

Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro

Proceedings of the 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2022

2021

Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error.

Nikhil S. Mande, Ronald de Wolf

Electron. Colloquium Comput. Complex., 2021

One-way communication complexity and non-adaptive decision trees.

Nikhil S. Mande, Swagato Sanyal

Electron. Colloquium Comput. Complex., 2021

Exact quantum query complexity of computing Hamming weight modulo powers of two and three.

Arjan Cornelissen, Nikhil S. Mande, Maris Ozols, Ronald de Wolf

CoRR, 2021

Tight Chang's-Lemma-Type Bounds for Boolean Functions.

Sourav Chakraborty, Nikhil S. Mande, Rajat Mittal, Tulasimohan Molli, Manaswi Paraashar, Swagato Sanyal

Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2021

2020

Improved Approximate Degree Bounds for k-Distinctness.

Nikhil S. Mande, Justin Thaler, Shuchen Zhu

Proceedings of the 15th Conference on the Theory of Quantum Computation, 2020

On Parity Decision Trees for Fourier-Sparse Boolean Functions.

Nikhil S. Mande, Swagato Sanyal

Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

Quantum Query-To-Communication Simulation Needs a Logarithmic Overhead.

Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande, Manaswi Paraashar

Proceedings of the 35th Computational Complexity Conference, 2020

2019

Lower Bounds for Linear Decision Lists.

Arkadev Chattopadhyay, Meena Mahajan, Nikhil S. Mande, Nitin Saurabh

Electron. Colloquium Comput. Complex., 2019

The log-approximate-rank conjecture is false.

Arkadev Chattopadhyay, Nikhil S. Mande, Suhail Sherif

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Sign-Rank Can Increase Under Intersection.

Mark Bun, Nikhil S. Mande, Justin Thaler

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Approximate Degree, Secret Sharing, and Concentration Phenomena.

Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, Christopher Williamson

Proceedings of the Approximation, 2019

2018

Separation of Unbounded-Error Models in Multi-Party Communication Complexity.

Arkadev Chattopadhyay, Nikhil S. Mande

Theory Comput., 2018

A Short List of Equalities Induces Large Sign Rank.

Arkadev Chattopadhyay, Nikhil S. Mande

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Weights at the Bottom Matter When the Top is Heavy.

Arkadev Chattopadhyay, Nikhil S. Mande

Electron. Colloquium Comput. Complex., 2017

Dual polynomials and communication complexity of XOR functions.

Arkadev Chattopadhyay, Nikhil S. Mande

Electron. Colloquium Comput. Complex., 2017

A Lifting Theorem with Applications to Symmetric Functions.

Arkadev Chattopadhyay, Nikhil S. Mande

Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017

2016

Small Error Versus Unbounded Error Protocols in the NOF Model.

Arkadev Chattopadhyay, Nikhil S. Mande

Electron. Colloquium Comput. Complex., 2016