Long time member Eric Zhu is giving a talk on group theory and how it relates to complexity!
It will cover the word representation problem along with its connections to undecidability. Here is an abstract:
“In this talk, I will discuss the word problem for groups. First, I will explain what group presentations are, in terms of generators and relations so that no group theory knowledge will be necessary. Then, I will state the word problem and give some examples of how one might go about trying to solve this, including a technique called normal forms and some different algorithms. Then, I will talk about what undecidability means for this problem and the related concept of unsolvability. I will give some examples of group presentations that are unsolvable, but proving why they are unsolvable may be left out due to difficulty. I may also discuss other similar group theoretic decision problems, given the time.”
If you are a student and are interested in giving a talk, please contact our talk coordinator Daniel Hathcock. We are very interested in hearing what the undergraduate student body is studying in Theory CS!
This meeting will be a talk on zero knowledge proofs by the chair of the school of computer science, Dr. Lance Fortnow (also Theory Club’s advisor)!
continue reading ❯