Seminar

http://events.berkeley.edu/index.php/calendar/sn/math.html?event_ID=114448

Lecture 2: Mathematics and Computation (through the lens of one problem and one algorithm). Proving Algebraic Identities.

In numerous mathematical settings, an object typically has several representations. This leads to the “isomorphism problem” or “word problem”: when are two given representations equivalent. Such problems have driven much structural and algorithmic research across mathematics.

We will focus on the algebraic setting, where our objects will be polynomials and rational functions in many variables, that are represented by arithmetic formulae. Here the word problem is simply proving algebraic identities. I will describe the history, motivation and the state-of-art of this word problem in two settings: when the variables commute, and when they do not.

For commuting variables, a probabilistic polynomial time algorithm was known for decades, and it remains a major open problem to find a deterministic counterpart. To explain this we will go on a tour of arithmetic analog of the P versus NP problem, permanents versus determinants, the GCT (Geometric Complexity Theory) program and more.

For non-commuting variables, no sub-exponential algorithm for the word problem was known (deterministic or probabilistic) till recently. I will describe a deterministic polynomial time algorithm based on the ideas of the first lecture, appealing to the theory of free skew fields and to degree bounds on invariant rings of linear group actions.

Finally, I will show how the two settings are related, and that their relation may be relevant to resolving the commutative problem and to other problems in arithmetic complexity.

This talk is self-contained, and requires no special background knowledge. The new material covered is taken mostly from https://arxiv.org/abs/1511.03730 and https://arxiv.org/abs/1711.08039