Cohomology in Grothendieck Topologies and Lower Bounds in Boolean Complexity II: A Simple Example

Simple item page
dc.creatorFriedman, Joel
dc.date2006-04-06
dc.date.accessioned2026-07-07T07:09:20Z
dc.date.available2026-07-07T07:09:20Z
dc.descriptionIn a previous paper we have suggested a number of ideas to attack circuit size complexity with cohomology. As a simple example, we take circuits that can only compute the AND of two inputs, which essentially reduces to SET COVER. We show a very special case of the cohomological approach (one particular free category, using injective and superskyscraper sheaves) gives the linear programming bound coming from the relaxation of the standard integer programming reformulation of SET COVER.
dc.description8 pages
dc.identifierhttps://arxiv.org/abs/cs/0604024
dc.identifierhttp://arxiv.org/abs/cs/0604024
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/111024
dc.subjectComputational Complexity
dc.subjectAlgebraic Geometry
dc.titleCohomology in Grothendieck Topologies and Lower Bounds in Boolean Complexity II: A Simple Example
dc.typetext

Files

Collections

arXiv