Conference/journal publications

All papers below are listed roughly in reverse-chronological order of first acceptance at a conference/journal. In case you do not have access to the published versions of any of my papers, please shoot me an email; I'll be happy to share a copy with you.

• New: "Randomized and Quantum Query Complexities of Finding a King in a Tournament", with Manaswi Paraashar and Nitin Saurabh
  arXiv preprint
  FSTTCS 2023
  
  
• New: "Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error", with Olivier Lalonde and Ronald de Wolf
  ECCC report and arXiv preprint of an older version.
  FSTTCS 2023
  
  
• New: "Tight Bounds for Quantum Phase Estimation and Related Problems", with Ronald de Wolf
  arXiv preprint
  ESA 2023
  
  
• "Randomized versus Deterministic Decision Tree Size", with Arkadev Chattopadhyay, Yogesh Dahiya, Jaikumar Radhakrishnan and Swagato Sanyal
  ECCC report
  STOC 2023
  
  
• "Lifting to Parity Decision Trees via Stifling", with Arkadev Chattopadhyay, Swagato Sanyal and Suhail Sherif
  ECCC report, arXiv preprint
  ITCS 2023
  
  
• "Improved Quantum Query Upper Bounds Based on Classical Decision Trees", with Arjan Cornelissen and Subhasree Patro, 2022
  arXiv preprint
  FSTTCS 2022
  TQC 2022 (workshop track)
  
  
• "One-Way Communication Complexity and Non-Adaptive Decision Trees", with Swagato Sanyal and Suhail Sherif
  arXiv preprint
  STACS 2022
  
  
• "Symmetry and Quantum Query-to-Communication Simulation", with Sourav Chakraborty, Arkadev Chattopadhyay, Peter Høyer, Manaswi Paraashar and Ronald de Wolf
  arXiv preprint
  STACS 2022
  
  
• "Tight Chang's-Lemma-Type Bounds for Boolean Functions", with Sourav Chakraborty, Rajat Mittal, Tulasimohan Molli, Manaswi Paraashar and Swagato Sanyal
  arXiv preprint
  FSTTCS 2021
  
  
• "On Parity Decision Trees for Fourier-Sparse Boolean Functions", with Swagato Sanyal
  ECCC report, arXiv preprint
  FSTTCS 2020
  Accepted to ACM Transactions on Computation Theory, 2023.
  
  
• "Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead", with Sourav Chakraborty, Arkadev Chattopadhyay and Manaswi Paraashar
  ECCC report, arXiv preprint
  CCC 2020
  QIP 2020
  
  
• "Improved Approximate Degree Bounds For k-distinctness", with Justin Thaler and Shuchen Zhu
  ECCC report, arXiv preprint
  TQC 2020
  
  
• "Lower Bounds for Linear Decision Lists", with Arkadev Chattopadhyay, Meena Mahajan and Nitin Saurabh
  ECCC report, arXiv preprint
  CJTCS, 2020
  
  
• "Approximate Degree, Secret Sharing, and Concentration Phenomena", with Andrej Bogdanov, Justin Thaler and Christopher Williamson
  ECCC report, arXiv preprint
  RANDOM 2019
  
  
• "Sign-Rank Can Increase Under Intersection", with Mark Bun and Justin Thaler
  ECCC report, arXiv preprint
  ICALP 2019
  
  
• "The Log-Approximate-Rank Conjecture is False", with Arkadev Chattopadhyay and Suhail Sherif
  ECCC report
  STOC 2019
  Journal of the ACM, 2020
  Invited to SICOMP (STOC special issue)
  Invited to ToC
  Invited talk at HALG 2020
  
  
• "A Short List of Equalities Induces Large Sign Rank", with Arkadev Chattopadhyay
  (An earlier version was titled "Weights at the Bottom Matter When the Top is Heavy".)
  ECCC report, arXiv preprint
  FOCS 2018
  SICOMP 2022
  
  
• "A Lifting Theorem with Applications to Symmetric Functions", with Arkadev Chattopadhyay
  FSTTCS 2017
  
  
• "Separation of Unbounded-Error Models in Multi-Party Communication Complexity", with Arkadev Chattopadhyay
  (An earlier version was titled "Small Error Versus Unbounded Error Models in the NOF Model".)
  ECCC report
  ToC 2018

Preprints

• New: "Lower Bounds for Quantum-Inspired Classical Algorithms Via Communication Complexity", with Changpeng Shao, 2024
  arXiv preprint
  
  
• New: "On the Communication Complexity of Finding a King in a Tournament", with Manaswi Paraashar, Swagato Sanyal and Nitin Saurabh, 2024
  arXiv preprint
  
  
• "Instance Complexity of Boolean Functions", with Alison Hsiang-Hsuan Liu, 2023
  arXiv preprint
  
  
• "Exact Quantum Query Complexity of Computing Hamming Weight Modulo Powers of Two and Three", with Arjan Cornelissen, Māris Ozols and Ronald de Wolf, 2021
  arXiv preprint
  
  
• "Dual Polynomials and Communication Complexity of XOR Functions", with Arkadev Chattopadhyay, 2017 (This is an extended version of "A Lifting Theorem with Applications to Symmetric Functions.")
  ECCC report, arXiv preprint