Entropy of contact circuits and lower bounds on their complexity

DOI10.1016/0304-3975(88)90166-1zbMATH Open0655.94020OpenAlexW1991547553MaRDI QIDQ1109754FDOQ1109754

Authors: Stasys 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

Recommendations

• scientific article; zbMATH DE number 3987204
• Publication:3033329
• scientific article; zbMATH DE number 4068270
• scientific article; zbMATH DE number 4189653
• Entropy and enumeration of Boolean functions

zbMATH Keywords

entropylower boundsBoolean functioncircuitbranching programscircuit complexity of Boolean functionscontact circuits

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (27)

• Neither reading few bits twice nor reading illegally helps much
• Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs
• Lower bounds for linearly transformed OBDDs and FBDDs
• Almost \(k\)-wise independence and hard Boolean functions.
• Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
• Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy
• Streaming and query once space complexity of longest increasing subsequence
• A simple function that requires exponential size read-once branching programs
• A very simple function that requires exponential size read-once branching programs.
• Title not available (Why is that?)
• A Well-Mixed Function with Circuit Complexity 5n ±o(n): Tightness of the Lachish-Raz-Type Bounds
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• Prediction from partial information and hindsight, with application to circuit lower bounds
• A well-mixed function with circuit complexity \(5n\): tightness of the Lachish-Raz-type bounds
• A hierarchy result for read-once branching programs with restricted parity nondeterminism
• Title not available (Why is that?)
• Title not available (Why is that?)
• Perspective on complexity measures targeting read-once branching programs
• Entropy and enumeration of Boolean functions
• Randomized OBDD-based graph algorithms
• Randomized OBDD-based graph algorithms
• Random problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The simplified weighted sum function and its average sensitivity
• Title not available (Why is that?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1109754)