Abstract:

  Consider a random k-DNF formula f: a disjunction of m clauses,
  each clause a conjunction of k literals out of {x(i),x(i)~, 1 <= i <= n}.
  
  Convincing evidence [trials,sort of proofs] show that to satisfy f by a
  fraction alpha of all vectors in Q={0,1}^n, m has to be in narrow band
  around a threshold value m(alpha,n,k).
  Each clause of f "covers" a subcube of Q of codimension k, it has a
  relative size 2^k in Q. The case of bounded k and alpha=1 [full cover] 
  have attracted much research. Relaxing to smaller subcubes, say k=logn 
  [relative size is 1/n], we can calculate the threshold m(alpha,n) and 
  estimate the bandwidth almost up to alpha=1. Geometric covers of 
  cubes Q=[0,1]^n or spheres are also treated.
  
  Subclasses of DNF are popular as targets of Learning algorithms, i.e.
  learning an approximation of f from [random] examples.
  We present an efficient algorithm for exact Learning of k-DNF when
  alpha has intermediate value, far from 0 and 1. It is based on
  calculating the 2nd order harmonics -- Fourier coefficients of f.
  
  Actually most of the arguments are pseudorandom, deriving from few 
  explicit statistical conditions [which hold WHP].
  e.g. for the learning algorithm [developed jointly with O. Gerlitz]
  the condition is that the clauses of f are edge disjoint --
  no two share a pair of variables.

  -------------------------------------------------------------------------
  This colloquium is a joint event with the "Haifa Winter Workshop on 
  Computer Science and Statistics" being held the same week (at the 
  University of Haifa.) 
  Further information: 
  
  http://rothschild.haifa.ac.il/csstat