ในคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎีการวิเคราะห์ฟังก์ชันบูลีนคือการศึกษาฟังก์ชันค่าจริงบนหรือ(บางครั้งฟังก์ชันดังกล่าวเรียกว่าฟังก์ชันบูลีนเทียม ) จากมุมมองเชิงสเปกตรัม^{[ 1 ]}ฟังก์ชันที่ศึกษามักจะเป็นฟังก์ชันบูลีน แต่ไม่เสมอไป ทำให้ฟังก์ชันเหล่านั้นเป็นฟังก์ชันบูลีนสาขานี้พบการประยุกต์ใช้มากมายในคณิตศาสตร์เชิงการจัดเรียงทฤษฎีการเลือกทางสังคมกราฟสุ่มและวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎี โดยเฉพาะอย่างยิ่งในความยากของการประมาณค่าการทดสอบคุณสมบัติและ การเรียน รู้ PAC${\displaystyle \{0,1\}^{n}}$${\displaystyle \{-1,1\}^{n}}$

โดยส่วนใหญ่เราจะพิจารณาฟังก์ชันที่กำหนดบนโดเมนบางครั้งการทำงานกับโดเมนโดยตรงอาจสะดวกกว่า ถ้ากำหนดบนแล้วฟังก์ชันที่สอดคล้องกันซึ่งกำหนดบนคือ ${\displaystyle \{-1,1\}^{n}}$${\displaystyle \{0,1\}^{n}}$${\displaystyle f}$${\displaystyle \{-1,1\}^{n}}$${\displaystyle \{0,1\}^{n}}$

${\displaystyle f_{01}(x_{1},\ldots ,x_{n})=f((-1)^{x_{1}},\ldots ,(-1)^{x_{n}}).}$

ในทำนองเดียวกัน สำหรับเรา ฟังก์ชันบูลีนคือฟังก์ชันที่มีค่าเป็น n แม้ว่าบ่อยครั้งการพิจารณาฟังก์ชันที่มีค่าเป็น n จะสะดวกกว่าก็ตาม ${\displaystyle \{-1,1\}}$${\displaystyle \{0,1\}}$

ฟังก์ชันค่าจริงทุกฟังก์ชันมีการกระจายที่ไม่ซ้ำกันในรูปพหุนามเชิงเส้นหลายตัวแปร : ${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$

${\displaystyle f(x)=\sum _{S\subseteq [n]}{\hat {f}}(S)\chi _{S}(x),\quad \chi _{S}(x)=\prod _{i\in S}x_{i}.}$

(โปรดทราบว่าถึงแม้ฟังก์ชันจะมีค่าเป็น 0-1 แต่นี่ไม่ใช่ผลรวมมอด 2 แต่เป็นเพียงผลรวมธรรมดาของจำนวนจริง)

นี่คือการแปลงฮาดามาร์ดของฟังก์ชันซึ่งเป็นการแปลงฟูริเยร์ในกลุ่มสัมประสิทธิ์เรียกว่าสัมประสิทธิ์ฟูริเยร์และผลรวมทั้งหมด เรียกว่าการขยายฟูริเยร์ของ ฟังก์ชัน เรียกว่าอักขระฟูริเยร์ และ ฟังก์ชันเหล่านี้ก่อให้เกิดฐานเชิงตั้งฉากปกติสำหรับปริภูมิของฟังก์ชันทั้งหมดเหนือโดยสัมพันธ์กับผลคูณภายใน ${\displaystyle f}$${\displaystyle \mathbb {Z} _{2}^{n}}$${\displaystyle {\hat {f}}(S)}$${\displaystyle f}$${\displaystyle \chi _{S}}$${\displaystyle \{-1,1\}^{n}}$${\displaystyle \langle f,g\rangle =2^{-n}\sum _{x\in \{-1,1\}^{n}}f(x)g(x)}$

สามารถคำนวณค่าสัมประสิทธิ์ฟูริเยร์ได้โดยใช้ผลคูณภายใน:

${\displaystyle {\hat {f}}(S)=\langle f,\chi _{S}\rangle .}$

โดยเฉพาะอย่างยิ่ง สิ่งนี้แสดงให้เห็นว่าโดยที่ค่าที่คาดหวังนั้นพิจารณาจากการกระจายแบบเอกรูปเหนือเอกลักษณ์ของ Parsevalกล่าวว่า ${\displaystyle {\hat {f}}(\emptyset )=\operatorname {E} [f]}$${\displaystyle \{-1,1\}^{n}}$

${\displaystyle \|f\|^{2}=\operatorname {E} [f^{2}]=\sum _{S}{\hat {f}}(S)^{2}.}$

ถ้าเราข้ามไปเราจะได้ค่าความแปรปรวนดังนี้: ${\displaystyle S=\emptyset }$${\displaystyle f}$

${\displaystyle \operatorname {Var} [f]=\sum _{S\neq \emptyset }{\hat {f}}(S)^{2}.}$

ดีกรีของฟังก์ชันคือค่าสูงสุดที่ทำให้สำหรับเซตที่มีขนาด บางเซต กล่าวอีกนัยหนึ่ง ดีกรีของฟังก์ชันคือดีกรีของฟังก์ชันนั้นในฐานะพหุนามเชิงเส้นหลายตัวแปร ${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$${\displaystyle d}$${\displaystyle {\hat {f}}(S)\neq 0}$${\displaystyle S}$${\displaystyle d}$${\displaystyle f}$

การแยกการขยายฟูริเยร์ออกเป็น ระดับต่างๆนั้นสะดวกกว่า เนื่องจากสัมประสิทธิ์ฟูริเยร์อยู่ที่ระดับ ${\displaystyle {\hat {f}}(S)}$${\displaystyle |S|}$

ส่วนที่เป็นระดับปริญญา${\displaystyle d}$คือ ${\displaystyle f}$

${\displaystyle f^{=d}=\sum _{|S|=d}{\hat {f}}(S)\chi _{S}.}$

ได้มาจากการกำหนดค่าสัมประสิทธิ์ฟูริเยร์ทั้งหมดที่ไม่ใช่ระดับให้เป็นศูนย์ ${\displaystyle f}$${\displaystyle d}$

เรากำหนดนิยามในทำนองเดียวกัน ${\displaystyle f^{>d},f^{<d},f^{\geq d},f^{\leq d}}$

อิทธิพล ลำดับที่ 'th ของฟังก์ชันสามารถนิยามได้ในสองวิธีที่เทียบเท่ากัน: ${\displaystyle i}$${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$

${\displaystyle {\begin{aligned}&\operatorname {Inf} _{i}[f]=\operatorname {E} \left[\left({\frac {ff^{\oplus i}}{2}}\right)^{2}\right]=\sum _{S\ni i}{\hat {f}}(S)^{2},\\[5pt]&f^{\oplus i}(x_{1},\ldots ,x_{n})=f(x_{1},\ldots ,x_{i-1},-x_{i},x_{i+1},\ldots ,x_{n}).\end{aligned}}}$

ถ้าเป็นค่าบูลีนความน่าจะเป็นที่การพลิกพิกัดที่ 'th จะเปลี่ยนค่าของฟังก์ชันคือ: ${\displaystyle f}$${\displaystyle \operatorname {Inf} _{i}[f]}$${\displaystyle i}$

${\displaystyle \operatorname {Inf} _{i}[f]=\Pr[f(x)\neq f^{\oplus i}(x)].}$

ถ้าเช่นนั้นจะไม่ขึ้นอยู่กับพิกัดที่ 'th' ${\displaystyle \operatorname {Inf} _{i}[f]=0}$${\displaystyle f}$${\displaystyle i}$

อิทธิพลโดยรวมของคือผลรวมของอิทธิพลทั้งหมดของมัน: ${\displaystyle f}$

${\displaystyle \operatorname {Inf} [f]=\sum _{i=1}^{n}\operatorname {Inf} _{i}[f]=\sum _{S}|S|{\hat {f}}(S)^{2}.}$

อิทธิพลโดยรวมของฟังก์ชันบูลีนก็คือค่าความไวเฉลี่ยของฟังก์ชันนั้น ค่าความไวของฟังก์ชันบูลีนณ จุดใดจุดหนึ่ง คือจำนวนพิกัดที่หากเราเปลี่ยนค่าพิกัดที่ n ค่าของฟังก์ชันจะเปลี่ยนแปลง ค่าเฉลี่ยของปริมาณนี้ก็คืออิทธิพลโดยรวมนั่นเอง ${\displaystyle f}$${\displaystyle i}$${\displaystyle i}$

อิทธิพลโดยรวมสามารถกำหนดได้โดยใช้Laplacian แบบไม่ต่อเนื่องของกราฟ Hammingที่ปรับให้เป็นมาตรฐานอย่างเหมาะสม: . ${\displaystyle \operatorname {Inf} [f]=\langle f,Lf\rangle }$

รูปแบบทั่วไปของอิทธิพลคืออิทธิพลแบบคงที่ ซึ่งกำหนดโดย: ${\displaystyle \rho }$

${\displaystyle \operatorname {Inf} _{i}^{\,(\rho )}[f]=\operatorname {Stab} _{\rho }[\operatorname {D} _{i}f]=\sum _{S\ni i}\rho ^{|S|-1}{\hat {f}}(S)^{2}.}$

อิทธิพลโดยรวมที่สอดคล้องกันคือ

${\displaystyle \operatorname {I} ^{(\rho )}[f]={\frac {d}{d\rho }}\operatorname {Stab} _{\rho }[f]=\sum _{S}|S|\rho ^{|S|-1}{\hat {f}}(S)^{2}.}$

เราสามารถพิสูจน์ได้ว่าฟังก์ชันหนึ่งๆจะมีพิกัดที่มี "อิทธิพลอย่างเสถียร" มากที่สุด "จำนวนคงที่" พิกัด: ${\displaystyle f:\{-1,1\}^{n}\to \{-1,1\}}$${\displaystyle |\{i\in [n]:\operatorname {Inf} _{i}^{\,(1-\delta )}[f]\geq \epsilon \}|\leq {\frac {1}{\delta \epsilon }}.}$

กำหนดให้เรากล่าวว่าเวกเตอร์สุ่มสองตัวมีความสัมพันธ์กันแบบถ้าการแจกแจงแบบมาร์จินัลของเป็นแบบเอกรูป และ. โดยเฉพาะอย่างยิ่ง เราสามารถสร้างคู่ของตัวแปรสุ่มที่มีความสัมพันธ์กันแบบ ได้โดยการเลือกแบบสุ่มอย่างสม่ำเสมอเป็นอันดับแรก จากนั้นเลือกตามกฎที่เทียบเท่ากันสองข้อต่อไปนี้ข้อใดข้อหนึ่ง ซึ่งนำไปใช้กับแต่ละพิกัดอย่างอิสระ: ${\displaystyle -1\leq \rho \leq 1}$${\displaystyle x,y\in \{-1,1\}^{n}}$${\displaystyle \rho }$${\displaystyle x,y}$${\displaystyle \operatorname {E} [x_{i}y_{i}]=\rho }$${\displaystyle \rho }$${\displaystyle x,z\in \{-1,1\}^{n}}$${\displaystyle y}$

${\displaystyle y_{i}={\begin{cases}x_{i}&{\text{w.p. }}\rho ,\\z_{i}&{\text{w.p. }}1-\rho .\end{cases}}\quad {\text{or}}\quad y_{i}={\begin{cases}x_{i}&{\text{w.p. }}{\frac {1+\rho }{2}},\\-x_{i}&{\text{w.p. }}{\frac {1-\rho }{2}}.\end{cases}}}$

เราใช้สัญลักษณ์ แทน การแจกแจงนี้${\displaystyle y\sim N_{\rho }(x)}$

ความเสถียรต่อสัญญาณรบกวนของฟังก์ชันที่สามารถนิยามได้ในสองวิธีที่เทียบเท่ากัน: ${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$${\displaystyle \rho }$

${\displaystyle \operatorname {Stab} _{\rho }[f]=\operatorname {E} _{x;y\sim N_{\rho }(x)}[f(x)f(y)]=\sum _{S\subseteq [n]}\rho ^{|S|}{\hat {f}}(S)^{2}.}$

สำหรับค่าความไวต่อเสียงรบกวนของที่คือ ${\displaystyle 0\leq \delta \leq 1}$${\displaystyle f}$${\displaystyle \delta }$

${\displaystyle \operatorname {NS} _{\delta }[f]={\frac {1}{2}}-{\frac {1}{2}}\operatorname {Stab} _{1-2\delta }[f].}$

ถ้าเป็นค่าบูลีน นี่คือความน่าจะเป็นที่ค่าของจะเปลี่ยนไป หากเราพลิกพิกัดแต่ละจุดด้วยความน่าจะเป็น โดยเป็นอิสระ ต่อกัน ${\displaystyle f}$${\displaystyle f}$${\displaystyle \delta }$

ตัวดำเนินการเสียงรบกวน คือตัวดำเนินการที่รับฟังก์ชันหนึ่งและส่งคืนฟังก์ชันอีกฟังก์ชันหนึ่งที่กำหนดโดย ${\displaystyle T_{\rho }}$${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$${\displaystyle T_{\rho }f\colon \{-1,1\}^{n}\to \mathbb {R} }$

${\displaystyle (T_{\rho }f)(x)=\operatorname {E} _{y\sim N_{\rho }(x)}[f(y)]=\sum _{S\subseteq [n]}\rho ^{|S|}{\hat {f}}(S)\chi _{S}.}$

เมื่อเงื่อนไขเป็นจริง ตัวดำเนินการเสียงรบกวนสามารถกำหนดได้โดยใช้ลูกโซ่ Markov แบบต่อเนื่องซึ่งแต่ละบิตจะถูกพลิกอย่างอิสระด้วยอัตรา 1 ตัวดำเนินการนี้สอดคล้องกับการเรียกใช้ลูกโซ่ Markov นี้ตามขั้นตอนที่เริ่มต้นที่และหาค่าเฉลี่ยของที่สถานะสุดท้าย ลูกโซ่ Markov นี้ถูกสร้างขึ้นโดย Laplacian ของกราฟ Hamming และสิ่งนี้เชื่อมโยงอิทธิพลทั้งหมดกับตัวดำเนินการเสียงรบกวน ${\displaystyle \rho >0}$${\displaystyle T_{\rho }}$${\displaystyle {\frac {1}{2}}\log {\frac {1}{\rho }}}$${\displaystyle x}$${\displaystyle f}$

ความเสถียรของสัญญาณรบกวนสามารถกำหนดได้โดยใช้ตัวดำเนินการสัญญาณรบกวน: . ${\displaystyle \operatorname {Stab} _{\rho }[f]=\langle f,T_{\rho }f\rangle }$

สำหรับค่า-นอร์มของฟังก์ชันถูกกำหนดโดย ${\displaystyle 1\leq q<\infty }$${\displaystyle L_{q}}$${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$

${\displaystyle \|f\|_{q}={\sqrt[{q}]{\operatorname {E} [|f|^{q}]}}.}$

เรายังกำหนดอีกด้วย${\displaystyle \|f\|_{\infty }=\max _{x\in \{-1,1\}^{n}}|f(x)|.}$

ทฤษฎีบทไฮเปอร์คอนแทรกติวิตีกล่าวว่า สำหรับทุกค่าถ้าแล้ว ${\displaystyle p>q>1}$${\displaystyle |\rho |\leq {\sqrt {\frac {q-1}{p-1}}}}$

${\displaystyle \|T_{\rho }f\|_{p}\leq \|f\|_{q}.}$

ภาวะหดตัวมากเกินไปมีความเกี่ยวข้องอย่างใกล้ชิดกับอสมการโซโบเลฟแบบลอการิทึมของการวิเคราะห์เชิงฟังก์ชัน^{[ 2 ]}

ผลลัพธ์ที่คล้ายกันสำหรับเรียกว่าภาวะหดตัวเกินแบบย้อนกลับ [ ^{3 ] ระบุ}ว่าถ้าแล้ว ${\displaystyle 1>p>q}$${\displaystyle |\rho |\leq {\sqrt {\frac {1-p}{1-q}}}}$

${\displaystyle \|T_{\rho }f\|_{q}\geq \|f\|_{p}.}$

ในหลายสถานการณ์ อินพุตของฟังก์ชันไม่ได้กระจายอย่างสม่ำเสมอทั่วแต่มีแนวโน้มไปทางหรือมากกว่า ในสถานการณ์เหล่านี้ มักจะพิจารณาฟังก์ชันบนโดเมนสำหรับค่าp -biased measure จะกำหนดโดย ${\displaystyle \{-1,1\}^{n}}$${\displaystyle -1}$${\displaystyle 1}$${\displaystyle \{0,1\}^{n}}$${\displaystyle 0<p<1}$${\displaystyle \mu _{p}}$

${\displaystyle \mu _{p}(x)=p^{\sum _{i}x_{i}}(1-p)^{\sum _{i}(1-x_{i})}.}$

มาตรการนี้สามารถสร้างขึ้นได้โดยการเลือกพิกัดแต่ละพิกัดอย่างอิสระให้เป็น 1 ด้วยความน่าจะเป็นและเป็น 0 ด้วยความน่าจะเป็น ${\displaystyle p}$${\displaystyle 1-p}$

อักขระฟูริเยร์แบบคลาสสิกไม่ตั้งฉากกันอีกต่อไปเมื่อเทียบกับมาตรวัดนี้ ดังนั้นเราจึงใช้อักขระต่อไปนี้แทน:

${\displaystyle \omega _{S}(x)=\left({\sqrt {\frac {p}{1-p}}}\right)^{|\{i\in S:x_{i}=0\}|}\left(-{\sqrt {\frac {1-p}{p}}}\right)^{|\{i\in S:x_{i}=1\}|}.}$

การ ขยายอนุกรมฟูริเยร์ แบบ p -biased ของคือการขยายอนุกรมของในรูปผลรวมเชิงเส้นของ อักขระ แบบ p -biased: ${\displaystyle f}$${\displaystyle f}$

${\displaystyle f=\sum _{S\subseteq [n]}{\hat {f}}(S)\omega _{S}.}$

เราสามารถขยายคำจำกัดความของอิทธิพลและตัวดำเนินการเสียงรบกวนไปยัง การตั้งค่า แบบ p -biased ได้โดยใช้คำจำกัดความเชิงสเปกตรัมของพวกมัน

อิทธิพลของ สิ่งนั้นเกิดจาก ${\displaystyle i}$

${\displaystyle \operatorname {Inf} _{i}[f]=\sum _{S\ni i}{\hat {f}}(S)^{2}=p(1-p)\operatorname {E} [(f-f^{\oplus i})^{2}].}$

อิทธิพลโดยรวมคือผลรวมของอิทธิพลแต่ละส่วน:

${\displaystyle \operatorname {Inf} [f]=\sum _{i=1}^{n}\operatorname {Inf} _{i}[f]=\sum _{S}|S|{\hat {f}}(S)^{2}.}$

สามารถสร้างตัวแปรสุ่มสองตัวที่มีความสัมพันธ์กันได้โดยการเลือกและอย่างอิสระ โดยที่กำหนดโดย ${\displaystyle \rho }$${\displaystyle x,z\sim \mu _{p}}$${\displaystyle y\sim N_{\rho }(x)}$${\displaystyle N_{\rho }}$

${\displaystyle y_{i}={\begin{cases}x_{i}&{\text{w.p. }}\rho ,\\z_{i}&{\text{w.p. }}1-\rho .\end{cases}}}$

ตัวดำเนินการเสียงรบกวนจะได้รับดังนี้

${\displaystyle (T_{\rho }f)(x)=\sum _{S\subseteq [n]}\rho ^{|S|}{\hat {f}}(S)\omega _{S}(x)=\operatorname {E} _{y\sim N_{\rho }(x)}[f(y)].}$

เมื่อใช้สิ่งนี้ เราสามารถกำหนดความเสถียรของสัญญาณรบกวนและความไวต่อสัญญาณรบกวนได้เช่นเดิม

สูตร Russo–Margulis (เรียกอีกอย่างว่าสูตร Margulis–Russo ^{[ 1 ]} ) ระบุว่าสำหรับฟังก์ชันบูลีนแบบโมโนโทน ${\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}$

${\displaystyle {\frac {d}{dp}}\operatorname {E} _{x\sim \mu _{p}}[f(x)]={\frac {\operatorname {Inf} [f]}{p(1-p)}}=\sum _{i=1}^{n}\Pr[f\neq f^{\oplus i}].}$

ทั้งอิทธิพลและความน่าจะเป็นนั้นพิจารณาโดยสัมพันธ์กับและทางด้านขวามือเรามีความไวเฉลี่ยของถ้าเราคิดว่าเป็นคุณสมบัติ สูตรจะระบุว่า เมื่อเปลี่ยนแปลงไป อนุพันธ์ของความน่าจะเป็นที่เกิดขึ้นที่ จะเท่ากับความไวเฉลี่ยที่ ${\displaystyle \mu _{p}}$${\displaystyle f}$${\displaystyle f}$${\displaystyle p}$${\displaystyle f}$${\displaystyle p}$${\displaystyle p}$

สูตร Russo–Margulis เป็นกุญแจสำคัญในการพิสูจน์ทฤษฎีบทเกณฑ์ที่แม่นยำ เช่น ทฤษฎีบทของ Friedgut

หนึ่งในผลลัพธ์ที่ลึกซึ้งที่สุดในสาขานี้ คือหลักการ ไม่เปลี่ยนแปลงซึ่งเชื่อมโยงการกระจายตัวของฟังก์ชันบนลูกบาศก์บูลีนกับการกระจายตัวของฟังก์ชันเหล่านั้นบนปริภูมิเกาส์เซียนซึ่งเป็นปริภูมิที่มีมาตรวัดเกาส์เซียน มาตรฐาน มิติ${\displaystyle \{-1,1\}^{n}}$${\displaystyle \mathbb {R} ^{n}}$${\displaystyle n}$

แนวคิดพื้นฐานหลายอย่างของการวิเคราะห์ฟูริเยร์บนลูกบาศก์บูลีนนั้น มีความสอดคล้องกันในปริภูมิเกาส์เซียน:

• การขยายอนุกรมฟูริเยร์ในปริภูมิเกาส์เซียนนั้นเทียบเท่ากับการขยายอนุกรมเฮอร์ไมต์ ซึ่งเป็นการขยายไปสู่ผลรวมอนันต์ (ลู่เข้าสู่) ของพหุนามเฮอร์ไมต์ หลาย ตัวแปร${\displaystyle L^{2}}$
• สิ่งที่เทียบเท่ากับอิทธิพลโดยรวมหรือความไวเฉลี่ยสำหรับฟังก์ชันตัวบ่งชี้ของเซต คือ พื้นที่ผิวแบบเกาส์เซียน ซึ่งก็คือเนื้อหาแบบมินคอฟสกีของขอบเขตของเซต
• ตัวดำเนินการที่เทียบเท่ากับตัวดำเนินการเสียงรบกวนคือตัวดำเนินการ Ornstein–Uhlenbeck (ซึ่งเกี่ยวข้องกับการแปลง Mehler ) โดยกำหนดโดยหรืออีกทางหนึ่งโดย โดยที่คือคู่ของฟังก์ชันเกาส์เซียนมาตรฐานที่มีความสัมพันธ์กัน${\displaystyle (U_{\rho }f)(x)=\operatorname {E} _{z\sim N(0,1)}[f(\rho x+{\sqrt {1-\rho ^{2}}}z)]}$${\displaystyle (U_{\rho }f)(x)=\operatorname {E} [f(y)]}$${\displaystyle x,y}$${\displaystyle \rho }$
• คุณสมบัติการหดตัวเกินปกติ (Hypercontractivity) ยังคงมีอยู่ (เมื่อใช้พารามิเตอร์ที่เหมาะสม) ในพื้นที่เกาส์เซียนเช่นกัน

ปริภูมิเกาส์เซียนมีความสมมาตรมากกว่าลูกบาศก์บูลีน (ตัวอย่างเช่น มันไม่เปลี่ยนแปลงเมื่อหมุน) และรองรับอาร์กิวเมนต์แบบต่อเนื่อง ซึ่งอาจทำได้ยากกว่าในบริบทแบบไม่ต่อเนื่องของลูกบาศก์บูลีน หลักการไม่เปลี่ยนแปลงเชื่อมโยงทั้งสองบริบทเข้าด้วยกัน และช่วยให้สามารถอนุมานผลลัพธ์ในลูกบาศก์บูลีนจากผลลัพธ์ในปริภูมิเกาส์เซียนได้

ถ้าฟังก์ชันมีดีกรีไม่เกิน 1 ฟังก์ชันนั้นจะมีค่าคงที่ เท่ากับพิกัด หรือเท่ากับค่าลบของพิกัด โดยเฉพาะอย่างยิ่ง ฟังก์ชันนี้เป็นฟังก์ชันเผด็จการ กล่าวคือ เป็นฟังก์ชันที่ขึ้นอยู่กับพิกัดไม่เกินหนึ่งพิกัด ${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$${\displaystyle f}$${\displaystyle f}$

ทฤษฎีบท Friedgut–Kalai–Naor ^{[ 4 ]}หรือที่รู้จักกันในชื่อทฤษฎีบท FKNระบุว่า ถ้าเกือบจะมีดีกรี 1 แล้วมันจะใกล้เคียงกับระบอบเผด็จการ ในเชิงปริมาณ ถ้าและแล้วจะใกล้เคียงกับระบอบเผด็จการ นั่นคือสำหรับระบอบเผด็จการบูลีนบางหรือเทียบเท่ากับสำหรับระบอบเผด็จการบูลีนบาง ${\displaystyle f}$${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$${\displaystyle \|f^{>1}\|^{2}<\varepsilon }$${\displaystyle f}$${\displaystyle O(\varepsilon )}$${\displaystyle \|f-g\|^{2}=O(\varepsilon )}$${\displaystyle g}$${\displaystyle \Pr[f\neq g]=O(\varepsilon )}$${\displaystyle g}$

ในทำนองเดียวกัน ฟังก์ชันบูลีนที่มีดีกรีสูงสุดจะขึ้นอยู่กับพิกัดสูงสุด ทำให้เป็นจุนตา (ฟังก์ชันที่ขึ้นอยู่กับพิกัดจำนวนคงที่) โดยที่เป็นค่าคงที่สัมบูรณ์เท่ากับอย่างน้อย 1.5 และอย่างมาก 4.41 ดังที่แสดงโดยเวลเลนส์^{[ 5 ]}ทฤษฎีบทคินด์เลอร์-ซาฟรา^{[ 6 ]}ขยายทฤษฎีบทฟรีดกุต-คาไล-นาออร์ไปสู่การตั้งค่านี้ โดยระบุว่าถ้าสอดคล้องกับแล้วจะ ใกล้เคียงกับฟังก์ชันบูลี น ที่มีดีกรีสูงสุด${\displaystyle d}$${\displaystyle C_{W}2^{d}}$${\displaystyle C_{W}}$${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$${\displaystyle \|f^{>d}\|^{2}<\varepsilon }$${\displaystyle f}$${\displaystyle O(\varepsilon )}$${\displaystyle d}$

อสมการปวงกาเรสำหรับลูกบาศก์บูลีน (ซึ่งเป็นผลมาจากสูตรที่ปรากฏข้างต้น) ระบุว่าสำหรับฟังก์ชัน, ${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$

${\displaystyle \operatorname {Var} [f]\leq \operatorname {Inf} [f]\leq \deg f\cdot \operatorname {Var} [f].}$

นี่หมายความว่า. ${\displaystyle \max _{i}\operatorname {Inf} _{i}[f]\geq {\frac {\operatorname {Var} [f]}{n}}}$

ทฤษฎีบท Kahn–Kalai–Linial ^{[ 7 ]}หรือที่รู้จักกันในชื่อทฤษฎีบท KKLระบุว่าถ้าเป็น Boolean แล้ว ${\displaystyle f}$${\displaystyle \max _{i}\operatorname {Inf} _{i}[f]=\Omega \left({\frac {\log n}{n}}\right)}$

ขอบเขตที่กำหนดโดยทฤษฎีบท Kahn–Kalai–Linial นั้นแน่นหนา และบรรลุผลสำเร็จโดย ฟังก์ชัน Tribesของ Ben-Or และ Linial: ^{[ 8 ]}

${\displaystyle (x_{1,1}\land \cdots \land x_{1,w})\lor \cdots \lor (x_{2^{w},1}\land \cdots \land x_{2^{w},w}).}$

ทฤษฎีบท Kahn–Kalai–Linial เป็นหนึ่งในผลลัพธ์แรกๆ ในสาขานี้ และเป็นผลลัพธ์ที่นำเอาคุณสมบัติ hypercontractivity มาใช้ในบริบทของฟังก์ชันบูลีน

ถ้าเป็น-junta (ฟังก์ชันที่ขึ้นอยู่กับพิกัดไม่เกิน n ตัว) แล้วตามอสมการของ Poincaré ${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$${\displaystyle M}$${\displaystyle M}$${\displaystyle \operatorname {Inf} [f]\leq M}$

ทฤษฎีบทของ Friedgut ^{[ 9 ]}เป็นบทกลับของผลลัพธ์นี้ โดยระบุว่าสำหรับค่าใดๆฟังก์ชันจะใกล้เคียงกับ Boolean junta ขึ้นอยู่กับพิกัด ${\displaystyle \varepsilon >0}$${\displaystyle f}$${\displaystyle \varepsilon }$${\displaystyle \exp(\operatorname {Inf} [f]/\varepsilon )}$

เมื่อรวมกับบทตั้งของ Russo–Margulis ทฤษฎีบทจุนตาของ Friedgut บ่งชี้ว่า สำหรับทุกค่าทุกฟังก์ชันเอกพันธุ์จะใกล้เคียงกับจุนตาเมื่อเทียบกับค่าสำหรับ บางค่า${\displaystyle p}$${\displaystyle \mu _{q}}$${\displaystyle q\approx p}$

หลักการไม่เปลี่ยนแปลง^{[ 10 ]}ขยายทฤษฎีบท Berry–Esseenไปยังฟังก์ชันที่ไม่เป็นเชิงเส้น

ทฤษฎีบทเบอร์รี-เอสซีนกล่าวไว้ (ในบรรดาข้ออื่นๆ) ว่า ถ้าและ ไม่มีค่าใดใหญ่เกินไปเมื่อเทียบกับค่าอื่นๆ แล้ว การกระจายของเหนือจะใกล้เคียงกับการกระจายแบบปกติที่มีค่าเฉลี่ยและความแปรปรวนเท่ากัน ${\displaystyle f=\sum _{i=1}^{n}c_{i}x_{i}}$${\displaystyle c_{i}}$${\displaystyle f}$${\displaystyle \{-1,1\}^{n}}$

หลักการไม่เปลี่ยนแปลง (ในกรณีพิเศษ) กล่าวอย่างไม่เป็นทางการว่า ถ้าเป็นพหุนามหลายเชิงเส้นที่มีดีกรีจำกัดเหนือและอิทธิพลทั้งหมดของมีขนาดเล็ก การกระจายของภายใต้การวัดแบบเอกรูปเหนือจะใกล้เคียงกับการกระจายของ ในปริภูมิเกาส์เซียน ${\displaystyle f}$${\displaystyle x_{1},\ldots ,x_{n}}$${\displaystyle f}$${\displaystyle f}$${\displaystyle \{-1,1\}^{n}}$

กล่าวอย่างเป็นทางการมากขึ้น ให้เป็นฟังก์ชันลิปชิตซ์ แบบตัวแปรเดียว ให้, ให้, และให้ สมมติว่าแล้ว ${\displaystyle \psi }$${\displaystyle f=\sum _{S\subseteq [n]}{\hat {f}}(S)\chi _{S}}$${\displaystyle k=\deg f}$${\displaystyle \varepsilon =\max _{i}\sum _{S\ni i}{\hat {f}}(S)^{2}}$${\displaystyle \sum _{S\neq \emptyset }{\hat {f}}(S)^{2}\leq 1}$

${\displaystyle \left|\operatorname {E} _{x\sim \{-1,1\}^{n}}[\psi (f(x))]-\operatorname {E} _{g\sim N(0,I)}[\psi (f(g))]\right|=O(k9^{k}\varepsilon ).}$

โดยการเลือกค่าที่เหมาะสมหมายความว่าการกระจายของค่าภายใต้มาตรวัดทั้งสองจะอยู่ใกล้กันในระยะทาง CDFซึ่งกำหนดโดย ${\displaystyle \psi }$${\displaystyle f}$${\displaystyle \sup _{t}|\Pr[f(x)<t]-\Pr[f(g)<t]|}$

หลักการไม่เปลี่ยนแปลงเป็นส่วนประกอบสำคัญในการพิสูจน์ทฤษฎีบท"เสียงข้างมากมีเสถียรภาพที่สุด"ใน ครั้งแรก

ฟังก์ชันบูลีนเป็นฟังก์ชันเชิงเส้นก็ต่อเมื่อมันสอดคล้องกับเงื่อนไขโดยที่ไม่ใช่เรื่องยากที่จะแสดงว่าฟังก์ชันบูลีนเชิงเส้นคืออักขระ อย่างแท้จริง ${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$${\displaystyle f(xy)=f(x)f(y)}$${\displaystyle xy=(x_{1}y_{1},\ldots ,x_{n}y_{n})}$${\displaystyle \chi _{S}}$

ในการทดสอบคุณสมบัติเราต้องการทดสอบว่าฟังก์ชันที่กำหนดเป็นเชิงเส้นหรือไม่ เป็นเรื่องปกติที่จะลองการทดสอบต่อไปนี้: เลือกแบบสุ่มอย่างสม่ำเสมอ และตรวจสอบว่าถ้าเป็นเชิงเส้น มันจะผ่านการทดสอบเสมอ Blum, Luby และ Rubinfeld ^{[ 11 ]}แสดงให้เห็นว่าถ้าการทดสอบผ่านด้วยความน่าจะเป็น แสดง ว่าใกล้เคียงกับอักขระฟูริเยร์ การพิสูจน์ของพวกเขาเป็นแบบเชิงการจัดเรียง ${\displaystyle x,y\in \{-1,1\}^{n}}$${\displaystyle f(xy)=f(x)f(y)}$${\displaystyle f}$${\displaystyle 1-\varepsilon }$${\displaystyle f}$${\displaystyle O(\varepsilon )}$

Bellare et al. ^{[ 12 ]}ได้ให้การพิสูจน์เชิงวิเคราะห์ฟูริเยร์ที่ง่ายมาก ซึ่งแสดงให้เห็นด้วยว่าหากการทดสอบสำเร็จด้วยความน่าจะเป็น แล้วจะมีความสัมพันธ์กับอักขระฟูริเยร์ การพิสูจน์ของพวกเขาอาศัยสูตรต่อไปนี้สำหรับความน่าจะเป็นของความสำเร็จของการทดสอบ: ${\displaystyle 1/2+\varepsilon }$${\displaystyle f}$

${\displaystyle {\frac {1}{2}}+{\frac {1}{2}}\sum _{S\subseteq [n]}{\hat {f}}(S)^{3}.}$

ทฤษฎีบทความเป็นไปไม่ได้ของแอร์โรว์กล่าวว่า สำหรับผู้สมัครสามคนขึ้นไป กฎการลงคะแนนเสียงเอกฉันท์เพียงกฎเดียวที่ทำให้มีผู้ชนะตามทฤษฎีคอนดอร์เซต์ เสมอ คือระบอบเผด็จการ

การพิสูจน์ทฤษฎีบทของ Arrow ตามปกติจะใช้การจัดเรียง Kalai ^{[ 13 ]}ได้ให้การพิสูจน์ทางเลือกของผลลัพธ์นี้ในกรณีที่มีผู้สมัครสามคนโดยใช้การวิเคราะห์ฟูริเยร์ ถ้าเป็นกฎที่กำหนดผู้ชนะระหว่างผู้สมัครสองคนโดยพิจารณาจากลำดับสัมพัทธ์ในการลงคะแนนเสียง ความน่าจะเป็นที่จะมีผู้ชนะ Condorcet เมื่อพิจารณาจากการลงคะแนนเสียงแบบสุ่มอย่างสม่ำเสมอคือซึ่งทฤษฎีบทนี้เป็นไปตามนั้นได้ง่าย ${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$${\displaystyle {\frac {3}{4}}-{\frac {3}{4}}\operatorname {Stab} _{-1/3}[f]}$

ทฤษฎีบทFKNบ่งชี้ว่า ถ้าเป็นกฎที่มีผู้ชนะแบบคอนดอร์เซต์เกือบตลอดเวลา ก็จะใกล้เคียงกับระบอบเผด็จการ ${\displaystyle f}$${\displaystyle f}$

ผลลัพธ์คลาสสิกในทฤษฎีกราฟสุ่มระบุว่า ความน่าจะเป็นที่กราฟสุ่มจะเป็นกราฟเชื่อมต่อมีแนวโน้มเข้าใกล้0 เมื่อ นี่เป็นตัวอย่างของเกณฑ์ที่คมชัด : ความกว้างของ "หน้าต่างเกณฑ์" ซึ่งคือจะมีค่าน้อยกว่าเกณฑ์เองในเชิงอะซิมโทติก ซึ่งมีค่าประมาณในทางตรงกันข้าม ความน่าจะเป็นที่กราฟจะมีรูปสามเหลี่ยมมีแนวโน้มเข้าใกล้ 0 เมื่อในกรณีนี้ทั้งหน้าต่างเกณฑ์และเกณฑ์เองมีค่า เท่ากับ ดังนั้นนี่จึงเป็น เกณฑ์ ที่ หยาบ${\displaystyle G(n,p)}$${\displaystyle e^{-e^{-c}}}$${\displaystyle p\sim {\frac {\log n+c}{n}}}$${\displaystyle O(1/n)}$${\displaystyle {\frac {\log n}{n}}}$${\displaystyle G(n,p)}$${\displaystyle e^{-c^{3}/6}}$${\displaystyle p\sim {\frac {c}{n}}}$${\displaystyle \Theta (1/n)}$

ทฤษฎีบทเกณฑ์ที่คมชัดของ Friedgut ^{[ 14 ]}กล่าวโดยคร่าวๆ ว่าคุณสมบัติของกราฟแบบโมโนโทน (คุณสมบัติของกราฟคือคุณสมบัติที่ไม่ขึ้นอยู่กับชื่อของจุดยอด) มีเกณฑ์ที่คมชัด เว้นแต่จะมีความสัมพันธ์กับการปรากฏของกราฟย่อยขนาดเล็ก ทฤษฎีบทนี้ถูกนำไปใช้อย่างกว้างขวางในการวิเคราะห์กราฟสุ่มและการ แพร่กระจาย

ในประเด็นที่เกี่ยวข้องทฤษฎีบท KKLบ่งชี้ว่าความกว้างของหน้าต่างเกณฑ์จะมีค่าสูงสุดเพียง^{[ 15 ]}${\displaystyle O(1/\log n)}$

ให้แทนฟังก์ชันเสียงข้างมากบนพิกัด สูตรของเชพพาร์ดให้เสถียรภาพของสัญญาณรบกวนเชิงอะซิมโทติกของฟังก์ชันเสียงข้างมาก: ${\displaystyle \operatorname {Maj} _{n}\colon \{-1,1\}^{n}\to \{-1,1\}}$${\displaystyle n}$

${\displaystyle \operatorname {Stab} _{\rho }[\operatorname {Maj} _{n}]\longrightarrow 1-{\frac {2}{\pi }}\arccos \rho .}$

สิ่งนี้เกี่ยวข้องกับความน่าจะเป็นที่ว่า หากเราเลือกแบบสุ่มอย่างสม่ำเสมอและสร้างโดยการพลิกบิตแต่ละบิตด้วยความน่าจะเป็นแล้วส่วนใหญ่จะยังคงเหมือนเดิม: ${\displaystyle x\in \{-1,1\}^{n}}$${\displaystyle y\in \{-1,1\}^{n}}$${\displaystyle x}$${\displaystyle {\frac {1-\rho }{2}}}$

${\displaystyle \operatorname {Stab} _{\rho }[\operatorname {Maj} _{n}]=2\Pr[\operatorname {Maj} _{n}(x)=\operatorname {Maj} _{n}(y)]-1}$.

มีฟังก์ชันบูลีนบางประเภทที่มีความเสถียรต่อสัญญาณรบกวนสูงกว่า ตัวอย่างเช่น ระบอบเผด็จการมีความเสถียรต่อสัญญาณรบกวนสูง ${\displaystyle x_{i}}$${\displaystyle \rho }$

ทฤษฎีบท "เสียงข้างมากมีเสถียรภาพที่สุด" กล่าวอย่างไม่เป็นทางการว่า ฟังก์ชันเดียวที่มีเสถียรภาพของสัญญาณรบกวนมากกว่าเสียงข้างมากจะมีพิกัดที่มีอิทธิพล ในทางทฤษฎี สำหรับทุก ๆ จะมีอยู่จริงที่ ถ้ามีค่าเฉลี่ยเป็นศูนย์และแล้ว${\displaystyle \varepsilon >0}$${\displaystyle \tau >0}$${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$${\displaystyle \max _{i}\operatorname {Inf} _{i}[f]\leq \tau }$${\displaystyle \operatorname {Stab} _{\rho }[f]\leq 1-{\frac {2}{\pi }}\arccos \rho +\varepsilon }$

การพิสูจน์ทฤษฎีบทนี้ครั้งแรกใช้หลักการความไม่แปรเปลี่ยนร่วมกับทฤษฎีบทไอโซเพอริเมตริกของโบเรลล์ในปริภูมิเกาส์เซียน ตั้งแต่นั้นมาก็มีการคิดค้นการพิสูจน์โดยตรงมากขึ้น^{[ 16 ] [ 17 ]}

Majority is Stablest หมายความว่าอัลกอริทึมการประมาณค่า Goemans–WilliamsonสำหรับMAX-CUTนั้นเหมาะสมที่สุด โดยถือว่าสมมติฐานเกมที่ไม่ซ้ำกันเป็นจริงข้อสรุปนี้ ซึ่งได้มาจาก Khot et al. ^{[ 18 ]}เป็นแรงผลักดันเบื้องหลังการพิสูจน์ทฤษฎีบท