pseudorandomness publications 2010-2011
- A biological solution to a fundamental distributed computing problem
Y. Afek, N. Alon, O. Barad, N. Barkai, E. Hornstein and Z. Bar-Joseph
Science, 331(6014), 183-185, (2011) - A non-linear lower bound for planar epsilon nets
N. Alon
Proceedings of FOCS 2010, pp. 341-346. Also to appear in Discrete and Computational Geometry - Multicolored matchings in hypergraphs
N. Alon
Moscow Journal of Combinatorics and Number Theory 1 (2011), pp. 3-10 - Dense uniform hypergraphs have high list chromatic number
N. Alon and A. Kostochka
Discrete Math., to appear - Hypergraph list coloring and Euclidean Ramsey Theory
N. Alon and A. Kostochka
Random Structures and Algorithms, to appear - Weighted families of k-wise independent permutations
N. Alon and S. Lovett
submitted - Modular orientations of random and quasi-random regular graphs
N. Alon and P. Pralat
Combinatorics, Probability and Computing 20(2011), pp. 321-329 - Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions
N. Alon and S. Lovett
submitted - On a generalization of Meyniel's Conjecture on the Cops and Robbers Game
N. Alon and A. Mehrabian
Combinatorics 18 (2011), pp. 19-26 - Approximating AC^0 circuits by small height decision tree
P. Beame, R. Impagliazzo and S. Srinivasan.
preprint 2011 - Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
B. Barak, Z. Dvir, A. Wigderson and A. Yehudayoff
Proceedings of STOC 2011, to appear - Making branching programs oblivious requires super-polynomial overhead
P. Beame and W. Machmouchi
ECCC TR10-104 (2010); also to appear in Proceedings of CCC 2011 - Random CNFs are Hard for the Polynomial Calculus
E. Ben-Sasson and R. Impagliazzo
Computational Complexity 19(4): 501-519 (2010) - Correlation bounds for Mobius and Walsh
J. Bourgain
preprint 2011 - Finitely supported measures on SL_2(R) which are absolutely continuous at infinity
J. Bourgain
GAFA, to appear - Integral Apollonian circle packings and prime curvatures
J. Bourgain
preprint 2011 - Moebius Schrodinger
J. Bourgain
arXiv:1012.5217v1; to appear in GAFA - On the Furstenberg measure and density of states for Anderson-Bernoulli model at small disorder
J. Bourgain
arXiv:1101.2148v1; submitted to J. Analyse. - Prescribing the binary digits of primes
J. Bourgain
preprint 2011 - A remark on computing the Moebius function by AC(2)-circuits
J. Bourgain
preprint 2011 - Explicit Constructions of RIP Matrices and Related Problems
J. Bourgain, S. Dilworth, K. Ford, S. Konyagin and D. Kutzarova
Proceedings of STOC 2011 - On representation of integers by binary quadratic forms
J. Bourgain and E. Fuchs
arXiv:0250186, preprint 2011. - Generalizations of Selberg's 3/16 Theorem with Affine Sieve
J. Bourgain, A. Gamburd and P. Sarnak
Acta Math., to appear - Affine linear sieve, expanders and sum product
J. Bourgain, A. Gamburd and P. Sarnak
Invent. Math. 179 (2010): 559-644 - Bounds on oscillatory integral operators based on multilinear estimates
J. Bourgain and L. Guth
arXiv:1012-3760, to appear in GAFA - On Zaremba's conjecture
J. Bourgain and A. Kontorovich
CR Acad. Sc., in press - Sector estimates for hyperbolic isometries
J. Bourgain, A. Kontorovich and P. Sarnak
GAFA 20 (2010): 1175.1200. - Distribution of elements of co-sets of small subgroups and applications
J. Bourgain, S. Konyagin and I. Shparlinski
arXiv:1103.0567v1; to appear in IMRN - Expansion on SL_d (Z/q Z), q arbitrary
J. Bourgain and P. Varju
Submitted to Inventiones Math. - On the Exact Complexity of Evaluating Quantified k-CNF
C. Calabro, R. Impagliazzo and R. Paturi
IPEC 2010, pp. 50-59 - Linear systems over finite abelian groups
A. Chattopadhyay and S. Lovett
Proceedings of CCC 2011, to appear - The f-vector of the descent polytope
D. Chebikin and R. Ehrenborg
Discrete and Computational Geometry, 45(2011): 410-424. - Almost Settling the Hardness of the Noncommutative Determinant
S. Chien, P. Harsha, A. Sinclair and S. Srinivasan
Proceedings of STOC 2011, to appear - Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions
I. Diakonikolas, R. O'Donnell, R. Servedio and Y. Wu
SODA 2011 - Coboundary Expanders
D. Dotterrer and M. Kahle
submitted - Restricted access
Z. Dvir, A. Rao, A. Wigderson and A. Yehudayoff
submitted. - A spectral approach to pattern-avoiding permutations
R. Ehrenborg, S. Kitaev and P. Perry
arXiv:1009.2119; submitted 2011 - Descent pattern avoidance
R. Ehrenborg and J. Jung
preprint 2011 - The cubical matching complex
R. Ehrenborg
preprint 2011 - The cd-index of balanced and Bruhat graphs
R. Ehrenborg and M. Readdy
preprint 2011 - Warmth and mobility of random graphs
S. Fadnavis and M. Kahle
submitted - Generalizaitons of the Kolmogorov-Barzdin embedding estimates
M. Gromov and L. Guth
arXiv:1103-3423; submitted 2011 - On the Erdos distinct distance problem in the plane
L. Guth and N. Katz
arXiv:1011.4105; submitted 2011 - On symmetric indivisibility of countable structures
A. Hasson, M. Kojman and A. Onshuus
preprint 2011. - Correlation testing of the Affine Invariant properties on F^n_p in the high error regime
H. Hatami and S. Lovett
Proceedings of STOC 2011. - Higher-order Fourier analysis of F^n_p and the complexity of systems of linear forms
H. Hatami and S. Lovett
Geometric and Functional Analysis, to appear 2011 - An asymptotic bound on integer sums of squares
P. Hrubes, A. Wigderson and A. Yehudayoff
Canadian Journal of Math., to appear. - Relativized Separation of Worst-Case and Average-Case Complexity for NP
R. Impagliazzo
Computational Complexity, to appear June 2011 - Limit Theorems of Betti numbers of random simplicial complexes
M. Kahle and E. Merckes
submitted - Shelah's revised gch and a question by Alon
M. Kojman
preprint 2011 - Order-theoretic properties of bases in topological spaces
M. Kojman, D. Milovich and S. Spadaro
submitted - Spherical cubes: optimal foams from computational hardness amplification
G. Kindler, R. O'Donnell, A. Rao and A. Wigderson
submitted - On the complexity of powering in finite fields
S. Kopparty
Proceedings of STOC 2011, to appear - High-rate codes with sublinear-time decoding
S. Kopparty, S. Saraf and S. Yekhanin
Proceedings of STOC 2011, to appear - Linear programming robustly decides width-1 CSPs
G. Kun, R. O'Donnell and Y. Zhou
manuscript - Integral points on quadrics in three variables whose coordinates have few prime factors
J. Y. Liu and P. Sarnak
Israel Jour. of Math. 178 (2010): 393-426 - The Mobius function and distal flows
J. Y. Liu and P. Sarnak
in preparation - Bounded-depth circuits cannot sample good codes
S. Lovett and E. Viola
Proceedings of CCC 2011, to appear - Correlation bounds for poly-size AC^0 circuits with InI^(1-o(1)) symmetric gates
S. Lovett and S. Srinivasan
submitted - Pareto optimal solutions for smoothed analysts
A. Moitra and R. O'Donnell
Symposium on Theory of Computation, 2011 - Prime and almost prime integral points on principal homogeneous spaces
A. Nevo and P. Sarnak
Acta Math. 205 (2010): 361-402 - Analysis of Boolean Functions
R. O'Donnell
manuscript - Sharpness of KKL on Schreier graphs
R. O'Donnell and K. Wimmer
submitted - The Fourier Entropy-Influence Conjecture for certain classes of Boolean functions
R. O'Donnell, J. Wright and Y. Zhou
Proceedings of ICALP 2011, to appear - Hardness of Max-2Lin and Max-3Lin over integers, reals, and large cyclic groups
R. O'Donnell, Y. Wu and Y. Zhou
Proceedings of CCC 2011, to appear - Integral Apollonian Packing
P. Sarnak
American Mathematical Monthly, 118(4), (2011):291-306 - Affine Sieve
A. Salehi-Golsefidy and P. Sarnak
in preparation - The Mobius function, randomness and dynamics
P. Sarnak
In preparation - The horocycle flow at prime arguments
P. Sarnak and A. Ubis
in preparation