Area

Combinatorial Computing, Algorithms, Cryptography, Complexity

The specific problems of particular interest are algorithms for hard problems like: Ramsey numbers, combinatorial designs, arithmetic of large integers, tests for primality, factoring into primes and other combinatorial problems in graph theory. The general problems of particular interest are in the complexity of algorithms, hierarchies of complexity classes and related areas, such as P=NP conjecture.

My past and current projects are best clustered into the domains: Ramsey numbers | graph theory | applied cryptography | combinatorial designs | miscellaneous.

Main Results

I was fortunate to obtain some interesting results in computational discrete mathematics, of which the most cherished are:

• 1986, the discovery of the first simple 6-(14,7,4) design, the smallest possible 6-design
  jointly with Don Kreher [111], [102].

• 1990, the computation of the first classical Ramsey number for hypergraphs R(4,4;3) = 13
  jointly with Brendan McKay [94].

• 1993, 1995, the computation of the classical Ramsey number for graphs
  R(4,5) = 25 [87], and the upper bound R(5,5) <= 49 [84]
  jointly with Brendan McKay.

• 1995, computational proof of the nonexistence of 4-(12,6,6) designs
  answering the last open existence question in design theory for at most 12 points
  jointly with Brendan McKay [86].

• 1998, the computation of the smallest unknown Folkman number F(3,3;5) = 15
  jointly with Konrad Piwakowski and Sebastian Urbański [81].

• 2001, an upper bound for the 4-color Ramsey number R(3,3,3,3) <= 62
  jointly with Susan Fettes and Richard Kramer [76].

• 2004, general and computational constructive lower bounds for
  classical two-color [74] and multicolor [72] Ramsey numbers
  jointly with Xu Xiaodong, Xie Zheng and Geoffrey Exoo.

• 2006, (22,8,4)-designs do not exist [68]
  jointly with Richard Bilous, Clement W. H. Lam, Larry H. Thiel, (Ben) P. C. Li, G. H. John van Rees, Wolfgang Holzmann and Hadi Kharaghani.

• 2009, 2011, progress on graph reconsruction conjecture for vertex and edge deleted cards,
  existential and universal reconstruction numbers for up to 11 vertices
  jointly with David Rivshin [59], [53].

• 2011, 2012, more constructive lower bounds for classical Ramsey numbers [47]
  and their relation to Shannon capacity of noisy channels [42]
  jointly with Xu Xiaodong.

• 2013, progress on bounds for Ramsey numbers R(3,k) [43] and R(3,Kk-e) [39]
  jointly with Jan Goedgebeur.

• 2016, on R(3,k+1)-R(3,k) [26]
  jointly with Rujie Zhu and Xiaodong Xu.

• 2022, on Folkman (K4-e)-free graphs [5]
  jointly with Zohair Hassan, Yu Jiang, David Narváez and Xiaodong Xu.

CPU intensive computations on networked computers are an essential tool and an object of study for most researched problems, including those listed above.

back to spr's main page