08 Five-Color Theorem, Brooks Theorem, 3-Colorable Coloring Approximation, Randomness

Lecture from: 13.03.2025 | Video: Homelab

Recap

Let’s first revisit the concept of graph coloring, which we discussed in the previous lecture, as it provides a good starting point before we delve into the world of algorithms and probability.

k-Färbung (k-Coloring) and Chromatic Number $\chi (G)$

Definition of k-Coloring:

A k-coloring of a graph $G=(V,E)$ with $k$ colors is a mapping or function $c:V\to [k]$, where $[k]=\{1,2,...,k\}$ represents the set of $k$ colors. The essential condition for a valid k-coloring is that for every edge $\{u,v\}\in E$, the colors assigned to vertices $u$ and $v$ must be different:

$c(u)\ne c(v)$ for all edges $\{u,v\}\in E$.

In essence, we are assigning one of $k$ colors to each vertex such that no two adjacent vertices (connected by an edge) share the same color.

Chromatic Number $\chi (G)$

The chromatic number of a graph $G$, denoted as $\chi (G)$, is the minimum number of colors needed to achieve a valid vertex coloring of $G$. It is the smallest integer $k$ for which a k-coloring of $G$ exists.

Equivalence to k-Partite Graphs:

A graph $G$ is k-colorable (i.e., $\chi (G)\le k$) if and only if $G$ is k-partite. A k-partite graph is one whose vertices can be partitioned into $k$ independent sets (stable sets). An independent set is a set of vertices where no two vertices are adjacent. In a k-coloring, vertices of the same color form an independent set.

Special Case: Bipartite Graphs and 2-Colorability:

A graph $G$ is bipartite if and only if it is 2-colorable, i.e., $\chi (G)\le 2$. We can efficiently check if a graph is bipartite and find a 2-coloring in linear time $O(|E|)$ using BFS or DFS.

Greedy Coloring Algorithm: A Simple Approach

We discussed the Greedy Coloring Algorithm as a basic heuristic for graph coloring.

GREEDY-FÄRBUNG (G):

1. Choose a Vertex Ordering: Select an arbitrary ordering of the vertices $V=\{v_1,...,v_n\}$.
2. Color the First Vertex: Assign color 1 to the first vertex in the ordering: $c[v_1]\leftarrow 1$.
3. Iterate and Color: For each subsequent vertex $v_i$ (from $i=2$ to $n$): $c[v_i]\leftarrow \min \{k\in \mathbb{N}\mid k\ne c(u)\text{ for all }u\in N(v_i)\cap \{v_1,...,v_{i-1}\}\}$ This means, for each vertex $v_i$, we assign the smallest positive integer color that is not already used by any of its neighbors that come before it in the chosen vertex ordering.

Observation about Greedy Coloring:

For any vertex ordering, the Greedy Coloring Algorithm will never use more than $\Delta (G)+1$ colors, where $\Delta (G)$ is the maximum degree of the graph $G$. This is because, when coloring a vertex $v$, it has at most $\Delta (G)$ neighbors, so there is always at least one color available from the first $\Delta (G)+1$ colors.

Heuristic: Smallest Degree Vertex Ordering

To improve the performance of the Greedy Algorithm, we can use a heuristic for vertex ordering:

1. Find a vertex $v_n$ with the minimum degree in the current graph.
2. Remove $v_n$ and all incident edges.
3. Recursively find a smallest-last ordering for the remaining graph, say $v_1,...,v_{n-1}$.
4. The smallest-last ordering is then $v_1,...,v_{n-1},v_n$.

This heuristic tends to color vertices with fewer constraints (lower degree) later, which often leads to better colorings.

Observation with Smallest-Last Ordering:

If for a chosen vertex ordering $v_1,...,v_n$, for all $2\le i\le n$, the number of already colored neighbors of $v_i$ is at most $k$ (i.e., $|N(v_i)\cap \{v_1,...,v_{i-1}\}|\le k$), then the Greedy Algorithm will use at most $k+1$ colors.

Corollaries based on Heuristic and Graph Properties:

• Trees: The heuristic finds a 2-coloring for trees because in any subgraph of a tree (which is a forest), there is always a vertex of degree at most 1 (a leaf, or an isolated vertex). Thus, $k\le 1$, and the algorithm uses at most $1+1=2$ colors.
• Planar Graphs: For planar graphs, it is known that there’s always a vertex of degree at most 5. Using the smallest-last heuristic, we can often ensure that for each vertex $v_i$, it has at most 5 already colored neighbors. Thus, the heuristic finds a coloring with at most $5+1=6$ colors for planar graphs.
• Connected Graphs with a Low Degree Vertex: If a connected graph $G=(V,E)$ has a vertex $v\in V$ with degree $\text{deg}(v)<\Delta (G)$, then the heuristic (or even BFS/DFS ordering) can provide a vertex ordering for which the Greedy Algorithm uses at most $\Delta (G)$ colors.

Color Class Swapping and Block Graphs

In some situations, we can improve a coloring by swapping color classes. If we have a valid coloring, and we decide to swap the vertices colored with color A with vertices colored with color B, we might still have a valid coloring or create a new valid coloring with desired properties.

Application: Block Graphs

Consider a Block Graph. A block of a graph is a maximal 2-connected subgraph, or a bridge, or an isolated vertex. Block graphs have a structure composed of blocks connected at cut vertices (articulation points).

Property: If every block of a graph $G$ can be colored with $k$ colors, then the entire graph $G$ can also be colored with $k$ colors.

Reasoning: We can color each block independently with $k$ colors. When blocks share vertices (at articulation points), we might need to adjust the color classes within some blocks (by swapping colors) to ensure that at the articulation points, the colorings are consistent across different blocks. Since each block is k-colorable, and we can manage color assignments at articulation points using color swapping, we can extend the k-coloring to the whole graph.

Four-Color Theorem

4-Farben-Theorem: Every planar graph (a graph that can be drawn in the plane without edge crossings) can be colored with at most 4 colors.

This is a famous theorem in graph theory.

Algorithm for Coloring Planar Graphs with 5 Colors (Sketch):

While the 4-Color Theorem is complex to prove, there is a simpler algorithm to color planar graphs with 5 colors.

1. Find a Vertex of Degree $\le 5$: In any planar graph, there is always at least one vertex with degree at most 5. Let’s find such a vertex $v$.
2. Recursively Color $G^{\prime }=G\setminus \{v\}$: Remove $v$ and its incident edges to get a smaller planar graph $G^{\prime }=G\setminus \{v\}$. Recursively color $G^{\prime }$ with 5 colors.
3. Color Vertex $v$: Consider the neighbors of $v$ in the original graph $G$.
   • Case 1: Neighbors use $\le 4$ colors: If the neighbors of $v$ in $G$ use at most 4 different colors in the coloring of $G^{\prime }$, then we can simply color $v$ with the 5th color (or any color not used by its neighbors).
   • Case 2: Neighbors use 5 colors: If the neighbors of $v$, say $v_1,v_2,v_3,v_4,v_5$ (in cyclic order), use all 5 colors (say colors 1, 2, 3, 4, 5, respectively).
     • Consider the subgraph $G_{1,3}$ induced by vertices colored with colors 1 or 3 in $G^{\prime }$. Similarly, consider $G_{2,4}$ for colors 2 and 4.
     • Subcase 2a: If $v_1$ and $v_3$ are in different connected components in $G_{1,3}$, then we can swap colors 1 and 3 in the component of $G_{1,3}$ containing $v_1$. After swapping, $v_1$ and $v_3$ both have color 3 (or both color 1, depending on swap direction), so color 1 becomes available for $v$. Color $v$ with color 1.
     • Subcase 2b: If $v_1$ and $v_3$ are in the same component in $G_{1,3}$, then $v_2$ and $v_4$ must be in different components in $G_{2,4}$ (otherwise, paths from $v_1$ to $v_3$ and from $v_2$ to $v_4$ would cross in a planar graph, forming a Kempe chain contradiction). Swap colors 2 and 4 in the component of $G_{2,4}$ containing $v_2$. Color 2 becomes available for $v$. Color $v$ with color 2.

This algorithm recursively colors planar graphs with 5 colors.

Observation: Dependence on Vertex Ordering

As we’ve seen, the performance of the Greedy Coloring Algorithm is heavily dependent on the chosen vertex ordering. While for some orderings, it can achieve the optimal chromatic number, for others, it can perform significantly worse, even for simple graphs like bipartite graphs.

Improved Greedy Coloring with Heuristics

To mitigate the dependency on arbitrary vertex orderings and improve the practical performance of the Greedy Coloring Algorithm, we can employ heuristics to guide the selection of vertex orderings.

Smallest-Last Vertex Ordering Heuristic (Revisited)

We discussed the smallest-last vertex ordering as a heuristic. Let’s reiterate its benefits:

• Intuition: Delay coloring vertices with lower degrees until later. These vertices have fewer constraints and are more likely to be easily colorable with already used colors.
• Procedure: Repeatedly find and remove a vertex of minimum degree from the remaining graph, placing it last in the ordering.

Heuristic Algorithm

1. Initialize an empty vertex ordering list $L$.
2. While the graph is not empty: a. Find a vertex $v$ with the minimum degree in the current graph. b. Append $v$ to the beginning of $L$. c. Remove $v$ and its incident edges from the graph.
3. Reverse the list $L$ to get the final vertex ordering $v_1,v_2,...,v_n$.
4. Apply the Greedy Coloring Algorithm using the vertex ordering $v_1,v_2,...,v_n$.

Benefits of Smallest-Last Ordering

• Trees: Guarantees a 2-coloring for trees.
• Planar Graphs: Often produces colorings with 6 or fewer colors for planar graphs (though 4 colors are always sufficient by the Four-Color Theorem).
• General Graphs: Generally performs better than arbitrary orderings, especially for sparse graphs.

Brooks’ Theorem

Brooks’ Theorem: For a connected graph $G$, if $G$ is not a complete graph $K_n$ and not an odd cycle $C_{2n+1}$, then the chromatic number of $G$ is at most its maximum degree $\Delta (G)$:

If $G\ne K_n$, $G\ne C_{2n+1}$, and $G$ is connected, then $\chi (G)\le \Delta (G)$.

Furthermore, such a $\Delta (G)$-coloring can be found in time $O(|E|)$.

Significance of Brooks’ Theorem:

• Tight Bound: Brooks’ Theorem provides a tighter upper bound on the chromatic number than the $\Delta (G)+1$ bound given by the Greedy Coloring Algorithm with an arbitrary ordering. It shows that in most cases, we can color a graph using at most its maximum degree of colors, not necessarily one more.
• Exceptions: The exceptions ($K_n$ and $C_{2n+1}$) are necessary. For a complete graph $K_n$, $\chi (K_n)=n=\Delta (K_n)+1$. For an odd cycle $C_{2n+1}$, $\chi (C_{2n+1})=3$, while $\Delta (C_{2n+1})=2$, so $\chi (C_{2n+1})=\Delta (C_{2n+1})+1$.
• Algorithmic Implication: Brooks’ Theorem not only gives a bound but also implies that there is an efficient algorithm (running in $O(|E|)$ time) to find such a $\Delta (G)$-coloring (under the given conditions).

Algorithm Sketch for Brooks’ Theorem

Here’s a sketch of an algorithm to find a $\Delta (G)$-coloring for graphs satisfying the conditions of Brooks’ Theorem, running in time $O(|E|)$.

1. Case: $\Delta (G)=2$:

   • If $\Delta (G)=2$ and $G$ is connected and not an odd cycle, then $G$ must be either a path or an even cycle.
   • In this case, we can color $G$ with just two colors. (Paths and even cycles are bipartite and 2-colorable).

2. Case: $\exists v\in V$ with $\text{deg}(v)<\Delta (G)$:

   • If there exists a vertex $v$ in $G$ whose degree is strictly less than the maximum degree $\Delta (G)$, we can use the Greedy Coloring Algorithm with the Smallest-Last Heuristic.
   • As discussed earlier, in this scenario, the Greedy Algorithm with a good heuristic (like smallest-last) is guaranteed to use at most $\Delta (G)$ colors.

3. Case: Articulation Point (Cut Vertex) Exists:

   • If $G$ has an articulation point (cut vertex) $v$, we can decompose $G$ into its blocks.
   • Color each block of $G$ (which are 2-connected components, bridges, or isolated vertices) with $\Delta (G)$ colors using a suitable heuristic. Note that within each block (except possibly the block containing the vertex with maximum degree in G), vertices will have a degree less than $\Delta (G)$ in the original graph $G$.
   • After coloring all blocks, we might need to perform color class swapping to ensure that the coloring is consistent at the articulation point $v$. Since $v$ is in multiple blocks, we need to make sure it has the same color in all blocks it belongs to. We can achieve this by swapping color classes within blocks, if necessary.

4. Case: Determine Vertices $v,x,y\in V$ with $x,y\in N(v)$ and $\{x,y\}\notin E$:

   • If none of the above cases apply, we need to find vertices $v,x,y\in V$ such that $x$ and $y$ are neighbors of $v$ ($x,y\in N(v)$), but $x$ and $y$ are not adjacent to each other ($\{x,y\}\notin E$). Such vertices must exist because $G$ is connected and not a complete graph.

5. Construct $G^{\prime }=G[V\setminus \{x,y\}]$:

   • Consider a new graph $G^{\prime }$ obtained by removing vertices $x$ and $y$ from $G$, i.e., $G^{\prime }=G[V\setminus \{x,y\}]$.

6. Subcases based on Connectivity of $G^{\prime }$:

   • Case 6a: $G^{\prime }$ is connected ($G^{\prime }$ zshgd):

     • Pre-color $x$ and $y$: Since $x$ and $y$ are not adjacent, we can initially consider coloring them with the same color. However, for the algorithm’s structure, it’s more convenient to handle them as the first two vertices to be colored in a specific ordering of $G$.
     • Color $G^{\prime }$ with Greedy Algorithm: We now need to color the connected graph $G^{\prime }=G[V\setminus \{x,y\}]$. We can use the Greedy Coloring Algorithm combined with a suitable Heuristic (like the smallest-last vertex ordering) for $G^{\prime }$.

   • Case 6b: $G^{\prime }$ is not connected ($G^{\prime }$ nicht zshgd):

     • Consider Connected Components of $G^{\prime }$: If removing $x$ and $y$ disconnects $G$, let $G_1,G_2,...,G_s$ be the connected components of $G^{\prime }=G[V\setminus \{x,y\}]$.
     • Analyze Neighbors of $x$ and $y$ in Components: For each component $G_i$, consider the neighbors of $x$ and $y$ within $G_i$.
     • Subcase 6b(i): Limited Neighbors in at least one Component: If for at least one component, say $G_1$, both $x$ and $y$ have at most $\Delta (G)-1$ neighbors in $G_1$. This implies that when we consider coloring $G_1\cup \{x,y\}$, even if we force $x$ and $y$ to have the same color, the maximum degree condition within $G_1\cup \{x,y\}$ (considering neighbors within $G_1\cup \{x,y\}$) is still manageable for the Greedy Algorithm to work within $\Delta (G)$ colors.
     • Subcase 6b(ii): Many Neighbors in Components, but Specific Structure: If for every component $G_i$, either $x$ or $y$ (or both) have close to $\Delta (G)$ neighbors in $G_i$. Brooks’ theorem algorithm uses a more detailed argument here, possibly involving considering only two components ($s=2$) and analyzing the degrees of $x$ and $y$ in these components to carefully assign colors and possibly swap color classes to avoid using more than $\Delta (G)$ colors. For the entire proof look at the script…

7. Final Coloring: By carefully handling all these cases, particularly Case 6 and its subcases, and potentially using color class swaps or specific ordering strategies within the Greedy Algorithm, Brooks’ Theorem guarantees that we can color the graph $G$ using at most $\Delta (G)$ colors, provided $G$ is not a complete graph $K_n$ or an odd cycle $C_{2n+1}$. The algorithm can be implemented to run in $O(|E|)$ time by efficiently managing the graph structure and color assignments.

This algorithm sketch outlines how to find a $\Delta (G)$-coloring for graphs satisfying Brooks’ Theorem conditions in $O(|E|)$ time. The details, especially for handling disconnected cases and color class swapping, are more involved but are based on careful application of the Greedy Algorithm and color adjustments.

Further Algorithmic Ideas

Heuristic: Smallest Degree Vertex Ordering (Revisited):

We have discussed the smallest-last vertex ordering heuristic. The underlying principle is:

“Save the easy-to-color vertices for last.”

Opposite Idea

An alternative, sometimes useful, idea is the opposite:

“Start with a simple subgraph and color it first. Use new colors for the rest.”

Coloring 3-Colorable Graphs with $O(\sqrt{|V|})$ Colors:

1. Iterative Removal of High-Degree Vertices (max $\sqrt{|V|}$ iterations): While there exists a vertex $v$ with more than $\sqrt{|V|}$ uncolored neighbors:

   • Color $v$ with a new color.
   • Color all uncolored neighbors of $v$ with 2 additional new colors (which we can since $N(v)$ is two colorable).
   • Remove all newly colored vertices from the graph.

2. Greedy Coloring on Remaining Graph: The remaining graph will have a maximum degree $\Delta \le \sqrt{|V|}$. Color the remaining vertices using the Greedy Coloring Algorithm, which will use at most $\Delta +1\le \sqrt{|V|}+1$ new colors.

This algorithm combines the idea of dealing with “complex” (high-degree) parts of the graph first using new colors and then using a simpler greedy approach for the remaining, “simpler” part.

Randomness in Computer Science

Let’s now shift our focus to the crucial role of probability in algorithms and computer science.

Why Should Every Computer Scientist Understand Probability Theory?

Randomness and probability are not merely abstract mathematical concepts. They are, in fact, powerful and practical tools that computer scientists use to design algorithms that are both efficient and effective. The introduction of randomness into algorithms can often lead to solutions that are simpler, faster, or even possible when deterministic approaches fall short.

Examples of Algorithms Utilizing Randomness

Let’s explore several key examples where randomness is not just an add-on, but a core component enabling the algorithm’s success.

1. QuickSort Algorithm: Random Pivot Selection

Question: What truly makes QuickSort live up to its name, “QuickSort”?

Answer: The defining characteristic of QuickSort, and the key to its efficiency, especially in average-case scenarios, is the random selection of the pivot element.

In QuickSort, a pivot element is chosen to partition the array. A naive, deterministic choice of the pivot (like always picking the first or last element) can lead to worst-case $O(n^2)$ time complexity when the input array is already sorted or nearly sorted.

However, by selecting the pivot element randomly from the array, we drastically reduce the probability of consistently encountering these worst-case scenarios. Randomization ensures that, on average, the pivot will be reasonably close to the median, leading to balanced partitions and a much faster sorting process. This randomized pivot selection “averages out” the performance across all possible input arrays, resulting in an expected time complexity of $O(n\log n)$ for sorting $n$ elements. This is the reason behind QuickSort’s celebrated “quick” performance in practice.

2. Primality Testing: Randomized Probabilistic Tests

Problem: Given a natural number $n$, we want to determine efficiently whether $n$ is a prime number.

Importance: Primality testing is a fundamental problem with immense practical significance, particularly in the field of cryptography. Public-key cryptography systems like RSA rely heavily on the generation and use of large prime numbers. The ability to efficiently test if a large number is prime is thus critical for secure communication and data protection.

Randomized Algorithm for Primality Testing (Probabilistic Tests):

For very large numbers, deterministic primality tests can be computationally expensive. Randomized primality tests offer a much more efficient alternative. A typical approach is as follows:

• Random Witness Selection: Choose a random integer $x$ within a specific range (e.g., $1\le x\le n$).
• Probabilistic Test: Perform a probabilistic primality test, such as the Miller-Rabin test, to check if $x$ acts as a “witness” for the compositeness of $n$.
  • If $x$ is found to be a witness, we can definitively conclude that $n$ is composite (not prime).
  • If $x$ is not a witness after the test, we can say that $n$ is likely prime. There is a small probability of error, but we cannot be absolutely certain based on a single test.

Reducing Error Probability through Repetition:

The power of randomized primality testing lies in the fact that by repeating the test multiple times with independently chosen random values of $x$, we can dramatically reduce the probability of error. Each independent test provides additional evidence. If $n$ is composite, the probability of a randomly chosen $x$ not being a witness is bounded, meaning that with enough repetitions, the chance of incorrectly declaring a composite number as prime becomes negligibly small. Randomized primality tests like Miller-Rabin are significantly faster than deterministic methods, making them indispensable for cryptographic applications dealing with very large numbers.

3. Cryptography: Leveraging Randomness for Security

Randomness is not just about efficiency in cryptography; it’s often about security itself. Let’s look at two examples:

Visual Cryptography:

Visual cryptography is an intriguing cryptographic technique that cleverly uses randomness to encrypt visual information (like images). The beauty of visual cryptography is that decryption can be performed by the human visual system, simply by overlaying or stacking encrypted shares, without the need for complex computations.

The process typically involves:

• Image Splitting: An original image is split into multiple “shares” (often two).
• Random Share Generation: These shares are generated using random processes in such a way that:
  • Individual shares reveal absolutely no information about the original image when viewed in isolation. They appear as random noise.
  • When the shares are combined correctly (e.g., overlaid), the original image magically reappears.

Randomness is absolutely crucial in the share generation process to ensure that individual shares leak no information, and that only the correct combination of shares reveals the secret image.

Zero-Knowledge Protocols:

Zero-knowledge protocols are a fascinating concept in cryptography. They enable one party (the prover, often called Alice) to convince another party (the verifier, often called Bob) that a statement is true, without revealing any information beyond the mere truth of the statement. Randomness is a fundamental building block in the design of many zero-knowledge protocols.

Let’s consider two illustrative examples of zero-knowledge protocols:

Example 1: Graph Isomorphism Zero-Knowledge Proof

Imagine Alice knows that two graphs, $G$ and $G^{\prime }$, are isomorphic (they have the same structure, just possibly with different vertex labels). She wants to prove this to Bob, but without revealing the actual isomorphism (the mapping of vertices between $G$ and $G^{\prime }$). A zero-knowledge protocol allows her to do this:

1. Random Permutation by Alice: Alice takes her graph $G$ and applies a random permutation to its vertices, creating a new graph $H$. She then sends this permuted graph $H$ to Bob. Crucially, Bob does not know the permutation used.
2. Random Challenge by Bob: Bob, upon receiving $H$, randomly chooses one of two challenges for Alice to prove:
   • (a) Isomorphism to Original G: Prove that $H$ is isomorphic to the original graph $G$ (i.e., $G\sim H$).
   • (b) Isomorphism to G’: Prove that $H$ is isomorphic to the graph $G^{\prime }$ (i.e., $G^{\prime }\sim H$).
3. Alice’s Proof: Alice, because she knows the isomorphism between $G$ and $G^{\prime }$, and she created $H$ by permuting $G$, can fulfill either challenge:
   • If Bob chooses (a): Alice simply sends Bob the permutation she used to create $H$ from $G$. Bob can easily verify that applying this permutation to $G$ indeed results in $H$.
   • If Bob chooses (b): Alice uses her knowledge of the isomorphism between $G$ and $G^{\prime }$ and the inverse of the permutation she used. She can construct and send Bob a permutation that demonstrates the isomorphism between $G^{\prime }$ and $H$.
4. Bob’s Verification: Bob verifies the permutation he receives against the chosen challenge (either (a) or (b)).

Iteration and Increasing Confidence:

Bob only receives a proof for one of the two possibilities (a) or (b) in a single round. However, if Alice truly knows the isomorphism between $G$ and $G^{\prime }$, she can successfully respond to either challenge. If Alice did not know the isomorphism, she could at best guess correctly with a 50% probability in each round. By repeating this protocol multiple times (e.g., 1000 rounds), Bob’s confidence that Alice genuinely knows the isomorphism grows exponentially. After many rounds, the probability of Alice successfully cheating becomes astronomically small. Yet, Bob learns nothing about the actual isomorphism itself – only that Alice can consistently prove isomorphism to either $G$ or $G^{\prime }$ when challenged randomly.

Example 2: Zero-Knowledge Proof for Solving $x^l\equiv m(\mathrm{mod}n)$

Suppose Alice knows a solution $x$ to the modular exponentiation equation $x^l\equiv m(\mathrm{mod}n)$. She wants to prove this to Bob, but without revealing the secret value $x$.

1. Random Value Generation by Alice: Alice chooses a random number $y$ from the multiplicative group modulo $n$, denoted as $(\mathbb{Z}/n\mathbb{Z}{)}^{\ast }$ (numbers coprime to $n$). The randomness of $y$ is key.
2. Commitment Sending: Alice computes $y^l(\mathrm{mod}n)$ and sends this value to Bob. This is her “commitment” – a value derived from her random choice.
3. Random Challenge by Bob: Bob then randomly challenges Alice to reveal one of two things:
   • (a) Reveal $y$: Bob asks Alice to reveal the random number $y$ she chose.
   • (b) Reveal $x\cdot y(\mathrm{mod}n)$: Bob asks Alice to reveal the product of her secret solution $x$ and her random number $y$, modulo $n$.
4. Alice’s Response: Alice provides the value requested by Bob.
5. Bob’s Verification: Bob verifies the response:
   • If Bob chose (a): Bob checks if Alice’s revealed $y$, when raised to the power $l$ modulo $n$, indeed matches the value $y^l(\mathrm{mod}n)$ that Alice sent in step 2.
   • If Bob chose (b): Bob checks if the revealed value, say $z=x\cdot y(\mathrm{mod}n)$, satisfies $z^l\equiv m\cdot (y^l)(\mathrm{mod}n)$. This verification uses the commitment $y^l(\mathrm{mod}n)$ and the original equation $x^l\equiv m(\mathrm{mod}n)$.

Security and Zero-Knowledge Property:

Again, by repeating this protocol multiple times with fresh random choices of $y$, Bob gains high confidence that Alice genuinely knows a solution $x$ to the equation. However, in each round, Bob only learns either $y$ or $x\cdot y(\mathrm{mod}n)$. Neither of these values alone reveals the secret solution $x$. The protocol is carefully constructed to be zero-knowledge – Bob learns nothing about $x$ itself, only that Alice can consistently prove she knows a solution when challenged randomly.

4. Distributed Computing and Swarm Computing: Breaking Symmetry

Distributed Computing: In distributed computing systems, multiple independent computers or nodes must cooperate and coordinate their actions to solve a common problem. A significant challenge in distributed algorithms is breaking symmetry. In many scenarios, nodes might have identical initial states and perceive the network symmetrically. Deterministic algorithms, in such cases, can lead to all nodes making the same decisions, which can hinder progress or lead to suboptimal outcomes.

Swarm Computing: Swarm computing draws inspiration from collective behaviors observed in natural swarms, such as bird flocks, fish schools, and insect colonies. These systems are characterized by decentralized control, local interactions, and often, the use of randomness to achieve complex collective behaviors. Swarm computing algorithms often employ randomized strategies for coordination and problem-solving in multi-agent systems.

Example: Distributed Algorithm for Finding a Large Stable Set

Consider a line graph or a grid graph. We want to design a distributed algorithm for finding a large stable set (a set of vertices with no edges between them) in such a graph. If all nodes were to follow a deterministic algorithm in a symmetric graph, nodes in equivalent positions might end up making identical decisions, potentially leading to a small or inefficiently constructed stable set.

Using Randomness to Break Symmetry in Stable Set Algorithm:

Randomness provides a powerful mechanism to break symmetry in distributed algorithms. For finding a large stable set, a randomized approach can be as follows:

1. Round-Based Deletion: The algorithm proceeds in rounds. In each round, consider every edge $\{u,v\}$ in the current graph.
2. Random Node Deletion: For each edge $\{u,v\}$, nodes $u$ and $v$ independently and randomly decide with a certain probability (e.g., 1/2) whether to “delete” themselves. “Deleting” a node means deciding not to include it in the stable set. If a node decides to delete itself, it informs its neighbors about this decision.
3. Graph Reduction: After each round, remove all nodes that decided to delete themselves and all edges incident to these deleted nodes.
4. Iteration: Repeat steps 1-3 for a predetermined number of rounds or until no more edges remain.
5. Resulting Stable Set: The nodes that survive after these rounds, i.e., those that were not deleted, will, with high probability, form a stable set. The randomness ensures that in each round, the decisions of neighboring nodes are not perfectly correlated, leading to a more diverse and ultimately larger stable set compared to deterministic approaches.

Why Deterministic Algorithms Fail in Symmetric Scenarios:

Deterministic algorithms in distributed settings, especially in symmetric graphs, often struggle to achieve good solutions because of the inherent symmetry. Without randomness, nodes in equivalent positions tend to make identical decisions, leading to a lack of diversity and potentially suboptimal global outcomes. Randomness introduces the necessary asymmetry to break these deadlock situations and allows distributed algorithms to explore a wider range of possibilities, leading to better average-case performance and the ability to find good solutions in scenarios where deterministic algorithms are limited.

Continue here: 09 Discrete Probability Space, Properties of Probability, Union of Events, Laplace Space, Composite Probability, Combinatorics