Personal tools

Necktie knots, formal languages and network security

Speaker: Mikael Vejdemo-Johansson Affiliations: Jozef Stefan Institute (JSI), Royal Institute of Technology (KTH), and the IMA (at University of Minnesota)

  • Computer Science Seminar
  • Geometry/ Topology Seminar
When Fri, Feb 28, 2014
from 11:00 AM to 12:00 PM
Where TBD
Contact Name
Contact Phone 3149777002
Add event to calendar vCal

A chore for some, space for personal expression for others, the necktie knot used to have very few specific knots in widespread use. In their 1999 paper, Fink & Mao (Designing tie knots by random walks." Nature 398, no. 6722 (1999): 31-32) list all possible ways to tie a necktie. They limit their enumeration task by focusing on knots that present a flat front just like all the classical tie knots. This way they established a list of 85 possible tie knots.


Tie knots with intricate patterns of the necktie winding into symmetric but no longer at front displays have emerged in the past decade, introduced by the movie Matrix Reloaded and recreated hobbyists. These tie knots are tied with the narrow end of the tie, wrapping it to create patterns on the surface of the tie knot. As such these knots are not covered by the listing proposed by Fink & Mao.


With a team of collaborators I have extended the listing by Fink and Mao to cover these new tie knots. While doing this we have been able to determine the computational complexity classes of the grammar that describes tie knots.


The formal language techniques that help us analyze the tie knot grammars are used in contemporary security research: a large class of security problems online emerge from different implementations of a communications protocol disagreeing on the actual grammar used. We will talk about the connections between the language techniques for tie knots and those that help us analyze security.


For recent news coverage on this result, see the following:

« April 2018 »
Upcoming Events
Geometry/ Topology Seminar
Tue, Apr 24, 2018
Necessary and Sufficient Conditions for a Triangle Comparison Theorem, I James Hebda, SLU
Math/CS Club
Wed, Apr 25, 2018
The Mathematical Match Game Brody Johnson, SLU
PhD Oral Defense
Thu, Apr 26, 2018
Finite, fiber-preserving group actions on orientable Seifert manifolds Benjamin Peet, SLU
PhD Oral Exam
Fri, Apr 27, 2018
Leavitt Path Superalgebras Katie Radler, SLU
Annual Awards Ceremony
Fri, Apr 27, 2018
The 2018 Math & Statistics Department Award Ceremony Featuring Sarah Greenwald, Appalachian State University
Previous events…
Upcoming events…