The following pages link to (Q4385519):
Displayed 50 items.
- Monotone real circuits are more powerful than monotone Boolean circuits (Q290209) (← links)
- The average sensitivity of bounded-depth circuits (Q290255) (← links)
- Lower bounds for monotone real circuit depth and formula size and tree-like cutting planes (Q293309) (← links)
- Depth of Boolean functions realized by circuits over an arbitrary infinite basis (Q355347) (← links)
- On derandomization and average-case complexity of monotone functions (Q428873) (← links)
- Partial-order Boolean games: informational independence in a logic-based model of strategic interaction (Q516248) (← links)
- The communication complexity of addition (Q519955) (← links)
- The strongest model of computation obeying 0-1 Principles (Q633766) (← links)
- Negation-limited circuit complexity of symmetric functions (Q671626) (← links)
- Computing threshold functions by depth-3 threshold circuits with smaller thresholds of their gates (Q672256) (← links)
- On input read-modes of alternating Turing machines (Q672377) (← links)
- Interpolants, cut elimination and flow graphs for the propositional calculus (Q674415) (← links)
- On the computation of Boolean functions by analog circuits of bounded fan-in (Q676434) (← links)
- Improvements on Khrapchenko's theorem (Q685364) (← links)
- Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy (Q685431) (← links)
- An extension of Khrapchenko's theorem (Q753798) (← links)
- On the complexity of second-best abductive explanations (Q899129) (← links)
- On the complexity of cutting-plane proofs using split cuts (Q969513) (← links)
- Smallest formulas for the parity of \(2^k\) variables are essentially unique (Q974758) (← links)
- Linear-size log-depth negation-limited inverter for \(k\)-tonic binary sequences (Q1007246) (← links)
- Negation-limited complexity of parity and inverters (Q1022345) (← links)
- Parameterized circuit complexity and the \(W\) hierarchy (Q1127315) (← links)
- ERCW PRAMs and optical communication (Q1128717) (← links)
- Matching theory -- a sampler: From Dénes König to the present (Q1198643) (← links)
- Separating complexity classes related to \(\Omega\)-decision trees (Q1202936) (← links)
- The computational complexity of universal hashing (Q1208411) (← links)
- Relating polynomial time to constant depth (Q1274992) (← links)
- Reductions in circuit complexity: An isomorphism theorem and a gap theorem (Q1276160) (← links)
- Positive versions of polynomial time (Q1281503) (← links)
- An exponential lower bound for the size of monotone real circuits (Q1288204) (← links)
- Characterizing linear size circuits in terms of privacy (Q1305927) (← links)
- The relative power of logspace and polynomial time reductions (Q1312179) (← links)
- Shallow circuits and concise formulae for multiple addition and multiplication (Q1312182) (← links)
- Directed monotone contact networks for threshold functions (Q1327314) (← links)
- Complexity models for incremental computation (Q1331947) (← links)
- \(\Sigma\Pi\Sigma\) threshold formulas (Q1340142) (← links)
- On ACC (Q1346616) (← links)
- On almost bad Boolean bases (Q1349706) (← links)
- Query languages for bags and aggregate functions (Q1376407) (← links)
- A query language for NC (Q1376409) (← links)
- On the complexity of entailment in propositional multivalued logics (Q1380415) (← links)
- Gap-languages and log-time complexity classes (Q1389651) (← links)
- Optimal bounds for the approximation of Boolean functions and some applications (Q1390872) (← links)
- Some connections between bounded query classes and non-uniform complexity. (Q1426008) (← links)
- Time-space tradeoffs for satisfiability (Q1567402) (← links)
- The complexity of belief update (Q1575185) (← links)
- No feasible monotone interpolation for simple combinatorial reasoning (Q1575265) (← links)
- Can large fanin circuits perform reliable computations in the presence of faults? (Q1575437) (← links)
- Which problems have strongly exponential complexity? (Q1604206) (← links)
- The expressiveness of DAC (Q1608890) (← links)