Entropy of contact circuits and lower bounds on their complexity

DOI10.1016/0304-3975(88)90166-1zbMath0655.94020OpenAlexW1991547553MaRDI QIDQ1109754

Stasys P. Jukna

Publication date: 1988

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

Full work available at URL: https://doi.org/10.1016/0304-3975(88)90166-1

zbMATH Keywords

entropylower boundscircuitBoolean functionbranching programscircuit complexity of Boolean functionscontact circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Measures of information, entropy (94A17)

Related Items (14)

A simple function that requires exponential size read-once branching programs ⋮ Randomized OBDD-based graph algorithms ⋮ Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs ⋮ Randomized OBDD-Based Graph Algorithms ⋮ Neither reading few bits twice nor reading illegally helps much ⋮ A Well-Mixed Function with Circuit Complexity 5n ±o(n): Tightness of the Lachish-Raz-Type Bounds ⋮ Almost \(k\)-wise independence and hard Boolean functions. ⋮ Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines. ⋮ A well-mixed function with circuit complexity \(5n\): tightness of the Lachish-Raz-type bounds ⋮ The simplified weighted sum function and its average sensitivity ⋮ A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs ⋮ A hierarchy result for read-once branching programs with restricted parity nondeterminism ⋮ A very simple function that requires exponential size read-once branching programs. ⋮ Lower bounds for linearly transformed OBDDs and FBDDs

Cites Work

• Lower bounds on monotone complexity of the logical permanent
• The monotone circuit complexity of Boolean functions
• The complexity of symmetric functions in bounded-depth circuits
• Boolean functions whose monotone complexity is of size \(n^ 2\) / log n
• Bounds for Width Two Branching Programs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Entropy of contact circuits and lower bounds on their complexity