Formula complexity of a linear function in a \(k\)-ary basis
From MaRDI portal
Publication:2037681
DOI10.1134/S0001434621030123zbMath1484.94046OpenAlexW3181531192MaRDI QIDQ2037681
Publication date: 8 July 2021
Published in: Mathematical Notes (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1134/s0001434621030123
bipartite graphslinear functionmajority functionBoolean formulasKhrapchenko methodlower bounds for complexity
Boolean functions (94D10) Networks and circuits as models of computation; circuit complexity (68Q06)
Related Items
Cites Work
- Complexity and depth of formulas for symmetric Boolean functions
- Upper bounds for the formula size of symmetric Boolean functions
- Boolean function complexity. Advances and frontiers.
- Using amplification to compute majority with small majority gates
- Realization of linear functions by formulas in various bases
- Method of determining lower bounds for the complexity of \(\Pi\)-circuits
- Formula Complexity of Ternary Majorities
- On the complexity of realization of the linear function by formulas over finite Boolean bases
- On circuits of functional elements of finite depth of branching
- Which bases admit non-trivial shrinkage of formulae?
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item