On the sensitivity conjecture for read-k formulas

DOI10.4230/LIPICS.MFCS.2016.16zbMATH Open1398.68176MaRDI QIDQ4608575FDOQ4608575

Authors: Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, Ameya Velingker 

Publication date: 21 March 2018

Recommendations

• On the sensitivity conjecture
• On the resolution of the sensitivity conjecture
• Sensitivity versus certificate complexity of Boolean functions
• On the sensitivity conjecture for disjunctive normal forms
• Tighter relations between sensitivity and other complexity measures

zbMATH Keywords

analysis of Boolean functionssensitivity conjectureread-\(k\) formulas

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Boolean functions (06E30)

Cited In (8)

• On the resolution of the sensitivity conjecture
• A tighter relation between sensitivity complexity and certificate complexity
• Alternation, sparsity and sensitivity: bounds and exponential gaps
• Sensitivity of Boolean formulas
• The average sensitivity of bounded-depth formulas
• On the sensitivity complexity of \(k\)-uniform hypergraph properties
• On the average sensitivity and density of \(k\)-CNF formulas
• Tight bounds on sensitivity and block sensitivity of some classes of transitive functions

This page was built for publication: On the sensitivity conjecture for read-\(k\) formulas

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