DIMACS Challenge Update: July 29, 1993 Just a reminder that if you would like to submit a paper for consideration for the October 11-13 conference on the Challenge, I need to receive it by August 3 (next Tuesday). In addition to the normal email route (challenge@dimacs.rutgers.edu), the street address for courier deliveries is DIMACS Challenge DIMACS/Rutgers University CORE Building 4th Floor, Room 406 Piscataway, NJ 08855-1179 A note on benchmarks: I have had a few enquiries on the benchmarks,generally along the lines of "Do I have to solve all of the instances". I would be very surprised if any code can solve all of the benchmark instances. The benchmarks are there to provide a common area to compare algorithms and heuristics. It is not necessary to solve all (or even any, though I would not encourage the complete ignoring of the benchmarks) of the instances to submit a paper to the Challenge. Conversely, a computational test that does not go beyond the benchmark instances may be too limited to adequately portray the advantages and disadvantages of an algorithm. Feel free to contact me if you have any questions. Mike Trick Challenge Coordinator/ Carnegie Mellon University NEW FILES: In addition to expanded benchmark instances (particularly for satisfiability and clique: see the benchmark directories), there are a few new files available: graph/contributed/brockington/graphgen.c: A graph generator that attempts to hide larger cliques in graphs. Some of these instances have been added to the graph/benchmarks/clique area. sat/contributed/crawford: README: A description of a method for generating propositional versions of parity learning problems. From the README: These theories are guaranteed to be SAT (assuming my generator is bug free !) but seem to be difficult for both systematic and local search based methods (there is some theoretical indication that they might be quite hard in general). Details are given in the README file. tableau.ps: This is the post-script version of our paper from AAAI. It reports on a large collection of experiments to determine as precisely as possible the location of the cross-over point in randomly generated 3-SAT problems. The main result is that at cross-over the number of clauses seems empirically to be a *linear* function of the number of variables.