Home


I am further supported by the Rothschild Fellowship.

Here is my CV.

Contact information

IAS:                                              DIMACS:
                                                                        
Office: Fuld Hall 211                    Office: CoRE 411
Phone: 609-734-8099                Phone: 732-445-6755
E-mail: nogazewi at ias.edu         E-mail: noga.zewi at rutgers.edu

Research interests

Theory of computation, mainly computational aspects of communication and coding. Specific areas in which I have been interested lately are error-correcting codes, locally decodable and testable codes, communication complexity, coding for multiparty communication, and applications of additive combinatorics methods and other modern research directions in discrete mathematics in these ares.

Education


Publications

Locally testable and locally correctable codes approaching the Gilbert-Varshamov bound
  • With Sivakanth Gopi, Swastik Kopparty, Rafael Oliveira and Shubhangi Saraf
  • Submitted.

High-rate locally-testable codes with quasi-polylogarithmic query complexity
  • With Swastik Kopparty, Or Meir and Shubhangi Saraf
  • In proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC 2016), merged with paper below.

High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity
  • With Swastik Kopparty, Or Meir and Shubhangi Saraf.
  • In proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC 2016), merged with paper above.

Towards optimal deterministic coding for interactive communication
  • With Ran Gelles, Bernhard Haeuplr, Gillat Kol and Avi Wigderson. 
  • In proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)
    [Full version]

On public key encryption from noisy codewords
  • With Eli Ben-Sasson, Iddo Ben-Tov, Ivan Damgard and Yuval Ishai.
  • In Proceedings of the 19th International Conference on the Theory and Practice of Public-key Cryptography (PKC 2016)

Sampling-based proofs of almost-periodicity results and algorithmic applications
  • With Eli Ben-Sasson, Madhur Tulsiani and Julia Wolf.
  • In proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014).
    [Full version]

Absolutely sound testing of lifted codes
  • With Elad Haramaty and Madhu Sudan.
  • In Theory of Computing, volume 11(12), pages 299-338, 2015 (Special issue of Random 2013)
  • Preliminary version in proceedings of the 7th International Workshop on Randomization and Computation (Random 2013).
    [Full version]

An additive combinatorics approach relating rank to communication complexity
  • With Eli Ben-Sasson and Shachar Lovett.
  • In journal of the ACM (JACM), volume 61, issue 4, 2014.
  • Preliminary version in proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012).

Sparse affine-invariant linear codes are locally testable
  • With Eli Ben-Sasson and Madhu Sudan.
  • To appear in Computational Complexity.
  • Preliminary version in proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012).
    [Full version]

A new upper bound on the query complexity of testing the generalized Reed-Muller codes
  • With  Madhu Sudan.
  • In Theory of Computing, volume 25(9), pages 781-807, 2013 (Special issue of Random 2012).
  • Preliminary version in proceedings of the 6th International Workshop on Randomization and Computation (Random 2012).
    [Full version]

Space complexity in polynomial calculus
  • With Yuval Filmus, Massimo Lauria, Jakob Nordstrom and Neil Thapen.
  • In SIAM Journal of Computing (SICOMP), volume 44(4), pages 889-1172, 2015
  • Preliminary version in proceedings of the 27th IEEE Conference on Computational Complexity (CCC 2012).
    [Full version]

From affine to two-source extractors via approximate duality
  • With Eli Ben-Sasson.
  • In SIAM Journal of Computing (SICOMP), volume 44(6), pages 1670-1695, 2015
  • Preliminary version in proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC 2011).
    [Full version]

Vector representation of graph domination
  • In Journal of Graph Theory, volume 70, issue 2, pages 152-170, 2012.
    [Full version]

Theses

Additive combinatorics methods in computational complexity
  • Ph.D. Thesis, Technion, 2014.

Vector representation fo graph domination
  • M.Sc. Thesis, Technion, 2010.

Teaching

Lecturer:
  • Logic and Set Theory for Computer Science, Technion (2012-2013)
Teaching assistant:
  • Logic and Set Theory for Computer Science, Technion (2008-2014)
  • Probability Theory for Computer Science, Technion (2009-2010, head teaching assistant)
  • Differential and Integral Calculus 2, Technion (2007)

Subpages (2): Publications Teaching