Pages that link to "Item:Q3218066"
From MaRDI portal
The following pages link to Short monotone formulae for the majority function (Q3218066):
Displaying 50 items.
- The graph clustering problem has a perfect zero-knowledge interactive proof (Q294656) (← links)
- A limit theorem for continuous selectors (Q312333) (← links)
- Complexity and depth of formulas for symmetric Boolean functions (Q334301) (← links)
- A stronger LP bound for formula size lower bounds via clique constraints (Q428879) (← links)
- Clique problem, cutting plane proofs and communication complexity (Q456115) (← links)
- A sorting network in bounded arithmetic (Q638498) (← links)
- Using amplification to compute majority with small majority gates (Q677991) (← links)
- Randomized vs. deterministic decision tree complexity for read-once Boolean functions (Q685705) (← links)
- Negation-limited formulas (Q729897) (← links)
- Random Boolean formulas representing any Boolean function with asymptotically equal probability (Q915747) (← links)
- Reductions for monotone Boolean circuits (Q959813) (← links)
- Monotone circuits for monotone weighted threshold functions (Q1044746) (← links)
- Threshold functions and bounded depth monotone circuits (Q1088970) (← links)
- ERCW PRAMs and optical communication (Q1128717) (← links)
- On LR(k) grammars and languages (Q1239009) (← links)
- \(\Sigma\Pi\Sigma\) threshold formulas (Q1340142) (← links)
- Better lower bounds for monotone threshold formulas (Q1356879) (← links)
- On the shrinkage exponent for read-once formulae (Q1367534) (← links)
- On the limits of efficient teachability (Q1603392) (← links)
- Adaptively secure distributed PRFs from LWE (Q1631339) (← links)
- Permanent v. determinant: an exponential lower bound assuming symmetry and a potential path towards Valiant's conjecture (Q1679675) (← links)
- From discrepancy to majority (Q1751093) (← links)
- Monotone simulations of non-monotone proofs. (Q1872729) (← links)
- Monotone Boolean formulas can approximate monotone linear threshold functions (Q1878411) (← links)
- Fourier concentration from shrinkage (Q2012185) (← links)
- Adaptively secure distributed PRFs from \(\mathsf{LWE}\) (Q2043324) (← links)
- On the complexity of the clone membership problem (Q2048213) (← links)
- Blackbox secret sharing revisited: a coding-theoretic approach with application to expansionless near-threshold schemes (Q2055621) (← links)
- Non-interactive CCA2-secure threshold cryptosystems: achieving adaptive security in the standard model without pairings (Q2061939) (← links)
- Golden games (Q2235746) (← links)
- Computing majority by constant depth majority circuits with low fan-in gates (Q2321926) (← links)
- On the computational complexity of coalitional resource games (Q2457612) (← links)
- Associative and commutative tree representations for Boolean functions (Q2514128) (← links)
- The fraction of large random trees representing a given Boolean function in implicational logic (Q2884007) (← links)
- Proofs with monotone cuts (Q2888631) (← links)
- Complexity and Limiting Ratio of Boolean Functions over Implication (Q3599140) (← links)
- On the Complexity of the Hidden Weighted Bit Function for Various BDD Models (Q4265532) (← links)
- How Do Read-Once Formulae Shrink? (Q4325332) (← links)
- A Hierarchy Theorem for Interactive Proofs of Proximity (Q4638092) (← links)
- (Q5005185) (← links)
- Cubic Formula Size Lower Bounds Based on Compositions with Majority (Q5090412) (← links)
- Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits (Q5091231) (← links)
- Fourier bounds and pseudorandom generators for product tests (Q5091757) (← links)
- Parity helps to compute majority (Q5091774) (← links)
- On (Valiant’s) Polynomial-Size Monotone Formula for Majority (Q5098767) (← links)
- Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory (Q5135262) (← links)
- On Expressing Majority as a Majority of Majorities (Q5220471) (← links)
- Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations (Q5864666) (← links)
- Regular expression length via arithmetic formula complexity (Q5918469) (← links)
- A robust version of Hegedűs's lemma, with applications (Q6566590) (← links)
