🚀 go-pugleaf

      DEPARTMENT OF COMPUTER SCIENCE
        COLORADO STATE UNIVERSITY

               BARNEY'S
      MONDAY AFTERNOON CLUB SEMINAR

	Speaker:  Soraya Rana
		  Department of Computer Science
		  Colorado State University

	   Date:  Monday, April 20, 1998
	   Time:  4:00-5:00 p.m.
	  Place:  100 USC

	Refreshments:  following the talk

  A TRACTABLE WALSH ANALYSIS OF SAT AND ITS
     IMPLICATIONS FOR GENETIC ALGORITHMS

    Walsh Transforms measure all sources of non-
 linear interactions for functions that have a bit 
 representation.  There can be exponentially many 
 nonlinear interactions, and exactly computing all 
 Walsh coefficients is usually intractable for non-
 trivial functions.  I will provide an overview of 
 Walsh Analysis and how it relates to genetic algo-
 rithms.  I will then show that SAT problems eval-
 uated as MAXSAT functions have a highly restricted
 set of nonzero Walsh coefficients and that those 
 coefficients can be computed in linear time with 
 respect to the number of clauses.  This analysis
 suggests why standard simple genetic algorithms 
 should perform poorly on MAXSAT problems.


The BMAC seminar schedule can be found by clicking on 
the "Upcoming Events" button on the Computer Science 
Department's web page at http://www.cs.colostate.edu/