Senior Lecturer, Department of Computer Science, Technion - Israel Institute of Technology , Haifa, Israel. Students: Michael Viderman (Ph.D.), Shir Ben-Israel (M.Sc.). Postdocs: Oded Lachish (2006-7). Long term Visitors: Prahladh Harsha (2008-9).
Teaching Spring 2009 (Monday 10:30-12:30): Research laboratory in Foundations of Computer Science (236610) Fall 2008: Propositional proof complexity (236604) Spring 2008: Research laboratory in Foundations of Computer Science (236602) Fall 2007: Probabilistically Checkable Proofs (236603) Spring 2007: Noise in Computation (236601) Fall 2006: Research laboratory in Foundations of Computer Science (236602) Spring 2006: Research laboratory in Foundations of Computer Science (236602) Fall 2005: From error correcting codes to inapproximability via Probabilistically Checkable Proofs (236610). Fields of interest (within Theory of Computation) Propositional Proof Complexity Analysis of SAT solving algorithms Probabilistically Checkable Proofs and Locally Testable Codes Publications (in reverse chronological order) Affine Dispersers from Subspace Polynomials. With Swastik Kopparty . Proceedings of STOC 2009. Locally Testable Codes Require Redundant Testers. With Venkatesan Guruswami , Tali Kaufman, Madhu Sudan and Michael Viderman. Proceedings of Conference on Computational Complexity, 2009. A Space Hierarchy for k-DNF Resolution [ PDF]. With Jakob Nordstrom. Submitted to ECCC. Understanding Space in Resolution: Optimal Lower Bounds and Exponential Trade-offs [ ECCC Technical report TR09-034]. With Jakob Nordstrom. Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution [ ECCC Technical report TR09-002]. With Jakob Nordstrom. Appeared in Proceedings of FOCS 2008, pages 709-718. Tensor Products of Weakly Smooth Codes are Robust [ ECCC Technical report TR09-007]. With Michael Viderman. Appeared in Proceedings of APPROX-RANDOM 2008, pages 290-302. Sound 3-query PCPPs are Long [PDF]. With Prahladh Harsha, Oded Lachish and Arie Matsliah. ICALP 2008. Appeared as Report TR07-127, Electronic Colloquium on Computational Complexity, 2007. An Approach to Bounded Rationality [PDF]. With Adam Tauman Kalai and Ehud Kalai. NIPS 2006. Subspace Polynomials and List Decoding of Reed-Solomon Codes [ PDF, postscript]. With Swastik Kopparty and Jaikumar Radhakrishnan. FOCS 2006. Short PCPs verifiable in polylogarithmic time.[ PDF, postscript]. With Oded Goldreich, Prahladh Harsha, Madhu Sudan and Salil Vadhan. In Proc. 20th IEEE Conference on Computational Complexity, pages 120-134, San Jose, California, 12-15 June 2005. Short PCPs with Poly-log Rate and Query Complexity (journal version, updated Nov. 21, 2006) [ PDF, postscript]. With Madhu Sudan . STOC 2005. Robust Locally Testable Codes and Products of Codes . With Madhu Sudan . Random 2004. Robust PCPs of Proximity, Shorter PCPs and Applications to Coding . With Oded Goldreich, Prahladh Harsha, Madhu Sudan and Salil Vadhan. SIAM Journal on Computing, volume 36, issue 4, pages 889-974, 2006. Preliminary version appeared in STOC 2004. Linear Upper Bounds for Random Walk on Small Density Random 3-CNFs [ PDF, postscript]. With Mikhail Alekhnovich. SIAM Journal on Computing, volume 36, issue 5, page 1248-1263, 2006. Preliminary version appeared in FOCS 2003. Randomness-efficient Low Degree Tests and Short PCPs via Epsilon-Biased Sets. With Madhu Sudan , Salil Vadhan and Avi Wigderson. Appeared in STOC 2003. Bounds on 2-Query Codeword Testing. With Oded Goldreich and Madhu Sudan . Appeared in Random 2003. Some 3CNF Properties are Hard to Test. With Prahladh Harsha and Sofya Raskhodnikova. SIAM Journal on Computing, volume 35, issue 1, pages 1-21, 2005. Preliminary version appeared in STOC 2003. Finding a Randomly Planted Assignment in a Random 3-CNF. With Yonatan Bilu and Danny Gutfreund. Manuscript, 2002. Lower Bounds for Bounded Depth Frege Proofs via Buss-Pudlak Games. With Prahladh Harsha. Preprint. Size Space Tradeoffs for Resolution. [PDF, PS]. SIAM Journal on Computing (to appear), initial version appeared in STOC 2002. A Gap in Average Proof Complexity. With Yonatan Bilu. Manuscript. Hard Examples for Bounded Depth Frege. Computational Complexity 11 (2002), pp. 109-136. Preliminary version in STOC and Complexity 2002. Space Complexity of Random Formulae in Resolution. With Nicola Galesi. Random Structures and Algorithms, Volume 23, No. 1 (2003), pp. 92-109. Initial version appeared in Complexity 2001. Pseudorandom Generators in Propositional Proof Complexity. With Mikhail Alekhnovich, Alexander Razborov and Avi Wigderson. SIAM Journal on Computing, Vol 34, Number 1, 2004. Preliminary version appeared in FOCS2000. Random CNF's are hard for the Polynomial Calculus. With Russell Impagliazzo. Appeared in FOCS99. Space Complexity in Propositional Calculus. With Mikhail Alekhnovich, Alexander Razborov and Avi Wigderson. SIAM Journal on Computing, Vol. 31 No. 4, pp. 1184-1211. Preliminary version appeared in STOC2000. Near-Optimal Separation of General and Tree-Like Resolution. With Russell Impagliazzo and Avi Wigderson. Combinatorica, Vol 24, Issue 4, pp 585-604, 2004. Short Proofs are Narrow - Resolution made Simple. With Avi Wigderson. Journal of the ACM, March 2001, Vol. 48 No. 2. Preliminary version appeared in STOC99. Expansion in Proof Complexity. Ph. D. thesis, Computer Science Department, Hebrew University, Jerusalem, Israel. Advisor: Avi Wigderson. Submitted September 2001. Personal information: I am married to Ayelet and father to Hallel, Nitzan and Yair. Drop me a line
Fields of interest (within Theory of Computation) Propositional Proof Complexity Analysis of SAT solving algorithms Probabilistically Checkable Proofs and Locally Testable Codes Publications (in reverse chronological order) Affine Dispersers from Subspace Polynomials. With Swastik Kopparty . Proceedings of STOC 2009. Locally Testable Codes Require Redundant Testers. With Venkatesan Guruswami , Tali Kaufman, Madhu Sudan and Michael Viderman. Proceedings of Conference on Computational Complexity, 2009. A Space Hierarchy for k-DNF Resolution [ PDF]. With Jakob Nordstrom. Submitted to ECCC. Understanding Space in Resolution: Optimal Lower Bounds and Exponential Trade-offs [ ECCC Technical report TR09-034]. With Jakob Nordstrom. Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution [ ECCC Technical report TR09-002]. With Jakob Nordstrom. Appeared in Proceedings of FOCS 2008, pages 709-718. Tensor Products of Weakly Smooth Codes are Robust [ ECCC Technical report TR09-007]. With Michael Viderman. Appeared in Proceedings of APPROX-RANDOM 2008, pages 290-302. Sound 3-query PCPPs are Long [PDF]. With Prahladh Harsha, Oded Lachish and Arie Matsliah. ICALP 2008. Appeared as Report TR07-127, Electronic Colloquium on Computational Complexity, 2007. An Approach to Bounded Rationality [PDF]. With Adam Tauman Kalai and Ehud Kalai. NIPS 2006. Subspace Polynomials and List Decoding of Reed-Solomon Codes [ PDF, postscript]. With Swastik Kopparty and Jaikumar Radhakrishnan. FOCS 2006. Short PCPs verifiable in polylogarithmic time.[ PDF, postscript]. With Oded Goldreich, Prahladh Harsha, Madhu Sudan and Salil Vadhan. In Proc. 20th IEEE Conference on Computational Complexity, pages 120-134, San Jose, California, 12-15 June 2005. Short PCPs with Poly-log Rate and Query Complexity (journal version, updated Nov. 21, 2006) [ PDF, postscript]. With Madhu Sudan . STOC 2005. Robust Locally Testable Codes and Products of Codes . With Madhu Sudan . Random 2004. Robust PCPs of Proximity, Shorter PCPs and Applications to Coding . With Oded Goldreich, Prahladh Harsha, Madhu Sudan and Salil Vadhan. SIAM Journal on Computing, volume 36, issue 4, pages 889-974, 2006. Preliminary version appeared in STOC 2004. Linear Upper Bounds for Random Walk on Small Density Random 3-CNFs [ PDF, postscript]. With Mikhail Alekhnovich. SIAM Journal on Computing, volume 36, issue 5, page 1248-1263, 2006. Preliminary version appeared in FOCS 2003. Randomness-efficient Low Degree Tests and Short PCPs via Epsilon-Biased Sets. With Madhu Sudan , Salil Vadhan and Avi Wigderson. Appeared in STOC 2003. Bounds on 2-Query Codeword Testing. With Oded Goldreich and Madhu Sudan . Appeared in Random 2003. Some 3CNF Properties are Hard to Test. With Prahladh Harsha and Sofya Raskhodnikova. SIAM Journal on Computing, volume 35, issue 1, pages 1-21, 2005. Preliminary version appeared in STOC 2003. Finding a Randomly Planted Assignment in a Random 3-CNF. With Yonatan Bilu and Danny Gutfreund. Manuscript, 2002. Lower Bounds for Bounded Depth Frege Proofs via Buss-Pudlak Games. With Prahladh Harsha. Preprint. Size Space Tradeoffs for Resolution. [PDF, PS]. SIAM Journal on Computing (to appear), initial version appeared in STOC 2002. A Gap in Average Proof Complexity. With Yonatan Bilu. Manuscript. Hard Examples for Bounded Depth Frege. Computational Complexity 11 (2002), pp. 109-136. Preliminary version in STOC and Complexity 2002. Space Complexity of Random Formulae in Resolution. With Nicola Galesi. Random Structures and Algorithms, Volume 23, No. 1 (2003), pp. 92-109. Initial version appeared in Complexity 2001. Pseudorandom Generators in Propositional Proof Complexity. With Mikhail Alekhnovich, Alexander Razborov and Avi Wigderson. SIAM Journal on Computing, Vol 34, Number 1, 2004. Preliminary version appeared in FOCS2000. Random CNF's are hard for the Polynomial Calculus. With Russell Impagliazzo. Appeared in FOCS99. Space Complexity in Propositional Calculus. With Mikhail Alekhnovich, Alexander Razborov and Avi Wigderson. SIAM Journal on Computing, Vol. 31 No. 4, pp. 1184-1211. Preliminary version appeared in STOC2000. Near-Optimal Separation of General and Tree-Like Resolution. With Russell Impagliazzo and Avi Wigderson. Combinatorica, Vol 24, Issue 4, pp 585-604, 2004. Short Proofs are Narrow - Resolution made Simple. With Avi Wigderson. Journal of the ACM, March 2001, Vol. 48 No. 2. Preliminary version appeared in STOC99. Expansion in Proof Complexity. Ph. D. thesis, Computer Science Department, Hebrew University, Jerusalem, Israel. Advisor: Avi Wigderson. Submitted September 2001. Personal information: I am married to Ayelet and father to Hallel, Nitzan and Yair.
