Ph.D Student | Ron-Zewi Noga |
---|---|

Subject | Additivie Combinatorics Methods in Computational Complexity |

Department | Department of Computer Science |

Supervisor | Professor Eliyahu Ben Sasson |

Full Thesis text |

In particular, we show applications in the following sub-fields:

•
**Pseudorandomness**: We use the *approximate duality
conjecture *from additive
combinatorics for the design of *randomness extraction *procedures that
distill (almost) perfect randomness, required for the performance of randomized
algorithms and protocols, from weak sources of randomness that exist in nature.
More specifically, we show how *affine extractors*, which distill
randomness from sources with ‘algebraic structure’, can be converted in a
black-box manner to *two-source extractors*, which distill randomness from
a pair of independent weak sources of randomness.

•
**Communication
complexity**: We
use the approximate duality conjecture mentioned above for the design of
communication protocols that minimize the amount of communication needed for
performing computational tasks, jointly, by multiple parties. In particular, we
make progress on the well-known *log-rank conjecture* in communication
complexity by proposing the first non-trivial communication protocols in which
the amount of communication is *sub-linear* in the *rank *of the
task, where the latter is a measure of how complex the task is.

•
**Public
key cryptography**:
We use the approximate duality conjecture to show sub-exponential attacks on instances
of known public key encryption schemes based on noisy codewords.

•
**Local
decoding**: We
show applications of additive combinatorics methods to the design of local
decoding procedures that allow an extremely efficient detection and correction
of errors in transmission by examining only a few bits of the corrupted
codeword. Our first result in this direction uses *almost-periodicity*
results from additive combinatorics to obtain an improved local decoding
procedure for the well-known class of *Reed-Muller codes* in the scenario
of an highly erroneous transmission channel. Our procedure improves on previous
such procedures in that its running time and performance guarantee depend only
quasipolynomially on the error parameter instead of exponentially. Our second
result uses the *Waring's problem over finite fields* from additive
combinatorics for the design of local decoding procedures for the class of *sparse
affine-invairant linear codes*.