2009
12. Explicit lower bound for fooling polynomials by the sum of small-bias generators Shachar Lovett and Yoav Tzur Technical report TR09-088 at the Electronic Colloquium on Computational Complexity (ECCC) Report 11. Pseudorandom Bit Generators that Fool Modular Sums Shachar Lovett, Omer Reingold, Luca Trevisan and Salil Vadhan The 13th Intl. Workshop on Randomization and Computation (RANDOM 2009) Extended abstract 10. The Density of Weights of Generalized Reed-Muller codes Shachar Lovett Submitted Extended abstract 9. On the Complexity of Boolean Functions in Different Characteristics
Parikshit Gopalan, Shachar Lovett and Amir Shpilka The IEEE Conference on Computational Complexity (CCC 2009) 8. On Cryptography with Auxiliary Input Yevgeniy Dodis, Yael Tauman Kalai and Shachar Lovett The 41st ACM Symposium on Theory of Computing (STOC 2009) Extended abstract 7. Weight Distribution and List-Decoding Size of Reed-Muller codes Tali Kaufman and Shachar Lovett Submitted Extended abstract Talk 6. Random Low Degree Polynomials are Hard to Approximate
Ido Ben-Eliezer, Rani Hod and Shachar Lovett 2008
5. Worst Case to Average Case Reductions for Polynomials
Tali Kaufman and Shachar Lovett The 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008) Extended abstract Short talk Long talk 4. Inverse Conjecture for the Gowers Norm is False
Shachar Lovett, Roy Meshulam and Alex Samorodnitsky The 40th ACM Symposium on Theory of Computing (STOC 2008) 3. Unconditional Pseudorandom Generators for Low Degree Polynomials
Shachar Lovett The Theory of Computing journal (TOC), Vol. 5, article 3 Preliminary version appeared in the 40th ACM Symposium on Theory of Computing (STOC 2008)
Full version Talk 2. Lower bounds for Adaptive Linearity tests
Shachar Lovett The 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008) Extended abstract Talk 1. Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits Shachar Lovett and Sasha Sodin Communications in Contemporay Mathematics (CCM), Vol. 10, No. 4, 2008 Full version |