Fast exact algorithms using Hadamard product of polynomials

DOI10.1007/s00453-021-00900-0OpenAlexW2829833608MaRDI QIDQ832524

Rajit Datta, Abhranil Chatterjee, Partha Mukhopadhyay, V. Arvind

Publication date: 25 March 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/11571/

zbMATH Keywords

parameterized complexityarithmetic circuitsmultilinear monomial countingmultilinear monomial detection

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Evaluation of permanents in rings and semirings
• Algorithm engineering for color-coding with applications to signaling pathway detection
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• A probabilistic remark on algebraic program testing
• Deterministic polynomial identity testing in non-commutative models
• Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
• Integer multiplication in time \(O(n\log n)\)
• Modern Computer Algebra
• Arithmetic Circuits and the Hadamard Product of Polynomials
• Fast Parallel Computation of Polynomials Using Few Processors
• Arithmetic Circuits: A survey of recent results and open questions
• Diagonal Circuit Identity Testing and Lower Bounds
• Faster Algebraic Algorithms for Path and Packing Problems
• Counting Paths and Packings in Halves
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Sums of Like Powers of Multivariate Linear Forms
• Color-coding
• LIMITS and Applications of Group Algebras for Parameterized Problems
• Approximately counting and sampling small witnesses using a colourful decision oracle
• Extensor-coding
• Fine-grained reductions from approximate counting to decision
• Counting Solutions to Polynomial Systems via Reductions
• Parameterized Algorithms
• On the hardness of the noncommutative determinant
• On the hardness of the noncommutative determinant

This page was built for publication: Fast exact algorithms using Hadamard product of polynomials