Yesterday, I went to an interesting talk by Klim Efremenko about testing equality in networks. The talk was based on his joint paper with Noga Alon and Benny Sudakov. The basic problem is as follows. Suppose there is a network with \(k\) nodes, and each node \(v\) has an input in the form of an \(n\)-bit string \(M_v \in \{0, 1\}^n\). All of the nodes in the network want to verify that all of their strings are equal, i.e., that \(M_v = M_u\) for all…

Recently, the brilliant mathematician John Nash and his wife were killed in a car crash. While Nash was probably most famous for his pioneering work on game theory and his portrayal in Ron Howard‘s popular film A Beautiful Mind, he also worked in the field of cryptography. Several years ago, the NSA declassified several letters from 1955 between Nash and the NSA wherein Nash describes some ideas for an encryption/decryption scheme. While the NSA was not interested in the particular scheme devised by Nash, it seems that Nash…

Suppose two players, Alice and Bob, each hold equal sized subsets of \([n] = {1, 2, \ldots, n}\). A third party, Carole, wishes to convince Alice and Bob that their subsets are disjoint, i.e., their sets have no elements in common. How efficiently can Carole prove to Alice and Bob that their sets are disjoint? To formalize the situation, suppose \(k\) is an integer with \(1 \leq k \leq n\), and let \(A\) and \(B\) be, respectively, Alice and Bob's subsets of \([n]\), both of size \(k\). Carole produces a…

In his essay The Work of Art in the Age of Mechanical Reproduction, Walter Benjamin introduces the idea that original artwork has an aura — some ineffable something that the work’s creator imbues into the work, but which is lost in reproductions made by mechanical means. There is something unique about an original work. Let us imagine that Walter is able to read the aura of work of art, or sense its absence. Thus, he has the seemingly magical ability to tell original art from mechanical forgery. Andy Warhol is…

PSIZE is the set of languages recognized by boolean circuits of size polynomial in the input size. Here we give a very simple proof that PSIZE is uncountable. This is in contrast to the countable set of languages recognized by Turing machines. Indeed, there are only countably many Turing machines, each of which recognizes only one language. The reason that we expect PSIZE to recognize more languages than Turing machines is the non-uniformity in the definition of PSIZE: we can define a different circuit for inputs of each size. On…