On enumerating monomials and other combinatorial structures by polynomial interpolation

DOI10.1007/S00224-012-9442-ZzbMATH Open1298.68096OpenAlexW2031539449MaRDI QIDQ385504FDOQ385504

Authors: Yann Strozecki 

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

Recommendations

• Enumeration of the monomials of a polynomial and related complexity classes
• Interpolation polynomials. Application in findingsome combinatorial formulas
• scientific article; zbMATH DE number 6603592
• On monomial complete permutation polynomials
• Combinatorics of F-Polynomials
• Combinatorics of polynomials iterations
• scientific article; zbMATH DE number 123387
• Combinatorial algorithms for the interpolation of polynomials in dimension \(\geq 2\)
• Recurrence relations and enumerative interpretations of some combinatorial numbers and polynomials
• On enumeration of polynomial equivalence classes

zbMATH Keywords

interpolationcircuitNP-hardnessblack box polynomialenumeration complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Title not available (Why is that?)
• Computational Complexity
• The complexity of computing the permanent
• A probabilistic remark on algebraic program testing
• Parametrized complexity theory.
• Limits and Applications of Group Algebras for Parameterized Problems
• Title not available (Why is that?)
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Title not available (Why is that?)
• Title not available (Why is that?)
• Multiplying matrices faster than coppersmith-winograd
• Matrix multiplication via arithmetic progressions
• PRIMES is in P
• Characterizing Valiant's algebraic complexity classes
• Interpolating polynomials from their values
• Generating Linear Extensions Fast
• Completeness and reduction in algebraic complexity theory
• Matching is as easy as matrix inversion
• On generating all maximal independent sets
• First-order queries on structures of bounded degree are computable with constant delay
• Jacobian hits circuits: hitting-sets, lower bounds for depth-\(D\) occur-\(k\) formulas \& depth-\(3\) transcendence degree-\(k\) circuits
• Black-box identity testing of depth-4 multilinear circuits
• Matroid matching and some applications
• Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
• Expressing a fraction of two determinants as a determinant
• Interpolation of polynomials given by straight-line programs
• Feasible arithmetic computations: Valiant's hypothesis
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• Listing graphs that satisfy first-order sentences
• Deterministic identity testing of depth-\(4\) multilinear circuits with bounded top fan-in
• Monomials in arithmetic circuits: complete problems in the counting hierarchy
• 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
• Title not available (Why is that?)
• Randomness efficient identity testing of multivariate polynomials
• Linear delay enumeration and monadic second-order logic

Cited In (11)

• Enumerating models of DNF faster: breaking the dependency on the formula size
• Incremental delay enumeration: space and time
• The Hermit-type reproducing kernel particle method for elasticity problems
• Combinatorial algorithms for the interpolation of polynomials in dimension \(\geq 2\)
• Enumeration of the monomials of a polynomial and related complexity classes
• Monomials in arithmetic circuits: complete problems in the counting hierarchy
• Derandomizing isolation in space-bounded settings
• Radial basis reproducing kernel particle method for piezoelectric materials
• The numerical analysis of piezoelectric ceramics based on the Hermite-type RPIM
• Monomials, multilinearity and identity testing in simple read-restricted circuits
• Weight enumerators, intersection enumerators, and Jacobi polynomials

This page was built for publication: On enumerating monomials and other combinatorial structures by polynomial interpolation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q385504)