CAREER: Discrete Structures and Orthogonal Systems

University Of California-Irvine, Irvine CA

Investigators

Abstract

How much can quantum algorithms outperform classical algorithms? This open question has been recently formulated as a mathematical problem that has challenged the mathematical community but has yet to be solved. The question is related to another one: what is the most "efficient" way to encode and transmit given information? For example, a) one can try to minimize the number of symbols used in encoding the information, or b) one can maintain "certain structures" (say by repeating some "pattern") in encoded messages in order to avoid loss of information, provided that a couple of errors can be made during its transmission. The goal of this project is to investigate what the best way is to approximate given information or a given signal using only zeros and ones. The principal investigator will involve undergraduate and graduate students in research projects described in the proposal. The PI will organize a yearly summer school in analysis and probability for graduate students. This will be a good opportunity for PhD students to participate in research discussions with leading experts and to learn about emerging areas in mathematics. The question of quantum algorithms described above can be formulated as an explicit Fourier–analytic question on the boolean cube. On a technical level the proposal focuses on hypercontractivity, i.e., boundedness of a semigroup between normed spaces, its holomorphic extensions to complex domains, applications in moment comparison estimates, Markov—Bernstein type inequalities (for polynomials living on low and high frequencies), discrete approximation theory, and complexity of classical and quantum algorithms. One of the important examples involves the Hamming cube, equipped with a product measure. This project focuses on dimension independent estimates and proposes a program, a series of fundamental questions together with steps towards the resolution of these questions (heat flow arguments, martingale techniques, conformal maps, and probabilistic arguments), necessary for advancing and developing Fourier analysis on the Boolean cube. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.