Almost \(k\)-wise independence and hard Boolean functions.
type: Item
instance of: scholarly article
title: Almost \(k\)-wise independence and hard Boolean functions.
zbMATH Open document ID: 1051.68080
DOI: 10.1016/S0304-3975(02)00643-6
author: Valentine Kabanets
published in: Theoretical Computer Science
publication date: 2003-08-17T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 1965324
zbMATH Keywords: read-once branching program
MaRDI profile type: Publication
cites work: Simple Constructions of Almost k-wise Independent Random Variables
cites work: Q4938624
cites work: A very simple function that requires exponential size read-once branching programs.
cites work: Q3694708
cites work: A simple function that requires exponential size read-once branching programs
cites work: Q4526985
cites work: Entropy of contact circuits and lower bounds on their complexity
cites work: Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
cites work: Small-Bias Probability Spaces: Efficient Constructions and Applications
cites work: A Lower Bound for Integer Multiplication with Read-Once Branching Programs
cites work: Q3822097
cites work: Natural proofs
cites work: Improved boolean formulas for the Ramsey graphs
cites work: Q4287364
cites work: On the complexity of branching programs and decision trees for clique functions
cites work: Q3347300
description: scientific article; zbMATH DE number 1965324