The circuit complexity of checking polynomiality for functions over residue ring modulo a composite number is linear
type: Item
instance of: scholarly article
title: The circuit complexity of checking polynomiality for functions over residue ring modulo a composite number is linear
zbMATH Open document ID: 1275.65099
DOI: 10.3103/S0278641913010032
author: Svetlana N. Selezneva
published in: Moscow University Computational Mathematics and Cybernetics
publication date: 2013-08-15T00:00:00Z
review text: This paper studies the circuit complexity of checking the properties of Boolean and multivalued functions. In fact, the problem of checking polynomiality of \(k\)-valued logic functions is considered. The author considers in detail the case of an arbitrary composite \(k\). An algorithm is described that, by the vector of values of \(k\)-valued logic functions \(f(x_1,\dots,x_n)\), checks whether this function can be represented by a polynomial modulo \(k\) and, if the answer is positive, then one of its polynomials is constructed.
Mathematics Subject Classification ID: 65Y20
Mathematics Subject Classification ID: 06E30
Mathematics Subject Classification ID: 03B50
zbMATH DE Number: 6198425
zbMATH Keywords: function over a finite ring
zbMATH Keywords: polynomial over a finite ring
zbMATH Keywords: polynomial function
zbMATH Keywords: algorithm
zbMATH Keywords: circuit
zbMATH Keywords: circuit complexity
zbMATH Keywords: multivalued functions
zbMATH Keywords: \(k\)-valued logic functions
MaRDI profile type: Publication
cites work: Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
cites work: Q3807115
cites work: Q3340780
cites work: Q5445419
cites work: A fast algorithm for the construction of polynomials modulo k for k-valued functions for composite k
cites work: A Generalization of Fermat's Theorem
cites work: On polynomial functions (mod m)
cites work: Q3898440
full work available at URL: s0278641913010032
OpenAlex ID: W2076623897
Recommended article: Constructing Polynomials for Functions over Residue Rings Modulo a Composite Number in Linear Time
Recommended article: Complex polynomials and circuit lower bounds for modular counting
Recommended article: An Upper Bound on the Complexity of Multiplication of Polynomials Modulo a Power of an Irreducible Polynomial
Recommended article: A faster algorithm for testing polynomial representability of functions over finite integer rings
Recommended article: On the reduction in multiplicative complexity achieved by the polynomial residue number system
Recommended article: Q3221975
Recommended article: Q4036870
Recommended article: Computing modular polynomials in quasi-linear time
Recommended article: Efficient checking of polynomials and proofs and the hardness of approximation problems
Recommended article: Polynomial multiplication over finite fields: from quadratic to straight-line complexity
description: scientific article; zbMATH DE number 6198425