home

    
 


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


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.  My M.Sc. research focused on applying methods from algebraic topology to matching theory in graphs. 


Theses

Additive combinatorics methods in computational complexity.

Ph.D. Thesis, Technion, 2014.


Vector representation fo graph domination.

M.Sc. Thesis, Technion, 2010.


Publications

On the limitations of 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.
  • To appear in Journal of the ACM.
  • 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.
  • 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]

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.