"We report results from large-scale experiments in satisfiability testing. As has been observed by others, testing the satisfiability of random formulas often appears surprisingly easy. Here we show that by using the right distribution of instances, and appropriate parameter values, it is possible to generate random formulas that are hard, that is, for which satisfiability testing is quite difficult. Our results provide a benchmark for the evaluation of satisfiability-testing procedures." Proc. AAAI-92.

"We introduce a greedy local search procedure called GSAT for solving propositional satisfiability problems. Our experiments show that this procedure can be used to solve hard, randomly generated problems that are an order of magnitude larger than those that can be handled by more traditional approaches such as the Davis-Putnam procedure or resolution. We also show that GSAT can solve structured satisfiability problems quickly. In particular, we solve encodings of graph coloring problems, N-queens, and Boolean induction. General application strategies and limitations of the approach are also discussed. GSAT is best viewed as a model-finding procedure. Its good performance suggests that it may be advantageous to reformulate reasoning tasks that have traditionally been viewed as theorem-proving problems as model-finding tasks." Proc. AAAI-92.

McGraw-Hill

JAR, 8 (2), 183-212.

Viewing n-variable boolean functions as vectors in'R'2", we invoke tools from linear algebra and linear programming to derive new results on the realizability of boolean functions using threshold gat.es. Using this approach, one can obtain: (1) upper-bounds on the number of spurious memories in HopfielJ networks, and on the number of functions implementable by a depth-d threshold circuit; (2) a lower bound on the number of ort.hogonal input.

Viewing n-variable boolean functions as vectors in'R'2", we invoke tools from linear algebra and linear programming to derive new results on the realizability of boolean functions using threshold gat.es. Using this approach, one can obtain: (1) upper-bounds on the number of spurious memories in HopfielJ networks, and on the number of functions implementable by a depth-d threshold circuit; (2) a lower bound on the number of ort.hogonal input.

Viewing n-variable boolean functions as vectors in'R'2", we invoke tools from linear algebra and linear programming to derive new results on the realizability of boolean functions using threshold gat.es. Using this approach, one can obtain: (1) upper-bounds on the number of spurious memories in HopfielJ networks, and on the number of functions implementable by a depth-d threshold circuit; (2) a lower bound on the number of ort.hogonal input.

Based Analysis of Indirect Speech Acts.

There has been a good deal of discussion recently about the possibility of standardizing knowledge representation efforts, including the development of an interlingua, or knowledge interchange format (KIF), that would allow developers of declarative knowledge to share their results with other AI researchers. In this article, I examine the practicality of this idea. I present some philosophical arguments against it, describe a straw-man KIF, and suggest specific experiments that would help explore these issues.

Intelligence (AAAI) hopes that these This year's conference featured a new A talk united by a set of related research This year's program represented an by Jim Green0 addressed modeling issues. Constraint this approach is not seen There was time to interact Reasoning and Component Technologies as often today. Where is it session following each set of presentations. Highlights from the program focused on a presentation on among the accepted papers. A panel entitled "How Long which ran for two consecutive days Until the Household Robot: The For the first time, Innovative Applications during the conference. The emergence State of the Art in Robotics" featured in Artificial Intelligence (IAAI) of the forum Planning, Perception, speakers from industry and Carnegie presentations and AI Online interactive and Robotics reflected a recent trend Mellon's Robotic Institute, who panels were presented concurrently in Planning, with videotapes and a live robot providing an impressive demonstration Perception, and Robotics included demonstration.