Colloquium: Progress in computation of van der Waerden numbers

Windstream Room, Hardymon Building

Dr. Michal Kouril, University of Cincinnati

This talk presents reflections on the  evolution of the FPGA based solvers for van der  Waerden numbers which lead to computation of the last two known ones. The Van der Waerden number w(k,l), where k indicates number of partitions, l is the length of the arithmetic progression and n is the smallest number for which no coloring exists such that none of the k  blocks of the partition contain an arithmetic progression length l. I recap my previous results. In 2006  (these results were previously presented in Lexington) I succeeded in computation of W(2,6) using a cluster-based processing and later FPGA. In 2009 using the modified algorithms I computed W(3,4) (publication is preparation). The latest work have involved improving the solver in order to compute W(5,3). The runtime estimate for 5 Virtex 5 - XC5VLX110 is about 25 years and I expect further improvements in order to find better bound or even prove the number. I will review some of the pitfalls and optimizations during the development of the solvers as well as show the advantage of using equivalence checking tool such as CRYPTOL to verify and optimize the design.  

Speaker's page:  http://www.cs.uc.edu/~kourilm

 

Host:  Dr. Mirek Truszczynski