scientific article; zbMATH DE number 3257409
From MaRDI portal
Publication:5545524
zbMath0161.00901MaRDI QIDQ5545524
Publication date: 1966
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Boolean functions (06E30) Switching theory, applications of Boolean algebras to circuits and networks (94C11)
Related Items (44)
Time-space trade-offs for branching programs ⋮ Some observations on holographic algorithms ⋮ On the limits of gate elimination ⋮ On the complexity of encoding in analog circuits ⋮ A lower bound for read-once-only branching programs ⋮ Entropy of contact circuits and lower bounds on their complexity ⋮ Meanders and their applications in lower bounds arguments ⋮ Tradeoffs for language recognition on alternating machines ⋮ On Nečiporuk's theorem for branching programs ⋮ Efficient oblivious branching programs for threshold and mod functions ⋮ Neither reading few bits twice nor reading illegally helps much ⋮ Size-depth tradeoff in non-monotone Boolean formulae ⋮ Algorithms and lower bounds for comparator circuits from shrinkage ⋮ On uncertainty versus size in branching programs. ⋮ Unnamed Item ⋮ Improving \(3N\) circuit complexity lower bounds ⋮ Discrete extremal problems ⋮ Circuit complexity of linear functions: gate elimination and feeble security ⋮ Size-treewidth tradeoffs for circuits computing the element distinctness function ⋮ Lower bounds to the complexity of symmetric Boolean functions ⋮ BDDs -- design, analysis, complexity, and applications. ⋮ Lower bounds of the complexity of symmetric Boolean functions of contact- rectifier circuits ⋮ Lower bounds for depth-restricted branching programs ⋮ Lower bounds on the complexity of real-time branching programs ⋮ ON THE MEANING OF WORKS BY V. M. KHRAPCHENKO ⋮ Limitations of incremental dynamic programming ⋮ Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs ⋮ Entropy of operators or why matrix multiplication is hard for depth-two circuits ⋮ New lower bounds and hierarchy results for restricted branching programs ⋮ A nondeterministic space-time tradeoff for linear codes ⋮ A class of Boolean functions with linear combinational complexity ⋮ Lower bounds for the size of expressions for certain functions in d-ary logic ⋮ Unnamed Item ⋮ Lower bounds for restricted read-once parity branching programs ⋮ The Orthogonal Vectors Conjecture for Branching Programs and Formulas ⋮ Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs ⋮ Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates ⋮ On the complexity of the marriage problem ⋮ A quadratic lower bound for homogeneous algebraic branching programs ⋮ A hierarchy result for read-once branching programs with restricted parity nondeterminism ⋮ On the complexity of planar Boolean circuits ⋮ On oblivious branching programs of linear length ⋮ Mining circuit lower bound proofs for meta-algorithms
This page was built for publication:
