The universal relation is the communication problem in which Alice and Bob get as inputs two distinct strings, and they are required to find a coordinate on which the strings differ. The study of this problem is motivated by its connection to Karchmer-Wigderson relations, which are communication problems that are ... more >>>

We deterministically construct quasi-polynomial weights in quasi-polynomial time, such that in a given polytope with totally unimodular constraints, one vertex is isolated, i.e., there is a unique minimum weight vertex.
More precisely,
the property that we need is that every face of the polytope lies in an affine space defined ... more >>>

We survey the state of the art in constructions of locally testable
codes, locally decodable codes and locally correctable codes of high rate.

more >>>