scientific article; zbMATH DE number 176508
From MaRDI portal
Publication:4035673
Boolean functiondeterministic threshold circuitsmultivariate polynomialprobabilistic threshold circuitsrandomized polynomial
Recommendations
- On Threshold Circuits and Polynomial Computation
- Satisfiability and derandomization for small polynomial threshold circuits
- Publication:3031835
- Quantified derandomization of linear threshold circuits
- Improved bounds for quantified derandomization of constant-depth circuits and polynomials
- Improved bounds for quantified derandomization of constant-depth circuits and polynomials
- A Note on Randomized Polynomial Time
- Polynomial-time random oracles and separating complexity classes
- Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions
- Computationally private randomizing polynomials and their applications
Cited in
(16)- The log-rank conjecture and low degree polynomials
- On sparse hard sets for counting classes
- On the computational power of depth-2 circuits with threshold and modulo gates
- On bounded-probability operators and C\(_ =\)P
- The expressive power of voting polynomials
- Saving queries with randomness
- Improved bounds for quantified derandomization of constant-depth circuits and polynomials
- On the power of deterministic reductions to C=P
- Generalized theorems on relationships among reducibility notions to certain complexity classes
- Threshold Computation and Cryptographic Security
- On closure properties of bounded two-sided error complexity classes
- A lower bound for monotone perceptrons
- The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
- Computational complexity of counting coincidences
- Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
- Complexity classes of equivalence problems revisited
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4035673)
