A Caltech Library Service

Complexity of information extraction


Abu-Mostafa, Yaser Said (1983) Complexity of information extraction. Dissertation (Ph.D.), California Institute of Technology.


This thesis describes a mathematical theory that interrelates the basic concepts of complexity, cost, information and reliability. The accessibility of information, as opposed to its availability, is characterized. Universal bounds for complexity distribution, implementation cost and decision reliability are estimated. These bounds give rise to a methodology for any consistent definition of a complexity measure. The basic notions of pattern recognition and information theory are directly related to computational complexity.

Item Type:Thesis (Dissertation (Ph.D.))
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Awards:Milton and Francis Clauser Doctoral Prize, 1983
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Psaltis, Demetri
Thesis Committee:
  • Kechris, Alexander S.
  • Mead, Carver
  • Psaltis, Demetri
  • Posner, Edward C.
  • Ryser, Herbert J.
  • McEliece, Robert J.
  • Wilson, Richard M.
Defense Date:23 May 1983
Record Number:CaltechETD:etd-05142003-111719
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1786
Deposited By: Imported from ETD-db
Deposited On:14 May 2003
Last Modified:26 Dec 2012 02:42

Thesis Files

PDF (Abu-Mostafa_ys_1983.pdf) - Final Version
See Usage Policy.


Repository Staff Only: item control page