Understanding the power and limitations of randomness and quantumness

21^st April 2023, 13:00 Ashton Lecture Theatre
Dr. Nikhil Mande
Department of Computer Science, University of Liverpool

Abstract

In this talk we will try to understand whether access to randomness and quantumness gives an advantage to algorithms, in the settings of query complexity and communication complexity. The talk will consist of two parts:

In the first part of the talk, we consider query-to-communication simulation and show a surprising weakness of the quantum model as compared to the classical deterministic and randomized models.
In the second part of the talk, we consider the query complexity of algorithms, with oracle access to AND's and OR's of arbitrary subsets of the inputs, computing Boolean functions. We show that randomized algorithms give at most a polynomial advantage over their deterministic counterparts.

Biography

I am a lecturer in the Department of Computer Science at the University of Liverpool since January 2023. Until December 2022, I was a postdoctoral researcher in the Algorithms and Complexity Group at CWI, hosted by Ronald de Wolf. Before this, I was a postdoctoral researcher in the Department of Computer Science at Georgetown University, where I was hosted by Justin Thaler. Before that, I was a research scholar in the School of Technology and Computer Science at TIFR Mumbai, where Arkadev Chattopadhyay was my advisor. I am broadly interested in the area of computational complexity theory. More specifically, I have an interest in (classical and quantum)(query complexity and communication complexity), analysis of Boolean functions, approximation theory, quantum computing, Boolean circuit complexity, and the connections between them.