home

    
 
I am a Ph.D. student at the Department of Computer Science, Technion. 


My research interests lie in theoretical computer science and its interactions with modern research directions in discrete mathematics. A unifying theme in my work so far has been the use of methods and techniques from the mathematical field of additive combinatorics for making progress on open problems in the area of computational complexity, most notably in the sub-fields of pseudorandomness, communication complexity and local decoding. 

I did my M.Sc. at the department of computer science at the Technion under the supervision of Prof. Ron Aharoni and Prof. Seffi Naor. My M.Sc. research focused on applying methods from algebraic topology to matching theory in graphs. My thesis, titled "Vector representation of graph domination" can be found here

Phone: 04-8294932
Office: Taub 510
E-mail: nogaz at cs.technion.ac.il

Publications

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

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

An additive combinatorics approach relating rank to communication complexity.
  • With Eli Ben-Sasson and Shachar Lovett.
  • 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.
  • In proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012).

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).
    [Proceedings version],  [Full version, 19/06/2013]

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

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).
    [Proceedings version], [Full version, 2/09/12]

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

Technion Theory Lunch

In years 2010-2013 I organized the Theory Lunch at my department. 

Teaching

Lecturer:
  • Winter 2012-2013 - Logic and set theory for computer science, Department of computer science, Technion.

Teaching assistant:
  • 2008-2013 (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.
Music
I play the flute (and also the piccolo) at the Technion Symphony Orchestra. I also play chamber music at Yanshf, ACMP, and The Israel Chamber Music Club.