pseudorandomness publications 2008-2009
- Public Key Cryptography from Different Assumptions
B. Applebaum, B. Barak and A. Wigderson.
Submitted, 2009. - Towards a study of low-complexity graphs.
A. Arora, D. Steurer and A. Wigderson.
Proceedings of ICALP 2009. - Entropy of random walk range.
I. Benjamini, G. Kozma, A. Yadin and A. Yehudayoff.
Submitted. - Expanders and dimensional expansion.
J. Bourgain.
CRASc Paris 347 (2009), pp 357--362 - Random walks and expansion in SLd(Z/pnZ.
J. Bourgain and A. Gamburd.
CRASc Paris 346, no. 11-12 (2008), pp. 619-623. - Primes in thick subgroups of SL2(Z).
J. Bourgain and A. Kontorovich.
In preparation. - The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs.
C. Calabro, R. Impagliazzo, V. Kabanets and R. Patri.
J. Comput. Syst. Sci. 74(3): 386-393 (2008). - Linear systems over composite moduli.
A. Chattopadhyay and A. Wigderson.
Proceedings of FOCS 2009. - Security Amplification for Interactive Cryptographic Primitives.
Y. Dodis, R. Impagliazzo, R. Jaiswal and V. Kabanets.
TCC 2009: 128-145. - Extensions to the method of multiplicities, with applications to kakeya sets and mergers.
Z. Dvir, S. Kopparty, S. Saraf and M. Sudan.
Manuscript, 2009. - On the size of Kakeya sets in finite fields.
Z. Dvir.
J. AMS, 2008. To appear - Extractors for varieties.
Z. Dvir
In CCC 09, 2009. To appear. - Kakeya sets, new mergers and old extractors.
Z. Dvir and A. Wigderson.
Proceedings of the 2008 49th Annual FOCS 08, pp. 625-633. - Recent progress on the Kakeya problem.
Z. Dvir
Report, June 2009. - Arithmetic complexity in algebraic extensions.
P. Hrubes and A. Yehudayoff.
Submitted - Homogeneous Multilinear formulas and symmetric polynomials.
P. Hrubes and A. Yehudayoff.
Submitted - Monotone separations for constant degree.
P. Hrubes and A. Yehudayoff.
Submitted - Chernoff-Type Direct Product Theorems.
R. Impagliazzo, R. Jaiswal and V. Kabanets.
J. Cryptology 22(1): 75-92 (2009). - An axiomatic approach to algebrization.
R. Impagliazzo, V. Kabanets and A. Kolokolova.
STOC 2009: 695-704. - New direct-product testers and 2-query PCPs.
R. Impagliazzo, V. Kabanets and A. Wigderson.
STOC 2009: 131-140. - Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized.
R. Impagliazzo, R. Jaiswal, V. Kabanets, A. Wigderson.
Proceedings of STOC 2008, pp. 579-588. - The variance of arithmetic measures associated with closed geodesics on modular surfaces.
W. Luo, Z. Rudnick and P. Sarnak.
J. of Modern Dynamics, vol. 3, no. 2 (2009): 113-151. - Prime and Almost Prime Integral Points on Principal Homogeneous Spaces.
A. Nevo and P. Sarnak.
To appear in Acta Mathematica. - Parallel Repetition in Projection Games and a Concentration Bound.
A. Rao.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008. - Equidistribution and Primes.
P. Sarnak.
Asterisque 163 (2008), Societe Math de France. - Integral Apollonian Packings.
P. Sarnak.
In preparation. - The Mobius function, randomness and dynamics.
P. Sarnak.
In preparation. - Unipotent orbits and primes.
P. Sarnak and A. Ubis.
In preparation.