Speaker: |
Sreejata Kishor Bhattacharya |

Organiser: |
Arkadev Chattopadhyay |

Date: |
Thursday, 8 Sep 2022, 10:30 to 12:00 |

Venue: |
D-405 (D-Block Seminar Room) |

(Scan to add to calendar)

One of the long-standing questions in this direction is the following: given a quantum query algorithm for a Boolean function (defined on a subset of the Boolean hypercube with at least inverse polynomial density) making d queries, does there exist a classical query algorithm which makes at most poly(d) queries and approximates the output probability of the quantum algorithm on most inputs? We shall discuss the body of previous work done on this question: weak results that are known, a recent attempt to resolve the conjecture which turned out to have a fatal flaw and our attempts to fix the argument.