home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / ba / seminars / 757 next >
Encoding:
Internet Message Format  |  1992-12-23  |  1.2 KB
  1. Path: sparky!uunet!spool.mu.edu!agate!darkstar.UCSC.EDU!gerri
  2. From: gerri@cse.ucsc.edu (Gerri McLellan)
  3. Newsgroups: ba.seminars,ucsc.baskin.general
  4. Subject: UCSC CE/CIS Research Seminar 1/14/93
  5. Date: 23 Dec 1992 16:17:55 GMT
  6. Organization: University of California, Santa Cruz (CE/CIS Boards)
  7. Lines: 29
  8. Distribution: ba ucsc
  9. Message-ID: <1ha3fjINNpkk@darkstar.UCSC.EDU>
  10. NNTP-Posting-Host: rio.ucsc.edu
  11.  
  12. UC Santa Cruz:        Computer & Information Sciences, and
  13.             Computer Engineering
  14.  
  15. RESEARCH SEMINAR:    Thursday, January 14, 1993, 10:30 - 11:30 AM
  16.             Room 330, Applied Sciences Building
  17.             Refreshments at 10:15.
  18.  
  19. Muli Safra, Stanford University, will speak on "Probabilistic Checking of
  20. Proof and the Hardness of Approximation Problems"
  21.  
  22. Abstract:
  23.  
  24. The talk will discuss a new characterization of the class NP --- as
  25. all languages whose membership proofs can be verified
  26. probabilistically, using a small number of random bits and reading
  27. only a few bits of the membership proof --- and the application of
  28. this characterization to show NP-hardness of various approximation
  29. problems.
  30.  
  31.  
  32. __________________________
  33.  
  34. Anyone needing special arrangements to accommodate a disability is
  35. encouraged to call Gerri McLellan at the Baskin Center - (408) 459-3695.
  36.  
  37.  
  38.  
  39.  
  40.  
  41.