אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב
יום רביעי, 26.10.2016, 12:30
Guruswami and Smith (Journal of the ACM, to appear) present a construction for an explicit codes for additive channels (channels that can induce a fixed error) that succeeds with high probability.
Furthermore Guruswami and Smith gave an explicit construction against channels of size n^c if we provide the encoding and decoding with public shared randomness (Monte-Carlo construction).
In this paper we solve several open problems posed by Guruswami and Smith:
1. We show a fully explicit construction for bonded channels under standard hardness assumptions.
2. We present a fully explicit unconditional construction for logarithmic space online channels.
3. We consider a tighter notion of explicitness in which the run time of the encoding and decoding is a fixed polynomial (does not depend on the complexity of the channel), and give a fully explicit construction for superpolynomial size circuits of constant depth.
This is a joint work with Ronen Shaltiel.