Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site ucbvax.BERKELEY.EDU
Path: utzoo!decvax!ucbvax!SRI-STRIPE.ARPA!Laws
From: Laws@SRI-STRIPE.ARPA (Ken Laws)
Newsgroups: mod.ai
Subject: Integer Equations
Message-ID: <12244938481.29.LAWS@SRI-STRIPE.ARPA>
Date: Tue, 7-Oct-86 13:36:01 EDT
Article-I.D.: SRI-STRI.12244938481.29.LAWS
Posted: Tue Oct  7 13:36:01 1986
Date-Received: Sat, 11-Oct-86 00:22:27 EDT
Sender: daemon@ucbvax.BERKELEY.EDU
Organization: The ARPA Internet
Lines: 17
Approved: ailist@sri-stripe.arpa

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