1
Boolean Analysis — Core Definitions
▶
1.1
Overview
1.2
The Boolean hypercube and functions
1.3
Uniform measure and expectation
1.4
Walsh–Fourier characters
1.5
Fourier coefficients
1.6
Walsh expansion
1.7
Orthonormality and Parseval’s identity
1.8
Coordinate influence
1.9
Noise operator
1.10
Notable Boolean functions
1.11
Sensitivity
1.12
Properties for Arrow’s theorem
1.13
Additional declarations
2
Arrow’s Impossibility Theorem
▶
2.1
Overview
2.2
Social choice definitions
2.3
Voter ordering model
2.4
Key correlation lemmas
2.5
Fourier formula for the cycle correlation
2.6
Acyclicity implies degree-1 structure
2.7
Degree-1 implies dictatorship
2.8
Arrow’s Impossibility Theorem
2.9
Additional declarations
3
Håstad’s Switching Lemma
▶
3.1
Overview
3.2
The formalised statement
3.3
Faithfulness critique
3.4
Dependency graph
3.5
Corollary: no small CNF approximations
4
Error-Correcting Codes — Core Definitions
▶
4.1
Overview
4.2
Basic objects: codewords and codes
4.3
Distance, weight, and rate
4.4
Basic lemma: distance vs. block length
4.5
Additional declarations
5
Singleton Bound
▶
5.1
Overview
5.2
Main result
6
Hamming Bound
▶
6.1
Overview
6.2
Volume formula
6.3
Disjointness of decoding balls
6.4
Hamming bound
7
Entropy and Asymptotic Bounds
▶
7.1
Overview
7.2
Asymptotic upper bound on ball size
7.3
Entropy algebra lemmas
7.4
Analytic helpers
7.5
Stirling-based binomial lower bound
7.6
Positivity of \(q\)-ary entropy
7.7
Additional declarations
8
Linear Codes and the Uniformity Lemma
▶
8.1
Overview
8.2
Distance equals minimum weight in linear codes
8.3
Uniform distributions and random matrices
8.4
Uniformity lemma
9
Gilbert–Varshamov Bound
▶
9.1
Overview
9.2
Probabilistic bound on low-weight outputs
9.3
Union bound over bad matrices
9.4
Gilbert–Varshamov bound
10
List Decoding
▶
10.1
Overview
10.2
List-decodable codes
10.3
Counting lemmas
10.4
List-decoding capacity
11
Johnson Bound
▶
11.1
Overview
11.2
Johnson bound
11.3
Additional declarations
12
CSS Codes (Not Yet Formalized)
▶
12.1
Overview
12.2
Symplectic vector space
12.3
CSS construction
12.4
CSS code parameters
13
Quantum Hamming Bound
▶
13.1
Overview
13.2
Pauli strings
13.3
\(n\)-qubit Hilbert space
13.4
Knill–Laflamme conditions
13.5
Error sphere and sphere-packing
13.6
Quantum Hamming bound
13.7
Additional declarations
14
Quantum Singleton Bound
▶
14.1
Overview
14.2
Symplectic vector space
14.3
Support, weight, and isotropic subspaces
14.4
Code parameters and erasure correctability
14.5
Key lemma: two disjoint correctable sets
14.6
Quantum Singleton bound
14.7
Additional declarations
15
Boolean Analysis — Gate Merge
▶
15.1
Overview
15.2
Declarations
16
Boolean Analysis — LMN
▶
16.1
Overview
16.2
Declarations
17
Boolean Analysis — Bernoulli Cost
▶
17.1
Overview
17.2
Declarations
18
Boolean Analysis — Circuit Compression
▶
18.1
Overview
18.2
Declarations
19
Boolean Analysis — Circuit Helpers
▶
19.1
Overview
19.2
Declarations
20
Boolean Analysis — Circuit Layer Reduction
▶
20.1
Overview
20.2
Declarations
21
Boolean Analysis — Circuit Reindex
▶
21.1
Overview
21.2
Declarations
22
Boolean Analysis — Circuit Tree Manip
▶
22.1
Overview
22.2
Declarations
23
Boolean Analysis — Compression Step
▶
23.1
Overview
23.2
Declarations
24
Boolean Analysis — Depth3 Switching
▶
24.1
Overview
24.2
Declarations
25
Boolean Analysis — Gate Switching
▶
25.1
Overview
25.2
Declarations
26
Boolean Analysis — Iterative Reduction
▶
26.1
Overview
26.2
Declarations
27
Boolean Analysis — Normal Form Conversion
▶
27.1
Overview
27.2
Declarations
28
Boolean Analysis — Recursive Reduction
▶
28.1
Overview
28.2
Declarations
29
Boolean Analysis — Restriction Compose
▶
29.1
Overview
29.2
Declarations
30
Boolean Analysis — Restriction Monotonicity
▶
30.1
Overview
30.2
Declarations
31
Boolean Analysis — Switching Bernoulli
▶
31.1
Overview
31.2
Declarations
32
Boolean Analysis — Switching
▶
32.1
Overview
32.2
Declarations
32.3
Additional declarations
33
Boolean Analysis — Bernoulli Restriction
▶
33.1
Overview
33.2
Declarations
34
Boolean Analysis — Canonical D Tree
▶
34.1
Overview
34.2
Declarations
35
Boolean Analysis — Circuit
▶
35.1
Overview
35.2
Declarations
35.3
Base literal, formula, and decision-tree definitions
36
Boolean Analysis — Encoding
▶
36.1
Overview
36.2
Declarations
37
Boolean Analysis — Encoding Properties
▶
37.1
Overview
37.2
Declarations
37.3
Additional declarations
38
Boolean Analysis — Restriction
▶
38.1
Overview
38.2
Declarations
39
Boolean Analysis — Round Trip
▶
39.1
Overview
39.2
Declarations
40
Communication Complexity — Det Basic
▶
40.1
Overview
40.2
Declarations
41
Communication Complexity — Det Complexity
▶
41.1
Overview
41.2
Declarations
42
Communication Complexity — Det Composition
▶
42.1
Overview
42.2
Declarations
43
Communication Complexity — Det Rectangle
▶
43.1
Overview
43.2
Declarations
43.3
Additional declarations
44
Communication Complexity — Finite Message
▶
44.1
Overview
44.2
Declarations
44.3
Additional declarations
45
Communication Complexity — Func Disjointness
▶
45.1
Overview
45.2
Declarations
45.3
Additional declarations
46
Communication Complexity — Helper
▶
46.1
Overview
46.2
Declarations
47
Communication Complexity — One Way
▶
47.1
Overview
47.2
Declarations
47.3
Additional declarations
48
Communication Complexity — Rectangle
▶
48.1
Overview
48.2
Declarations
49
Communication Complexity — Subprotocol
▶
49.1
Overview
49.2
Declarations
49.3
Additional declarations
50
Communication Complexity — Transcript
▶
50.1
Overview
50.2
Declarations
50.3
Additional declarations
51
Communication Complexity — Trees
▶
51.1
Overview
51.2
Declarations
52
Communication Complexity — Upper Bounds
▶
52.1
Overview
52.2
Declarations
52.3
Additional declarations
53
Communication Complexity — Coin Tape
▶
53.1
Overview
53.2
Declarations
54
Communication Complexity — Comparison
▶
54.1
Overview
54.2
Declarations
55
Communication Complexity — Finite Probability Space
▶
55.1
Overview
55.2
Declarations
56
Communication Complexity — Func Hash
▶
56.1
Overview
56.2
Declarations
57
Communication Complexity — Minimax
▶
57.1
Overview
57.2
Declarations
58
Communication Complexity — One Way Minimax
▶
58.1
Overview
58.2
Declarations
59
Communication Complexity — Private Coin Approximation
▶
59.1
Overview
59.2
Declarations
60
Communication Complexity — Private Coin Basic
▶
60.1
Overview
60.2
Declarations
61
Communication Complexity — Private Coin Complexity
▶
61.1
Overview
61.2
Declarations
62
Communication Complexity — Private Coin Composition
▶
62.1
Overview
62.2
Declarations
63
Communication Complexity — Private Coin Finite Message
▶
63.1
Overview
63.2
Declarations
64
Communication Complexity — Public Coin Approximation
▶
64.1
Overview
64.2
Declarations
65
Communication Complexity — Public Coin Basic
▶
65.1
Overview
65.2
Declarations
66
Communication Complexity — Public Coin Complexity
▶
66.1
Overview
66.2
Declarations
67
Communication Complexity — Public Coin Composition
▶
67.1
Overview
67.2
Declarations
68
Communication Complexity — Public Coin Finite Message
▶
68.1
Overview
68.2
Declarations
69
Communication Complexity — Public Coin One Way
▶
69.1
Overview
69.2
Declarations
70
Cryptography — Schnorr Protocol
▶
70.1
Overview
70.2
Declarations
71
Boolean Analysis — Bool BLR
▶
71.1
Overview
71.2
Declarations
71.3
Additional declarations
72
Boolean Analysis — Bool Fourier
▶
72.1
Overview
72.2
Declarations
72.3
Additional declarations
73
Boolean Analysis — Low Degree
▶
73.1
Overview
73.2
Declarations
74
Boolean Analysis — Zk BLR
▶
74.1
Overview
74.2
Declarations
75
Boolean Analysis — Zk Fourier
▶
75.1
Overview
75.2
Declarations
76
Communication Complexity — Balanced Simulation
▶
76.1
Overview
76.2
Declarations
76.3
Additional declarations
77
Communication Complexity — Bit String
▶
77.1
Overview
77.2
Declarations
78
Communication Complexity — Func Equality
▶
78.1
Overview
78.2
Declarations
78.3
Additional declarations
79
Communication Complexity — Hamming
▶
79.1
Overview
79.2
Declarations
80
Communication Complexity — Rank
▶
80.1
Overview
80.2
Declarations
81
Communication Complexity — Newman Theorem
▶
81.1
Overview
81.2
Declarations
82
Communication Complexity — Derandomization
▶
82.1
Overview
82.2
Declarations
83
Communication Complexity — Discrepancy
▶
83.1
Overview
83.2
Declarations
84
Communication Complexity — Entropy
▶
84.1
Overview
84.2
Declarations
85
Communication Complexity — Func Disjointness Lower Bound
▶
85.1
Overview
85.2
Declarations
86
Communication Complexity — Func Inner Product
▶
86.1
Overview
86.2
Declarations
87
Communication Complexity — KL Divergence
▶
87.1
Overview
87.2
Declarations
88
Communication Complexity — Pinsker
▶
88.1
Overview
88.2
Declarations
88.3
Additional declarations
89
Communication Complexity — TV Distance
▶
89.1
Overview
89.2
Declarations
89.3
Additional declarations
90
Complexity — NAESAT To Coloring
▶
90.1
Overview
90.2
Declarations
90.3
Additional declarations
91
Complexity — SAT To3 SAT
▶
91.1
Overview
91.2
Declarations
91.3
Additional declarations
92
Complexity — Three SAT To Clique
▶
92.1
Overview
92.2
Declarations
92.3
Additional declarations
93
Complexity — Three SAT To Coloring
▶
93.1
Overview
93.2
Declarations
93.3
Additional declarations
94
Graph Theory — Basic
▶
94.1
Overview
94.2
Declarations
95
Graph Theory — Reach
▶
95.1
Overview
95.2
Declarations
96
Learning Theory — Halving
▶
96.1
Overview
96.2
Declarations
97
Learning Theory — Hedge
▶
97.1
Overview
97.2
Declarations
98
Learning Theory — Convex Prediction
▶
98.1
Overview
98.2
Declarations
99
Learning Theory — Episode
▶
99.1
Overview
99.2
Declarations
100
Learning Theory — Hoeffding
▶
100.1
Overview
100.2
Declarations
100.3
Additional declarations
101
Learning Theory — Bernstein
▶
101.1
Overview
101.2
Declarations
102
Learning Theory — Concentration Bound
▶
102.1
Overview
102.2
Declarations
103
Learning Theory — Johnson–Lindenstrauss Main
▶
103.1
Overview
103.2
Declarations
104
Learning Theory — Rademacher
▶
104.1
Overview
104.2
Declarations
104.3
Additional declarations
105
Learning Theory — CCE
▶
105.1
Overview
105.2
Declarations
105.3
Additional declarations
106
Learning Theory — Convex Minimax Core
▶
106.1
Overview
106.2
Declarations
107
Learning Theory — Convex Minimax No Regret
▶
107.1
Overview
107.2
Declarations
107.3
Additional declarations
108
Learning Theory — Finite Minimax
▶
108.1
Overview
108.2
Declarations
109
Learning Theory — Weighted Majority
▶
109.1
Overview
109.2
Declarations
110
Error-Correcting Codes — MRRW Bound
▶
110.1
Overview
110.2
Declarations
111
Kikuchi LDC — Background Facts
▶
111.1
Overview
111.2
Declarations
112
Kikuchi LDC — Decomposition
▶
112.1
Overview
112.2
Declarations
113
Kikuchi LDC — Defs
▶
113.1
Overview
113.2
Declarations
114
Kikuchi LDC — High Value
▶
114.1
Overview
114.2
Declarations
115
Kikuchi LDC — Main Theorem
▶
115.1
Overview
115.2
Declarations
116
Kikuchi LDC — Three XOR
▶
116.1
Overview
116.2
Declarations
117
Kikuchi LDC — Two XOR
▶
117.1
Overview
117.2
Declarations
118
Boolean Analysis — Decision Tree Fourier
▶
118.1
Overview
118.2
Declarations
119
Boolean Analysis — Restriction Card Tail
▶
119.1
Overview
119.2
Declarations
120
Boolean Analysis — Restriction Fourier
▶
120.1
Overview
120.2
Declarations
120.3
Additional declarations
121
Boolean Analysis — A Cp Gates
▶
121.1
Overview
121.2
Declarations
122
Boolean Analysis — Circuit Degree
▶
122.1
Overview
122.2
Declarations
123
Boolean Analysis — Circuit Size
▶
123.1
Overview
123.2
Declarations
124
Complexity — Feed Forward
▶
124.1
Overview
124.2
Declarations
124.3
Additional declarations
125
Boolean Analysis — Low Degree Obstruction
▶
125.1
Overview
125.2
Declarations
126
Boolean Analysis — Smolensky Algebra
▶
126.1
Overview
126.2
Declarations
127
Complexity — Subset Sum To Partition
▶
127.1
Overview
127.2
Declarations
128
Cryptography — RSA
▶
128.1
Overview
128.2
Declarations
128.3
Additional declarations
129
Graph Theory — Karger Min Cut
▶
129.1
Overview
129.2
Declarations
130
Graph Theory — Karger Min Cut Trace
▶
130.1
Overview
130.2
Declarations
131
Graph Theory — Exchange
▶
131.1
Overview
131.2
Declarations
132
Graph Theory — Optimality
▶
132.1
Overview
132.2
Declarations
133
Graph Theory — Union Find
▶
133.1
Overview
133.2
Declarations
134
Learning Theory — Minimax
▶
134.1
Overview
134.2
Declarations
135
Learning Theory — Convex Minimax Separation
▶
135.1
Overview
135.2
Declarations
135.3
Additional declarations
136
Connectivity
▶
136.1
Connectivity
137
Cycle Space Bond Space
▶
137.1
Cycle Space Bond Space
137.2
Additional declarations
138
Directed Graphs
▶
138.1
Directed Graphs
139
Edge Colourings
▶
139.1
Edge Colourings
140
Euler Hamilton
▶
140.1
Euler Hamilton
141
Graphs And Subgraphs
▶
141.1
Graphs And Subgraphs
142
Independent Sets Cliques
▶
142.1
Independent Sets Cliques
142.2
Additional declarations
143
Matchings
▶
143.1
Matchings
144
Networks
▶
144.1
Networks
145
Planar Graphs
▶
145.1
Planar Graphs
146
Trees
▶
146.1
Trees
147
Vertex Colourings
▶
147.1
Vertex Colourings
148
Boolean Analysis — Fourier Concentration
▶
148.1
Overview
148.2
Declarations
149
Boolean Analysis — LMN Concentration
▶
149.1
Overview
149.2
Declarations
150
Boolean Analysis — Razborov Smolensky
▶
150.1
Overview
150.2
Declarations
151
Complexity — DTIME
▶
151.1
Overview
151.2
Declarations
152
Complexity — Examples
▶
152.1
Overview
152.2
Declarations
153
Complexity — Model Invariance
▶
153.1
Overview
153.2
Declarations
154
Complexity — P
▶
154.1
Overview
154.2
Declarations
155
Complexity — Time Constructible
▶
155.1
Overview
155.2
Declarations
156
Complexity — Code Parser
▶
156.1
Overview
156.2
Declarations
157
Complexity — Composition
▶
157.1
Overview
157.2
Declarations
157.3
Additional declarations
158
Complexity — Configuration
▶
158.1
Overview
158.2
Declarations
159
Complexity — Deterministic
▶
159.1
Overview
159.2
Declarations
159.3
Additional declarations
160
Complexity — Encoding
▶
160.1
Overview
160.2
Declarations
160.3
Additional declarations
161
Complexity — Finite
▶
161.1
Overview
161.2
Declarations
162
Complexity — Mathlib Bridge
▶
162.1
Overview
162.2
Declarations
163
Complexity — Oracle
▶
163.1
Overview
163.2
Declarations
164
Complexity — Alphabet Reduction
▶
164.1
Overview
164.2
Declarations
165
Complexity — Bidirectional
▶
165.1
Overview
165.2
Declarations
166
Complexity — Oblivious
▶
166.1
Overview
166.2
Declarations
167
Complexity — Oblivious Candidate
▶
167.1
Overview
167.2
Declarations
168
Complexity — Oblivious Ledger
▶
168.1
Overview
168.2
Declarations
169
Complexity — Oblivious Schedule
▶
169.1
Overview
169.2
Declarations
170
Complexity — Oblivious Setup
▶
170.1
Overview
170.2
Declarations
171
Complexity — Single Tape
▶
171.1
Overview
171.2
Declarations
172
Complexity — Simulation
▶
172.1
Overview
172.2
Declarations
172.3
Additional declarations
173
Complexity — State Renaming
▶
173.1
Overview
173.2
Declarations
174
Complexity — Sweep
▶
174.1
Overview
174.2
Declarations
175
Complexity — Universal
▶
175.1
Overview
175.2
Declarations
175.3
Additional declarations
176
Complexity — Universal Block
▶
176.1
Overview
176.2
Declarations
177
Complexity — Universal Interpreter
▶
177.1
Overview
177.2
Declarations
178
Complexity — Universal Startup
▶
178.1
Overview
178.2
Declarations
179
Complexity — Computable
▶
179.1
Overview
179.2
Declarations
180
Complexity — Diagonalization
▶
180.1
Overview
180.2
Declarations
181
Complexity — Halting
▶
181.1
Overview
181.2
Declarations
182
Communication Complexity — Indexing: Basic
▶
182.1
Overview
182.2
Declarations
183
Communication Complexity — Lower Bound
▶
183.1
Overview
183.2
Declarations
184
Communication Complexity — Dual Hard Sample
▶
184.1
Overview
184.2
Declarations
185
Communication Complexity — Hard Sample
▶
185.1
Overview
185.2
Declarations
186
Communication Complexity — Information Terms
▶
186.1
Overview
186.2
Declarations
187
Learning Theory — Regret
▶
187.1
Overview
187.2
Declarations
188
Learning Theory — Union Bound
▶
188.1
Overview
188.2
Declarations
189
Learning Theory — Hedge Interaction
▶
189.1
Overview
189.2
Declarations
190
Learning Theory — Sub Gaussian
▶
190.1
Overview
190.2
Declarations
191
Complexity — Co NP
▶
191.1
Overview
191.2
Declarations
192
Complexity — Counter Prog Poly Time
▶
192.1
Overview
192.2
Declarations
193
Complexity — EXP
▶
193.1
Overview
193.2
Declarations
194
Complexity — Exp Poly
▶
194.1
Overview
194.2
Declarations
195
Complexity — NP
▶
195.1
Overview
195.2
Declarations
196
Complexity — NTIME
▶
196.1
Overview
196.2
Declarations
197
Complexity — Nondeterminism
▶
197.1
Overview
197.2
Declarations
198
Complexity — P Closure
▶
198.1
Overview
198.2
Declarations
199
Complexity — Poly Time
▶
199.1
Overview
199.2
Declarations
200
Complexity — Poly Time Pairing
▶
200.1
Overview
200.2
Declarations
201
Complexity — Reductions
▶
201.1
Overview
201.2
Declarations
202
Complexity — SAT
▶
202.1
Overview
202.2
Declarations
203
Complexity — TMSAT
▶
203.1
Overview
203.2
Declarations
204
Complexity — Tautology
▶
204.1
Overview
204.2
Declarations
205
Complexity — Transducer
▶
205.1
Overview
205.2
Declarations
206
Complexity — Cook–Levin Hardness
▶
206.1
Overview
206.2
Declarations
207
Complexity — Snapshot
▶
207.1
Overview
207.2
Declarations
208
Complexity — CNF
▶
208.1
Overview
208.2
Declarations
209
Complexity — CNF Encoding
▶
209.1
Overview
209.2
Declarations
210
Complexity — DNF
▶
210.1
Overview
210.2
Declarations
211
Complexity — Convention
▶
211.1
Overview
211.2
Declarations
212
Complexity — Loop
▶
212.1
Overview
212.2
Declarations
213
Complexity — Primitives
▶
213.1
Overview
213.2
Declarations
214
Complexity — Wrappers
▶
214.1
Overview
214.2
Declarations
215
Complexity — Counter Prog
▶
215.1
Overview
215.2
Declarations
216
Complexity — Counter Prog Run
▶
216.1
Overview
216.2
Declarations
217
Complexity — Nondeterministic
▶
217.1
Overview
217.2
Declarations
218
Complexity — Unary Tape
▶
218.1
Overview
218.2
Declarations
219
Boolean Analysis — Bobkov
▶
219.1
Overview
219.2
Declarations
220
Boolean Analysis — Cube
▶
220.1
Overview
220.2
Declarations
221
Boolean Analysis — Discrete Approximation
▶
221.1
Overview
221.2
Declarations
222
Boolean Analysis — Interpolation
▶
222.1
Overview
222.2
Declarations
223
Boolean Analysis — Noise
▶
223.1
Overview
223.2
Declarations
224
Boolean Analysis — Tensorization
▶
224.1
Overview
224.2
Declarations
225
Boolean Analysis — Two Point
▶
225.1
Overview
225.2
Declarations
226
Boolean Analysis — Boolean Blocks
▶
226.1
Overview
226.2
Declarations
227
Boolean Analysis — Definitions
▶
227.1
Overview
227.2
Declarations
228
Boolean Analysis — Gaussian Bobkov
▶
228.1
Overview
228.2
Declarations
229
Boolean Analysis — Gaussian Density
▶
229.1
Overview
229.2
Declarations
230
Boolean Analysis — Halfspace
▶
230.1
Overview
230.2
Declarations
231
Boolean Analysis — Indicator Regularity
▶
231.1
Overview
231.2
Declarations
232
Boolean Analysis — Indicator Smoothing
▶
232.1
Overview
232.2
Declarations
233
Boolean Analysis — InputMoments
▶
233.1
Overview
233.2
Declarations
234
Boolean Analysis — Inputs
▶
234.1
Overview
234.2
Declarations
235
Boolean Analysis — Invariance
▶
235.1
Overview
235.2
Declarations
236
Boolean Analysis — Invariance — Coordinates
▶
236.1
Overview
236.2
Declarations
237
Boolean Analysis — Invariance — Moments
▶
237.1
Overview
237.2
Declarations
238
Boolean Analysis — Invariance — Replacement
▶
238.1
Overview
238.2
Declarations
239
Boolean Analysis — Invariance — Sequence
▶
239.1
Overview
239.2
Declarations
240
Boolean Analysis — Invariance — Smoothing
▶
240.1
Overview
240.2
Declarations
241
Boolean Analysis — Invariance — Taylor
▶
241.1
Overview
241.2
Declarations
242
Boolean Analysis — Normalized Blocks
▶
242.1
Overview
242.2
Declarations
243
Boolean Analysis — Normalized Sums
▶
243.1
Overview
243.2
Declarations
244
Boolean Analysis — Product Bounds
▶
244.1
Overview
244.2
Declarations
245
Boolean Analysis — Product Density
▶
245.1
Overview
245.2
Declarations
246
Boolean Analysis — Product Differentiation
▶
246.1
Overview
246.2
Declarations
247
Boolean Analysis — Product Hessian
▶
247.1
Overview
247.2
Declarations
248
Boolean Analysis — Profile
▶
248.1
Overview
248.2
Declarations
249
Boolean Analysis — Profile Approximation
▶
249.1
Overview
249.2
Declarations
250
Boolean Analysis — Rotation
▶
250.1
Overview
250.2
Declarations
251
Boolean Analysis — Smooth Variation
▶
251.1
Overview
251.2
Declarations
252
Boolean Analysis — SurfaceArea
▶
252.1
Overview
252.2
Declarations
253
Boolean Analysis — Influence
▶
253.1
Overview
253.2
Declarations
254
Boolean Analysis — KKL
▶
254.1
Overview
254.2
Declarations
255
Boolean Analysis — Basic
▶
255.1
Overview
255.2
Declarations
256
Boolean Analysis — Concentration
▶
256.1
Overview
256.2
Declarations
257
Boolean Analysis — DNF
▶
257.1
Overview
257.2
Declarations
258
Boolean Analysis — Elementary
▶
258.1
Overview
258.2
Declarations
259
Boolean Analysis — Junta
▶
259.1
Overview
259.2
Declarations
260
Boolean Analysis — Rounding
▶
260.1
Overview
260.2
Declarations
261
Boolean Analysis — Threshold
▶
261.1
Overview
261.2
Declarations
262
Boolean Analysis — Low Degree
▶
262.1
Overview
262.2
Declarations
263
Boolean Analysis — Small Set Expansion
▶
263.1
Overview
263.2
Declarations
264
Boolean Analysis — Concentration
▶
264.1
Overview
264.2
Declarations
265
Boolean Analysis — Basic
▶
265.1
Overview
265.2
Declarations
266
Boolean Analysis — Bonami
▶
266.1
Overview
266.2
Declarations
267
Boolean Analysis — Decomposition
▶
267.1
Overview
267.2
Declarations
268
Boolean Analysis — Definitions
▶
268.1
Overview
268.2
Declarations
269
Boolean Analysis — Even Moments
▶
269.1
Overview
269.2
Declarations
270
Boolean Analysis — Fourth Moment
▶
270.1
Overview
270.2
Declarations
271
Boolean Analysis — Bounds
▶
271.1
Overview
271.2
Declarations
272
Boolean Analysis — Duality
▶
272.1
Overview
272.2
Declarations
273
Boolean Analysis — Kernel
▶
273.1
Overview
273.2
Declarations
274
Boolean Analysis — Tensorization
▶
274.1
Overview
274.2
Declarations
275
Boolean Analysis — Two Point
▶
275.1
Overview
275.2
Declarations
276
Boolean Analysis — One Bit
▶
276.1
Overview
276.2
Declarations
277
Boolean Analysis — Basic
▶
277.1
Overview
277.2
Declarations
278
Boolean Analysis — Extension
▶
278.1
Overview
278.2
Declarations
279
Boolean Analysis — Holder
▶
279.1
Overview
279.2
Declarations
280
Boolean Analysis — Tensorization
▶
280.1
Overview
280.2
Declarations
281
Boolean Analysis — Two Function
▶
281.1
Overview
281.2
Declarations
282
Boolean Analysis — Two Point
▶
282.1
Overview
282.2
Declarations
283
Boolean Analysis — Moment Bounds
▶
283.1
Overview
283.2
Declarations
284
Boolean Analysis — Parameters
▶
284.1
Overview
284.2
Declarations
285
Boolean Analysis — Applications
▶
285.1
Overview
285.2
Declarations
286
Boolean Analysis — Low Degree
▶
286.1
Overview
286.2
Declarations
287
Boolean Analysis — Basic
▶
287.1
Overview
287.2
Declarations
288
Boolean Analysis — Comparison
▶
288.1
Overview
288.2
Declarations
289
Boolean Analysis — General
▶
289.1
Overview
289.2
Declarations
290
Boolean Analysis — Noise Kernel
▶
290.1
Overview
290.2
Declarations
291
Boolean Analysis — Norms
▶
291.1
Overview
291.2
Declarations
292
Boolean Analysis — Tensorization
▶
292.1
Overview
292.2
Declarations
293
Boolean Analysis — Basic
▶
293.1
Overview
293.2
Declarations
294
Boolean Analysis — Discrete
▶
294.1
Overview
294.2
Declarations
295
Boolean Analysis — Finite Law
▶
295.1
Overview
295.2
Declarations
296
Boolean Analysis — General
▶
296.1
Overview
296.2
Declarations
297
Boolean Analysis — Moments
▶
297.1
Overview
297.2
Declarations
298
Boolean Analysis — Norms
▶
298.1
Overview
298.2
Declarations
299
Boolean Analysis — Polynomial
▶
299.1
Overview
299.2
Declarations
300
Boolean Analysis — Finite Law
▶
300.1
Overview
300.2
Declarations
301
Boolean Analysis — Finite Noise Contraction
▶
301.1
Overview
301.2
Declarations
302
Boolean Analysis — Finite Noise Duality
▶
302.1
Overview
302.2
Declarations
303
Boolean Analysis — Finite Noise Optimization
▶
303.1
Overview
303.2
Declarations
304
Boolean Analysis — Parameters
▶
304.1
Overview
304.2
Declarations
305
Boolean Analysis — Two Point Calculus
▶
305.1
Overview
305.2
Declarations
306
Boolean Analysis — Two Point Contraction
▶
306.1
Overview
306.2
Declarations
307
Boolean Analysis — Two Point Law
▶
307.1
Overview
307.2
Declarations
308
Boolean Analysis — Symmetric
▶
308.1
Overview
308.2
Declarations
309
Boolean Analysis — Tensorization
▶
309.1
Overview
309.2
Declarations
310
Boolean Analysis — Basic
▶
310.1
Overview
310.2
Declarations
311
Boolean Analysis — Centered
▶
311.1
Overview
311.2
Declarations
312
Boolean Analysis — Contraction
▶
312.1
Overview
312.2
Declarations
313
Boolean Analysis — Definitions
▶
313.1
Overview
313.2
Declarations
314
Boolean Analysis — General
▶
314.1
Overview
314.2
Declarations
315
Boolean Analysis — Projection Bounds
▶
315.1
Overview
315.2
Declarations
316
Boolean Analysis — Definitions
▶
316.1
Overview
316.2
Declarations
317
Boolean Analysis — General
▶
317.1
Overview
317.2
Declarations
318
Boolean Analysis — Threshold Functions — Affine Khintchine
▶
318.1
Overview
318.2
Declarations
319
Boolean Analysis — Threshold Functions: Basic
▶
319.1
Overview
319.2
Declarations
320
Boolean Analysis — Threshold Functions — Bit Flip Sets
▶
320.1
Overview
320.2
Declarations
321
Boolean Analysis — Degree One
▶
321.1
Overview
321.2
Declarations
322
Boolean Analysis — Fourier Theory of Threshold Functions
▶
322.1
Overview
322.2
Declarations
323
Boolean Analysis — Threshold Functions — Gaussian
▶
323.1
Overview
323.2
Declarations
324
Boolean Analysis — Threshold Functions — Gaussian Polar
▶
324.1
Overview
324.2
Declarations
325
Boolean Analysis — Gaussian Tail
▶
325.1
Overview
325.2
Declarations
326
Boolean Analysis — Threshold Functions — Linear Threshold Influence
▶
326.1
Overview
326.2
Declarations
327
Boolean Analysis — Threshold Functions — Low Degree Norm
▶
327.1
Overview
327.2
Declarations
328
Boolean Analysis — Majority
▶
328.1
Overview
328.2
Declarations
329
Boolean Analysis — Noise Stability
▶
329.1
Overview
329.2
Declarations
330
Boolean Analysis — Threshold Functions — Polynomial
▶
330.1
Overview
330.2
Declarations
331
Boolean Analysis — Threshold Functions — Sparse Sampling
▶
331.1
Overview
331.2
Declarations
Dependency graph
TCSLib
1
Boolean Analysis — Core Definitions
1.1
Overview
1.2
The Boolean hypercube and functions
1.3
Uniform measure and expectation
1.4
Walsh–Fourier characters
1.5
Fourier coefficients
1.6
Walsh expansion
1.7
Orthonormality and Parseval’s identity
1.8
Coordinate influence
1.9
Noise operator
1.10
Notable Boolean functions
1.11
Sensitivity
1.12
Properties for Arrow’s theorem
1.13
Additional declarations
2
Arrow’s Impossibility Theorem
2.1
Overview
2.2
Social choice definitions
2.3
Voter ordering model
2.4
Key correlation lemmas
2.5
Fourier formula for the cycle correlation
2.6
Acyclicity implies degree-1 structure
2.7
Degree-1 implies dictatorship
2.8
Arrow’s Impossibility Theorem
2.9
Additional declarations
3
Håstad’s Switching Lemma
3.1
Overview
3.2
The formalised statement
3.3
Faithfulness critique
3.4
Dependency graph
3.5
Corollary: no small CNF approximations
4
Error-Correcting Codes — Core Definitions
4.1
Overview
4.2
Basic objects: codewords and codes
4.3
Distance, weight, and rate
4.4
Basic lemma: distance vs. block length
4.5
Additional declarations
5
Singleton Bound
5.1
Overview
5.2
Main result
6
Hamming Bound
6.1
Overview
6.2
Volume formula
6.3
Disjointness of decoding balls
6.4
Hamming bound
7
Entropy and Asymptotic Bounds
7.1
Overview
7.2
Asymptotic upper bound on ball size
7.3
Entropy algebra lemmas
7.4
Analytic helpers
7.5
Stirling-based binomial lower bound
7.6
Positivity of \(q\)-ary entropy
7.7
Additional declarations
8
Linear Codes and the Uniformity Lemma
8.1
Overview
8.2
Distance equals minimum weight in linear codes
8.3
Uniform distributions and random matrices
8.4
Uniformity lemma
9
Gilbert–Varshamov Bound
9.1
Overview
9.2
Probabilistic bound on low-weight outputs
9.3
Union bound over bad matrices
9.4
Gilbert–Varshamov bound
10
List Decoding
10.1
Overview
10.2
List-decodable codes
10.3
Counting lemmas
10.4
List-decoding capacity
11
Johnson Bound
11.1
Overview
11.2
Johnson bound
11.3
Additional declarations
12
CSS Codes (Not Yet Formalized)
12.1
Overview
12.2
Symplectic vector space
12.3
CSS construction
12.4
CSS code parameters
13
Quantum Hamming Bound
13.1
Overview
13.2
Pauli strings
13.3
\(n\)-qubit Hilbert space
13.4
Knill–Laflamme conditions
13.5
Error sphere and sphere-packing
13.6
Quantum Hamming bound
13.7
Additional declarations
14
Quantum Singleton Bound
14.1
Overview
14.2
Symplectic vector space
14.3
Support, weight, and isotropic subspaces
14.4
Code parameters and erasure correctability
14.5
Key lemma: two disjoint correctable sets
14.6
Quantum Singleton bound
14.7
Additional declarations
15
Boolean Analysis — Gate Merge
15.1
Overview
15.2
Declarations
16
Boolean Analysis — LMN
16.1
Overview
16.2
Declarations
17
Boolean Analysis — Bernoulli Cost
17.1
Overview
17.2
Declarations
18
Boolean Analysis — Circuit Compression
18.1
Overview
18.2
Declarations
19
Boolean Analysis — Circuit Helpers
19.1
Overview
19.2
Declarations
20
Boolean Analysis — Circuit Layer Reduction
20.1
Overview
20.2
Declarations
21
Boolean Analysis — Circuit Reindex
21.1
Overview
21.2
Declarations
22
Boolean Analysis — Circuit Tree Manip
22.1
Overview
22.2
Declarations
23
Boolean Analysis — Compression Step
23.1
Overview
23.2
Declarations
24
Boolean Analysis — Depth3 Switching
24.1
Overview
24.2
Declarations
25
Boolean Analysis — Gate Switching
25.1
Overview
25.2
Declarations
26
Boolean Analysis — Iterative Reduction
26.1
Overview
26.2
Declarations
27
Boolean Analysis — Normal Form Conversion
27.1
Overview
27.2
Declarations
28
Boolean Analysis — Recursive Reduction
28.1
Overview
28.2
Declarations
29
Boolean Analysis — Restriction Compose
29.1
Overview
29.2
Declarations
30
Boolean Analysis — Restriction Monotonicity
30.1
Overview
30.2
Declarations
31
Boolean Analysis — Switching Bernoulli
31.1
Overview
31.2
Declarations
32
Boolean Analysis — Switching
32.1
Overview
32.2
Declarations
32.3
Additional declarations
33
Boolean Analysis — Bernoulli Restriction
33.1
Overview
33.2
Declarations
34
Boolean Analysis — Canonical D Tree
34.1
Overview
34.2
Declarations
35
Boolean Analysis — Circuit
35.1
Overview
35.2
Declarations
35.3
Base literal, formula, and decision-tree definitions
36
Boolean Analysis — Encoding
36.1
Overview
36.2
Declarations
37
Boolean Analysis — Encoding Properties
37.1
Overview
37.2
Declarations
37.3
Additional declarations
38
Boolean Analysis — Restriction
38.1
Overview
38.2
Declarations
39
Boolean Analysis — Round Trip
39.1
Overview
39.2
Declarations
40
Communication Complexity — Det Basic
40.1
Overview
40.2
Declarations
41
Communication Complexity — Det Complexity
41.1
Overview
41.2
Declarations
42
Communication Complexity — Det Composition
42.1
Overview
42.2
Declarations
43
Communication Complexity — Det Rectangle
43.1
Overview
43.2
Declarations
43.3
Additional declarations
44
Communication Complexity — Finite Message
44.1
Overview
44.2
Declarations
44.3
Additional declarations
45
Communication Complexity — Func Disjointness
45.1
Overview
45.2
Declarations
45.3
Additional declarations
46
Communication Complexity — Helper
46.1
Overview
46.2
Declarations
47
Communication Complexity — One Way
47.1
Overview
47.2
Declarations
47.3
Additional declarations
48
Communication Complexity — Rectangle
48.1
Overview
48.2
Declarations
49
Communication Complexity — Subprotocol
49.1
Overview
49.2
Declarations
49.3
Additional declarations
50
Communication Complexity — Transcript
50.1
Overview
50.2
Declarations
50.3
Additional declarations
51
Communication Complexity — Trees
51.1
Overview
51.2
Declarations
52
Communication Complexity — Upper Bounds
52.1
Overview
52.2
Declarations
52.3
Additional declarations
53
Communication Complexity — Coin Tape
53.1
Overview
53.2
Declarations
54
Communication Complexity — Comparison
54.1
Overview
54.2
Declarations
55
Communication Complexity — Finite Probability Space
55.1
Overview
55.2
Declarations
56
Communication Complexity — Func Hash
56.1
Overview
56.2
Declarations
57
Communication Complexity — Minimax
57.1
Overview
57.2
Declarations
58
Communication Complexity — One Way Minimax
58.1
Overview
58.2
Declarations
59
Communication Complexity — Private Coin Approximation
59.1
Overview
59.2
Declarations
60
Communication Complexity — Private Coin Basic
60.1
Overview
60.2
Declarations
61
Communication Complexity — Private Coin Complexity
61.1
Overview
61.2
Declarations
62
Communication Complexity — Private Coin Composition
62.1
Overview
62.2
Declarations
63
Communication Complexity — Private Coin Finite Message
63.1
Overview
63.2
Declarations
64
Communication Complexity — Public Coin Approximation
64.1
Overview
64.2
Declarations
65
Communication Complexity — Public Coin Basic
65.1
Overview
65.2
Declarations
66
Communication Complexity — Public Coin Complexity
66.1
Overview
66.2
Declarations
67
Communication Complexity — Public Coin Composition
67.1
Overview
67.2
Declarations
68
Communication Complexity — Public Coin Finite Message
68.1
Overview
68.2
Declarations
69
Communication Complexity — Public Coin One Way
69.1
Overview
69.2
Declarations
70
Cryptography — Schnorr Protocol
70.1
Overview
70.2
Declarations
71
Boolean Analysis — Bool BLR
71.1
Overview
71.2
Declarations
71.3
Additional declarations
72
Boolean Analysis — Bool Fourier
72.1
Overview
72.2
Declarations
72.3
Additional declarations
73
Boolean Analysis — Low Degree
73.1
Overview
73.2
Declarations
74
Boolean Analysis — Zk BLR
74.1
Overview
74.2
Declarations
75
Boolean Analysis — Zk Fourier
75.1
Overview
75.2
Declarations
76
Communication Complexity — Balanced Simulation
76.1
Overview
76.2
Declarations
76.3
Additional declarations
77
Communication Complexity — Bit String
77.1
Overview
77.2
Declarations
78
Communication Complexity — Func Equality
78.1
Overview
78.2
Declarations
78.3
Additional declarations
79
Communication Complexity — Hamming
79.1
Overview
79.2
Declarations
80
Communication Complexity — Rank
80.1
Overview
80.2
Declarations
81
Communication Complexity — Newman Theorem
81.1
Overview
81.2
Declarations
82
Communication Complexity — Derandomization
82.1
Overview
82.2
Declarations
83
Communication Complexity — Discrepancy
83.1
Overview
83.2
Declarations
84
Communication Complexity — Entropy
84.1
Overview
84.2
Declarations
85
Communication Complexity — Func Disjointness Lower Bound
85.1
Overview
85.2
Declarations
86
Communication Complexity — Func Inner Product
86.1
Overview
86.2
Declarations
87
Communication Complexity — KL Divergence
87.1
Overview
87.2
Declarations
88
Communication Complexity — Pinsker
88.1
Overview
88.2
Declarations
88.3
Additional declarations
89
Communication Complexity — TV Distance
89.1
Overview
89.2
Declarations
89.3
Additional declarations
90
Complexity — NAESAT To Coloring
90.1
Overview
90.2
Declarations
90.3
Additional declarations
91
Complexity — SAT To3 SAT
91.1
Overview
91.2
Declarations
91.3
Additional declarations
92
Complexity — Three SAT To Clique
92.1
Overview
92.2
Declarations
92.3
Additional declarations
93
Complexity — Three SAT To Coloring
93.1
Overview
93.2
Declarations
93.3
Additional declarations
94
Graph Theory — Basic
94.1
Overview
94.2
Declarations
95
Graph Theory — Reach
95.1
Overview
95.2
Declarations
96
Learning Theory — Halving
96.1
Overview
96.2
Declarations
97
Learning Theory — Hedge
97.1
Overview
97.2
Declarations
98
Learning Theory — Convex Prediction
98.1
Overview
98.2
Declarations
99
Learning Theory — Episode
99.1
Overview
99.2
Declarations
100
Learning Theory — Hoeffding
100.1
Overview
100.2
Declarations
100.3
Additional declarations
101
Learning Theory — Bernstein
101.1
Overview
101.2
Declarations
102
Learning Theory — Concentration Bound
102.1
Overview
102.2
Declarations
103
Learning Theory — Johnson–Lindenstrauss Main
103.1
Overview
103.2
Declarations
104
Learning Theory — Rademacher
104.1
Overview
104.2
Declarations
104.3
Additional declarations
105
Learning Theory — CCE
105.1
Overview
105.2
Declarations
105.3
Additional declarations
106
Learning Theory — Convex Minimax Core
106.1
Overview
106.2
Declarations
107
Learning Theory — Convex Minimax No Regret
107.1
Overview
107.2
Declarations
107.3
Additional declarations
108
Learning Theory — Finite Minimax
108.1
Overview
108.2
Declarations
109
Learning Theory — Weighted Majority
109.1
Overview
109.2
Declarations
110
Error-Correcting Codes — MRRW Bound
110.1
Overview
110.2
Declarations
111
Kikuchi LDC — Background Facts
111.1
Overview
111.2
Declarations
112
Kikuchi LDC — Decomposition
112.1
Overview
112.2
Declarations
113
Kikuchi LDC — Defs
113.1
Overview
113.2
Declarations
114
Kikuchi LDC — High Value
114.1
Overview
114.2
Declarations
115
Kikuchi LDC — Main Theorem
115.1
Overview
115.2
Declarations
116
Kikuchi LDC — Three XOR
116.1
Overview
116.2
Declarations
117
Kikuchi LDC — Two XOR
117.1
Overview
117.2
Declarations
118
Boolean Analysis — Decision Tree Fourier
118.1
Overview
118.2
Declarations
119
Boolean Analysis — Restriction Card Tail
119.1
Overview
119.2
Declarations
120
Boolean Analysis — Restriction Fourier
120.1
Overview
120.2
Declarations
120.3
Additional declarations
121
Boolean Analysis — A Cp Gates
121.1
Overview
121.2
Declarations
122
Boolean Analysis — Circuit Degree
122.1
Overview
122.2
Declarations
123
Boolean Analysis — Circuit Size
123.1
Overview
123.2
Declarations
124
Complexity — Feed Forward
124.1
Overview
124.2
Declarations
124.3
Additional declarations
125
Boolean Analysis — Low Degree Obstruction
125.1
Overview
125.2
Declarations
126
Boolean Analysis — Smolensky Algebra
126.1
Overview
126.2
Declarations
127
Complexity — Subset Sum To Partition
127.1
Overview
127.2
Declarations
128
Cryptography — RSA
128.1
Overview
128.2
Declarations
128.3
Additional declarations
129
Graph Theory — Karger Min Cut
129.1
Overview
129.2
Declarations
130
Graph Theory — Karger Min Cut Trace
130.1
Overview
130.2
Declarations
131
Graph Theory — Exchange
131.1
Overview
131.2
Declarations
132
Graph Theory — Optimality
132.1
Overview
132.2
Declarations
133
Graph Theory — Union Find
133.1
Overview
133.2
Declarations
134
Learning Theory — Minimax
134.1
Overview
134.2
Declarations
135
Learning Theory — Convex Minimax Separation
135.1
Overview
135.2
Declarations
135.3
Additional declarations
136
Connectivity
136.1
Connectivity
137
Cycle Space Bond Space
137.1
Cycle Space Bond Space
137.2
Additional declarations
138
Directed Graphs
138.1
Directed Graphs
139
Edge Colourings
139.1
Edge Colourings
140
Euler Hamilton
140.1
Euler Hamilton
141
Graphs And Subgraphs
141.1
Graphs And Subgraphs
142
Independent Sets Cliques
142.1
Independent Sets Cliques
142.2
Additional declarations
143
Matchings
143.1
Matchings
144
Networks
144.1
Networks
145
Planar Graphs
145.1
Planar Graphs
146
Trees
146.1
Trees
147
Vertex Colourings
147.1
Vertex Colourings
148
Boolean Analysis — Fourier Concentration
148.1
Overview
148.2
Declarations
149
Boolean Analysis — LMN Concentration
149.1
Overview
149.2
Declarations
150
Boolean Analysis — Razborov Smolensky
150.1
Overview
150.2
Declarations
151
Complexity — DTIME
151.1
Overview
151.2
Declarations
152
Complexity — Examples
152.1
Overview
152.2
Declarations
153
Complexity — Model Invariance
153.1
Overview
153.2
Declarations
154
Complexity — P
154.1
Overview
154.2
Declarations
155
Complexity — Time Constructible
155.1
Overview
155.2
Declarations
156
Complexity — Code Parser
156.1
Overview
156.2
Declarations
157
Complexity — Composition
157.1
Overview
157.2
Declarations
157.3
Additional declarations
158
Complexity — Configuration
158.1
Overview
158.2
Declarations
159
Complexity — Deterministic
159.1
Overview
159.2
Declarations
159.3
Additional declarations
160
Complexity — Encoding
160.1
Overview
160.2
Declarations
160.3
Additional declarations
161
Complexity — Finite
161.1
Overview
161.2
Declarations
162
Complexity — Mathlib Bridge
162.1
Overview
162.2
Declarations
163
Complexity — Oracle
163.1
Overview
163.2
Declarations
164
Complexity — Alphabet Reduction
164.1
Overview
164.2
Declarations
165
Complexity — Bidirectional
165.1
Overview
165.2
Declarations
166
Complexity — Oblivious
166.1
Overview
166.2
Declarations
167
Complexity — Oblivious Candidate
167.1
Overview
167.2
Declarations
168
Complexity — Oblivious Ledger
168.1
Overview
168.2
Declarations
169
Complexity — Oblivious Schedule
169.1
Overview
169.2
Declarations
170
Complexity — Oblivious Setup
170.1
Overview
170.2
Declarations
171
Complexity — Single Tape
171.1
Overview
171.2
Declarations
172
Complexity — Simulation
172.1
Overview
172.2
Declarations
172.3
Additional declarations
173
Complexity — State Renaming
173.1
Overview
173.2
Declarations
174
Complexity — Sweep
174.1
Overview
174.2
Declarations
175
Complexity — Universal
175.1
Overview
175.2
Declarations
175.3
Additional declarations
176
Complexity — Universal Block
176.1
Overview
176.2
Declarations
177
Complexity — Universal Interpreter
177.1
Overview
177.2
Declarations
178
Complexity — Universal Startup
178.1
Overview
178.2
Declarations
179
Complexity — Computable
179.1
Overview
179.2
Declarations
180
Complexity — Diagonalization
180.1
Overview
180.2
Declarations
181
Complexity — Halting
181.1
Overview
181.2
Declarations
182
Communication Complexity — Indexing: Basic
182.1
Overview
182.2
Declarations
183
Communication Complexity — Lower Bound
183.1
Overview
183.2
Declarations
184
Communication Complexity — Dual Hard Sample
184.1
Overview
184.2
Declarations
185
Communication Complexity — Hard Sample
185.1
Overview
185.2
Declarations
186
Communication Complexity — Information Terms
186.1
Overview
186.2
Declarations
187
Learning Theory — Regret
187.1
Overview
187.2
Declarations
188
Learning Theory — Union Bound
188.1
Overview
188.2
Declarations
189
Learning Theory — Hedge Interaction
189.1
Overview
189.2
Declarations
190
Learning Theory — Sub Gaussian
190.1
Overview
190.2
Declarations
191
Complexity — Co NP
191.1
Overview
191.2
Declarations
192
Complexity — Counter Prog Poly Time
192.1
Overview
192.2
Declarations
193
Complexity — EXP
193.1
Overview
193.2
Declarations
194
Complexity — Exp Poly
194.1
Overview
194.2
Declarations
195
Complexity — NP
195.1
Overview
195.2
Declarations
196
Complexity — NTIME
196.1
Overview
196.2
Declarations
197
Complexity — Nondeterminism
197.1
Overview
197.2
Declarations
198
Complexity — P Closure
198.1
Overview
198.2
Declarations
199
Complexity — Poly Time
199.1
Overview
199.2
Declarations
200
Complexity — Poly Time Pairing
200.1
Overview
200.2
Declarations
201
Complexity — Reductions
201.1
Overview
201.2
Declarations
202
Complexity — SAT
202.1
Overview
202.2
Declarations
203
Complexity — TMSAT
203.1
Overview
203.2
Declarations
204
Complexity — Tautology
204.1
Overview
204.2
Declarations
205
Complexity — Transducer
205.1
Overview
205.2
Declarations
206
Complexity — Cook–Levin Hardness
206.1
Overview
206.2
Declarations
207
Complexity — Snapshot
207.1
Overview
207.2
Declarations
208
Complexity — CNF
208.1
Overview
208.2
Declarations
209
Complexity — CNF Encoding
209.1
Overview
209.2
Declarations
210
Complexity — DNF
210.1
Overview
210.2
Declarations
211
Complexity — Convention
211.1
Overview
211.2
Declarations
212
Complexity — Loop
212.1
Overview
212.2
Declarations
213
Complexity — Primitives
213.1
Overview
213.2
Declarations
214
Complexity — Wrappers
214.1
Overview
214.2
Declarations
215
Complexity — Counter Prog
215.1
Overview
215.2
Declarations
216
Complexity — Counter Prog Run
216.1
Overview
216.2
Declarations
217
Complexity — Nondeterministic
217.1
Overview
217.2
Declarations
218
Complexity — Unary Tape
218.1
Overview
218.2
Declarations
219
Boolean Analysis — Bobkov
219.1
Overview
219.2
Declarations
220
Boolean Analysis — Cube
220.1
Overview
220.2
Declarations
221
Boolean Analysis — Discrete Approximation
221.1
Overview
221.2
Declarations
222
Boolean Analysis — Interpolation
222.1
Overview
222.2
Declarations
223
Boolean Analysis — Noise
223.1
Overview
223.2
Declarations
224
Boolean Analysis — Tensorization
224.1
Overview
224.2
Declarations
225
Boolean Analysis — Two Point
225.1
Overview
225.2
Declarations
226
Boolean Analysis — Boolean Blocks
226.1
Overview
226.2
Declarations
227
Boolean Analysis — Definitions
227.1
Overview
227.2
Declarations
228
Boolean Analysis — Gaussian Bobkov
228.1
Overview
228.2
Declarations
229
Boolean Analysis — Gaussian Density
229.1
Overview
229.2
Declarations
230
Boolean Analysis — Halfspace
230.1
Overview
230.2
Declarations
231
Boolean Analysis — Indicator Regularity
231.1
Overview
231.2
Declarations
232
Boolean Analysis — Indicator Smoothing
232.1
Overview
232.2
Declarations
233
Boolean Analysis — InputMoments
233.1
Overview
233.2
Declarations
234
Boolean Analysis — Inputs
234.1
Overview
234.2
Declarations
235
Boolean Analysis — Invariance
235.1
Overview
235.2
Declarations
236
Boolean Analysis — Invariance — Coordinates
236.1
Overview
236.2
Declarations
237
Boolean Analysis — Invariance — Moments
237.1
Overview
237.2
Declarations
238
Boolean Analysis — Invariance — Replacement
238.1
Overview
238.2
Declarations
239
Boolean Analysis — Invariance — Sequence
239.1
Overview
239.2
Declarations
240
Boolean Analysis — Invariance — Smoothing
240.1
Overview
240.2
Declarations
241
Boolean Analysis — Invariance — Taylor
241.1
Overview
241.2
Declarations
242
Boolean Analysis — Normalized Blocks
242.1
Overview
242.2
Declarations
243
Boolean Analysis — Normalized Sums
243.1
Overview
243.2
Declarations
244
Boolean Analysis — Product Bounds
244.1
Overview
244.2
Declarations
245
Boolean Analysis — Product Density
245.1
Overview
245.2
Declarations
246
Boolean Analysis — Product Differentiation
246.1
Overview
246.2
Declarations
247
Boolean Analysis — Product Hessian
247.1
Overview
247.2
Declarations
248
Boolean Analysis — Profile
248.1
Overview
248.2
Declarations
249
Boolean Analysis — Profile Approximation
249.1
Overview
249.2
Declarations
250
Boolean Analysis — Rotation
250.1
Overview
250.2
Declarations
251
Boolean Analysis — Smooth Variation
251.1
Overview
251.2
Declarations
252
Boolean Analysis — SurfaceArea
252.1
Overview
252.2
Declarations
253
Boolean Analysis — Influence
253.1
Overview
253.2
Declarations
254
Boolean Analysis — KKL
254.1
Overview
254.2
Declarations
255
Boolean Analysis — Basic
255.1
Overview
255.2
Declarations
256
Boolean Analysis — Concentration
256.1
Overview
256.2
Declarations
257
Boolean Analysis — DNF
257.1
Overview
257.2
Declarations
258
Boolean Analysis — Elementary
258.1
Overview
258.2
Declarations
259
Boolean Analysis — Junta
259.1
Overview
259.2
Declarations
260
Boolean Analysis — Rounding
260.1
Overview
260.2
Declarations
261
Boolean Analysis — Threshold
261.1
Overview
261.2
Declarations
262
Boolean Analysis — Low Degree
262.1
Overview
262.2
Declarations
263
Boolean Analysis — Small Set Expansion
263.1
Overview
263.2
Declarations
264
Boolean Analysis — Concentration
264.1
Overview
264.2
Declarations
265
Boolean Analysis — Basic
265.1
Overview
265.2
Declarations
266
Boolean Analysis — Bonami
266.1
Overview
266.2
Declarations
267
Boolean Analysis — Decomposition
267.1
Overview
267.2
Declarations
268
Boolean Analysis — Definitions
268.1
Overview
268.2
Declarations
269
Boolean Analysis — Even Moments
269.1
Overview
269.2
Declarations
270
Boolean Analysis — Fourth Moment
270.1
Overview
270.2
Declarations
271
Boolean Analysis — Bounds
271.1
Overview
271.2
Declarations
272
Boolean Analysis — Duality
272.1
Overview
272.2
Declarations
273
Boolean Analysis — Kernel
273.1
Overview
273.2
Declarations
274
Boolean Analysis — Tensorization
274.1
Overview
274.2
Declarations
275
Boolean Analysis — Two Point
275.1
Overview
275.2
Declarations
276
Boolean Analysis — One Bit
276.1
Overview
276.2
Declarations
277
Boolean Analysis — Basic
277.1
Overview
277.2
Declarations
278
Boolean Analysis — Extension
278.1
Overview
278.2
Declarations
279
Boolean Analysis — Holder
279.1
Overview
279.2
Declarations
280
Boolean Analysis — Tensorization
280.1
Overview
280.2
Declarations
281
Boolean Analysis — Two Function
281.1
Overview
281.2
Declarations
282
Boolean Analysis — Two Point
282.1
Overview
282.2
Declarations
283
Boolean Analysis — Moment Bounds
283.1
Overview
283.2
Declarations
284
Boolean Analysis — Parameters
284.1
Overview
284.2
Declarations
285
Boolean Analysis — Applications
285.1
Overview
285.2
Declarations
286
Boolean Analysis — Low Degree
286.1
Overview
286.2
Declarations
287
Boolean Analysis — Basic
287.1
Overview
287.2
Declarations
288
Boolean Analysis — Comparison
288.1
Overview
288.2
Declarations
289
Boolean Analysis — General
289.1
Overview
289.2
Declarations
290
Boolean Analysis — Noise Kernel
290.1
Overview
290.2
Declarations
291
Boolean Analysis — Norms
291.1
Overview
291.2
Declarations
292
Boolean Analysis — Tensorization
292.1
Overview
292.2
Declarations
293
Boolean Analysis — Basic
293.1
Overview
293.2
Declarations
294
Boolean Analysis — Discrete
294.1
Overview
294.2
Declarations
295
Boolean Analysis — Finite Law
295.1
Overview
295.2
Declarations
296
Boolean Analysis — General
296.1
Overview
296.2
Declarations
297
Boolean Analysis — Moments
297.1
Overview
297.2
Declarations
298
Boolean Analysis — Norms
298.1
Overview
298.2
Declarations
299
Boolean Analysis — Polynomial
299.1
Overview
299.2
Declarations
300
Boolean Analysis — Finite Law
300.1
Overview
300.2
Declarations
301
Boolean Analysis — Finite Noise Contraction
301.1
Overview
301.2
Declarations
302
Boolean Analysis — Finite Noise Duality
302.1
Overview
302.2
Declarations
303
Boolean Analysis — Finite Noise Optimization
303.1
Overview
303.2
Declarations
304
Boolean Analysis — Parameters
304.1
Overview
304.2
Declarations
305
Boolean Analysis — Two Point Calculus
305.1
Overview
305.2
Declarations
306
Boolean Analysis — Two Point Contraction
306.1
Overview
306.2
Declarations
307
Boolean Analysis — Two Point Law
307.1
Overview
307.2
Declarations
308
Boolean Analysis — Symmetric
308.1
Overview
308.2
Declarations
309
Boolean Analysis — Tensorization
309.1
Overview
309.2
Declarations
310
Boolean Analysis — Basic
310.1
Overview
310.2
Declarations
311
Boolean Analysis — Centered
311.1
Overview
311.2
Declarations
312
Boolean Analysis — Contraction
312.1
Overview
312.2
Declarations
313
Boolean Analysis — Definitions
313.1
Overview
313.2
Declarations
314
Boolean Analysis — General
314.1
Overview
314.2
Declarations
315
Boolean Analysis — Projection Bounds
315.1
Overview
315.2
Declarations
316
Boolean Analysis — Definitions
316.1
Overview
316.2
Declarations
317
Boolean Analysis — General
317.1
Overview
317.2
Declarations
318
Boolean Analysis — Threshold Functions — Affine Khintchine
318.1
Overview
318.2
Declarations
319
Boolean Analysis — Threshold Functions: Basic
319.1
Overview
319.2
Declarations
320
Boolean Analysis — Threshold Functions — Bit Flip Sets
320.1
Overview
320.2
Declarations
321
Boolean Analysis — Degree One
321.1
Overview
321.2
Declarations
322
Boolean Analysis — Fourier Theory of Threshold Functions
322.1
Overview
322.2
Declarations
323
Boolean Analysis — Threshold Functions — Gaussian
323.1
Overview
323.2
Declarations
324
Boolean Analysis — Threshold Functions — Gaussian Polar
324.1
Overview
324.2
Declarations
325
Boolean Analysis — Gaussian Tail
325.1
Overview
325.2
Declarations
326
Boolean Analysis — Threshold Functions — Linear Threshold Influence
326.1
Overview
326.2
Declarations
327
Boolean Analysis — Threshold Functions — Low Degree Norm
327.1
Overview
327.2
Declarations
328
Boolean Analysis — Majority
328.1
Overview
328.2
Declarations
329
Boolean Analysis — Noise Stability
329.1
Overview
329.2
Declarations
330
Boolean Analysis — Threshold Functions — Polynomial
330.1
Overview
330.2
Declarations
331
Boolean Analysis — Threshold Functions — Sparse Sampling
331.1
Overview
331.2
Declarations