Sensitivity conjecture and signed hypercubes

DOI10.1145/3777401MaRDI QIDQ7228639zbMATH OpenFDO

Authors Sophie Laplante, Reza Naserasr, Anupa Sunny, Zhouningxin Wang

Publication date 14 April 2026

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International

Full work available at URL https://doi.org/10.1145/3777401

zbMATH Keywords

Boolean functionfrustration indexsensitivitysigned graphs

Mathematics Subject Classification ID

Computer science (68-XX)

Cites work

• Complexity measures and decision tree complexity: a survey.
• Graph covers with two new eigenvalues
• scientific article; zbMATH DE number 3880754 (Why is no real title available?)
• scientific article; zbMATH DE number 5485488 (Why is no real title available?)
• scientific article; zbMATH DE number 867703 (Why is no real title available?)
• Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
• Minimum number of distinct eigenvalues of graphs
• On generalized hexagons and a near octagon whose lines have three points
• On induced subgraphs of the cube
• On the degree of Boolean functions as real polynomials
• On the maximum number of edges in a c₄‐free subgraph of q_n
• Polynomial degree vs. quantum query complexity
• Properties and applications of Boolean function composition
• Sensitivity vs. block sensitivity of Boolean functions
• Signed graphs
• The equivalence of two problems on the cube
• The quantum adversary method and classical formula size power bounds
• The sensitivity conjecture, induced subgraphs of cubes, and Clifford algebras

This page was built for publication: Sensitivity conjecture and signed hypercubes

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