scientific article; zbMATH DE number 176875

zbMATH Open0769.68038MaRDI QIDQ4036706FDOQ4036706

Authors: Miklós Ajtai 

Publication date: 18 May 1993

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

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

zbMATH Keywords

circuit complexityBoolean circuitrandom constructionsweak dependence of random variables

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (7)

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

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)