Short monotone formulae for the majority function
From MaRDI portal
Publication:3218066
DOI10.1016/0196-6774(84)90016-6zbMath0554.94017OpenAlexW2008470071WikidataQ56057733 ScholiaQ56057733MaRDI QIDQ3218066
Publication date: 1984
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(84)90016-6
Analysis of algorithms and problem complexity (68Q25) Boolean functions (06E30) Logical aspects of Boolean algebras (03G05)
Related Items
Monotone simulations of non-monotone proofs., The fraction of large random trees representing a given Boolean function in implicational logic, Monotone Boolean formulas can approximate monotone linear threshold functions, Proofs with monotone cuts, \(\Sigma\Pi\Sigma\) threshold formulas, Threshold functions and bounded depth monotone circuits, The graph clustering problem has a perfect zero-knowledge interactive proof, On the Complexity of the Hidden Weighted Bit Function for Various BDD Models, Adaptively secure distributed PRFs from LWE, A Hierarchy Theorem for Interactive Proofs of Proximity, A limit theorem for continuous selectors, Better lower bounds for monotone threshold formulas, Complexity and depth of formulas for symmetric Boolean functions, On the shrinkage exponent for read-once formulae, ERCW PRAMs and optical communication, Permanent v. determinant: an exponential lower bound assuming symmetry and a potential path towards Valiant's conjecture, On (Valiant’s) Polynomial-Size Monotone Formula for Majority, Threshold linearly homomorphic encryption on \(\mathrm{Z}/2^k\mathrm{Z}\), How Do Read-Once Formulae Shrink?, Unnamed Item, A stronger LP bound for formula size lower bounds via clique constraints, A sorting network in bounded arithmetic, Random Boolean formulas representing any Boolean function with asymptotically equal probability, Clique problem, cutting plane proofs and communication complexity, Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory, On the computational complexity of coalitional resource games, Golden games, Using amplification to compute majority with small majority gates, From discrepancy to majority, Randomized vs. deterministic decision tree complexity for read-once Boolean functions, Reductions for monotone Boolean circuits, Fourier concentration from shrinkage, Complexity and Limiting Ratio of Boolean Functions over Implication, On LR(k) grammars and languages, Negation-limited formulas, Associative and commutative tree representations for Boolean functions, Regular expression length via arithmetic formula complexity, Adaptively secure distributed PRFs from \(\mathsf{LWE}\), On the complexity of the clone membership problem, On Expressing Majority as a Majority of Majorities, Blackbox secret sharing revisited: a coding-theoretic approach with application to expansionless near-threshold schemes, Non-interactive CCA2-secure threshold cryptosystems: achieving adaptive security in the standard model without pairings, Parity helps to compute majority, Cubic Formula Size Lower Bounds Based on Compositions with Majority, Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits, Fourier bounds and pseudorandom generators for product tests, Computing majority by constant depth majority circuits with low fan-in gates, Monotone circuits for monotone weighted threshold functions, Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations, On the limits of efficient teachability
