scientific article

zbMATH Open0764.94026MaRDI QIDQ4035673FDOQ4035673

Jun Tarui

Publication date: 18 May 1993

Title of this publication is not available (Why is that?)

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

zbMATH Keywords

Boolean functionmultivariate polynomialdeterministic threshold circuitsprobabilistic threshold circuitsrandomized polynomial

Mathematics Subject Classification ID

Cited In (15)

• On the computational power of depth-2 circuits with threshold and modulo gates
• Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
• Improved bounds for quantified derandomization of constant-depth circuits and polynomials
• On closure properties of bounded two-sided error complexity classes
• Complexity classes of equivalence problems revisited
• Saving queries with randomness
• Generalized theorems on relationships among reducibility notions to certain complexity classes
• On sparse hard sets for counting classes
• The expressive power of voting polynomials
• Computational complexity of counting coincidences
• On bounded-probability operators and C\(_ =\)P
• The log-rank conjecture and low degree polynomials
• The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
• On the power of deterministic reductions to C=P
• A lower bound for monotone perceptrons

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)