On enumerating monomials and other combinatorial structures by polynomial interpolation
From MaRDI portal
Publication:385504
DOI10.1007/s00224-012-9442-zzbMath1298.68096OpenAlexW2031539449MaRDI QIDQ385504
Publication date: 2 December 2013
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-012-9442-z
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)
Related Items
Monomials, multilinearity and identity testing in simple read-restricted circuits ⋮ The Hermit-Type Reproducing Kernel Particle Method for Elasticity Problems ⋮ Radial basis reproducing kernel particle method for piezoelectric materials ⋮ The numerical analysis of piezoelectric ceramics based on the Hermite-type RPIM ⋮ Enumerating models of DNF faster: breaking the dependency on the formula size ⋮ Incremental delay enumeration: space and time ⋮ A complexity theory for hard enumeration problems ⋮ Derandomizing Isolation in Space-Bounded Settings ⋮ Monomials in arithmetic circuits: complete problems in the counting hierarchy
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Interpolating polynomials from their values
- Matrix multiplication via arithmetic progressions
- Linear delay enumeration and monadic second-order logic
- Interpolation of polynomials given by straight-line programs
- Matching is as easy as matrix inversion
- On generating all maximal independent sets
- Feasible arithmetic computations: Valiant's hypothesis
- Matroid matching and some applications
- A probabilistic remark on algebraic program testing
- The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
- Listing graphs that satisfy first-order sentences
- Completeness and reduction in algebraic complexity theory
- PRIMES is in P
- Characterizing Valiant's algebraic complexity classes
- Parametrized complexity theory.
- Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in
- Identity Testing, Multilinearity Testing, and Monomials in Read-Once/Twice Formulas and Branching Programs
- Enumeration Complexity of Logical Query Problems with Second-order Variables
- An Almost Optimal Rank Bound for Depth-3 Identities
- The Complexity of Acyclic Subhypergraph Problems
- A Course in Enumeration
- Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm
- Enumeration of the Monomials of a Polynomial and Related Complexity Classes
- Limits and Applications of Group Algebras for Parameterized Problems
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
- Generating Linear Extensions Fast
- Randomness efficient identity testing of multivariate polynomials
- First-order queries on structures of bounded degree are computable with constant delay
- Expressing a fraction of two determinants as a determinant
- Computational Complexity
- Jacobian hits circuits
- Multiplying matrices faster than coppersmith-winograd
- Black-box identity testing of depth-4 multilinear circuits
