Basic Definitions and Motivation For Property Testing Algorithms. Testing Graph Properties in The Dense and The Sparse Model. Testing For Monotonicity. Testing Of Boolean Functions. The Sampling Model For Distribution Testing. Testing By Learning. Methods For Lower Bounds. Learning Outcomes# By The End of The Course The Students Will Acquire Basic Proficiency In The Topic of Property Testing and The Problems Investigated There, Including Common Proof Methods. Additionally, The Student Will Acquire Knowledge That Is Useful to Investigate Randomized Approximation Algorithms in General.

Faculty: Computer Science
|Undergraduate Studies |Graduate Studies

Pre-required courses

(94412 - Probability (advanced) and 234247 - Algorithms 1) or (104222 - Probability Theory and 104291 - Combinatorial Algorithms)

Course with no extra credit

236620 - Advanced Topics in Algorithms L

Semestrial Information