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.