scientific article; zbMATH DE number 176875

<a class="pub-badge pub-badge--grey" href="https://zbmath.org/0769.68038" rel="nofollow">zbMATH</a><a class="pub-badge pub-badge--mardi" href="https://portal.mardi4nfdi.de/wiki/Item:Q4036706" rel="nofollow">MaRDI QID Q4036706</a><a class="pub-badge pub-badge--grey" href="https://fdo.portal.mardi4nfdi.de/fdo/Q4036706" rel="nofollow">FDO</a>

Authors Miklós Ajtai

Publication date 18 May 1993

zbMATH Keywords

circuit complexityBoolean circuitrandom constructionsweak dependence of random variables

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Complexity and Probability of Some Boolean Formulas
• On construction of \(k\)-wise independent random variables
• Simple Constructions of Almost k-wise Independent Random Variables
• On families of weakly dependent random variables
• On construction of \(k\)-wise independent random variables

Cited in

(7)

• scientific article; zbMATH DE number 1875423 (Why is no real title available?)
• A nearly-optimal transfixing set
• On families of weakly dependent random variables
• Prediction from partial information and hindsight, with application to circuit lower bounds
• The dual BKR inequality and Rudich's conjecture
• On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
• Oblivious bounds on the probability of boolean functions

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 Q4036706)