Towards deterministic tree code constructions

Research output: Chapter in Book/Report/Conference proceedingConference contribution

38 Scopus citations

Abstract

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 . Moreover, T is also encodable and decodable in time 2 . 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).

Original languageEnglish (US)
Title of host publicationITCS 2012 - Innovations in Theoretical Computer Science Conference
Pages161-167
Number of pages7
DOIs
StatePublished - Feb 6 2012
Event3rd Conference on Innovations in Theoretical Computer Science, ITCS 2012 - Cambridge, MA, United States
Duration: Jan 8 2012Jan 10 2012

Publication series

NameITCS 2012 - Innovations in Theoretical Computer Science Conference

Other

Other3rd Conference on Innovations in Theoretical Computer Science, ITCS 2012
CountryUnited States
CityCambridge, MA
Period1/8/121/10/12

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Towards deterministic tree code constructions'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M. (2012). Towards deterministic tree code constructions. In ITCS 2012 - Innovations in Theoretical Computer Science Conference (pp. 161-167). (ITCS 2012 - Innovations in Theoretical Computer Science Conference). https://doi.org/10.1145/2090236.2090250