Previous Conferences & Workshops

Valiant's theory of holographic algorithms is a new design method to produce polynomial time algorithms. Information is represented in a superposition of linear vectors in a holographic mix. This mixture creates the possibility for exponential sized...

Let Q(n,p) denote the adjacency matrix of the Erdos-Renyi graph G(n,p), that is to say a symmetric matrix whose entries above the main diagonal are independently set to 1 with probability p and 0 with probability 1-p. We will examine the behavior of...

A k-query Locally Decodable Code (LDC) encodes an n-bit message x as an N-bit codeword C(x), such that one can probabilistically recover any bit x_i of the message by querying only k bits of the codeword C(x), even after some constant fraction of...