NSF Org:	CCF Division of Computing and Communication Foundations
Recipient:	UNIVERSITY OF TEXAS AT AUSTIN
Initial Amendment Date:	July 2, 1999
Latest Amendment Date:	May 9, 2002
Award Number:	9874862
Award Instrument:	Continuing Grant
Program Manager:	David Du CCF  Division of Computing and Communication Foundations CSE  Directorate for Computer and Information Science and Engineering
Start Date:	July 15, 1999
End Date:	June 30, 2004 (Estimated)
Total Intended Award Amount:	$200,000.00
Total Awarded Amount to Date:	$200,000.00
Funds Obligated to Date:	FY 1999 = $100,000.00 FY 2001 = $50,000.00 FY 2002 = $50,000.00
History of Investigator:	Anna Gal (Principal Investigator) panni@cs.utexas.edu
Recipient Sponsored Research Office:	University of Texas at Austin 110 INNER CAMPUS DR AUSTIN TX  US  78712-1139 (512)471-6424
Sponsor Congressional District:	25
Primary Place of Performance:	University of Texas at Austin 110 INNER CAMPUS DR AUSTIN TX  US  78712-1139
Primary Place of Performance Congressional District:	25
Unique Entity Identifier (UEI):	V6AFQPN18437
Parent UEI:
NSF Program(s):	THEORY OF COMPUTING
Primary Program Source:	01000102DB NSF RESEARCH & RELATED ACTIVIT app-0102  app-0199
Program Reference Code(s):	1045, 9216, HPCC
Program Element Code(s):	286000
Award Agency Code:	4900
Fund Agency Code:	4900
Assistance Listing Number(s):	47.070

ABSTRACT


Gal
CCR-9874862


This project studies combinatorial and algebraic models of computation for Boolean functions. Such models are Boolean circuits and formulae, branching programs, span programs and models of communication complexity. The complexity of computational problems in these models corresponds to their inherent complexity in terms of important computational resources.

The main questions addressed in this research are: finding new methods for proving complexity lower bounds, the role of randomness and pseudorandomness in the complexity of Boolean functions, and issues of fault tolerance in the above models. The educational component of the project includes the development of an upper level undergraduate course on fault tolerance and error correcting codes, and development of a series of graduate research courses in complexity theory.

Please report errors in award information by writing to: awardsearch@nsf.gov.