[Proof Complexity] MIAO seminar Fri Feb 6 at 15:15 CET with Sreejata Kishor Bhattacharya: Aaronson-Ambainis Conjecture is True for Random Restrictions

[Jakob Nordström]

Dear all,

With a lot of excitement, albeit with apologies for the short notice, we would like to announce a seminar tomorrow Friday February 6 at 15:15 CET (note the time!) with Sreejata Kishor Bhattacharya from the Tata Institute of Fundamental Research Mumbai, who will give a presentation titled "Aaronson-Ambainis Conjecture is True for Random Restrictions". You find the abstract at the bottom of this message.

We will run this as a MIAO hybrid seminar at the IT University of Copenhagen. Local participants are warmly welcome to ITU at Rued Langgaards Vej 7, where the seminar will be held in Skybox 4A05, while other participants are equally warmly welcome to join virtually at https://lu-se.zoom.us/j/61925271827 . Please feel free to share this information with colleagues who you think might be interested. We are also hoping to record the seminar and post on the MIAO Research YouTube channel https://youtube.com/@MIAOresearch for people who would like to hear the talk but cannot attend.

More information about the MIAO seminar series can be found at https://jakobnordstrom.se/miao-seminars/ . If you do not wish to receive these announcements, or receive several copies of them, please send a message to jn at di.ku.dk.

Best regards,
Jakob Nordström

**********

/Friday Feb 6 at 15:15 (note the time!) in Skybox 4A05, Rued Langgaards Vej 7, IT University of Copenhagen, and on Zoom
*Aaronson-Ambainis Conjecture is True for Random Restrictions
*(Sreejata Kishor Bhattacharya, Tata Institute of Fundamental Research Mumbai)
/
The motivating question behind this talk is the following: for what kind of problems do quantum algorithms enjoy a significant (super-polynomial) advantage over classical algorithms? We study this problem in the setting of query complexity: a model of computation where the device computing the function gets access to the input only by limited interactions with an oracle. It has been long conjectured that the probability of acceptance of a quantum query algorithm making q queries can be well-approximated in the L^2 norm by a classical query algorithm making at most poly(q) queries.

Aaronson and Ambainis formulated a conjecture about bounded degree-d polynomials f:{-1,1}^n→[0,1] which implies the above conjecture. It states that any such polynomial f must have a coordinate i with influence Inf_i[f] >= poly(Var[f],1/d). The AA conjecture has recently received significant attention in the community — there is a series of partial results and failed attempts. The main contribution of this work is showing the following: given any such f, if we consider an appropriate random restriction, with high probability the conjecture is true for the restricted function. In other words, the AA conjecture is true for random restrictions.

In the end we shall sketch some potential ways of proving the full conjecture.

Based on a paper in ITCS 2025 (arxiv.org/abs/2402.13952).


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +45 28 78 38 11 / +46 70 742 21 98
https://jakobnordstrom.se