Pages that link to "Item:Q3798243"

The following pages link to On the complexity of branching programs and decision trees for clique functions (Q3798243):

Displaying 31 items.

• A simple function that requires exponential size read-once branching programs (Q287023) (← links)
• On the size of binary decision diagrams representing Boolean functions (Q673087) (← links)
• On oblivious branching programs of linear length (Q804285) (← links)
• Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice (Q841618) (← links)
• Forms of representation for simple games: sizes, conversions and equivalences (Q898760) (← links)
• Neither reading few bits twice nor reading illegally helps much (Q1130185) (← links)
• Lower bounds for depth-restricted branching programs (Q1173954) (← links)
• Separating complexity classes related to \(\Omega\)-decision trees (Q1202936) (← links)
• Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs (Q1275068) (← links)
• Efficient data structures for Boolean functions (Q1344625) (← links)
• A lower bound on branching programs reading some bits twice (Q1392030) (← links)
• Approximation of boolean functions by combinatorial rectangles (Q1399979) (← links)
• Almost \(k\)-wise independence and hard Boolean functions. (Q1401305) (← links)
• BDDs -- design, analysis, complexity, and applications. (Q1428568) (← links)
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs (Q1575258) (← links)
• On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs (Q1587348) (← links)
• Time-space tradeoffs for branching programs (Q1604208) (← links)
• Lower bounds for linearly transformed OBDDs and FBDDs (Q1608325) (← links)
• The complexity of minimizing and learning OBDDs and FBDDs (Q1613429) (← links)
• Boolean expression diagrams (Q2506489) (← links)
• A very simple function that requires exponential size read-once branching programs. (Q2583538) (← links)
• Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access (Q4032302) (← links)
• Communication Complexity and Lower Bounds on Multilective Computations (Q4265538) (← links)
• Separating complexity classes related to bounded alternating ?-branching programs (Q4327378) (← links)
• A note on read-$k$ times branching programs (Q4362278) (← links)
• Nonuniform complexity classes specified by lower and upper bounds (Q4730777) (← links)
• (Q4939662) (← links)
• (Q5020651) (← links)
• (Q5020998) (← links)
• Streaming and query once space complexity of longest increasing subsequence (Q6591455) (← links)
• Perspective on complexity measures targeting read-once branching programs (Q6647765) (← links)