-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathComplexity.py
More file actions
139 lines (108 loc) · 6.31 KB
/
Copy pathComplexity.py
File metadata and controls
139 lines (108 loc) · 6.31 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
from manim import *
class man(Scene):
def construct(self):
# Slide 1: Title
title = Tex("Computational Complexity for Verifying Entropy Inequalities").scale(0.9)
title.set_color_by_gradient(BLUE, PURPLE, TEAL) # Colorful gradient effect
self.play(Write(title))
self.wait(2)
self.play(FadeOut(title))
# Slide 2: Verifying Shannon-Type Inequalities
title = Tex("Verifying Shannon-Type Inequalities").scale(0.9).to_edge(UP)
title.set_color_by_gradient(RED, ORANGE, YELLOW) # Warm gradient colors
bullets = VGroup(
Tex("• Linear programming algorithm we discussed earlier can be used."),
Tex("• Problem size grows exponentially with number of random variables."),
Tex("• This program has a sparse structure of elemental inequalities."),
Tex("• But can it be modified to acceptable running time complexity?"),
Tex("• Some practical algorithms leverage sparse structure to speed up verification."),
).scale(0.7).arrange(DOWN, aligned_edge=LEFT, buff=0.5).next_to(title, DOWN, buff=0.4) # Increased buff for spacing
self.play(Write(title))
for bullet in bullets:
self.play(FadeIn(bullet))
self.wait(1)
self.wait(1)
self.play(FadeOut(title), *[FadeOut(b) for b in bullets])
# Slide 3: Verifying General Entropy Inequalities
title = Tex("Verifying General Entropy Inequalities").scale(0.9).to_edge(UP)
title.set_color_by_gradient(GREEN, BLUE_D)
bullets = VGroup(
Tex("• Verifying a general entropy inequality is significantly more complex."),
Tex("• Is verifying an entropy inequality even decidable?"),
Tex("• Complexity grows with number of variables and structure."),
).scale(0.7).arrange(DOWN, aligned_edge=LEFT, buff=0.5).next_to(title, DOWN, buff=0.4) # Increased buff for spacing
self.play(Write(title))
for bullet in bullets:
self.play(FadeIn(bullet))
self.wait(1)
self.wait(1)
self.play(FadeOut(title), *[FadeOut(b) for b in bullets])
# Slide 4: Copy Lemma
title = Tex("Copy Lemma").scale(0.9).to_edge(UP)
title.set_color_by_gradient(PURPLE, PINK) # Purple-pink gradient
# Definition
lemma_def = VGroup(
Tex(r"Let $A, B, C, D$ be random variables."),
Tex(r"There exists a random variable $R$ such that:"),
Tex(r"(i) $(A,B,C)$ and $(A,B,R)$ have the same distribution."),
Tex(r"(ii) $I(CD; R \mid AB) = 0$."),
).scale(0.65).arrange(DOWN, aligned_edge=LEFT, buff=0.35).next_to(title, DOWN, buff=0.5) # Increased spacing
self.play(Write(title))
for line in lemma_def:
self.play(FadeIn(line))
self.wait(1)
copy_points = VGroup(
Tex("• Helps prove non-Shannon inequalities."),
Tex("• Sufficiency of the copy lemma is still unproven."),
).scale(0.65).arrange(DOWN, aligned_edge=LEFT, buff=0.5).next_to(lemma_def, DOWN, buff=0.6) # Increased spacing
for point in copy_points:
self.play(FadeIn(point))
self.wait(1)
self.wait(2)
self.play(FadeOut(title), *[FadeOut(x) for x in lemma_def], *[FadeOut(x) for x in copy_points])
# Slide 5: Entropy Inequality as Logical Statement
title = Tex("Entropy Inequality as Logical Statement").scale(0.85).to_edge(UP)
title.set_color_by_gradient(YELLOW, GOLD)
paragraph = VGroup(
Tex(r"If the cardinalities of $X_1, \dots, X_n$ are bounded,"),
Tex(r"then the entropy $X_\alpha$ ($\alpha \in \mathbb{N}$) is a function of"),
Tex(r"the entries of the probability mass function $p(x_1,\dots,x_n)$"),
Tex(r"that can be expressed using addition, multiplication, and logarithm."),
Tex(r"For example, if $X \in \{0,1\}$, then"),
Tex(r"$H(X) = -p(0)\log p(0) - p(1)\log p(1)$."),
Tex(r"An entropy inequality is a logical statement:"),
Tex(r"Does a condition on $p(x_1,\dots,x_n)$ (expressed using +, ×, log)"),
Tex(r"hold for all variable choices under the bounded cardinality?")
).scale(0.55).arrange(DOWN, aligned_edge=LEFT, buff=0.3).next_to(title, DOWN, buff=0.5) # Increased spacing
self.play(Write(title))
for line in paragraph:
self.play(FadeIn(line))
self.wait(0.8)
self.wait(2)
self.play(FadeOut(title), *[FadeOut(p) for p in paragraph])
# Slide 6: First-order Decidability and Logarithms
title = Tex("First-order Decidability").scale(0.85).to_edge(UP)
title.set_color_by_gradient(BLUE_E, TEAL_E, GREEN_E)
theory_text = VGroup(
Tex(r"If only addition and multiplication are allowed, such statements are verifiable."),
Tex(r"This follows from the Tarski--Seidenberg theorem."),
Tex(r"It shows that first-order statements over reals using $+, \times$,"),
Tex(r"quantifiers, and logic are decidable."),
Tex(r"But adding exponentials (or $\log$) makes it an open problem."),
Tex(r"This is known as Tarski's exponential function problem."),
Tex(r"It is also shown that if only the cardinalities of a subset of the RVs are bounded"),
Tex(r"then the verification of constrained entropy inequalities with such"),
Tex(r"cardinality bounds is undecidable.")
).scale(0.55).arrange(DOWN, aligned_edge=LEFT, buff=0.3).next_to(title, DOWN, buff=0.5)
theory_text[-3:] = VGroup(
Tex(r"It is also shown that if only the cardinalities of a subset of the RVs are bounded"),
Tex(r"then the verification of constrained entropy inequalities with such"),
Tex(r"cardinality bounds is undecidable.")
).scale(0.55).arrange(DOWN, aligned_edge=LEFT, buff=0.3)
theory_text.arrange(DOWN, aligned_edge=LEFT, buff=0.3).next_to(title, DOWN, buff=0.5)
self.play(Write(title))
for line in theory_text:
self.play(FadeIn(line))
self.wait(0.8)
self.wait(2)
self.play(FadeOut(title), *[FadeOut(line) for line in theory_text])