Video Lectures

I will survey recent results and open problems in several areas of quantum complexity theory, with emphasis on open problems which can be phrased in terms of classical complexity theory or mathematics but have implications for quantum computing: 1...

Let \[ f(t)=\sum_{N n 2N}a_nn^{-it} \] be a Dirichlet polynomial. We consider the weighted square mean value \[ I=\int_{-\infty}^{\infty}|f(t)|^2\exp\{-\Delta^{-2}(t-T)^2\}\,dt, \] where \(T\) is a large paremeter and \[ \Delta = \frac{T}{\log T}...

If \(M\) is a complex manifold, the Bott-Chern cohomology \(H_{\mathrm{BC}}^{(\cdot,\cdot)}\left(M,\mathbf{C}\right)\) of \(M\) is a refinement of de Rham cohomology, that takes into account the \((p,q)\) grading of smooth differential forms. By...

How can we produce randomness of almost perfect quality, in large quantities, and under minimal assumptions? This question is fundamental not only to modern day information processing but also to physics. Yet a satisfactory answer is still elusive...

We consider two classes of \(n \times n\) sample covariance matrices arising in quantum informatics. The first class consists of matrices whose data matrix has \(m\) independent columns each of which is the tensor product of \(k\) independent \(d\)...

The IP theorem, which asserts that IP = PSPACE (Lund et. al., and Shamir, in J. ACM 39(4)), is one of the major achievements of complexity theory. The known proofs of the theorem are based on the arithmetization technique, which transforms a...

Constant mean curvature (CMC) tori in \(S^3\), \(R^3\) or \(H^3\) are in bijective correspondence with spectral curve data, consisting of a hyperelliptic curve, a line bundle on this curve and some additional data, which in particular determines the...

An error-correcting code is called locally decodable if there exists a decoding algorithm that can recover any symbol of the message with high probability by reading only a small number of symbols of the corrupted codeword. There is a fundamental...

The work of Green, Tao and Ziegler can be used to prove existence and approximation properties for rational solutions of the Diophantine equations that describe representations of a product of norm forms by a product of linear polynomials. One can...