pseudorandomness publications 2009-2010
- Public Key Cryptography from Different Assumptions
B. Applebaum, B. Barak and A. Wigderson
Proceedings of STOC, 2010. - On exponentail sums in finite fields
J. Bourgain
Preprint. - On the parity of k^th-powers (mod p), a generalization of a problem of Lehmer
J. Bourgain, T. Cochrane, J. Paulhus and C. Pinner
Submitted to Acta Arithm. - Explicit constructions of RIP matrices and related problems
J. Bourgain, S. Dilworth, K. Ford, S. Konyagin and D. Kutzarova
Submitted to Duke Math. - A proof of the positive density conjecture for integer Apollonian circle packings
J. Bourgain and E. Fuchs
Submitted to JAMS. - Spectral gaps in SU(d)
J. Bourgain and A. Gamburd
C.R. Acad. Sci. Paris, Ser. 1(2010) - Affine linear sieve, expanders and sum product
J. Bourgain, A. Gamburd and P. Sarnak
Inventiones Math., 179 (1), 559-644 (2010). - Generalizations of Selberg's 3/16 Theorem with Affine Sieve
J. Bourgain, A. Gamburd and P. Sarnak
Preprint. - Exponential sum estimates over sub-groups in an arbitrary finite field
J. Bourgain and A. Glibichuk
Submitted to J. d'Analyse Math. - On representation of integers in thin subgroups of SL_d(Z/qZ), q arbitrary
J. Bourgain and A. Kontorovich
Submitted to Inventiones Math. - Sector estimates for hyperbolic isometries
J. Bourgain, A. Kontorovich and P. Sarnak
To appear in GAFA. - On the nodal sets of toral eigenfunctions
J. Bourgain and Z. Rudnick
Submitted to Inventiones Math. - Expansion on SL_d (Z/q Z), q arbitrary
J. Bourgain and P. Varju
Submitted to Inventiones Math. - Efficient communication using partial information
M. Braverman and A. Rao
Manuscript, 2009 - Pseudorandom generators for regular branching programs
M. Braverman, A. Rao, R. Raz and A. Yehudayoff
Submitted, 2010. - Improved pseudorandom generators for depth 2 circuits
A. De, O. Etesami, L. Trevisan and M. Tulsiani
Manuscript, 2009. - Time-space tradeoffs for attacks against one-way functions and PRGs
A. De, L. Trevisan and M. Tulsiani
Manuscript, 2009. - Monotone expanders - constructions and applications
Z. Dvir and A. Wigderson
ECCC Report, TR09-135, (2009). - Relativized separation of average-case and worst-case complexities
R. Impagliazzo
Manuscript, 2010. - Uniform direct-product theorems: Simplified, optimized and derandomized
R. Impagliazzo, R. Jaiswal, V. Kabanets and A. Wigderson
SIAM Journal on Computing, 39 (4), 1637-1665, (2010). - Constructive proofs of concentration bounds
R. Impagliazzo and V. Kabanets
ECCC Report, TR10-072 (2010). - New direct-product tests and 2-query PCPs
R. Impagliazzo, V. Kabanets and A. Wigderson
Proceedings of STOC, 2009. - Communication complexity with synchronized clocks
R. Impagliazzo and R. Williams
Manuscript, 2010. - Strong spectral gaps for compact quotients of PSL(2,R)
D. Kelmer and P. Sarnak
J. Eur. Math. Soc., 11(2), 283-313, (2009). - Symmetric ldpc codes and local testing
T. Kaufman and A. Wigderson
ICS, 2010. - Reductions between expansion problems
P. Raghavendra, D. Steurer and M. Tulsiani
Manuscript, 2010. - Integral Apollonian Packing
P. Sarnak
Accepted, American Mathematical Monthly, 2010. - The Mobius function, dynamics and randomness
P. Sarnak
In preparation. - The horocycle flow at prime values
P. Sarnak and A. Ubis
Preprint, 2010.