scientific article; zbMATH DE number 6829287

DOI10.4230/LIPICS.CCC.2015.392MaRDI QIDQ4601839zbMATH OpenFDO

Authors Benjamin Rossman

Publication date 24 January 2018

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2015.392

zbMATH Keywords

average-case complexitycircuit complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Lower bound on the correlation between monotone families in the average case
• Proof of two conjectures on correlation inequalities for one class of monotone functions
• Monotone Measures for Non-Local Correlations
• Correlation inequalities and monotonicity properties of the Ruelle operator
• Correlation inequalities on \(\{-1,1\}^ n\) and \({\mathbb{R}}^ n\)
• Correlation lower bounds from correlation upper bounds
• Maximal correlation and monotonicity of free entropy and of Stein discrepancy
• On the decay of correlation for piecewise monotonic mappings. I
• On the decay of correlation for piecewise monotonic mappings. II

Cited in

(9)

• On the mystery of negations in circuits: structure vs power
• Lower bounds for Boolean circuits of bounded negation width
• Monotone Measures for Non-Local Correlations
• Formulas versus Circuits for Small Distance Connectivity
• Testing k-monotonicity
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Lower Bounds for DeMorgan Circuits of Bounded Negation Width
• Tree-Depth and the Formula Complexity of Subgraph Isomorphism
• Negation-limited formulas

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601839)