A complexity theory of constructible functions and sheaves

DOI10.1007/s10208-014-9222-zzbMath1349.68098arXiv1309.5905OpenAlexW2071238863MaRDI QIDQ2340508

Saugata Basu

Publication date: 20 April 2015

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1309.5905

zbMATH Keywords

polynomial hierarchyconstructible functionsconstructible sheavescomplexity classesadjoint functors

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Semialgebraic sets and related spaces (14P10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Topology of real algebraic varieties (14P25)

Related Items (4)

Discrete Morse theory for computing cellular sheaf cohomology ⋮ On the Reeb spaces of definable maps ⋮ CATEGORICAL COMPLEXITY ⋮ Complexity classes and completeness in algebraic geometry

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cohomology of sheaves
• Effective Hironaka resolution and its complexity
• A complex analogue of Toda's theorem
• Singularités des systèmes différentiels de Gauss-Manin. Avec des contributions de Lo Kam Chan, Philippe Maisonobe et Jean-Etienne Rombaldi
• The complexity of computing the permanent
• Motivic aspects of Hodge theory
• Operations on constructible functions
• Integration of positive constructible functions against Euler characteristic and dimension
• Efficient algorithm for computing the Euler-Poincaré characteristic of a semi-algebraic set defined by few quadratic inequalities
• Computing the top Betti numbers of semialgebraic sets defined by quadratic inequalities in polynomial time
• Computing the first Betti number of a semi-algebraic set
• Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials
• A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• Singularities and topology of hypersurfaces
• Sheaves in geometry and logic: a first introduction to topos theory
• Cohomologie étale. Seminaire de géométrie algébrique du Bois-Marie SGA 4 1/2 par P. Deligne, avec la collaboration de J. F. Boutot, A. Grothendieck, L. Illusie et J. L. Verdier
• The polynomial-time hierarchy
• Complexity of deciding Tarski algebra
• On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets
• Sheaves in topology
• Completeness and reduction in algebraic complexity theory
• Computing the Euler-Poincaré characteristics of sign conditions
• Constructible function and motivic integration. I.
• Lower bounds for arithmetic networks. II: Sum of Betti numbers
• Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem
• Feasibility testing for systems of real quadratic equations
• Computing the first few Betti numbers of semi-algebraic sets in single exponential time
• Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
• Théorie de Hodge. II. (Hodge theory. II)
• Théorie de Hodge. III
• Equations différentielles à points singuliers réguliers
• Geometric Complexity Theory I: An Approach to thePvs.NPand Related Problems
• Euler integration over definable functions
• An Overview of Mathematical Issues Arising in the Geometric Complexity Theory Approach to $\mathbf{VP}\neq\mathbf{VNP}$
• PP is as Hard as the Polynomial-Time Hierarchy
• Bounds on numers of vectors of multiplicities for polynomials which are easy to compute
• Bounding the number of stable homotopy types of a parametrized family of semi-algebraic sets defined by quadratic inequalities
• Semi-Algebraic Local-Triviality in Semi-Algebraic Mappings
• Torification and factorization of birational maps
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• The universal Euler characteristic for varieties of characteristic zero
• On the number of cells defined by a family of polynomials on a variety
• Approximation of definable sets by compact families, and upper bounds on homotopy and homology
• On the number of homotopy types of fibres of a definable map
• On the Betti Numbers of Real Varieties
• Decision tree complexity and Betti numbers
• Algorithms in real algebraic geometry

This page was built for publication: A complexity theory of constructible functions and sheaves