Show simple item record

dc.contributorRobert Sloan Program Manageren_US
dc.contributor.authorKenneth Regan Principal Investigatoren_US
dc.datestart 09/15/1999en_US
dc.dateexpiration 08/31/2002en_US
dc.date.accessioned2014-04-02T18:16:15Z
dc.date.available2014-04-02T18:16:15Z
dc.date.issued2014-04-02
dc.identifier9821040en_US
dc.identifier.urihttp://hdl.handle.net/10477/22370
dc.descriptionGrant Amount: $ 178529en_US
dc.description.abstractThis project extends the "Polynomial Method" in computational complexity theory to involve polynomial ideas and algebraic geometry. The attraction is that the latter concepts are hard enough to surmount the "Natural Proofs" obstacle to progress on lower bounds, yet are still part of a natural and important body mathematics. The Grobner theory of polynomial ideas shows regard in which the permanent function is more complex than the determinant, and combining it with an idea analogous to Hastad's method of restrictions shows promise of separating the permanent's complexity class #P from the NC hierarchy. The project also aims to quantify the computational significance of non-uniformity in circuit classes, growing out from the tightening the "Size-expansion tradeoffs" on circuits for natural computational problems obtained by the PI, determining whether the "Natural Proofs" framework carries over irom polynomial to quasilinear tine, and extending work by Forthnow on quasi-linear size circuit classes. The objective of this work is to increase scientific knowledge about the intrinsic cost of computational problems, which is important to researchers in many fields.en_US
dc.titleLow-Level Complexity and Hard Conceptsen_US
dc.typeNSF Granten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record