Open problem
Talks about or related to problems that have not yet been solved. Some open problems are known by a famous guess, often called a conjecture.
There have been 1 completed talk and 7 topic suggestions tagged with open problem.
Related Tags
- computational complexity
- theoretical computer science
- prime number
- automaton
- Galois theory
- group theory
- computational mathematics
- computability
Completed Talks
Inverse Galois Theory
Delivered by David Liu on Friday March 17, 2017
Almost 200 years after Évariste Galois's death, there is still one question about Galois groups — the symmetries of the roots of polynomials, that still remains unsolved. This is the Inverse Galois Problem — whether every group is a Galois group of a Galois extension of the rational numbers. In this talk, I will give an overview of the progress that has been made, the approaches that mathematicians are making, and directions for further research.
A note on the requirements for this talk: It is recommended that you be comfortable with groups, fields, field extensions, automorphisms, and basic Galois theory. This requirement can be met by any of the following suggested alternatives:
having taken PMATH 347, and currently taking PMATH 348;
having taken PMATH 347, and coming for the prerequisite knowledge presentation (see below);
having equivalent knowledge to PMATH 347 and PMATH 348;
otherwise, if you are currently taking or have taken MATH 146, this talk is still accessible, but it is highly recommended that you read An Introduction to Galois Theory by Dan Goodman, and watch this 18-minute lecture by Matthew Salomone (after reading the article) and optionally also come for the prerequisite knowledge presentation
A prerequisite knowledge presentation about Galois theory will be given at 17:00, prior to the beginning of the talk at 17:30. This presentation will last about 20 minutes. If you are unfamiliar with the material, it is recommended that you read some of the linked material above in addition to attending this presentation. Attending this presentation is optional. The reference material used for this presentation is the Galois Theory document.
Talk Suggestions
Complexity of Matrix Multiplication
Volker Strassen showed that $n^3$ matrix multiplication was not optimal in 1969. Since then, new algorithms such as Coppersmith-Winograd have further improved the time complexity of matrix multiplication. It is conjectured that matrix multiplication is possible in $O(n^{2+ɛ})$ for any $ɛ>0$, however small. This is one of the few remaining open problems in finite-dimensional linear algebra.
Possible reference materials for this topic include
Quick links: Google search, arXiv.org search, propose to present a talk
algebra algorithm computational mathematics computer science group theory linear algebra open problem
Distribution of Primes Modulo p
Possible reference materials for this topic include
Quick links: Google search, arXiv.org search, propose to present a talk
number theory open problem prime number
P vs. NP
Possible reference materials for this topic include
Arora, Bazak: Computational Complexity
Quick links: Google search, arXiv.org search, propose to present a talk
computability computational complexity computer science open problem theoretical computer science
Plausible Conjectures
Possible reference materials for this topic include
Quick links: Google search, arXiv.org search, propose to present a talk
first year friendly open problem
Separating Words Problem
Given two strings, we can write a computer program to tell them apart. A special kind of very simple computer program that accepts or rejects strings, using only a finite number of states while reading the string, is called a deterministic finite automaton. (These deterministic finite automata can also be expressed as a regular expression.) For any two strings of length $n$, there is some deterministic finite automaton (or regular expression) that recognizes one and not the other, and there is some smallest one. In the worst case, it is known (Robson 1989) that any two strings of length $n$ can be separated by an automaton of size $O(n^{2/5} (\log n)^{3/5})$, but this is not known to be optimal. The optimal upper bound remains an open problem.
Possible reference materials for this topic include
Quick links: Google search, arXiv.org search, propose to present a talk
automaton computer science open problem theoretical computer science
The Riemann Hypothesis
Possible reference materials for this topic include
Quick links: Google search, arXiv.org search, propose to present a talk
number theory open problem prime number
Unique Games Conjecture
The Unique Games Conjecture, if true, implies that many problems that lack exact polynomial time solutions also lack approximate polynomial time solutions. It was formulated by Subhash Khot in 2002 and is still unsolved.
Possible reference materials for this topic include
Quick links: Google search, arXiv.org search, propose to present a talk
computational complexity computer science open problem theoretical computer science