Login
Computer Science @ Rochester
Wednesday, May 01, 2002
11:00 AM
CSB 209
Ph.D. Thesis Proposal
Kumar Mayur Thakur
University of Rochester
Lower Bounds and Separations via Ambguity and Self-Reference
Rice's Theorem [Ric53] is a powerful tool in recursive function theory that allows one to prove a broad range of properties of Turing machines to be undecidable. Borchert and Stephan [BS00] started the search for analogous tools in complexity theory. They proved a Rice-style theorem in complexity theory, a result that allows one to prove a broad range of properties of boolean circuits to be intractable (under standard complexity-theoretic assumptions), in particular, hard for UP, the unambiguous version of NP. The broad class of properties that their results apply to are the class of nontrivial counting properties of boolean circuits. Hemaspaandra and Rothe [HR00] improved Borchert and Stephan's result; they improved the lower bound on the hardness of nontrivial counting properties from hardness for unambiguous nondeterminism to hardness for constant-ambiguity nondeterminism.

In this thesis, we provide a new, improved tool for proving the intractability (under standard complexity-theoretic hypotheses) of the same broad class of properties of boolean circuits that the previous two results dealt with. In particular, we prove that any nontrivial counting property of boolean circuits is hard for FewP, the polynomial-ambiguity version of NP. Thus, we raise the ambiguity tolerated by the lower bound from constant to polynomial. Furthermore, we prove, via an oracle construction using the Party Lemma of Cai et al. [CGH+80], that the polynomial-ambiguity lower bound cannot, in terms of the exact type of hardness reduction used, be improved much using relativizable techniques.

This talk will present our contributions toward finding Rice-style theorems in complexity theory. It will show that our hardness result for polynomial-ambiguity nondeterminism is rather tight. It will also briefly mention the other proposed research sub-topics in the thesis, namely (a) self-witnessing languages and collective completeness for promise classes, (b) length-respecting Turing reductions and (c) optimal bound on the nonuniform complexity of semi-feasible sets.