|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|
This thesis focuses on applications of methods and techniques from the mathematical field of additive combinatorics, the branch of discrete mathematics aimed at quantifying the amount of additive structure in subsets of additive groups, in computational complexity, the sub-area of theoretical computer science that studies the inherent limitations on efficient computation.
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.