Computer Science/Discrete Mathematics Seminar II

The query model is one of the most basic computational models.  In contrast to the Turing machine model, fundamental questions regarding the power of randomness and quantum computing are relatively well-understood.  For example, it is well-known since the 90s that deterministic, randomized, and quantum query complexities are polynomially related for total functions, and can be arbitrarily separated for partial functions.  The follow-up question of what are the largest separations between these models, however, is more subtle and has resisted 20 years of attacks.  In recent years, a lot of exciting progress is made.  Just to mention a few (for total functions):

1.  A quadratic separation between the deterministic query and zero-error randomized query complexity was discovered (Ambainis et al. 15). This separation is tight and refutes the Saks-Wigderson conjecture.

2.  A quartic separation between the deterministic query complexity and quantum query complexity was discovered (Ambainis et al. 15). A matching upper bound is later proved based on Huang's sensitivity theorem (Aaronson et al. 20). 

3.  The separation between randomized and quantum query complexity was improved from quadratic to cubic (Aaronson et al. 15, Tal 19, Bansal-Sinha 20, Sherstov et al. 20). A quartic upper bound follows from the above item (Aaronson et al. 20).

In the seminar, we will discuss these results and the techniques behind them.