Representing Boolean functions as polynomials modulo composite numbers
type: Item
instance of: scholarly article
title: Representing Boolean functions as polynomials modulo composite numbers
zbMATH Open document ID: 0829.68057
DOI: 10.1007/BF01263424
author: David A. Mix Barrington
author: Richard Beigel
author: Steven Rudich
published in: Computational Complexity
publication date: 1995-04-06T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 741033
zbMATH Keywords: circuit complexity
zbMATH Keywords: boolean function
zbMATH Keywords: representation by symmetric polynomials
MaRDI profile type: Publication
cites work: Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
cites work: Non-uniform automata over groups
cites work: Finite monoids and the fine structure of NC 1
cites work: Relativized counting classes: Relations among thresholds, parity, and mods
cites work: Counting classes: Thresholds, parity, mods, and fewness
cites work: On the power of parity polynomial time
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: On the construction of parallel computers from various basis of Boolean functions
cites work: Relations among MOD-classes
cites work: \(NC^ 1\): The automata-theoretic viewpoint
cites work: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
cites work: A lower bound on the MOD 6 degree of the OR function
cites work: Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
cites work: Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
full work available at URL: https://doi.org/10.1007/bf01263424
OpenAlex ID: W2054996571
description: scientific article; zbMATH DE number 741033