WEBVTT

1
00:00:00.000 --> 00:00:08.767
This overview explains how a circuit's output cone identifies relevant
structure, while cancellation can reduce semantic support further.

2
00:00:08.767 --> 00:00:15.931
The surrounding circuit size and nominal input list
may overstate the function actually being evaluated.

3
00:00:15.931 --> 00:00:15.933
The surrounding circuit size and nominal input list
may overstate the function actually being evaluated.

4
00:00:16.233 --> 00:00:19.833
Start at the output and follow its inputs backward.

5
00:00:19.833 --> 00:00:26.200
The output depends structurally on u and v; those depend on A through D.

6
00:00:26.200 --> 00:00:32.967
This identifies the output cone, the part of the graph that can feed the requested output.

7
00:00:32.967 --> 00:00:36.700
Now evaluate forward with one one zero one.

8
00:00:36.700 --> 00:00:42.533
The first and gives one; the or gives one; their final and gives one.

9
00:00:42.533 --> 00:00:47.467
Backtracing identifies relevant structure, while forward evaluation supplies

10
00:00:47.467 --> 00:00:51.167
values for a particular assignment.

11
00:00:51.167 --> 00:00:57.700
With A fixed to zero, u becomes zero and masks v at the final and.

12
00:00:57.700 --> 00:01:03.100
Changing C or D in that context cannot change the answer.

13
00:01:03.100 --> 00:01:10.752
This local fact does not prove that C and D are irrelevant to the unrestricted function.

14
00:01:10.752 --> 00:01:10.767
This local fact does not prove that C and D are irrelevant to the unrestricted function.

15
00:01:10.767 --> 00:01:15.367
An output cone contains the gates that can influence that output.

16
00:01:15.367 --> 00:01:20.900
Structural inputs can overestimate semantic support when logic cancels.

17
00:01:20.900 --> 00:01:27.633
Neither the surrounding gate count nor the nominal
input list alone describes the function being measured.

18
00:01:27.633 --> 00:01:33.200
The AND gate combines A and B into the intermediate result S.

19
00:01:33.200 --> 00:01:37.633
The next AND gate combines S with NOT C.

20
00:01:37.633 --> 00:01:41.700
The final OR gate combines that result with D.

21
00:01:41.700 --> 00:01:47.300
An unrelated input E feeds a different output and is outside this cone.

22
00:01:47.300 --> 00:01:53.667
At A B C D equal 1100, the selected output is one.

23
00:01:53.667 --> 00:01:56.833
Changing E cannot affect it.

24
00:01:56.833 --> 00:02:05.633
Each of A, B, C and D has some context that changes
the output; the companion enumerates those witnesses.

25
00:02:05.633 --> 00:02:11.400
This example is a teaching cone, not an EPFL result row.

26
00:02:11.400 --> 00:02:17.700
The retained EPFL AND/INV parity comparison belongs to its selected cones,

27
00:02:17.700 --> 00:02:22.000
exact checks and compiled-kernel boundary.

28
00:02:22.000 --> 00:02:29.667
Later descriptor-screening studies ask for a different
artifact and must not replace that parity conclusion.

29
00:02:29.976 --> 00:02:37.967
Return to Circuit One: u equals A and B, v equals C or D, and the output is u and v.

30
00:02:37.967 --> 00:02:45.203
Circuit Two in the intervening explanation instead computes A and B and not C, then or D.

31
00:02:45.203 --> 00:02:52.474
At A B C D equal one one zero zero, Circuit One gives zero and Circuit Two gives one.

32
00:02:52.474 --> 00:02:57.536
The formulas differ; neither answer contradicts the other.

33
00:02:58.286 --> 00:03:03.178
The first branch is one, so it no longer masks the second branch.

34
00:03:03.178 --> 00:03:09.172
With C and D both zero, v is zero and the output is zero.

35
00:03:09.172 --> 00:03:14.714
Changing only D to one makes v one and the output one.

36
00:03:14.714 --> 00:03:20.479
This fixed context demonstrates that D can influence the complete function.

37
00:03:21.229 --> 00:03:25.017
This case establishes a specific contrast.

38
00:03:25.017 --> 00:03:28.120
A structural path can carry influence.

39
00:03:28.120 --> 00:03:31.212
Use a fixed context to demonstrate it.

40
00:03:31.212 --> 00:03:38.414
Keep the input, intermediate values, and conclusion together when comparing it with the previous case.

41
00:03:38.414 --> 00:03:44.671
The calculated answer belongs to this complete assignment under the stated rule.

42
00:03:44.969 --> 00:03:50.335
In this different circuit, A appears twice in a branch leading to the output.

43
00:03:50.335 --> 00:03:54.735
A graph traversal therefore finds A in the output cone.

44
00:03:54.735 --> 00:03:59.969
Reachability alone does not yet establish semantic influence.

45
00:03:59.969 --> 00:04:05.702
For either value of A, exclusive-or of A with itself is zero.

46
00:04:05.702 --> 00:04:08.469
The output reduces to B.

47
00:04:08.469 --> 00:04:12.869
Changing A never changes the answer, even though A is structurally

48
00:04:12.869 --> 00:04:16.569
reachable in the unreduced graph.

49
00:04:16.569 --> 00:04:20.235
An output cone describes graph reachability.

50
00:04:20.235 --> 00:04:25.502
Live support describes variables that can affect the function in some context.

51
00:04:25.502 --> 00:04:30.435
Use the appropriate notion for the task and do not treat a structural over-approximation

52
00:04:30.435 --> 00:04:34.535
as an exact support calculation.

53
00:04:34.535 --> 00:04:34.538
Trace the gates that can reach the selected output.

54
00:04:34.538 --> 00:04:38.435
Trace the gates that can reach the selected output.

55
00:04:38.435 --> 00:04:44.802
Distinguish structural cone membership
from the inputs that can change its value.