Nikhil S. Mande

69 papers A* 4A 6B 1Journal 48Unranked 10

Year	Rank	Type	Title / Venue / Authors
2025	J	`jnl`	Complexity of learning matchings and half graphs via edge queries. CoRR Nikhil S. Mande, Swagato Sanyal, Viktor Zamaraev
2025	—	`conf`	Hardness of Finding Kings and Strong Kings. FSTTCS Ziad Ismaili Alaoui, Nikhil S. Mande
2025	J	`jnl`	Hardness of Finding Kings and Strong Kings. CoRR Ziad Ismaili Alaoui, Nikhil S. Mande
2025	J	`jnl`	Improved Quantum Query Upper Bounds Based on Classical Decision Trees. Quantum Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro
2025	J	`jnl`	Lower bounds for quantum-inspired classical algorithms via communication complexity. Quantum Nikhil S. Mande, Changpeng Shao
2025	J	`jnl`	Quantum Search With Generalized Wildcards. CoRR Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro, Nithish Raja, Swagato Sanyal
2025	B	`conf`	Sensitivity and Query Complexity Under Uncertainty. MFCS Deepu Benson, Balagopal Komarath, Nikhil S. Mande, Nalli Sai Soumya, Jayalal Sarma, Karteek Sreenivasaiah
2025	J	`jnl`	Sensitivity and Query Complexity under Uncertainty. CoRR Deepu Benson, Balagopal Komarath, Nikhil S. Mande, Nalli Sai Soumya, Jayalal Sarma, Karteek Sreenivasaiah
2024	J	`jnl`	Lower bounds for quantum-inspired classical algorithms via communication complexity. CoRR Nikhil S. Mande, Changpeng Shao
2024	J	`jnl`	On parity decision trees for Fourier-sparse Boolean functions. ACM Trans. Comput. Theory Nikhil S. Mande, Swagato Sanyal
2024	A	`conf`	On the Communication Complexity of Finding a King in a Tournament. APPROX/RANDOM Nikhil S. Mande, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh
2024	J	`jnl`	On the communication complexity of finding a king in a tournament. CoRR Nikhil S. Mande, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh
2024	—	`conf`	Quantum Sabotage Complexity. FSTTCS Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro
2024	J	`jnl`	Quantum Sabotage Complexity. CoRR Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro
2024	J	`jnl`	Query Complexity with Unknowns. CoRR Nikhil S. Mande, Karteek Sreenivasaiah
2023	J	`jnl`	Instance complexity of Boolean functions. CoRR Alison Hsiang-Hsuan Liu, Nikhil S. Mande
2023	A	`conf`	Lifting to Parity Decision Trees via Stifling. ITCS Arkadev Chattopadhyay, Nikhil S. Mande, Swagato Sanyal, Suhail Sherif
2023	—	`conf`	Randomized and Quantum Query Complexities of Finding a King in a Tournament. FSTTCS Nikhil S. Mande, Manaswi Paraashar, Nitin Saurabh
2023	J	`jnl`	Randomized and quantum query complexities of finding a king in a tournament. CoRR Nikhil S. Mande, Manaswi Paraashar, Nitin Saurabh
2023	A*	`conf`	Randomized versus Deterministic Decision Tree Size. STOC Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil S. Mande, Jaikumar Radhakrishnan, Swagato Sanyal
2023	A	`conf`	Tight Bounds for Quantum Phase Estimation and Related Problems. ESA Nikhil S. Mande, Ronald de Wolf
2023	J	`jnl`	Tight Bounds for Quantum Phase Estimation and Related Problems. CoRR Nikhil S. Mande, Ronald de Wolf
2023	—	`conf`	Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error. FSTTCS Olivier Lalonde, Nikhil S. Mande, Ronald de Wolf
2022	J	`jnl`	A Short List of Equalities Induces Large Sign-Rank. SIAM J. Comput. Arkadev Chattopadhyay, Nikhil S. Mande
2022	—	`conf`	Improved Quantum Query Upper Bounds Based on Classical Decision Trees. FSTTCS Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro
2022	J	`jnl`	Improved Quantum Query Upper Bounds Based on Classical Decision Trees. CoRR Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro
2022	J	`jnl`	Lifting to Parity Decision Trees Via Stifling. CoRR Arkadev Chattopadhyay, Nikhil S. Mande, Swagato Sanyal, Suhail Sherif
2022	J	`jnl`	Lifting to Parity Decision Trees Via Stifling. Electron. Colloquium Comput. Complex. Arkadev Chattopadhyay, Nikhil S. Mande, Swagato Sanyal, Suhail Sherif
2022	A	`conf`	One-Way Communication Complexity and Non-Adaptive Decision Trees. STACS Nikhil S. Mande, Swagato Sanyal, Suhail Sherif
2022	J	`jnl`	Randomized versus Deterministic Decision Tree Size. Electron. Colloquium Comput. Complex. Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil S. Mande, Jaikumar Radhakrishnan, Swagato Sanyal
2022	A	`conf`	Symmetry and Quantum Query-To-Communication Simulation. STACS Sourav Chakraborty, Arkadev Chattopadhyay, Peter Høyer, Nikhil S. Mande, Manaswi Paraashar, Ronald de Wolf
2021	J	`jnl`	Exact quantum query complexity of computing Hamming weight modulo powers of two and three. CoRR Arjan Cornelissen, Nikhil S. Mande, Maris Ozols, Ronald de Wolf
2021	J	`jnl`	One-way communication complexity and non-adaptive decision trees. CoRR Nikhil S. Mande, Swagato Sanyal
2021	J	`jnl`	One-way communication complexity and non-adaptive decision trees. Electron. Colloquium Comput. Complex. Nikhil S. Mande, Swagato Sanyal
2021	J	`jnl`	Sign-rank Can Increase under Intersection. ACM Trans. Comput. Theory Mark Bun, Nikhil S. Mande, Justin Thaler
2021	J	`jnl`	Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error. CoRR Nikhil S. Mande, Ronald de Wolf
2021	J	`jnl`	Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error. Electron. Colloquium Comput. Complex. Nikhil S. Mande, Ronald de Wolf
2021	—	`conf`	Tight Chang's-Lemma-Type Bounds for Boolean Functions. FSTTCS Sourav Chakraborty, Nikhil S. Mande, Rajat Mittal, Tulasimohan Molli, Manaswi Paraashar, Swagato Sanyal
2020	J	`jnl`	Improved Approximate Degree Bounds For $k$-distinctness. Electron. Colloquium Comput. Complex. Nikhil S. Mande, Justin Thaler, Shuchen Zhu
2020	J	`jnl`	Improved Approximate Degree Bounds For k-distinctness. CoRR Nikhil S. Mande, Justin Thaler, Shuchen Zhu
2020	—	`conf`	Improved Approximate Degree Bounds for k-Distinctness. TQC Nikhil S. Mande, Justin Thaler, Shuchen Zhu
2020	J	`jnl`	Lower bounds for linear decision lists. Chic. J. Theor. Comput. Sci. Arkadev Chattopadhyay, Meena Mahajan, Nikhil S. Mande, Nitin Saurabh
2020	—	`conf`	On Parity Decision Trees for Fourier-Sparse Boolean Functions. FSTTCS Nikhil S. Mande, Swagato Sanyal
2020	J	`jnl`	On parity decision trees for Fourier-sparse Boolean functions. CoRR Nikhil S. Mande, Swagato Sanyal
2020	J	`jnl`	On parity decision trees for Fourier-sparse Boolean functions. Electron. Colloquium Comput. Complex. Nikhil S. Mande, Swagato Sanyal
2020	A	`conf`	Quantum Query-To-Communication Simulation Needs a Logarithmic Overhead. CCC Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande, Manaswi Paraashar
2020	J	`jnl`	Symmetry and Quantum Query-to-Communication Simulation. CoRR Sourav Chakraborty, Arkadev Chattopadhyay, Peter Høyer, Nikhil S. Mande, Manaswi Paraashar, Ronald de Wolf
2020	J	`jnl`	The Log-Approximate-Rank Conjecture Is False. J. ACM Arkadev Chattopadhyay, Nikhil S. Mande, Suhail Sherif
2020	J	`jnl`	Tight Chang's-lemma-type bounds for Boolean functions. CoRR Sourav Chakraborty, Nikhil S. Mande, Rajat Mittal, Tulasimohan Molli, Manaswi Paraashar, Swagato Sanyal
2019	—	`conf`	Approximate Degree, Secret Sharing, and Concentration Phenomena. APPROX-RANDOM Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, Christopher Williamson
2019	J	`jnl`	Approximate degree, secret sharing, and concentration phenomena. CoRR Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, Christopher Williamson
2019	J	`jnl`	Approximate degree, secret sharing, and concentration phenomena. Electron. Colloquium Comput. Complex. Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, Christopher Williamson
2019	J	`jnl`	Lower Bounds for Linear Decision Lists. CoRR Arkadev Chattopadhyay, Meena Mahajan, Nikhil S. Mande, Nitin Saurabh
2019	J	`jnl`	Lower Bounds for Linear Decision Lists. Electron. Colloquium Comput. Complex. Arkadev Chattopadhyay, Meena Mahajan, Nikhil S. Mande, Nitin Saurabh
2019	J	`jnl`	Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead. CoRR Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande, Manaswi Paraashar
2019	J	`jnl`	Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead. Electron. Colloquium Comput. Complex. Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande, Manaswi Paraashar
2019	A*	`conf`	Sign-Rank Can Increase Under Intersection. ICALP Mark Bun, Nikhil S. Mande, Justin Thaler
2019	J	`jnl`	Sign-Rank Can Increase Under Intersection. CoRR Mark Bun, Nikhil S. Mande, Justin Thaler
2019	J	`jnl`	Sign-Rank Can Increase Under Intersection. Electron. Colloquium Comput. Complex. Mark Bun, Nikhil S. Mande, Justin Thaler
2019	A*	`conf`	The log-approximate-rank conjecture is false. STOC Arkadev Chattopadhyay, Nikhil S. Mande, Suhail Sherif
2018	A*	`conf`	A Short List of Equalities Induces Large Sign Rank. FOCS Arkadev Chattopadhyay, Nikhil S. Mande
2018	J	`jnl`	Separation of Unbounded-Error Models in Multi-Party Communication Complexity. Theory Comput. Arkadev Chattopadhyay, Nikhil S. Mande
2018	J	`jnl`	The Log-Approximate-Rank Conjecture is False. Electron. Colloquium Comput. Complex. Arkadev Chattopadhyay, Nikhil S. Mande, Suhail Sherif
2017	—	`conf`	A Lifting Theorem with Applications to Symmetric Functions. FSTTCS Arkadev Chattopadhyay, Nikhil S. Mande
2017	J	`jnl`	Dual polynomials and communication complexity of XOR functions. CoRR Arkadev Chattopadhyay, Nikhil S. Mande
2017	J	`jnl`	Dual polynomials and communication complexity of XOR functions. Electron. Colloquium Comput. Complex. Arkadev Chattopadhyay, Nikhil S. Mande
2017	J	`jnl`	Weights at the Bottom Matter When the Top is Heavy. CoRR Arkadev Chattopadhyay, Nikhil S. Mande
2017	J	`jnl`	Weights at the Bottom Matter When the Top is Heavy. Electron. Colloquium Comput. Complex. Arkadev Chattopadhyay, Nikhil S. Mande
2016	J	`jnl`	Small Error Versus Unbounded Error Protocols in the NOF Model. Electron. Colloquium Comput. Complex. Arkadev Chattopadhyay, Nikhil S. Mande