home

    
 

I am a member of the school of mathematics at the Institute for Advanced Study at Princeton as part of the theoretical computer science and discrete mathematics group led by Prof. Avi Wigderson I am supported by the IAS-DIMACS fellowship and the Rothschild Fellowship.

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

Education
Research interests

My research interests lie in theoretical computer science and its interactions with modern research directions in discrete mathematics. My Ph.d. research focused on applying methods and techniques from the mathematical field of additive combinatorics in computational complexity, most notably in the areas of communication and coding.  My M.Sc. research focused on applying methods from algebraic topology to matching theory in graphs. 

Publications

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

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).
  • 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 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.