home

    



I am further supported by the Rothschild Fellowship.

Here is my CV.

Phone: 609-734-8246
Office: Simonyi Hall 009
E-mail: nogazewi at ias.edu

Research interests

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

Education


Publications

High-rate locally-testable codes with quasi-polylogarithmic query complexity.
  • With Swastik Kopparty, Or Meir and Shubhangi Saraf.

High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity.
  • With Swastik Kopparty, Or Meir and Shubhangi Saraf.

On public key encryption from noisy codewords.
  • With Eli Ben-Sasson, Iddo Ben-Tov, Ivan Damgard and Yuval Ishai.

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.
  • To appear in Theory of Computing (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 9(25), 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.
  • To appear in SIAM Journal of Computing (SICOMP).
  • 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.
  • 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:
  • Winter 2012-2013 - Logic and set theory for computer science, Department of computer science, Technion
Teaching assistant:
  • 2008-2014 (9 semesters) - Logic and set theory for computer science, Department of computer science, Technion
  • 2009-2010 (2 semesters) - Probability M, Department of industrial engineering and management, Technion
  • Spring 2007 - Calculus 2, Department of mathematics, Technion