Dr Nikhil Mande PhD

Lecturer Computer Science

+44 (0)151 794 0604
Work email Nikhil.Mande@liverpool.ac.uk
Personal Websitehttps://mande-nikhil.github.io/

Publications

Selected Publications

The Log-Approximate-Rank Conjecture Is False (Conference Paper - 2019)
A Short List of Equalities Induces Large Sign-Rank (Journal article - 2022)
Randomized versus Deterministic Decision Tree Size (Conference Paper - 2023)

Filter the publication list

Filter list by type

Show all
Journal article
Conference paper
Chapter
Other

2024

On parity decision trees for Fourier-sparse Boolean functions (Journal article)

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

DOI: 10.1145/3647629

Lower bounds for quantum-inspired classical algorithms via communication complexity (Preprint)

DOI: 10.48550/arxiv.2402.15686

On the communication complexity of finding a king in a tournament (Preprint)

DOI: 10.48550/arxiv.2402.14751

2023

Randomized and quantum query complexities of finding a king in a tournament (Conference Paper)

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 (Conference Paper)

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

DOI: 10.4230/LIPIcs.FSTTCS.2023.32

Instance complexity of Boolean functions (Preprint)

DOI: 10.48550/arxiv.2309.15026

Tight Bounds for Quantum Phase Estimation and Related Problems (Conference Paper)

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

DOI: 10.4230/LIPIcs.ESA.2023.81

Randomized and quantum query complexities of finding a king in a tournament (Preprint)

DOI: 10.48550/arxiv.2308.02472

Randomized versus Deterministic Decision Tree Size (Conference Paper)

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. ACM. doi:10.1145/3564246.3585199

DOI: 10.1145/3564246.3585199

2022

Lifting to Parity Decision Trees Via Stifling (Preprint)

DOI: 10.48550/arxiv.2211.17214

A Short List of Equalities Induces Large Sign-Rank (Journal article)

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

DOI: 10.1137/19m1271348

Improved Quantum Query Upper Bounds Based on Classical Decision Trees (Preprint)

DOI: 10.48550/arxiv.2203.02968

2021

Sign-rank Can Increase under Intersection (Journal article)

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

DOI: 10.1145/3470863

Exact quantum query complexity of computing Hamming weight modulo powers of two and three (Preprint)

DOI: 10.48550/arxiv.2112.14682

Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error (Preprint)

DOI: 10.48550/arxiv.2107.11806

One-way communication complexity and non-adaptive decision trees (Preprint)

DOI: 10.48550/arxiv.2105.01963

2020

The Role of Symmetry in Quantum Query-to-Communication Simulation (Preprint)

DOI: 10.48550/arxiv.2012.05233

Tight Chang's-lemma-type bounds for Boolean functions (Preprint)

DOI: 10.48550/arxiv.2012.02335

The Log-Approximate-Rank Conjecture Is False (Journal article)

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

DOI: 10.1145/3396695

On parity decision trees for Fourier-sparse Boolean functions (Preprint)

DOI: 10.48550/arxiv.2008.00266

Improved Approximate Degree Bounds For k-distinctness (Preprint)

DOI: 10.48550/arxiv.2002.08389

(Journal article)

Chattopadhyay, A., Mahajan, M., Mande, N., & Saurabh, N. (n.d.). . Chicago Journal of Theoretical Computer Science, 26(1), 1-15. doi:10.4086/cjtcs.2020.001

DOI: 10.4086/cjtcs.2020.001

2019

Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead (Preprint)

DOI: 10.48550/arxiv.1909.10428

The Log-Approximate-Rank Conjecture Is False (Conference Paper)

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

DOI: 10.1145/3313276.3316353

2018

A Short List of Equalities Induces Large Sign Rank (Conference Paper)

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

DOI: 10.1109/FOCS.2018.00014

Separation of Unbounded-Error Models in Multi-Party Communication Complexity (Journal article)

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

DOI: 10.4086/toc.2018.v014a021

2017

Weights at the Bottom Matter When the Top is Heavy (Preprint)

DOI: 10.48550/arxiv.1705.02397