Laws@SRI-STRIPE.ARPA (Ken Laws) (10/07/86)
RIT Researchers Find Way to Reduce Transmission Errors, Communications of the ACM, Vol. 29, No. 7, July 1986, p. 702: Donald Kreher and Stanislaw Radziszowski at Rochester Institute of Technology have discovered a new geometry, the third 6-design, non-Euclidean geometry, that allows solution of difficult problems in designing error-correcting transmission codes. One problem with 99 integer equations and 132 unknowns was solved in 12 hours; previous search methods would have required several million centuries. Integer (Diophantine) equations are notoriously difficult to solve. Is this a breakthrough for other problem domains where search is used (e.g., bin packing, traveling salesman, map coloring, and the "approximately-solved" algorithms)? Is it a form of linear programming? -- Ken Laws