### 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 ^{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)}.

Original language | English (US) |
---|---|

Title of host publication | ITCS 2012 - Innovations in Theoretical Computer Science Conference |

Pages | 161-167 |

Number of pages | 7 |

DOIs | |

State | Published - Feb 6 2012 |

Event | 3rd Conference on Innovations in Theoretical Computer Science, ITCS 2012 - Cambridge, MA, United States Duration: Jan 8 2012 → Jan 10 2012 |

### Publication series

Name | ITCS 2012 - Innovations in Theoretical Computer Science Conference |
---|

### Other

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

Country | United States |

City | Cambridge, MA |

Period | 1/8/12 → 1/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

*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