TY - GEN

T1 - Towards deterministic tree code constructions

AU - Braverman, Mark

PY - 2012/2/6

Y1 - 2012/2/6

N2 - We present a deterministic operator on tree codes - we call tree code product - that allows one to deterministically combine two tree codes into a larger tree code. Moreover, if the original tree codes are efficiently encodable and decodable, then so is their product. This allows us to give the first deterministic subexponential-time construction of explicit tree codes: we are able to construct a tree code T of size n in time 2 nε. Moreover, T is also encodable and decodable in time 2 nε. We then apply our new construction to obtain a deterministic constant-rate error-correcting scheme for interactive computation over a noisy channel with random errors. If the length of the interactive computation is n, the amount of computation required is deterministically bounded by n 1+o(1), and the probability of failure is n -ω(1).

AB - We present a deterministic operator on tree codes - we call tree code product - that allows one to deterministically combine two tree codes into a larger tree code. Moreover, if the original tree codes are efficiently encodable and decodable, then so is their product. This allows us to give the first deterministic subexponential-time construction of explicit tree codes: we are able to construct a tree code T of size n in time 2 nε. Moreover, T is also encodable and decodable in time 2 nε. We then apply our new construction to obtain a deterministic constant-rate error-correcting scheme for interactive computation over a noisy channel with random errors. If the length of the interactive computation is n, the amount of computation required is deterministically bounded by n 1+o(1), and the probability of failure is n -ω(1).

UR - http://www.scopus.com/inward/record.url?scp=84856427371&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84856427371&partnerID=8YFLogxK

U2 - 10.1145/2090236.2090250

DO - 10.1145/2090236.2090250

M3 - Conference contribution

AN - SCOPUS:84856427371

SN - 9781450311151

T3 - ITCS 2012 - Innovations in Theoretical Computer Science Conference

SP - 161

EP - 167

BT - ITCS 2012 - Innovations in Theoretical Computer Science Conference

T2 - 3rd Conference on Innovations in Theoretical Computer Science, ITCS 2012

Y2 - 8 January 2012 through 10 January 2012

ER -