TITLE: Broad-Brush Theorems for Determining Problem Complexity

Mayur Thakur
Department of Computer Science, University of Rochester

2:00PM Wednesday, November 26, 2003
149 Cullinane Hall

ABSTRACT:

Programmers, computer science researchers, and engineers need to
determine the computational complexity of problems on a near-daily
basis, and they typically ask the following questions: Is there an
efficient algorithm for the problem?  Is the problem hard?  If so, how
hard is the problem?  It is desirable to have easily applied tools
(theorems, classification tests, complete characterizations, etc.)
that in one fell swoop classify a large class of problems in the
domain of interest.  Rice's Theorem is one such classic and powerful
tool from recursive function theory.  It classifies (as either
decidable or undecidable) each language property of the recursively
enumerable sets.

This talk will survey results on complexity-theoretic Rice-style
theorems.  We obtain the strongest known Rice-style theorem for a
broad class of properties of Boolean circuits, and show that this
result cannot be much improved using relativizable techniques.  We
also establish a generalized complexity-theoretic Rice-style theorem
that holds for language properties of many important problem classes.


BIO-SKETCH:

Mayur Thakur is a Ph.D. candidate in the department of Computer
Science at the University of Rochester.  His research interests
include algorithms and computational complexity theory---in
particular, Rice-style theorems in complexity theory, one-way
functions, network vulnerability detection and topology inference,
cyclomatic number problems in hypergraphs, semi-feasible algorithms,
data-streaming algorithms, cycle-length modularity problems in graphs,
theoretical models of simulations, query-monotonic database (oracle)
access, and quantum computing.