Almost \(k\)-wise independence and hard Boolean functions.

DOI10.1016/S0304-3975(02)00643-6zbMath1051.68080MaRDI QIDQ1401305

Valentine Kabanets

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

read-once branching program

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Randomized OBDD-based graph algorithms ⋮ Randomized OBDD-Based Graph Algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple function that requires exponential size read-once branching programs
• Entropy of contact circuits and lower bounds on their complexity
• Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
• A very simple function that requires exponential size read-once branching programs.
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• On the complexity of branching programs and decision trees for clique functions
• Simple Constructions of Almost k-wise Independent Random Variables
• A Lower Bound for Integer Multiplication with Read-Once Branching Programs
• Improved boolean formulas for the Ramsey graphs
• Natural proofs