Avi60

The festivities in honor of Avi Wigderson’s 60th birthday start tomorrow in Princeton, with a dream team of speakers. I will not be able to attend, but luckily a livestream will be available.

During the week, I will post a random selection of results of Avi’s.

Did you know that Avi’s first paper was an algorithm to color 3-colorable graphs using colors? Here is the algorithm, which has the flavor of Ramsey theory proofs.

Suppose all nodes have degree , then we can easily color the graph with colors. Otherwise, there is a node of degree . The neighbors of induce a bipartite graph (because, in the 3-coloring that we are promised to exist, they are colored with whichever are the two colors that are different from the color of ), and so we can find in linear time an independent set of size . So we keep finding independent sets (which we assign a color to, and remove) of size until we get to a point where we know how to color the residual graph with colors, meaning that we can color the whole graph with colors.

CS276 Lecture 27: Computational Zero Knowledge

Scribed by Madhur Tulsiani

Summary

In this lecture we begin the construction and analysis of a zero-knowledge protocol for the 3-coloring problem. Via reductions, this extends to a protocol for any problem in NP. We will only be able to establish a weak form of zero knowledge, called “computational zero knowledge” in which the output of the simulator and the interaction in the protocol are computationally indistinguishable (instead of identical). It is considered unlikely that NP-complete problem can have zero-knowledge protocols of the strong type we defined in the previous lectures.

As a first step, we will introduce the notion of a commitment scheme and provide a construction based on any one-way permutation.