scientific article; zbMATH DE number 3744549
From MaRDI portal
Publication:3929052
Boolean functionscomputing discrete functions in polynomial timep-definabilitypolynomial analogue of the Meyer-Stockmeyer hierarchypolynomialsreductionsubroutinesubstitution
Other degrees and reducibilities in computability and recursion theory (03D30) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Polynomials (irreducibility, etc.) (11R09) Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99) Linear programming (90C05)
Cited in
(34)- Feasible arithmetic computations: Valiant's hypothesis
- There are no p-complete families of symmetric Boolean functions
- The complexity of partial derivatives
- A note on the determinant and permanent problem
- On the algebraic complexity of some families of coloured Tutte polynomials
- On the relative power of reduction notions in arithmetic circuit complexity
- Affine projections of symmetric polynomials.
- Small space analogues of Valiant's classes and the limitations of skew formulas
- Cook's versus Valiant's hypothesis
- Vanishing symmetric Kronecker coefficients
- A \(\tau \)-conjecture for Newton polygons
- A complexity theory of constructible functions and sheaves
- Lower bounds for the circuit size of partially homogeneous polynomials
- Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
- Boolean circuits versus arithmetic circuits
- Algebraic complexity classes
- Lower bounds for depth-4 formulas computing iterated matrix multiplication
- Permanent versus determinant: not via saturations
- On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract)
- Resource trade-offs in syntactically multilinear arithmetic circuits
- A Wronskian approach to the real \(\tau\)-conjecture
- No occurrence obstructions in geometric complexity theory
- On the complexity of computing a random Boolean function over the reals
- Even partitions in plethysms.
- On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
- Algorithmic uses of the Feferman-Vaught theorem
- \(P\) versus \(NP\) and geometry
- Rigid continuation paths II. structured polynomial systems
- On the complexity of scheduling unrelated parallel machines with limited preemptions
- Semialgebraic proofs, IPS lower bounds, and the -conjecture: can a natural number be negative?
- How I got to like graph polynomials
- Enumeration and asymptotic analysis of edge-disjoint triangle packings in complete graphs
- Iterated lower bound formulas: a diagonalization-based approach to proof complexity
- \textsf{VNP} = \textsf{VP} in the multilinear world
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3929052)
