Negation-limited formulas
From MaRDI portal
Publication:729897
DOI10.1016/j.tcs.2016.11.027zbMath1357.68058OpenAlexW2553932890MaRDI QIDQ729897
Publication date: 22 December 2016
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2016.11.027
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (3)
Alternation, sparsity and sensitivity: bounds and exponential gaps ⋮ Lower bounds for Boolean circuits of bounded negation width ⋮ New bounds for energy complexity of Boolean functions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Boolean function complexity. Advances and frontiers.
- Negation-limited circuit complexity of symmetric functions
- Pseudorandom bits for constant depth circuits
- The monotone circuit complexity of Boolean functions
- Symmetric approximation arguments for monotone lower bounds without sunflowers
- Hardness vs randomness
- On the shrinkage exponent for read-once formulae
- How much are increasing sets positively correlated?
- Fourier concentration from shrinkage
- Mining circuit lower bound proofs for meta-algorithms
- An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas
- Higher lower bounds on monotone size
- Short monotone formulae for the majority function
- On the Inversion Complexity of a System of Functions
- Limiting Negations in Formulas
- On the Complexity of Negation-Limited Boolean Networks
- How Do Read-Once Formulae Shrink?
- The Shrinkage Exponent of de Morgan Formulas is 2
- The effect of random restrictions on formula size
- Shrinkage of de Morgan formulae under restriction
- Explicit lower bound of 4.5n - o(n) for boolena circuits
- Pseudorandomness from Shrinkage
- Communication lower bounds via critical block sensitivity
- The Power of Negations in Cryptography
- Learning circuits with few negations
- Average-case lower bounds for formula size
- A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log n Negation Gates
This page was built for publication: Negation-limited formulas
