Fields of interest (within Theory of Computation)

• Propositional Proof Complexity
  
• Analysis of SAT solving algorithms
  
• Probabilistically Checkable Proofs and Locally Testable Codes
  
• Derandomization

• Limits on the rate of locally testable affine-invariant codes. With Madhu Sudan .
• 
  
• Constructing Two-Source Extractors From Affine Ones. With Noga Zewi.
• 
  
• Low Rate Is Insufficient for Local Testability [ECCC report TR10-004]. With Michael Viderman.
• 
  
• Lower bounds for width-restricted clause learning on small width formulas. With Jan Johannsen .
• 
  
• Symmetry Breaking can Dramatically Reduce the Length of Propositional Refutations. With Shir Ben-Israel and David Karger.
• 
  
• Affine Dispersers from Subspace Polynomials. With Swastik Kopparty . Proceedings of STOC 2009, pages 65-74.
• 
  
• Locally Testable Codes Require Redundant Testers. With Venkatesan Guruswami , Tali Kaufman, Madhu Sudan and Michael Viderman. Proceedings of Conference on Computational Complexity, 2009, pages 52-61.
• 
  
• A Space Hierarchy for k-DNF Resolution [ ECCC Technical report TR09-047]. With Jakob Nordstrom.
• 
  
• 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 FregeProofs via Buss-Pudlak Games.With Prahladh Harsha. Preprint.
  
  
• Size Space Tradeoffs forResolution. [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 versionappeared in Complexity 2001.
  
  
• Pseudorandom Generators inPropositional 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 hardfor the Polynomial Calculus. With Russell Impagliazzo. Appeared in FOCS99.
  
  
• Space Complexity inPropositional 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 Separationof General and Tree-Like Resolution. With Russell Impagliazzo andAvi 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.
  
  

Drop me a line