Representing Boolean functions as polynomials modulo composite numbers
From MaRDI portal
Publication:1346617
DOI10.1007/BF01263424zbMath0829.68057OpenAlexW2054996571MaRDI QIDQ1346617
David A. Mix Barrington, Richard Beigel, Steven Rudich
Publication date: 6 April 1995
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01263424
Symbolic computation and algebraic computation (68W30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (27)
Boolean functions: degree and support ⋮ Polynomial-time algorithms for checking some properties of Boolean functions given by polynomials ⋮ A lower bound for depth-3 circuits with MOD \(m\) gates ⋮ Representing Boolean functions as polynomials modulo composite numbers ⋮ Pairs of codes with prescribed Hamming distances and coincidences ⋮ Towards breaking the exponential barrier for general secret sharing ⋮ Evaluating spectral norms for constant depth circuits with symmetric gates ⋮ Nearly complete graphs decomposable into large induced matchings and their applications ⋮ Upper and lower bounds for some depth-3 circuit classes ⋮ \(\text{Count}(q)\) does not imply \(\text{Count}(p)\) ⋮ Predicate encryption from bilinear maps and one-sided probabilistic rank ⋮ Permanent v. determinant: an exponential lower bound assuming symmetry and a potential path towards Valiant's conjecture ⋮ On the power of circuits with gates of low \(L_{1}\) norms. ⋮ Constructing Ramsey graphs from Boolean function representations ⋮ Unnamed Item ⋮ Standard monomials for \(q\)-uniform families and a conjecture of Babai and Frankl ⋮ On the correlation of symmetric functions ⋮ Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification ⋮ The Iota-Delta Function as an Alternative to Boolean Formalism ⋮ Learning Read-Constant Polynomials of Constant Degree Modulo Composites ⋮ Learning read-constant polynomials of constant degree modulo composites ⋮ Symmetric polynomials over \(\mathbb Z_{m}\) and simultaneous communication protocols ⋮ Co-orthogonal codes ⋮ Approximate evaluations of characteristic polynomials of Boolean functions ⋮ On the correlation of symmetric functions ⋮ Parity helps to compute majority ⋮ Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
Cites Work
- Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
- \(NC^ 1\): The automata-theoretic viewpoint
- Non-uniform automata over groups
- Relations among MOD-classes
- On the construction of parallel computers from various basis of Boolean functions
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- A lower bound on the MOD 6 degree of the OR function
- Representing Boolean functions as polynomials modulo composite numbers
- Relativized counting classes: Relations among thresholds, parity, and mods
- Parity, circuits, and the polynomial-time hierarchy
- Finite monoids and the fine structure of NC 1
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- On the power of parity polynomial time
- Counting classes: Thresholds, parity, mods, and fewness
This page was built for publication: Representing Boolean functions as polynomials modulo composite numbers
