Some Talks

All files are power-point presentations


From dense to sparse and back again: On testing graph properties (and some properties of Oded)
      (Given at Oded's birthday celebration, 2017)


On local partition oracles and their applications
      (Given at WOLA 2016)


You don't have to be perfect: On random choice in approximate computation
      (In Hebrew, given at an event of "No'ar Shocher Mada", 2016)


Approximately counting triangles in sublinear time
      (Given at the Sublinear algorithms workshop in Baltimore, 2016)


On centralized sublinear algorithms and some relations to distributed computing
      (Given at ADGA, 2015)


Fast, cheap but in control: Sublinear algorithms for approximate computations
      (Given at BGU, 2015)


On sample-based testers
      (Given at ITCS, 2015)


On learning and testing dynamic environments
      (Given at FOCS, 2014)

(Another version given at FILOFOCS, 2015)


Exponentially improved algorithms and lower bound of testing signed majorities
      (Given by Rocco Servedio, SODA, 2013)

(Another version given by me)


Finding cycles and tress in sublinear time
      (Given by Oded Goldreich, 2013)


A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
      (Given at Columbia University, 2012)


A Short Introduction to Sublinear-Time Algorithms
      (Given at the Women in Theory workshop, Princteon, 2012)


A survey on sublinear algorithms for approximating graph parameters
      (this version was given at the NY Area Theory Day, 2011)


Approximating the number of relevant variables in a function
      (Joint work with Gilad Tsur, given at RANDOM, 2011)


Distribution-Free Testing of Monomials with a Sublinear Number of Queries
      (Joint work with Elya Dolev, given at RANDOM, 2010)

Longer version (given at the Weizmann institute, 2010)


Algorithmic Aspects of Property Testing in the Dense Graphs Model
      (Joint work with Oded Goldreich, given at RANDOM, 2009)


On Proximity Oblivious Testing
      (Joint work with Oded Goldreich, given at STOC, 2009)


Some Techniques in Property Testing
      (Given a the TAU CS colloqium, December 2008)


On the Benefits of Adaptivity in Property Testing of Dense Graphs 
      (Joint works with Mira Gonen and Oded Goldreich, given at Dagsthul, 2008)


On the Benefits of Adaptivity in Property Testing of Dense Graphs 
      (Joint work with Mira Gonen, given at RANDOM, 2007)


Property Testing: A Learning Theory Perspective 
      (Given at COLT 2007)


Distance Approximation in Bounded-Degree and General Sparse Graphs
     (Joint work with Sharon Marko, given at RANDOM, 2006)


Approximating Average Parameters of Graphs 
     (Joint work with Oded Goldreich, given at RANDOM 2006)


Tight Bounds for Testing Bipartiteness in General Graphs 
     (Joint work with Tali  Kaufman and  Michael  Krivelevich)


On Testing Convexity and Submodularity 
     (Joint work with Michal Parnas and Ronitt Rubinfeld)


Testing Basic Boolean Formulae 
     (Joint work with Michal Parnas and Alex Samorodnitsky)


Testing Metric Properties
     (Joint work with Michal Parnas)


A Tutorial on Property Testing 


Testing of Clustering
     (Joint work with Noga Alon, Seannie Dar, and Michal Parnas)


Testing Acyclicity of Directed Graphs in Sublinear Time
     (Joint work with: Michael Bender)


Testing the Diameter of Graphs
     (Joint work with Michal Parnas)